Computation of discrete logarithms in prime fields
Let \(p\) be a prime and \(g\), \(x\) integers. The computation of \(y\) such that \(y\equiv g^ x(\mod p)\), \(0\leq y\leq p-1\), is referred to as discrete exponentiation. Given \(p\), \(g\) and \(y\) the computation of \(x\) is referred to as the discrete logarithm problem. Using the best published algorithms the problem has a running time on the order of \[ \exp((1+o(1))(\log p)^{1/2}(\log \log p)^{1/2})\text{ as } p\to\infty, \] which is on the same order as the time required to factor an integer of the same magnitude. This paper describes an attack on the Sun Microsystems Inc. secure identification system which uses discrete exponentiation modulo a prime of 192 bits, giving the first experimental evidence of discrete logarithms modulo a prime. The precomputation stage that constructs a database of logarithms for small primes used the method of Gaussian integers to generate equations. For the Sun prime of interest the database required a few days of computation on moderately sized machines to compute the database of less than one megabyte and a few minutes to then compute a particular logarithm. It is noted that the more recent number field sieve for factoring integers is likely to improve the running time for discrete logarithms.
- A public key cryptosystem and a signature scheme based on discrete logarithms
- A subexponential-time algorithm for computing discrete logarithms over<tex>GF(p^2)</tex>
- An interactive identification scheme based on discrete logarithms and factoring
- Computing Logarithms in Finite Fields of Characteristic Two
- Discrete Logarithms in $GF ( P )$ Using the Number Field Sieve
- Discrete logarithms in \(\mathrm{GF}(p)\)
- Elliptic Curve Cryptosystems
- Factoring with Two Large Primes
- Fast evaluation of logarithms in fields of characteristic two
- scientific article; zbMATH DE number 4214161 (Why is no real title available?)
- scientific article; zbMATH DE number 3750146 (Why is no real title available?)
- scientific article; zbMATH DE number 475432 (Why is no real title available?)
- scientific article; zbMATH DE number 503245 (Why is no real title available?)
- Modifications to the number field sieve
- Modular Multiplication Without Trial Division
- New directions in cryptography
- Reducing elliptic curve logarithms to logarithms in a finite field
- Using encryption for authentication in large networks of computers
- Lower bounds for decision problems in imaginary, norm-Euclidean quadratic integer rings
- An interactive identification scheme based on discrete logarithms and factoring
- Fast matrix decomposition in F₂
- Special prime numbers and discrete logs in finite prime fields
- Improved sieving on algebraic curves
- An experiment of number field sieve over \(\mathrm{GF}(p)\) of low Hamming weight characteristic
- Performance analysis of index calculus method
- Monte Carlo Methods for Index Computation (mod p)
- Discrete logarithm problem using index calculus method
- Faster individual discrete logarithms in finite fields of composite extension degree
- Computing Prime Factorization And Discrete Logarithms: From Index Calculus To Xedni Calculus
- Improvements to the general number field sieve for discrete logarithms in prime fields. A comparison with the gaussian integer method
- Solving systems of linear equations arising in the computation of logarithms in a finite prime field
- Public-key cryptography on smart cards
- Cryptography and Coding
- On the cubic sieve method for computing discrete logarithms over prime fields
This page was built for publication: Computation of discrete logarithms in prime fields
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1179517)
