GMP-ECM
GMP-ECM is a C implementation of the Elliptic Curve Method for factorizing integers. This library, gmp_ecm, provides Ruby bindings to this library.
The only prerequisite to using gmp_ecm is the gmp gem, which provides Ruby bindings to GMP, a prerequisite to using the GMP-ECM library. The gmp gem is required because most numbers (input integer, resultant factors, and various parameters) are passed around as GMP::Z
numbers.
Usage
The function of the gmp_ecm library is contained almost entirely in the GMP::Z#ecm_factor
method (binding to GMP-ECM's ecm_params
C function). So in order to start factorizing an integer, one must first initialize a GMP::Z
number, and then call #ecm_factor
against it. Just as in the C library, this method requires the B1
parameter to be passed in. Optionally, the user can pass in a second parameter, a Hash, or an ECMParams object. This will be passed to ecm_factor
as an ecm_params
struct.
Just now, not all of the fields in ecm_params
is available. The current list of supported parameters is in the docs.
Examples
Here is an example of repeatedly hitting up GMP-ECM for factors of 2**71 - 1
:
z = GMP::Z(2)**71 - 1 #=> 2361183241434822606847
z.ecm_factor(1_000_000) #=> [1, 2361183241434822606847]
z.ecm_factor(1_000_000) #=> [1, 11091312221959]
z.ecm_factor(1_000_000) #=> [1, 2361183241434822606847]
z.ecm_factor(1_000_000) #=> [1, 2361183241434822606847]
z.ecm_factor(1_000_000) #=> [1, 48639942238007]
GMP::Z#ecm_factor
returns a pair. The first element tells whether or not a factor was found:
- 1 means a factor was found in step 1.
- 2 means a factor was found in step 2.
- 0 means no factor was found.
- a negative value means an error occurred.
ECMParams
The ECMParams class is not implemented yet. For now, you can supply the ecm_params
parameter as a hash:
- Any value expected to be a
mpz_t
can be a Fixnum or aGMP::Z
. - Any value expected to be an
int
, includingunsigned
, must be a Fixnum. - Any value expected to be a double must be a ruby Float.
- Any value expected to be a
FILE*
must be a ruby IO object, typically created withFile.open('filename', 'w')
.
License
gmp_ecm is licensed under the Apache License, Version 2.0