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
where a=d+e2 and b=d−e2. Thus, one (inefficient) way of trying to factor n is to go through the values of the polynomial x2−n one-by-one, checking whether they are square. In this section we discuss the quadratic sieve, invented in 1981 by Carl Pomerance, which is one in a series of factorization algorithms which generalize this idea.
*Algorithms for Factoring and Computing Discrete Logarithms
Published in Jonathan Katz, Yehuda Lindell, Introduction to Modern Cryptography, 2020
Pollard’s rho algorithm is better than trial division, but still runs in exponential time. The quadratic sieve algorithm runs in sub-exponential time. It was the fastest known factoring algorithm until the early 1990s and remains the factoring algorithm of choice for numbers up to about 300 bits long. We describe the general principles of the algorithm but caution the reader that several important details are omitted.
Linear Algebra on Parallel Structures Using Wiedemann Algorithm to Solve Discrete Logarithm Problem
Published in IETE Journal of Research, 2022
K S Spoorthi, R. Padmavathy, S K Pal, S Ravi Chandra
Parallel solutions to sparse matrix computation are available in the literature [1, 30–33]. The Coppersmith Block Wiedemann algorithm is analyzed in [1]. Brent discussed implementation of integer factorization on vector processors and parallel machines in [34] and discussed about the parallel implementation of elliptic curve method and multiple polynomial quadratic sieve algorithms in [35]. An efficient CUDA implementation using hybrid sparse matrix format for linear algebra step of integer factorization of NFS is proposed in [36]. Initially, in 2001, Yang and Brent proposed improved version of Lanczos to solve integer factorization and discrete logarithm problem on parallel structures [37]. Again in 2001, Yang and Brent proposed parallel improved block Lanczos method for integer factorization to solve large sparse linear system over [32]. Recently, Jeljeli proposed the discrete logarithm problem computation using GPU's [30]. Other results are available in [31, 33, 38]. In this paper, the behavior of Joux's Wiedemann algorithm [20] with respect to density has been analyzed.