This file explains how to factor a number with two non linear polynomials.
This is currently experimental in CADO-NFS.
Assume for example we want to factor the following 59-digit number:
n = 71641520761751435455133616475667090434063332228247871795429
with the two quadratics below (found by Thomas Prest using Montgomery's two
quadratics method, see polyselect/twoquadratics.c):
f = 215609964539787*x^2 + 75006949764904*x + 44337721223995
g = -205964131819700*x^2 - 71651332635517*x + 1199051061668898
skew = 1.29196058385
m = 14849204829709953721577291784724593124898329527333780861554
(m is the common root of f and g mod n.)
1) you first have to create a polynomial file:
$ cat c59.poly
n: 71641520761751435455133616475667090434063332228247871795429
skew: 1.29196058385
c0: 44337721223995
c1: 75006949764904
c2: 215609964539787
Y0: 1199051061668898
Y1: -71651332635517
Y2: -205964131819700
2) then create a parameter file:
- start with a copy of params/params.c60
- add the required parameters to run the python script outside
factor.sh: slaves.nrclients, tasks.execpath, tasks.workdir,
slaves.hostnames, slaves.scriptpath, slaves.basepath.
[ if you don't remember what they mean, this is normal; just start
factor.sh, and look at the parameter file it creates in order to
imitate ]
- add a line with the number you want to factor:
N = 71641520761751435455133616475667090434063332228247871795429
- Tell the script to use your polynomial file:
tasks.polyselect.admax = 0
tasks.polyselect.import = /my/wonderful/path/c59.poly
Here is an example of lines added at the end of params.c60:
slaves.nrclients = 2
tasks.execpath = ${HOME}/svn/cado-nfs/build/coing
tasks.workdir = /tmp/c59
slaves.hostnames = localhost
slaves.scriptpath = ${HOME}/svn/cado-nfs/scripts/cadofactor
slaves.basepath = /tmp/c59
N = 71641520761751435455133616475667090434063332228247871795429
tasks.polyselect.admax = 0
tasks.polyselect.import = /tmp/c59.poly
3) Run the script:
scripts/cadofactor/cadofactor.py params.c59
And this should end with the factors. Please note that this is still very
experimental.