Pohlig-Hellman

265 days ago by bcr49

The Pohlig-Hellman algorithm for computing discrete logs:

#p = factorial(27)+1 p = 61 F = GF(p) a = F(primitive_root(p)) b = F(100) N = p-1 qi = [p^N.valuation(p) for p in prime_factors(N)] l = len(qi) Nqi = [ N/q for q in qi ] ai = [a^r for r in Nqi ] bi = [b^r for r in Nqi ] xi = [ discrete_log(bi[i],ai[i]) for i in range(l) ] x = CRT(xi,qi) print "qis =", qi print "ais =", ai print "bis =", bi print "xis =", xi print "x =", x a^x == b
 qis = [4, 3, 5] ais = [11, 47, 9] bis = [60, 47, 9] xis = [2, 1, 1] x = 46 True qis = [4, 3, 5] ais = [11, 47, 9] bis = [60, 47, 9] xis = [2, 1, 1] x = 46 True

The following can be used to generate a very big prime p such that p-1 is smooth (i.e. has only small prime factors). The output is a prime of the form N! + 1

m = 2 N = 1 while log(N) < 50 or not is_prime(N+1) : N *= m m = m + 1 print N #print prime_factors(N) p = N+1 print "p =", m-1, "! + 1 is prime"
 10888869450418352160768000000 p = 27 ! + 1 is prime 10888869450418352160768000000 p = 27 ! + 1 is prime

Sage automatically employs Pohlig-Hellman and Baby-step Giant-step when asked to compute a discrete log:

F = GF(p) aa = primitive_root(p) a = F(aa) time b = discrete_log(F(100),a)
 Time: CPU 0.00 s, Wall: 0.00 s Time: CPU 0.00 s, Wall: 0.00 s
p = next_prime(p) F = GF(p) aa = primitive_root(p) a = F(aa) print a
 5 5

The next prime number after N! + 1 is not smooth. It has large prime factors

print prime_factors(p-1) time x = discrete_log(F(100),a) #print x
 [2, 23, 353, 302928209, 2213658058565713] [2, 23, 353, 302928209, 2213658058565713]

The capabilities of our sage server are somewhat limited. For example it won't be able to compute Log_5(100) in F_p* with p = 27! + 47. More processing power can easily achieve this though. For cryptosystems based on the hardness of DLP it is recommended to use a prime p such that p-1 has a prime factor q that is at least 256 bits (i.e. q ~ 2^256). By way of contast the largest prime factor of p-1 = 27! + 47 -1 is approximately 50 bits.

p = factorial(27) + 47 is_prime(p) F = GF(p) a = F(5) b = F(100) x = 1393748935490913435527024478 a^x == 100
 True True

Here is another example verifying the solution to a DLP. It was found using better hardware and a better algorithm based on index calculus. Here the largest prime factor of p-1 has 145bits.

p = 2^150 + 6249 print "p is prime? ", is_prime(p) F = GF(p) a = F(7) b = F(2755) x = 1397041131326544918152217544982099366580777077 print "a^x =? b:", a^x == b N = p-1 q = max(prime_factors(N)) sizeq = float(log(q,2)) print "largest prime factor of p-1 has (bit) size", sizeq
 p is prime? True a^x =? b: True largest prime factor of p-1 has (bit) size 145.415037499 p is prime? True a^x =? b: True largest prime factor of p-1 has (bit) size 145.415037499