[Bug 1332764] New: Review Request: gap-pkg-factint - Advanced
methods for factoring integers
by Red Hat Bugzilla
https://bugzilla.redhat.com/show_bug.cgi?id=1332764
Bug ID: 1332764
Summary: Review Request: gap-pkg-factint - Advanced methods for
factoring integers
Product: Fedora
Version: rawhide
Component: Package Review
Severity: medium
Priority: medium
Assignee: nobody(a)fedoraproject.org
Reporter: loganjerry(a)gmail.com
QA Contact: extras-qa(a)fedoraproject.org
CC: package-review(a)lists.fedoraproject.org
Spec URL: https://jjames.fedorapeople.org/gap-pkg-factint/gap-pkg-factint.spec
SRPM URL:
https://jjames.fedorapeople.org/gap-pkg-factint/gap-pkg-factint-1.5.3-1.f...
Fedora Account System Username: jjames
Description: FactInt 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.
--
You are receiving this mail because:
You are on the CC list for the bug.
You are always notified about changes to this product and component
8 years, 1 month