0812 large a n mod p 문서 원본 보기

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.

<pre>
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 
</pre>


Below will be enough.
<pre>
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
</pre>

\(O(\log n)\) process can use recursive call freely.

<disqus />