| Title: | Factor Big Integers with the Parallel Quadratic Sieve |
|---|---|
| Description: | Features the multiple polynomial quadratic sieve (MPQS) algorithm for factoring large integers and a vectorized factoring function that returns the complete factorization of an integer. The MPQS is based off of the seminal work of Carl Pomerance (1984) <doi:10.1007/3-540-39757-4_17> along with the modification of multiple polynomials introduced by Peter Montgomery and J. Davis as outlined by Robert D. Silverman (1987) <doi:10.1090/S0025-5718-1987-0866119-8>. Utilizes the C library GMP (GNU Multiple Precision Arithmetic). For smaller integers, a simple Elliptic Curve algorithm is attempted followed by a constrained version of Pollard's rho algorithm. The Pollard's rho algorithm is the same algorithm used by the factorize function in the 'gmp' package. |
| Authors: | Joseph Wood [aut, cre], Free Software Foundation, Inc. [cph], Mike Tryczak [ctb] |
| Maintainer: | Joseph Wood <[email protected]> |
| License: | GPL (>= 2) |
| Version: | 1.1.0 |
| Built: | 2024-10-26 06:35:50 UTC |
| Source: | CRAN |
Quickly generates the complete factorization for many (possibly large) numbers.
divisorsBig(v, namedList = FALSE, showStats = FALSE, skipPolRho = FALSE, skipECM = FALSE, nThreads = NULL)divisorsBig(v, namedList = FALSE, showStats = FALSE, skipPolRho = FALSE, skipECM = FALSE, nThreads = NULL)
v |
Vector of integers, numerics, string values, or elements of class bigz. |
namedList |
Logical flag. If |
showStats |
Logical flag for showing summary statistics. The default is |
skipPolRho |
Logical flag passed to |
skipECM |
Logical flag passed to |
nThreads |
Number of threads to be used for the elliptic curve method and the quadratic sieve. The default is |
Highly optimized algorithm to generate the complete factorization after first obtaining the prime factorization. It is built specifically for the data type that is used in the gmp library (i.e. mpz_t).
The main part of the algorithm that generates all divisors is essentially the same algorithm that is implemented in divisorsRcpp from the RcppAlgos package. A modified merge sort algorithm is implemented to better deal with the mpz_t data type. This algorithm avoids directly swapping elements of the main factor array of type mpz_t but instead generates a vector of indexing integers for ordering.
The prime factorization is obtained using primeFactorizeBig, which attempts trial division, Pollard's rho algorithm, Lentra's elliptic curve method, and finally the quadratic sieve.
See this stackoverflow post for examples and benchmarks : R Function for returning ALL factors.
See quadraticSieve for information regarding showStats.
Returns an unnamed vector of class bigz if length(v) == 1 regardless of the value of namedList.
If length(v) > 1, a named/unnamed list of vectors of class bigz will be returned.
Joseph Wood
## Get the complete factorization of a single number divisorsBig(100) ## Or get the complete factorization of many numbers set.seed(29) myVec <- sample(-1000000:1000000, 1000) system.time(myFacs <- divisorsBig(myVec)) ## Return named list myFacsWithNames <- divisorsBig(myVec, namedList = TRUE) ## Get the complete factorization for a large semiprime big = gmp::prod.bigz(gmp::nextprime(gmp::urand.bigz(2, size = 65, seed = 3))) divisorsBig(big)## Get the complete factorization of a single number divisorsBig(100) ## Or get the complete factorization of many numbers set.seed(29) myVec <- sample(-1000000:1000000, 1000) system.time(myFacs <- divisorsBig(myVec)) ## Return named list myFacsWithNames <- divisorsBig(myVec, namedList = TRUE) ## Get the complete factorization for a large semiprime big = gmp::prod.bigz(gmp::nextprime(gmp::urand.bigz(2, size = 65, seed = 3))) divisorsBig(big)
Quickly generates the prime factorization for many (possibly large) numbers, using trial division, Pollard's rho algorithm, Lenstra's Elliptic Curve method, and finally the Quadratic Sieve.
primeFactorizeBig(v, namedList = FALSE, showStats = FALSE, skipPolRho = FALSE, skipECM = FALSE, nThreads = NULL)primeFactorizeBig(v, namedList = FALSE, showStats = FALSE, skipPolRho = FALSE, skipECM = FALSE, nThreads = NULL)
v |
Vector of integers, numerics, string values, or elements of class bigz. |
namedList |
Logical flag. If |
showStats |
Logical flag for showing summary statistics. The default is |
skipPolRho |
Logical flag for skipping the extended pollard rho algorithm. The default is |
skipECM |
Logical flag for skipping the extended elliptic curve algorithm. The default is |
nThreads |
Number of threads to be used for the elliptic curve method and the quadratic sieve.s The default is |
This function should be preferred in most situations and is identical to quadraticSieve when both skipECM and skipPolRho are set to TRUE.
It is optimized for factoring big and small numbers by dynamically using different algorithms based off of the input. It takes cares to not spend too much time in any of the methods and avoids wastefully switching to the quadratic sieve when the number is very large.
See quadraticSieve for information regarding showStats.
Returns an unnamed vector of class bigz if length(v) == 1 regardless of the value of namedList.
If length(v) > 1, a named/unnamed list of vectors of class bigz will be returned.
Note, the function primeFactorizeBig(n, skipECM = T, skipPolRho = T) is the same as quadraticSieve(n)
Joseph Wood
primeFactorize, primeFactors, factorize, quadraticSieve
## Get the prime factorization of a single number primeFactorizeBig(100) ## Or get the prime factorization of many numbers set.seed(29) myVec <- sample(-1000000:1000000, 1000) system.time(myFacs <- primeFactorizeBig(myVec)) ## Return named list myFacsWithNames <- primeFactorizeBig(myVec, namedList = TRUE)## Get the prime factorization of a single number primeFactorizeBig(100) ## Or get the prime factorization of many numbers set.seed(29) myVec <- sample(-1000000:1000000, 1000) system.time(myFacs <- primeFactorizeBig(myVec)) ## Return named list myFacsWithNames <- primeFactorizeBig(myVec, namedList = TRUE)
Get the prime factorization of a number, , using the Quadratic Sieve.
quadraticSieve(n, showStats = FALSE, nThreads = NULL)quadraticSieve(n, showStats = FALSE, nThreads = NULL)
n |
An integer, numeric, string value, or an element of class bigz. |
showStats |
Logical flag. If |
nThreads |
Number of threads to be used. The default is |
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 TimeThe time measured for the multiple polynomial quadratic sieve section in hours h, minutes m, seconds s, and milliseconds ms.
CompleteThe 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.
PolynomialsThe number of polynomials sieved
SmoothsThe number of Smooth numbers found
PartialsThe 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.
Vector of class bigz
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)
Joseph Wood
primeFactorizeBig, factorize
mySemiPrime <- gmp::prod.bigz(gmp::nextprime(gmp::urand.bigz(2, 50, 17))) quadraticSieve(mySemiPrime)mySemiPrime <- gmp::prod.bigz(gmp::nextprime(gmp::urand.bigz(2, 50, 17))) quadraticSieve(mySemiPrime)
Rcpp wrapper of std::thread::hardware_concurrency(). As stated by cppreference, the returned value should be considered only a hint.
stdThreadMax()stdThreadMax()
An integer representing the number of concurrent threads supported by the user implementation. If the value cannot be determined, 1L is returned.
stdThreadMax()stdThreadMax()