Discussion related to cado-nfs

[hermann@stamm-wilbrandt.de]

Thanks Greg for the detailed information.

And thanks Aurore for the simple instructions and the link to parameters 
selection.

I just leaned that under Ubuntu I was able to just do "sudo apt install 
gmp-ecm".
The executable is name ecm, not gmp-ecm after that install.
"man ecm" lists a wealth of options.

I did executed on AMD 7950X 16C/32T CPU, and ecm runs single threaded.
Single threaded computation reaches boost clock of 5.5GHz on that CPU.

I executed "... | time ecm ...", and each ecm run comleted in less than 
14 seconds.
AND the 12th run already factored in less than 3 minutes in total:

hermann@7950x:~$ head -64 gmp-ecm-6.txt | tail
Step 2 took 3765ms
GMP-ECM 7.0.5 [configured with GMP 6.3.0, --enable-asm-redc] [ECM]
Input number is 
122707855552185828468257427836864283300563571915184717192876562407609081222481009431414764530405548369855861509454229893234271790119941689194939718305389933643 
(159 digits)
Using B1=11000000, B2=35133391030, polynomial Dickson(12), 
sigma=1:710227113
Step 1 took 9356ms
Step 2 took 3768ms
********** Factor found in step 2: 
232199557797964905143390121842739619033812919
Found prime factor of 45 digits: 
232199557797964905143390121842739619033812919
Composite cofactor 
528458609981303297156242834999604689794730567149856574078164880268431329950637703635022461134725186623873710659597 
has 114 digits
GMP-ECM 7.0.5 [configured with GMP 6.3.0, --enable-asm-redc] [ECM]
hermann@7950x:~$


Regards,

Hermann.

On 2025-08-01 06:50, Aurore Guillevic wrote:
> Hi,
> The strategy to get a medium-size factor is to use GMP-ECM, with the
> parameters at
> https://members.loria.fr/PZimmermann/records/ecm/params.html
> The 6-th row gives:
> for i in `seq 1 5208` ; do echo
> 122707855552185828468257427836864283300563571915184717192876562407609081222481009431414764530405548369855861509454229893234271790119941689194939718305389933643
> | gmp-ecm 11000000 >> gmp-ecm-6.txt ; done
>
> Then grep the output file for `Factor found` and you will get the
> 45-digit factor, with another 114 digit composite cofactor. It takes
> some hours too (should be parallelized).
>
> A. Guillevic.
>
>
> On 7/31/25 08:48, hermann@stamm-wilbrandt.de wrote:
> > On 2025-07-30 23:54, Greg Marks wrote:
> > > In my experience, cado-nfs does work for non-semiprime input. In 2014
> > > I ran cado-nfs-2.0 to successfully factor the number
> > >
> > >
> > > 122707855552185828468257427836864283300563571915184717192876562407609081222481009431414764530405548369855861509454229893234271790119941689194939718305389933643. 
> > > The final cado-nfs output was the three prime factors, separated
> > > by spaces.  (I should say that I have not tested this on more recent
> > > versions of cado-nfs.)
> > >
> > > Incidentally, due to the relatively small size of the smallest prime
> > > factor of my number, ...
> > Thanks,
> >
> > "relatively small size" is bigger than I thought.
> > What is that prime factor?
> >
> > I did run this little GP script for more than 6 hours without factor 
> > found:
> >
> > hermann@7950x:~$ gp -q
> > ? 
> > o=2;forprime(p=3,,if(n%p==0,print(p);quit());if(p\10^8!=o\10^8,o=p;print1(".")))^C
> >   ***   user interrupt after 6h, 11min, 21,939 ms
> >
> > I counted the number of dots printed, and the smallest factor is not 
> > smaller than
> >
> > (128*114+16)*10^8 = 1460800000000
> >
> > Since single threaded, the AMD 7950X CPU did run a >5.5GHz ...
> >
> > Regards,
> >
> > Hermann.