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
LVL 1
YamSengAsked:
Who is Participating?
 
ozoConnect With a Mentor 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
 
griesshCommented:
There are libraries for large integers. How about http://www.codeproject.com/cpp/largenumber.asp.

======
Werner
0
 
griesshCommented:
I hate when that happens ....

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

======
Werner
0
The new generation of project management tools

With monday.com’s project management tool, you can see what everyone on your team is working in a single glance. Its intuitive dashboards are customizable, so you can create systems that work for you.

 
YamSengAuthor Commented:
what about solving the problem with maths?

Yam
0
 
0xDEADBEEFCommented:
Try ((a%p)^((p-1)/2)) % p, I think that should work.
0
 
YamSengAuthor 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.

I'm not sure about ozo's answer.....is it similar to mine?  

if yes, I'll award you.

Cheers!
Yam
0
 
ozoCommented:
Similar, but you only need to multiply log((b-1)/2) times
0
 
YamSengAuthor 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
 
ozoCommented:
//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
 
YamSengAuthor Commented:
but the performance would be slower right?   coz it's no longer log((b-1)/2) times ?
0
 
ozoCommented:
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
 
YamSengAuthor 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
All Courses

From novice to tech pro — start learning today.