quadraticSieve: Prime Factorization with the Quadratic Sieve

In bigIntegerAlgos: R Tool for Factoring Big Integers

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.

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.

Value

Vector of class bigz

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

factorize

Examples

mySemiPrime <- prod(nextprime(urand.bigz(2, 40, 17)))
quadraticSieve(mySemiPrime)

Example output

Loading required package: gmp

Attaching package: 'gmp'

The following objects are masked from 'package:base':

    %*%, apply, crossprod, matrix, tcrossprod

Seed default initialisation
Seed initialisation
Big Integer ('bigz') object of length 2:
[1] 342086446909 483830424611

bigIntegerAlgos documentation built on May 1, 2019, 8:46 p.m.