Some soluble cases of the discrete logarithm problem (Q1115897): Difference between revisions

Carmichael's function \(\lambda\) (n) is defined as follows. If \(\rho\) is an odd prime and \(\alpha\) is a natural number then, \(\lambda (\rho^{\alpha})=\phi (\rho^{\alpha})\) where \(\phi\) is Euler's totient function. \(\lambda (2^{\alpha})=\phi (2^{\alpha})\) if \(\alpha =1\) or 2 and \(\lambda (2^{\alpha})=\phi (2^{\alpha})/2\) if \(\alpha >2\). If \(n=q_ 1^{\alpha_ 1}q_ 2^{\alpha_ 2}... q_ s^{\alpha_ s}\) where the \(q_ i\) are distinct primes then \(\lambda\) (n) is the lowest common multiple of the set of integers \(\{\lambda (q_ 1^{\alpha_ 1}),...,\lambda (q_ s^{\alpha_ s})\}\). It is obvious that \(\lambda\) (n)\(| \phi (n)\). If n and g are relatively prime and the order of g modulo n is \(\lambda\) (n), then g is said to be a primitive \(\lambda\)-root modulo n. The powers \(g^ i\), where \(i=1,2,...,\lambda (n)\), form a cyclic subgroup of \(M_ n\), the group of order \(\phi\) (n) which consists of the positive integers relatively prime to n and less than n. If \(a\equiv g^ s (mod n)\) then s is called the discrete logarithm of a to the base g. Finding s if a is known is called the discrete logarithm problem. In the present paper, by making use of the Fermat quotient (defined by \(Q(a,\rho)=\rho^{-1}(a^{\rho^{-1}}-1) mod \rho)\) and its generalizations, the author shows that in certain cases the discrete logarithm problem can be solved, without guesswork, in time \(O(\log^ 3n)\) or less. This has important implications for the security of public- key cryptosystems.