quadraticSieve: Prime Factorization with the Parallel Quadratic Sieve

In RcppBigIntAlgos: Factor Big Integers with the Parallel Quadratic Sieve

Prime Factorization with the Parallel Quadratic Sieve

Description

Get the prime factorization of a number, n, using the Quadratic Sieve.

Usage

quadraticSieve(n, showStats = FALSE, nThreads = NULL)

Arguments

n	An integer, numeric, string value, or an element of class bigz.
showStats	Logical flag. If TRUE, summary statistics will be displayed.
nThreads	Number of threads to be used. The default is NULL.

Details

First, trial division is carried out to remove small prime numbers, then a constrained version of Pollard's rho algorithm is called to quickly remove further prime numbers. Next, we check to make sure that we are not passing a perfect power to the main quadratic sieve algorithm. After removing any perfect powers, we finally call the quadratic sieve with multiple polynomials in a recursive fashion until we have completely factored our number.

When showStats = TRUE, summary statistics will be shown. The frequency of updates is dynamic as writing to stdout can be expensive. It is determined by how fast smooth numbers (including partially smooth numbers) are found along with the total number of smooth numbers required in order to find a non-trivial factorization. The statistics are:

MPQS Time

The time measured for the multiple polynomial quadratic sieve section in hours h, minutes m, seconds s, and milliseconds ms.

Complete

The percent of smooth numbers plus partially smooth numbers required to guarantee a non-trivial solution when Gaussian Elimination is performed on the matrix of powers of primes.

Polynomials

The number of polynomials sieved

Smooths

The number of Smooth numbers found

Partials

The number of partially smooth numbers found. These numbers have one large factor, F, that is not reduced by the prime factor base determined in the algorithm. When we encounter another number that is almost smooth with the same large factor, F, we can combine them into one partially smooth number.

Value

Vector of class bigz

Note

• primeFactorizeBig is preferred for general prime factorization.

• Both the extended Pollard's rho algorithm and the elliptic curve method are skipped. For general prime factorization, see primeFactorizeBig.

• Safely interrupt long executing commands by pressing Ctrl + c, Esc, or whatever interruption command offered by the user's GUI. If you are using multiple threads, you can still interrupt execution, however there will be a delay up to 30 seconds if the number is very large.

• Note, the function primeFactorizeBig(n, skipECM = T, skipPolRho = T) is the same as quadraticSieve(n)

Author(s)

Joseph Wood

References

• Pomerance, C. (2008). Smooth numbers and the quadratic sieve. In Algorithmic Number Theory Lattices, Number Fields, Curves and Cryptography (pp. 69-81). Cambridge: Cambridge University Press.

• Silverman, R. D. (1987). The Multiple Polynomial Quadratic Sieve. Mathematics of Computation, 48(177), 329-339. doi:10.2307/2007894

• Integer Factorization using the Quadratic Sieve

• From https://codegolf.stackexchange.com/ (Credit to user primo for answer) P., & Chowdhury, S. (2012, October 7). Fastest semiprime factorization. Retrieved October 06, 2017

See Also

primeFactorizeBig, factorize

Examples

mySemiPrime <- gmp::prod.bigz(gmp::nextprime(gmp::urand.bigz(2, 50, 17)))
quadraticSieve(mySemiPrime)

RcppBigIntAlgos documentation built on Aug. 16, 2023, 5:06 p.m.