君は春の中にいる、かけがえのない春の中にいる.

你驻足于春色中,于那独一无二的春色之中.

数论基础-原根与指标

数论基础部分有关于原根和指标的学习脑图。

思维导图:

三位数内的原根求解程序,如果验证有错,欢迎指出~~:

#! /usr/bin/env python
# -*- coding=UTF-8 -*-

def gcd(a, b):  # 求最大公约数
    while b != 0:
        (a,b) = (b, a%b)
    return a

def factorize(n, wheel=3):  # 因数分解
    if n < 2:
        return []
    primes = (2, 3, 5, 7, 11)
    if wheel < 2 or wheel > len(primes):
        wheel = 3
    primes = primes[:wheel]
    q = []
    for p in primes:
        if n % p != 0:
            continue
        e = 1
        n //= p
        while n % p == 0:
            n //= p
               e += 1
        q.append((p, e))
    if n > 1:
        m = reduce(lambda x, y:x*y, primes, 1)
        offs = [x for x in xrange(2, m + 1) if gcd(m, x) == 1] + [m + 1]
        k, done = 0, False
        while n > 1:
            for offset in offs:
                p = k + offset
                if p ** 2 > n:
                    done = True
                    break
                if n % p != 0:
                    continue
                e = 1
                n //= p
                while n % p == 0:
                    n //= p
                    e += 1
                q.append((p, e))
            if done:
                break
            k += m
        if n > 1:
            q.append((n, 1))
    return q

def Euler(n, wheel=3):  # 求欧拉函数
    ''' Euler Totient Function of n using a prime wheel criterion.
        It's almost as fast as the phi(n, p) function '''
    if n < 2:
        return n
    q = factorize(n, wheel)
    r = 1
    for (p, e) in q:
        r *= (p - 1) * (p ** (e - 1))
    return r

def primitive_root(mod):  # 求原根
    simple = []
    root = []
    phi_m = Euler(mod)
    for i in range(1,mod):
        if gcd(i, mod) == 1:
            simple.append(i)
    for a in simple:
        for j in range(1,phi_m+1):
            if a ** j % mod == 1:
                if j == phi_m:
                    root.append(a)
                else:
                    break

    return root

if __name__ == '__main__':
    mod = raw_input('Please input mod:')
    print primitive_root(int(mod))`