×

A polynomial form for logarithms modulo a prime. (English) Zbl 0558.12009

Let p be prime, with a primitive root a. Let g be a polynomial such that, for \(1\leq k\leq p-1\), we have \(k\equiv a^{g(k)} (mod p)\), i.e. g(k) is the logarithm of k modulo p. It is shown that \(g(k)=\sum^{p- 2}_{i=1}(1-a^ i)^{-1} k^ i (mod p)\) is one such possibility for g, and that any such polynomial g has at least p-2 non-zero coefficients. Hence calculation of logarithms by this method (with a view to code- breaking) is not practical.
Reviewer: H.J.Godwin

MSC:

11T55 Arithmetic theory of polynomial rings over finite fields
11A07 Congruences; primitive roots; residue systems
94B35 Decoding
Full Text: DOI