"0812 large a n mod p"의 두 판 사이의 차이
ph
(새 문서: problem : for very large natural numbers \(a, n, p\), find the value of \(a^n \pmod{p}\). <pre> def a_exp_n_mod_p(a,n,p): assert a > 0 and n > 0 and p > 0 if a%p ==0 :...) |
잔글 |
||
| 3번째 줄: | 3번째 줄: | ||
<pre> | <pre> | ||
def a_exp_n_mod_p(a,n,p): | def a_exp_n_mod_p(a,n,p): | ||
| + | # `a` can be factorized. but it does not applied here. | ||
assert a > 0 and n > 0 and p > 0 | assert a > 0 and n > 0 and p > 0 | ||
if a%p ==0 : | if a%p ==0 : | ||
2017년 8월 12일 (토) 23:52 판
problem : for very large natural numbers \(a, n, p\), find the value of \(a^n \pmod{p}\).
def a_exp_n_mod_p(a,n,p):
# `a` can be factorized. but it does not applied here.
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