bigIntegerAlgos (version 0.1.2)

quadraticSieve: Prime Factorization with the Quadratic Sieve

Description

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

Usage

quadraticSieve(n)

Arguments

n

An integer, numeric, string value, or an element of class bigz.

Value

Vector of class bigz

Details

First, trial division is carried out to remove small prime numbers, then a modified version of Pollard's rho algorithm that is constrained 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.

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

factorize

Examples

# NOT RUN {
mySemiPrime <- prod(nextprime(urand.bigz(2, 40, 17)))
quadraticSieve(mySemiPrime)
# }