Elliptic curve factorization in ARIBAS

ARIBAS has a several builtin functions for integer factorization: Since version 1.41, ARIBAS has also the elliptic curve factorization
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_

    ==> 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