China
Africa
Explore chapters and articles related to this topic
Number Theory
Published in Paul L. Goethals, Natalie M. Scala, Daniel T. Bennett, Mathematics in Cyber Research, 2022
Other exponential-time algorithms for discrete logarithms include the Pohlig-Hellman algorithm and Pollard's rho algorithm for logarithms. Pohlig-Hellman works very well for primes p such that p−1 is the product of small prime numbers. Pollard's rho algorithm has runtime approximately O(p), but requires much less storage than the baby-step giant-step algorithm. It's main idea is the same as Pollard's rho algorithm for factorization, which we discuss in Section 12.7.1. Subexponential algorithms include the index calculus algorithm and the number field sieve for logarithms, which are similar to the quadratic sieve algorithm for integer factorization. The function field sieve is a subexponential algorithm that computes discrete logarithms in finite fields.
Discrete Logarithm Problem
Published in Khaleel Ahmad, M. N. Doja, Nur Izura Udzir, Manu Pratap Singh, Emerging Security Algorithms and Techniques, 2019
Khaleel Ahmad, Afsar Kamal, Khairol Amali Bin Ahmad
The function field sieve is used to compute the discrete logarithm in Fp*n within random time, as introduced by Leonard Adleman in 1994. It generalizes the algebraic number field into the function field sieve. It is the faster method for factoring integers than other older algorithm such as Coppersmith’s algorithm in the finite field of small characteristics. It is very similar to number field sieve (NFS) in the prime field, where a ring of integer Z is replaced by a ring of polynomial K[t] with a finite field of size κ = #K (Adleman & Huang, 1999). The probable running time of this algorithm is Lpn[1/3, c] for a constant c > 0, if log p ≤ ng(n) where g is a function that satisfies limn→∞g(n)=0 and 0.98 > g(n) > 0 replace κ. The calculation starts by taking a finite field F and a non-reducible polynomial p∈F[x]. The goal is to find out the absolute non-reducible polynomial A ∈ F[x, y] with m ∈ F[x] and degreed in y that satisfies H(x, m) ≡ 0 mod p. Continuously working in F[x] and the function field L = Quotient(F[x, y])/(H)) needs double smooth pair < r and s > ∈ F[x] * F[x], where r and s are relatively prime. The intersection of ry + s with H, rm + s and rd·H(x, −s/r) are smooth in F[x] (Schirokauer, 2008; Joux & Lercier, 2002).
Number-Theoretic Reference Problems
Published in Alfred J. Menezes, Paul C. van Oorschot, Scott A. Vanstone, Handbook of Applied Cryptography, 2018
Alfred J. Menezes, Paul C. van Oorschot, Scott A. Vanstone
It was not until 1992 that a subexponential-time algorithm for computing discrete logarithms over all finite fields Fq was discovered by Adleman and DeMarrais [11]. The expected running time of the algorithm is conjectured to be Lq[12,c] for some constant c. Adleman [9] generalized the number field sieve from algebraic number fields to algebraic function fields which resulted in an algorithm, called the function field sieve, for computing discrete logarithms in Fpm*; the algorithm has a heuristic expected running time of Lpm[13,c] for some constant c > 0 when log p ≤ mg(m), and where g is any function such that 0 < g(m) < 0.98 and limm→∞g(m) = 0. The practicality of the function field sieve has not yet been determined. It remains an open problem to find an algorithm with a heuristic expected running time of Lp[13,c] for all finite fields Fq.
A Framework for Filtering Step of Number Field Sieve and Function Field Sieve
Published in IETE Journal of Research, 2023
Rahul Janga, R. Padmavathy, S. K. Pal, S. Ravichandra
Number Field Sieve (NFS) is the best-known algorithm to solve Integer Factorization. There are two variants of NFS, one is NFS-IF which solves Integer Factorization and the other is NFS-DL which solves the Discrete Logarithm Problem. RSA-795 has been solved by using NFS-IF, which is the current world record in solving Integer Factorization. Function Field Sieve (FFS) is the algorithm to solve the Discrete Logarithm Problem. The discrete logarithm problem over is solved in 2013 using FFS.