## Elliptic curve factorization in ARIBAS

ARIBAS
has a several builtin functions for integer factorization:
`factor16`

does trial division by primes < 2**16
`rho_factorize`

uses the Pollard rho method. Its
runtime grows with the square root of the factor, so it
is useful to find (relatively) small prime factors, which
have not already been found by `factor16`

.
`cf_factorize`

and `qs_factorize`

use the continued fraction method and the quadratic sieve.
The runtime depends on the size of the number to be factored,
and not on the size of the factor. In general,
`qs_factorize`

is faster than `cf_factorize`

.

Since version 1.41, ARIBAS has also the elliptic curve
factorization
ec_factorize

as a builtin function. This is a probabilistic algorithm
using random elliptic curves. Its runtime depends
on the size of the factor. It can find larger factors
than `rho_factorize`

. Hence `ec_factorize`

can be used to factorize composite numbers which are too
big for `qs_factorize`

, but which have a
relatively small prime factor. One example
is the 8th Fermat number:
==> f8 := 2**256 + 1.
-: 115_79208_92373_16195_42357_09850_08687_90785_32699_84665_64056_40394_
57584_00791_31296_39937
==> ec_factorize(f8).
EC factorization, prime bound 3700, bigprime bound 33300
working .:.:.:.:.:.:.:.:.:.:.:.:.:.:.:.:.:.:.:.:.:.:.:.:.:.:.:.:.:.:.:.:.:.:.:.
:.:.:.:.:.:.:.:.:.:.:.:.:.:.:.:.:.:.:
factor found with curve parameter 912928 and bigprime 9343
-: 1_23892_63615_52897

`ec_factorize`

may be called with optional 2nd
and 3rd argument. The second argument is a pair
`(bound1, bound2)`

prescribing the prime bound
and bigprime bound for the factors of the order of the
randomly chosen elliptic curve, the third argument is
the maximal number of elliptic curves used. Example:
==> ec_factorize(f8,(10000,80000),200).
EC factorization, prime bound 10000, bigprime bound 80000
working .:.:.:.:.:.:.:.:
factor found with curve parameter 7149702 and bigprime 27541
-: 1_23892_63615_52897

One can exclude the execution of the big prime variation by
setting `bound2`

equal to 0.
==> ec_factorize(f8,(32000,0),200).
EC factorization with prime bound 32000
working ......................................
factor found with curve parameter 12160191 and prime bound 21504
-: 1_23892_63615_52897

Homepage of ARIBAS

Otto Forster 2004-08-16