Prime numbers: A computational perspective

By Tony Forbes. 2002

893 citations recorded by the source corpus.

View Paper: https://www.semanticscholar.org/paper/c3e32e5097f2e9e4cb154a725f89d422f98992a6

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Theoretical Computer Science

Citations in the corpus

Introduction to Modern Cryptography, Second Edition (2014, neutral): “The texts by Wagstaff [173], Shoup [159], Crandall and Pomerance [51], Joux [96], and Galbraith [69] provide further information on algorithms for factoring and computing discrete logarithms, including descriptions of the (general) number field sieve.”
Simple Encrypted Arithmetic Library-SEAL (2017, methodology): “Multiplication of polynomials in Z[x]/(x+ 1) is the most computationally expensive part of Mul, which in SEAL we implement using Nussbaumer convolution [16].”
Quantum Computation and Quantum Information (2012, methodology): “…quantum factoring algorithm can accomplish the task of factoring an n -bit integer with operations of order n 2 log n log log n , the current best known classical algorithm requires operations of order exp( n 1 / 3 log 2 / 3 n ) to factor an n -bit composite number (Crandall and Pomerance (2001)).”
The number field sieve (2008, methodology): “For the general number field sieve, one can compute a root of the polynomial X(2) − γ(2) in Q(α) by standard methods, such as successive approximation using Hensel’s lemma [1] at an appropriate prime.”
Imperfect Forward Secrecy: How Diffie-Hellman Fails in Practice (2015, neutral): “1 There is a closely related number field sieve algorithm for factoring [12,31], and in fact many parts of the implementations can be shared.”
Accelerating Homomorphic Evaluation on Reconfigurable Hardware (2015, background): “In this case it holds that d̂ = INTTq(NTTq(â)◦NTTq(b̂)), where ◦ means coefficient-wise multiplication [18,45].”
The Algorithm Design Manual (2020, methodology): “[CP05] R. Crandall and C. Pomerance.”