GMP-ECM
This library, gmp_ecm, provides Ruby bindings to GMP-ECM, a C implementation of the Elliptic Curve Method for factorizing integers.
Install
If you're using Bundler, add gem 'gmp_ecm'
to your Gemfile.
If you just want to install with Rubygems, just gem install gmp_ecm
.
The only dependency is the gmp gem, which
provides Ruby bindings to GMP. The gmp gem is required because gmp_ecm passes
around most numbers (input integer, resultant factors, and various parameters)
as GMP::Z
numbers.
Usage
gmp_ecm essentially just provides 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
integer, and then call #ecm_factor
. Just as in the C library, this
method requires the B1
parameter as the first parameter. Optionally, you can
pass in a second parameter, the params, as either a Hash or an ECMParams object.
Not all of the fields in ecm_params
are available yet. 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')
.
Compatibility
gmp_ecm has been tested with, and should be compatible with:
- ruby 1.9.3, 2.0.0, 2.1.0-preview2
- GMP 5.0.5, 5.1.3
- GMP-ECM 6.3, 6.4.4
- Mac OS X 10.6
License
gmp_ecm is licensed under the Apache License, Version 2.0