0812 large a n mod p
ph
problem : for very large natural numbers \(a, n, p\), find the value of \(a^n \pmod{p}\).
Below process is finding the period. But it will appear to be unnecessary.
def a_exp_n_mod_p(a,n,p):
# `a` can be factorized. but it does not applied here, maybe it will make this much slower.
# Factorization is a very expensive process.
assert a > 0 and n > 0 and p > 0
if a%p ==0 :
return 0
# find the period.
# a^(2^n) has a period.
LIMIT = 10000 # period limit
x = [0]*LIMIT
anmodp = a%p
for i in range(LIMIT):
if anmodp in x:
x = x[:i]
for j in range(len(x)):
if x[j]==anmodp:
break
break
x[i] = anmodp
anmodp *= anmodp
anmodp %= p
assert len(x) < LIMIT
period_len = len(x)-j
#print period_len
#print len(x)
digit = 0
r = 1
while n>0:
if n%2 == 1:
r *= x[digit]
r %= p
n /= 2
digit += 1
if digit >= len(x):
digit -= period_len
assert digit >= 0
return r
assert a_exp_n_mod_p(3,20,20) == pow(3,20)%20
assert a_exp_n_mod_p(12,15,20) == pow(12,15)%20
assert a_exp_n_mod_p(12,15,19) == pow(12,15)%19
assert a_exp_n_mod_p(4,15,497) == pow(4,15)%497
print a_exp_n_mod_p(2032343532,24234234324,2342434234)
1368242842
Below will be enough.
def anmodp(a, n, p):
if n==1:
return a%p
tmp = anmodp(a, n/2, p)
if n%2==1: #odd
return (a*(tmp**2))%p
else:
return (tmp**2)%p
\(O(\log n)\) process can use recursive call freely.