1

I have a % m. I want to find ax % m.

This is what I have observed.

Let a = 6 and m = 4

a % m = 2

We can find a2 % m as (6 + 6 + 6 + 6 + 6 + 6) % m which is equal to 

((6 % 4) + (6 % 4) + (6 % 4) + (6 % 4) + (6 % 4) + (6 % )) % 4 which is 0

This can be seen as 62 % 4 = (6 * (6 % 4) % 4

For 3 the above can be written as (6 * ((6 * (6 % 4)) % 4)) % 4

This can be done like that recursively.

Is there an efficient method than this ?

Bharat
  • 1,044
  • 15
  • 34
  • 1
    Are you looking for https://en.wikipedia.org/wiki/Modular_exponentiation? There are examples of pseudocode in the article. – Alex Riley Jan 19 '18 at 09:59
  • Ohh does it have a name !! – Bharat Jan 19 '18 at 10:00
  • @AlexRiley those pseudocodes are same as what I have asked in the question. I'm looking for an efficient method. – Bharat Jan 19 '18 at 10:02
  • [How to compute a^^b mod m?](https://stackoverflow.com/q/30713648/995714), [Calculating (a^b)%MOD](https://stackoverflow.com/q/11272437/995714) – phuclv Jan 19 '18 at 10:05
  • @bharath: those are the efficient methods. – Alex Riley Jan 19 '18 at 10:06
  • @LưuVĩnhPhúc those questions were about calculating (a ^ x ) % m but you can see that my question is calculating (a ^ x) % m from (a % m) – Bharat Jan 19 '18 at 10:06
  • 2
    @bharath that's the same thing. – harold Jan 19 '18 at 10:18
  • 1
    function name is `modpow` and algorithm name is [power by squaring](https://stackoverflow.com/a/30962495/2521214) with slight change and that is it uses modulus arithmetics like [this](https://stackoverflow.com/q/18577076/2521214) instead of standard one – Spektre Jan 19 '18 at 12:20

0 Answers0