Within discrete logarithms we use the form of \(h = g^x \pmod p\). The order of \(g\) is then defined as \(p-1\), and which can be factorized into small primes:
Discrete logs: Order of a prime and factorization into small primes |
Outline
An example of \(p=3,187\):
p= 3187 h = g^x (mod 3187) The factors of (p-1) are: [2, 3, 3, 3, 59] For factors, [q,e] prime, counts: [[59, 1], [2, 1], [3, 3]]
We can see that \(p-1\) is \(2 \times 3 \times 3 \times 3 \times 59\).
Coding
# coding: utf-8 from math import sqrt, ceil import sys def PrimeFactorization(p): """Find all prime factors of the number p""" d, primeFactors = 2, [] while d*d <= p: while (p % d) == 0: primeFactors.append(d) p //= d d += 1 if p > 1: primeFactors.append(p) return primeFactors def CountOccurences(primeFactors): """Count occurances of each prime factor""" return [[x, primeFactors.count(x)] for x in set(primeFactors)] def ExtendedGCD(a, b): """Extended Euclidean algorithm for finding GCD""" a2, a1 = 1, 0 b2, b1 = 0, 1 while b: q, r = divmod(a, b) a1, a2 = a2 - q * a1, a1 b1, b2 = b2 - q * b1, b1 a, b = b, r return a, a2, b2 def ModularInverse(b, n): """Return x s.t. x = a^(-1) (mod n)""" g, x, _ = ExtendedGCD(b, n) if g == 1: return x % n def ChineseRemainder(pairs): """Chinese remainder theorem for solving a system of congruences""" N, X = pairs[0][1], 0 for ni in pairs[1:]: N *= ni[1] for (ai, ni) in pairs: mi = (N / ni) X += mi * ai * ExtendedGCD(mi, ni)[1] return X % N def ShanksAlgorithm(alpha, beta, n): """Return x s.t. beta = alpha^(x) (mod n)""" m = int(ceil(sqrt(n - 1))) a = pow(alpha, m, n) b = ExtendedGCD(alpha, n)[1] L1 = [(j, pow(a, j, n)) for j in xrange(0, m)] L2 = [(i, beta * (b ** i) % n) for i in xrange(0, m)] L1.sort(key = lambda tup: tup[1]) L2.sort(key = lambda tup: tup[1]) i, j, Found = 0, 0, False while (not Found) and (i < m) and (j < m): if L1[j][1] == L2[i][1]: return m * L1[j][0] + L2[i][0] % n elif abs(L1[j][1]) > abs(L2[i][1]): i = i + 1 else: j = j + 1 def CongruencePair(g, h, p, q, e, e1, e2): """Return pair (x, q ** e) which represents one congruence""" alphaInverse = ModularInverse(e1, p) x = 0 # x = x_{0} + x_{1} * q + x_{2} * q^{2} + ... + x_{e - 1} * q^{e - 1} for i in xrange(1, e + 1): a = pow(e1, q ** (e - 1), p) b = pow(e2 * (alphaInverse ** x), q ** (e - i), p) x += ShanksAlgorithm(a, b, p) * (q ** (i - 1)) return (x, q ** e) def PrintFormated(arg1, arg2, arg3, arg4, arg5): print (" {:2s} | {:2s} | {:13s} | {:13s} | {:45s}".format(str(arg1), str(arg2), str(arg3), str(arg4), str(arg5))) print("-"*50) g=5 h=22 p=43 if (len(sys.argv)>1): p=int(sys.argv[1]) print ("p=",p) print("h = g^x (mod %d)" % (p)) CountOccurencesList = CountOccurences(PrimeFactorization(p - 1)) print ("\nThe factors of (p-1) are:",PrimeFactorization(p - 1)) print ("For factors, [q,e] prime, counts:",CountOccurencesList)