Some remarks on the Herlestam-Johannesson algorithm for computing logarithms over \(GF(2^ P)\).

*(English)*Zbl 0554.12012
Advances in cryptology, Proc. Workshop, Santa Barbara/Calif. 1982, 15-19 (1983).

[For the entire collection see Zbl 0511.00040.]

Let t be a primitive element in \(GF(2^ p)\) and let \(\alpha\) be expressed as \(\sum^{n-1}_{i=0}a_ it^ i\), where \(a_ i\) is 0 or 1. Define the Hamming weight, HWT(\(\alpha)\), as the number of non-zero \(a_ i\), and define MINHJ(\(\alpha)\) as min HWT(\(\beta)\), where \(\beta\) belongs to the set \(t^{-2^ r}\alpha^{2^ s}\) (0\(\leq r,s\leq p-1)\). T. Herlestam and R. Johannesson [BIT 21, 326-334 (1981; Zbl 0493.12023)], with a view to cryptanalysis of the Pohlig-Hellman algorithm [cf. S. C. Pohling and M. E. Hellman, IEEE Trans. Inf. Theory IT-24, 106-110 (1978; Zbl 0375.68023)], proposed an heuristic method of finding logarithms over \(GF(2^ p)\) that took fewer steps in practice than one would expect if HWT(\(\alpha)\) and MINHJ(\(\alpha)\) were independent.

In the present paper, to test this hypothesis of independence, the authors compute the probability that \(MINHJ(\alpha)=1\), given that \(HWT(\alpha)=i\), for various polynomials that implement \(GF(2^{31})\). Only for some polynomials does the assumption of independence appear to be supported. They report also that the assumption that the probability that \(MINJ(\alpha)=j\) depends only on HWT(\(\alpha)\) is somewhat suspect.

Let t be a primitive element in \(GF(2^ p)\) and let \(\alpha\) be expressed as \(\sum^{n-1}_{i=0}a_ it^ i\), where \(a_ i\) is 0 or 1. Define the Hamming weight, HWT(\(\alpha)\), as the number of non-zero \(a_ i\), and define MINHJ(\(\alpha)\) as min HWT(\(\beta)\), where \(\beta\) belongs to the set \(t^{-2^ r}\alpha^{2^ s}\) (0\(\leq r,s\leq p-1)\). T. Herlestam and R. Johannesson [BIT 21, 326-334 (1981; Zbl 0493.12023)], with a view to cryptanalysis of the Pohlig-Hellman algorithm [cf. S. C. Pohling and M. E. Hellman, IEEE Trans. Inf. Theory IT-24, 106-110 (1978; Zbl 0375.68023)], proposed an heuristic method of finding logarithms over \(GF(2^ p)\) that took fewer steps in practice than one would expect if HWT(\(\alpha)\) and MINHJ(\(\alpha)\) were independent.

In the present paper, to test this hypothesis of independence, the authors compute the probability that \(MINHJ(\alpha)=1\), given that \(HWT(\alpha)=i\), for various polynomials that implement \(GF(2^{31})\). Only for some polynomials does the assumption of independence appear to be supported. They report also that the assumption that the probability that \(MINJ(\alpha)=j\) depends only on HWT(\(\alpha)\) is somewhat suspect.

Reviewer: H.J.Godwin

##### MSC:

11T06 | Polynomials over finite fields |

94B35 | Decoding |

68Q25 | Analysis of algorithms and problem complexity |