divisorsBig: Vectorized Factorization (Complete) with GMP

In RcppBigIntAlgos: Factor Big Integers with the Parallel Quadratic Sieve

Vectorized Factorization (Complete) with GMP

Description

Quickly generates the complete factorization for many (possibly large) numbers.

Usage

divisorsBig(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 passed to primeFactorizeBig for skipping the extended pollard rho algorithm. The default is FALSE.
skipECM	Logical flag passed to primeFactorizeBig 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. The default is NULL.

Details

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.

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.

Author(s)

Joseph Wood

References

Divisor

See Also

divisorsRcpp, divisors

Examples

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

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