Some Remarks on the Herlestam-Johannesson Algorithm for Computing Logarithms over GF(2p)

At the 1981 IEEE Symposium on Information Theory, T. Herlestam and R. Johannesson presented a heurestic method for computing logarithms over GF(2p). They reported computing logarithms over GF(23 !) with surprisingly few iterations and claimed that the running time of their algorithm was polynomial in p. If this were true, the algorithm could be used to cryptanalyze the Pohlig-Hellman cryptosystem, currently in use by Mitre Corporation for key distribution. The Mitre system operates in GF(2127). However, the algorithm was not implemented for GF(2p) for p > 31 because it would require multiple precision arithmetic. Consequently attempts to evaluate the possible threat to the Pohlig-Hellman cryptosystem have centered on modeling the algorithm so that some predictions could be made analytically about the number of iterations required to find logarithms over GF(2P) for p > 31.