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.
Function fields, their places and valuations
Published in Jürgen Bierbrauer, Introduction to Coding Theory, 2016
20.1 Definition. Afunction fieldis a pair of fields F|K where F is a finite-dimensional extension of K(x) for some x ∈ F which is transcendental over the ground field K. Here x istranscendentalover K if the powers 1, x, x2 . . . are linearly independent over K (equivalently, if x is not algebraic over K). Thealgebraic closureK˜of K in F consists of the elements of F which arealgebraic(not transcendental) over K. We call Kalgebraically closedin F ifK˜=K.
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.