   # How to compute modulo power of big integers?

+5 votes
135 views

How to compute modulo power of 10,000 digit number to 10,000 digit number using C language
Eg:-(1234567891111123433434^211222324334343422233)%**********

And how to store and retrieve such a large values posted Nov 24, 2013
Share this question
I hope I understood your problem correctly, see the following mathematical properties -
a^n mod x = (a mod x)^n mod x
a^n mod x = (a^2 mod x)^(n/2) mod x
Any many similar operations

Now the problem can be solved using mix of modulo properties...Let me know if this is fine then we can write the program...
What if n <= 10^10000 ?
You can always do by breaking the mod operation
say n = n1*n2

a^n mod x = (a^n1 mod x)^n2 mod x

## 1 Answer

+2 votes

As Salil suggested say you have following problem -
(a1 ^ a2) mod n

Step 1: Replace a1 with mod value i.e. and initialize result as 1

``````a1 = a1 mod n
result = 1
``````

Step 2: Find out the prime factor of a2 say

``````a2 = n1 * n2 * n3 ....
``````

Step 3: for each factor (for each i)

``````result = result * (a1^ni mod n)
`````` answer Nov 24, 2013
Thanks Deepak and Salil for your valuable comments
I have a doubt
can we even reduce a2 to a2 mod (n)??
Now how to implement these with c program
Please help me out
No mod can not be applied on a2.
Similar Questions
+6 votes

What is the simples way to check if the sum of two unsigned integers has resulted in an overflow.

+1 vote

This was asked today at Amazon interview -

Given two Binary Trees (not BST). Each node of both trees has an integer value. Validate whether both trees have the same integers, there could be repetitive integers.

Example
Tree1:
5
1 6
5 4 3 6

Tree2:
1
3 4
6 5

Output
Identical integers

Sample C/C++/Java code would be helpful.

+2 votes

How to implement the function power(int x, int y) recursively.

+2 votes

Given Tree

``````          6
/     \
7        8
/   \     /  \
9    10  11    12
\
13
``````

Expected Output
6 8 12 13