R Tool for Factoring Big Integers

Features the multiple polynomial quadratic sieve algorithm for factoring large integers and a vectorized factoring function that returns the complete factorization of an integer. Utilizes the C library GMP (GNU Multiple Precision Arithmetic) and classes created by Antoine Lucas et al. found in the 'gmp' package.

Overview

bigIntegerAlgos uses the C library GMP (GNU Multiple Precision Arithmetic) for efficiently factoring big integers. For very large integers, prime factorization is carried out by a variant of the quadratic sieve algorithm that implements multiple polynomials. For smaller integers, a constrained version of the Pollard's rho algorithm is used (original code from https://gmplib.org/... this is the same algorithm found in the R gmp package (https://cran.r-project.org/web/packages/gmp/gmp.pdf) called by the function `factorize`). Finally, one can quickly obtain a complete factorization of given number `n` via `divisorsBig`.

Usage

First, we take a look at `divisorsBig`. It is vectorized and can also return a named list.

It is very efficient as well. It is equipped with a modified merge sort algorithm that significantly outperforms the `std::sort`/`bigvec` (the class utilized in the `R gmp` package) combination.

Another benefit is that it will return correct orderings on extremely large numbers when compared to sorting large vectors in `base R`. Typically in `base R` you must execute the following: `order(asNumeric(myVectorHere))`. When the numbers get large enough, precision is lost which leads to incorrect orderings. Observe:

The function `quadraticSieve` implements the multiple polynomial quadratic sieve algorithm. Currently, `quadraticSieve` can comfortably factor numbers with less than 50 digits (~160 bits).

It can also be used as a general prime factoring function:

However `gmp::factorize` is more suitable for numbers smaller than 60 bits and should be used in such cases.

Current Research:

Improvements are being made to the section of the quadratic sieve algorithm that selects smooth numbers. Right now, we are only selecting M-smooth numbers where M is the largest prime in our sieving base. A potential efficiency gain is to also keep track of mostly M-smooth numbers (i.e. numbers that are almost completely factored by our sieving base but have one factor that contains a prime number greater than M). This way, we can obtain more smooth numbers by essentially eliminating these larger factors when we find a pair of them (N.B. square terms come out in the wash, so the large factors won't influence the outcome).

We are also working on efficiently integrating `divisorsBig` with `quadraticSieve` as currently, `divisorsBig` utilizes `gmp::factorize`.

Contact

I welcome any and all feedback. If you would like to report a bug, have a question, or have suggestions for possible improvements, please contact me here: [email protected]

News

bigIntegerAlgos 0.1.2 (Release date: 2018-04-30)

bigIntegerAlgos 0.1.1 (Release date: 2018-04-25)

• Fixed error associated with the Solaris flavor in factorization.cc file.
• Forced complilation with C++11 on Windows build only (see Makevars.win) to address the following warnings : "ISO C++ 1998 does not support 'long long' [-Wlong-long]"
• Slightly altered factors that determine the cutoff point for sieving the log sum of the prime decomposition of the sieving interval constituents

bigIntegerAlgos 0.1.0 (Release date: 2018-04-11)

• Initial Release

Reference manual

install.packages("bigIntegerAlgos")

0.1.2 by Joseph Wood, a year ago

Report a bug at https://github.com/jwood000/bigIntegerAlgos/issues

Browse source code at https://github.com/cran/bigIntegerAlgos

Authors: Joseph Wood

Documentation:   PDF Manual