Re: Curious question from 480b Homework 4
William Stein
>
> I was playing around with problem 3 on the homework and noticed that for
> certain primes the discrete log was computed very quickly, while others took
> a much longer time, even though both primes were of similar size. For
> example 10^15+37 took 1.56 seconds while 10^17+3 took 0.02 seconds even
> though it is two orders of magnitude larger. 10^17+81 took over 35
> seconds. Is there something about the discrete logarithm algorithm that
> sage is using that causes this?
Yes.
> And does is suggest that in Diffie
> Hellman there are certain primes that are weaker than others of the same
> size?
Yes, indeed! That's a very astute observation you just made.
The explanation for what you see above is that the computational
complexity of doing discrete log mod p is not a function of just the
number of digits of p. It's really a function of the *largest* prime
divisor of p-1. Look at the factorization of p-1 for each of the
three primes above:
sage: factor(10^15+37 - 1)
2^2 * 7 * 37 * 965250965251
sage: factor(10^17+3-1)
2 * 3 * 7 * 61 * 65701 * 594085421
sage: factor(10^17+81 - 1)
2^4 * 3^2 * 5 * 138888888888889
Notice that the fastest one has the smallest "largest prime divisor",
and the slowest has the largest "largest prime divisor".
William