Simple Modular Exponentiation in C++ without overflow?

Question

I have to create a simple modular exponentiation function that takes input three integers, a, b and c, and performs the task: a^b %c without overflow.

Possible duplicate of [Modular Exponentiation for high numbers in C++](http://stackoverflow.com/questions/2207006/modular-exponentiation-for-high-numbers-in-c) — costrom, Jul 14 '16 at 22:29

AlexD · Accepted Answer · 2016-07-14T23:08:38.097

1

It is Modular exponentiation. Assuming unsigned a, b, c and that a * (c - 1) does not overflow:

unsigned int r = 1;
for (unsigned int k = 0; k < b; k++)
    r = r * a % c;

(Note that there is no power operator in C, ^ is for XOR (exclosive OR.)

edited Jul 14 '16 at 23:08

answered Jul 14 '16 at 22:32

AlexD

32,156
3
71
65

That's not really safe though, `r * a` could easily overflow. Also slow. – harold Jul 14 '16 at 22:45
So the answer to a^b %c is r after k=b? – Bartholomew Jul 14 '16 at 22:46
@harold Yes, I assumed a bit simplified case with reasonable `a`. Updated. I think the idea of the exercise was to avoid overflow related to exponentiation, not to focus on corner cases. But still, your remark is correct. – AlexD Jul 14 '16 at 22:50
@Bartholomew Yes, `r` is supposed to be the result. – AlexD Jul 14 '16 at 22:51
@AlexD Thank you very much. – Bartholomew Jul 14 '16 at 22:55

score 1 · Answer 2 · answered Jul 14 '16 at 22:47

Use Euler theorem for this, it can reduce the exponent down significantly.

You'll need a helper function for finding the phi function (or there might be a library with that in it). Then, all you have to do is

(a ^ b) % c => (a ^ (b % phi(c)) % c

That will definitely help reduce the chance of overflow. Further, mod has this property:

a*b % c = (a % c)*b % c

This means if your exponent will cause an overflow, you can half you exponent, and perform the mod on a smaller value. Look into some number theory books for more tricks to make this easier!

Thank you very much for your response. – Bartholomew Jul 14 '16 at 22:58 — Bartholomew, Jul 14 '16 at 22:58

Simple Modular Exponentiation in C++ without overflow?

2 Answers2