Calculating big powers modulo a prime number

Revision en1, by small_doubt, 2018-07-13 14:08:12

I have a number A and a number B(which is very large calculated by NcR or C(N,R) modulo 10e9+7) and i want to find A^B(A raise to the power B) but by fast exponentation i get wrong answer. Like for example A=2 and B=6 and mod=5 then actual answer is(2^6)%5=4 but since i have to use mod at every step my answer is (2^(6%5))%5=2. I can't store B in a number because it's too large.How should i go about it?Thanks in advance.

Tags fast power, modulo multiplication

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en1 English small_doubt 2018-07-13 14:08:12 472 Initial revision (published)