primeFactorizeBig: Vectorized Prime Factorization with GMP

In RcppBigIntAlgos: Factor Big Integers with the Parallel Quadratic Sieve

Vectorized Prime Factorization with GMP

Description

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.

Usage

primeFactorizeBig(v, namedList = FALSE, showStats = FALSE,
                  skipPolRho = FALSE, skipECM = FALSE, nThreads = NULL)

Arguments

v	Vector of integers, numerics, string values, or elements of class bigz.
namedList	Logical flag. If TRUE and the length(v) > 1, a named list is returned. The default is FALSE.
showStats	Logical flag for showing summary statistics. The default is FALSE.
skipPolRho	Logical flag for skipping the extended pollard rho algorithm. The default is FALSE.
skipECM	Logical flag for skipping the extended elliptic curve algorithm. The default is FALSE.
nThreads	Number of threads to be used for the elliptic curve method and the quadratic sieve.s The default is NULL.

Details

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.

Value

• 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

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

Author(s)

Joseph Wood

References

• Gaj K. et al. (2006) Implementing the Elliptic Curve Method of Factoring in Reconfigurable Hardware. In: Goubin L., Matsui M. (eds) Cryptographic Hardware and Embedded Systems - CHES 2006. CHES 2006. Lecture Notes in Computer Science, vol 4249. Springer, Berlin, Heidelberg. https://doi.org/10.1007/11894063_10

• Integer Factorization

See Also

primeFactorize, primeFactors, factorize, quadraticSieve

Examples

## 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)

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