FEDORA-2016-b2c351067e created by jjames 5 years ago for Fedora 24

This new package provides implementations of the following methods for factoring integers:

  • Pollard's p-1
  • Williams' p+1
  • Elliptic Curves Method (ECM)
  • Continued Fraction Algorithm (CFRAC)
  • Multiple Polynomial Quadratic Sieve (MPQS)

FactInt also makes use of Richard P. Brent's tables of known factors of integers of the form bk+/-1 for "small" b.

The ECM method is suited best for finding factors which are neither too small (i.e. have less than about 12 decimal digits) nor too close to the square root of the number to be factored. The MPQS method is designed for factoring products of two primes of comparable orders of magnitude. CFRAC is the historical predecessor of the MPQS method. Pollard's p-1 and Williams' p+1 are useful for finding factors p such that all prime factors of p-1 (respectively p+1) are "small", e.g. smaller than 1000000. All factoring methods implemented in this package are probabilistic. In particular the time needed by the ECM method depends largely on luck.

FactInt provides a general-purpose factorization routine which uses an appropriate combination of the methods mentioned above, the Pollard Rho routine which is implemented in the GAP Library and a variety of tricks for special cases to obtain a good average performance for "arbitrary" integers. At the user's option, FactInt provides detailed information about the progress of the factorization process.

How to install

sudo dnf install --advisory=FEDORA-2016-b2c351067e \*

This update has been submitted for testing by jjames.

5 years ago

This update has been pushed to testing.

5 years ago

This update has reached 3 days in testing and can be pushed to stable now if the maintainer wishes

5 years ago

This update has been submitted for stable by jjames.

5 years ago

This update has been pushed to stable.

5 years ago

Please login to add feedback.

Content Type
Test Gating
Unstable by Karma
Stable by Karma
Stable by Time
5 years ago
in testing
5 years ago
in stable
5 years ago
BZ#1332764 Review Request: gap-pkg-factint - Advanced methods for factoring integers

Automated Test Results