"0812 large a n mod p"의 두 판 사이의 차이
ph
잔글 |
잔글 |
||
| 48번째 줄: | 48번째 줄: | ||
assert a_exp_n_mod_p(4,15,497) == pow(4,15)%497 | assert a_exp_n_mod_p(4,15,497) == pow(4,15)%497 | ||
print a_exp_n_mod_p(2032343532,24234234324,2342434234) | print a_exp_n_mod_p(2032343532,24234234324,2342434234) | ||
| − | 1368242842 | + | 1368242842 # is this right? I don’t know hahahahahaha |
</pre> | </pre> | ||
<disqus /> | <disqus /> | ||
2017년 8월 12일 (토) 23:57 판
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 # is this right? I don’t know hahahahahaha