top button
Flag Notify
    Connect to us
      Site Registration

Site Registration

How to compute modulo power of big integers?

+5 votes
474 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 by Govindaluri Kishore

Share this question
Facebook Share Button Twitter Share Button LinkedIn Share Button
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 by Deepak Dasgupta
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

...