x
• Status: Solved
• Priority: Medium
• Security: Public
• Views: 271

# big numbers when doing maths

If I want to do a^b  (a to the power of b), and if the result is too big, my long integers cannot take it.  What can I do about it?

Infact, I'm doing a prime number test:
(a^((p-1)/2)) % p.  so in general the result should be a very small number.  ie. 1 ....

but when (a^(p-1)/2) is calculated, it's already too big.  I believe there should be a mathematical way to around it but I don't know......

Yam
0
YamSeng
• 5
• 4
• 2
• +1
1 Solution

Commented:
There are libraries for large integers. How about http://www.codeproject.com/cpp/largenumber.asp.

======
Werner
0

Commented:
I hate when that happens ....

http://www.codeproject.com/cpp/largenumber.asp

======
Werner
0

Author Commented:
what about solving the problem with maths?

Yam
0

Commented:
Try ((a%p)^((p-1)/2)) % p, I think that should work.
0

Commented:
#include <stdlib.h>
#include <iostream.h>
long powmod(long a, long p,long m){
long i;
i = 1;
if( p ){
i = powmod(a,p>>1,m);
i *= i;
i %= m;
}
if( p&1 ){
i *= a;
i %= m;
}
return i;
}
main(int argc,char *argv[]){
long a,p;
a = atol(argv[1]);
p = atol(argv[2]);
cout << powmod(a,(p-1)/2,p) << endl;
}
0

Author Commented:
I found the solution now.

ie for a^(b-1/2)p

I just need to calculate

(a mod p)*(a mod p)*......for ((b-1)/2)times

Then in the end, mod p again for the final result.

Mathematically proven.

if yes, I'll award you.

Cheers!
Yam
0

Commented:
Similar, but you only need to multiply log((b-1)/2) times
0

Author Commented:
hmm....yours seems to be a recursive function.  I've thought of doing that initially, but it just seems to me as too difficult....(I hate recursive functions!)

Thanks
0

Commented:
//I think it's simpler to understand as a recursive function,
//But it can also be done non-recursively:
long powmod(long a, long p,long m){
long i;
for( i=1; p; p>>=1 ){
if( p&1 ){
i *= a;
i %= m;
}
a *= a;
a %= m;
}
return i;
}
0

Author Commented:
but the performance would be slower right?   coz it's no longer log((b-1)/2) times ?
0

Commented:
The performance is the same for the recursive and itterative versions of the powmod function above.
One just goes left to right instead of right to left.
0

Author Commented:
ozo,

1 thing about right shifting. >> .  I've tried right shifting (previously) and found that sometimes when you right shift, 1 bit which is added to the left most is 1 or 0.  It's inconsistent.  But for left shifting, it's always 0 appended.

But I think there should be a way to ensure consistency for left shifting right?

Yam
0
Question has a verified solution.

Are you are experiencing a similar issue? Get a personalized answer when you ask a related question.

Have a better answer? Share it in a comment.