×

How to calculate a^b mod p i.e.(a^b%p) where p is a big prime number of the order 10^9....

 0 i have some knowldege of fermats little theorem but for that i think 'b' must be of the form : b=k*(p-1) + m...and the answer would be a^m...but in my case 'b' is smaller than p for example b is 10^7(so i cant express 'b' in terms of 'p') ...?? By simply writing the expression it is overflowing the long long int range ..plz help asked 12 May '15, 11:28 111●1●6 accept rate: 11%

 2 you can use repeated squaring it basically depends on the fact you can use code:- int mod = 1000000007 int powmod(int base,int pow) { int res=1; while(pow) { if (pow%2!=0) res=(res*base)%mod; base=(base*base)%mod; pow/=2; } return res; }  you can get more information from wiki-Exponentiation by squaring answered 12 May '15, 12:47 82●2 accept rate: 0%
 0  MOD 1000000007 int expo(int base,int power) { int result=1; while(power) { if(power&1) result=(resultbase)%MOD; base=(basebase)%MOD; power>>=1; } return result; }  answered 12 May '15, 15:42 893●2●11●34 accept rate: 10% for large prime, replace int with long long (12 May '15, 15:46)
 0  MOD 1000000007 int square(int a) { return (aa)%MOD; } int expo(int base,int power) { if(power==1) return base; else if(power&1) return (baseexpo(base,power-1)) % MOD; else return square(expo(base,power/2))%MOD; }  answered 12 May '15, 15:45 893●2●11●34 accept rate: 10% for large prime, replace int with long long (12 May '15, 15:46)
 toggle preview community wiki:
Preview

By Email:

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• image?![alt text](/path/img.jpg "title")
• numbered list: 1. Foo 2. Bar
• to add a line break simply add two spaces to where you would like the new line to be.
• basic HTML tags are also supported
• mathemetical formulas in Latex between \$ symbol

Question tags:

×626
×336
×48
×7

question asked: 12 May '15, 11:28

question was seen: 5,193 times

last updated: 12 May '15, 15:46