Analysis of the Herlestam and Johannesson discrete logarithm scheme inGF(2 N ) for largeN

The Herlestam and Johannesson algorithm for computing discrete logarithms inGF(2ⁿ) requires the precomputation of logarithms for a target set consisting of all field elements of Hamming weight less than some predetermined value. The procedure, both in precomputation and at run-time, selects elements of lowest weight from large sets of elements. These sets are not randomly chosen but their minimum weight statistics parallel those for sets of equal size chosen entirely at random. By analyzing the statistics for randomly chosen sets, we show that the target set must contain all elements up to about weightn/3–8. This is clearly impractical for even moderately large values ofn.This work was supported by MITRE Corp. IR & D funds.Dr. Berkovits was on leave from the University of Lowell, Lowell, MA, 01854.