Periods of Reciprocals of Integers

[Albert Chan]

(08-05-2018 08:49 PM)Thomas Klemm Wrote:  There are probably more efficient ways to calculate the smallest integer \(k\) such that \(10^k\equiv1(\mod n)\) since
it divides the Carmichael Function \(\lambda(n)\). But for this the we'd need to know the prime-factors of \(n\).

Hi, Thomas,

Your code is pretty good. Factoring number is hard.
A slight optimization is to check if p==n-1 too, and return k+k

The code with factoring (factor() not shown) look like this:

Code:

def order(a, n):             # assumed gcd(a, n) = 1
    m = n                    # m = phi(n) = k * period
    for (p,e) in factor(n): m -= m // p
    for (p,e) in factor(m):
        m //= p**e           # reduce k to 1, so m = period
        t = pow(a, m, n)
        while t != 1:        # m reduced too much
            m, e = m*p, e-1  # raise m, 1 p at a time
            if e==0: break
            t = pow(t, p, n)
    return m

Code:

def period(n):
    while n%2 == 0: n /= 2
    while n%5 == 0: n /= 5
    if n > 1: return order(10, n)