ECM Factoring
 

Hi all,

I just made some test with ecm and P-1 Factoring. I found out that it is easier to set the value of b1 and b2 on ecm when you start from the residue of the P-1 factoring. for every curve. There is also no need to test odd and non-quadratic residue curves.


I came up with the formula.
Y=0.0023*x^3.8671

where y is the number of curve you need to do to find a factor of x digits

I found that it is at least 100 time faster than P-1

To test the algorythm, I did some work on the first few mersennes up to M523 and was able to find all factors in a few hours. I`m now working on the last composite factor of M673. I'have 3 slow 400mhz celeron working on it. After 3 days I'm at 52 digits. If a factor is found this would be a great asset to GIMPS. I'll keep you up to date of my progress.

More details?
 

I would be interested in learning more details of what you have been doing:

(Quote:)
>I found out that it is easier to set the value of b1 and b2 on ecm when you start from the residue of the P-1 factoring. for every curve. There is also no need to test odd and non-quadratic residue curves.

What do you mean, the residue of the P-1 factoring? Are you referring to the eight-digit number in hexadecimal that the program prints out at the end of a P-1 factoring attempt? (I thought that was just a checksum word, but I could be wrong.) And what do you mean, odd and non-quadratic residue curves? Are you referring to the randomly generated s=xxxxxxxxxxxxxxxx that the program uses to parametrize a curve? Maybe an example of how you choose b1 and b2 would also help clarify things.

Good luck with M673 - I've thrown about 5000 curves at it, but it appears to be a stubborn one!

Phil

Hi Phil,

Have a look How I do P-1

[code:1]B=3:Prime=1:N=2^M-1
Prime=nxtprm(prime)
B=modpow(B,Prime@M+1,N)
B=modpow(B,Prime,N)
[/code:1]
B will be random S in Regular Ecm. It will be modified to get 3 other usefull number for ECM.
I found out that some B`s are useless to evaluate.
Like odd B`s
also if kro(B,prime)<>1 --- prime is not a quadratic residue of B
and if prime@(m@12) is odd.

if it`s all ok then inc ncurve.
B1 of ecm = prime.
b2 = 40 * B1.
So the first few curves ar really fast.
you can find 20 digits factors with about 200 short curves.


I`ll provide you later the small modification I made to the ECM code provided in the UBasic package.

[quote="jocelynl"]I`ll provide you later the small modification I made to the ECM code provided in the UBasic package.[/quote]
I'd be interested as well!
Joe O.

Re: ECM Factoring
 

[quote="jocelynl"]
I just made some test with ecm and P-1 Factoring. I found out that it is easier to set the value of b1 and b2 on ecm when you start from the residue of the P-1 factoring. for every curve. There is also no need to test odd and non-quadratic residue curves.
[/quote]

It is not generally believed that p-1 residues are of any use in ECM. Could you be more specific about what you did? Also, which factors of M-numbers have you actually reproduced this way?

Thanks,
-Ernst

I no longer use this seive, I use a new one. I'm still working on it. My effort are base on a curve of m101, m137 and m149. the ratio of p-1 is 100. so i do 100 p-1 for 1 ecm curve and it turns out that i find a factor for m101 after 3 curves, m137 after 9 and m149 after 19. with a small formula one can skip some curves n=1:start=2,skip=4:do the curve and then n=n+start:start=start+skip, and so on. m101 is found after 1 curve, m137 after 3, m149 after 4.
But it's not regular p-1.
c=2:n=the number to factor
for x=1 to 100
c=nxtprm(c)
b=modpow(b,c,n)
if bit(0,b) then b=modpow(b,c+1,n)
next

inc curve
repeat above according to the formla

then do ecm

Since I use UBASIC I cannot verify that with larger numbers.
Is anyone willing to test this with giant numbers?

I can test it for big numbers if you want. Just tell me what exactly shoud I code. Feel free to email me.

Hi Flava,

First you can use the code for ecm already in George's prime95 or the new ecm5.0. but you need to modify the code that get the X0 from S, and set it to B, B1 in ecm is set to C and B2 is set to 100*C. You'll have to code the new p-1.

ubasic code
N is the number to factor
C=1:B=3:start=2:mincurve=1
*loop
for x=1 to 100:c=nxtprm(c):B=MODPOW(B,C,N)
if bit(0,B) then B=MODPOW(B,C+1,N)
next
inc curve
if curve<mincurve then *loop
mincurve+=start:start+=4
( this produce 1,3,9,19,33,51 etc...)

here call the ECM function.
in ecm function
X0=B
B1=C
B2=100*C

and goback to *loop

let me know if it's not clear.

OK, before going to big numbers I tried your formula for M101 to see if I get the same results. Here they are:

X0 = 894471243215116893725727102456
B1 = 1993, B2 = 199300

Did not find a factor using this courve though...
Did you get the same values?

for M101 I have
X0=101813800079087249628348230084
B1=1987
B2=198700

I think you have one to many.


Here is also m137
X0=124935694671771646882899378162749224513424
B1=6997
B2=699700

M149
X0=572818463534096044693751061241120940114166745
B1=16381
B2=1638100


Let me know if you succed.

OK, now I get the good X0 values but I have a stupid question...
I looked at the ECM code in Primes95 and I see we choose a random point (x,z) on the curve using a random seed S. I can't figure out the relation between a integer X0 and the point (x,z) ... :question:

Did you succed in finding a factor with these X0?

The X0 generated from the random seed S is always mod N. You have to run many curves to find the right key. With P-1 it is also mod N. but the greatest advantage is that if you run many P-1 and that the key is inside those runs, it generaly, is still there at the end of the runs. I don`t if anyone has a better explanation?

[quote="jocelynl"]Did you succed in finding a factor with these X0?

The X0 generated from the random seed S is always mod N. You have to run many curves to find the right key. With P-1 it is also mod N. but the greatest advantage is that if you run many P-1 and that the key is inside those runs, it generaly, is still there at the end of the runs. I don`t if anyone has a better explanation?[/quote]

No, I didn't. I still don't see who is X0. I read the ECM from Prime95 and I found a starting point (x,z), not a X0

Flava have a look at this code and try it in UBASIC copy paste. and add the 2 ubb files (asm code).
[url]http://www3.sympatico.ca/jlcd[/url]

It works :)

I used your code to write an ECM I can compile in C++
For M137 and M149 it finds the factors for the expected B1. For M101 a bit further than expected.

Good work Flava,

If you did the GCD at the end of the ecm curve it might be the reason for m101 being found farther then expected. But this is the way to increase the speed. GCD is time consuming. I can`t wait to see your result when you try higher numbers. Keep us posted of your good work.

Joss

Hey, you did the work, I just translated it so it can be used with GMP for big numbers.
Where can I find the factorisation status of Mersenne numbers so I can test it for more&bigger exponents?

Hi, flava!

Under [url=ftp://mersenne.org/gimps/]ftp://mersenne.org/gimps/[/url] you can find

a) decomp.zip
-> a program to read out data from the following databases and its c-code
b) factors.zip
-> a database with the smallest known factors of mersennes
c) nofactor.zip
-> a database with mersennes w/o known factor

Cheers,
Benjamin

[quote="flava"]Where can I find the factorisation status of Mersenne numbers so I can test it for more&bigger exponents?[/quote]

for a more complet status of smaller exponents (< 1200) check [url]http://www.cerias.purdue.edu/homes/ssw/cun/index.html[/url] and click on the main tables.

more factors
 

The most complete list of factors available on the web, to my knowledge is at Will Edgington's site:
http://www.garlic.com/~wedgingt/mersenne.html
Download one of the mersdata files (available in several zipped formats). The file lowM.txt contains all known factors (as of Will's last update) of incompletely factored Mersenne numbers with prime or composite exponents <= 200,000. The file factoredM.txt contains the factors for completely factored Mersenne numbers. Since George's web-pages only includes composite exponents <= 1200, I have used Will's tables to find a number of factors for Mersenne numbers with larger composite exponents. Note that these tables only list factors for the primitive part of each Mersenne number, so if you want all the known factors for M101909, for example, where 101909=101*1009, you also need to include the factors of M101 from factoredM.txt and the known factors of M1009 from lowM.txt. (Note that lowM.txt doesn't usually list the largest factor of each completely factored Mersenne number to save space.)

After some testing here are the results. It seems this method works quite well for smallish factors (up to 20 digits). All the factors listed below were found after at most 50 curves. Most of them after less than 20 curves. Big factors where not found, but I did not search for more than 100 curves.
Here are the tested numbers so far:

M101 7432339208719
M137 32032215596496435569
M149 86656268566282183151
M227 26986333437777017
M257 535006138814359
M293 not found
M331 16937389168607
M347 not found
M349 1779973928671
M421 614002928307599
M523 not found
M1123 777288435261989969
M33529 804697
M33581 not found
M33617 46566739039

Have you tried it with very large numbers, over 1,000,000?
It would be great to see if it works faster than trial factoring at these ranges, since trial doesn`t go higher than 21 digits.

Also could provide us with a small executable to test it on a large scale?

thanks much

Joss.

[quote="jocelynl"]Have you tried it with very large numbers, over 1,000,000?
It would be great to see if it works faster than trial factoring at these ranges, since trial doesn`t go higher than 21 digits.

Also could provide us with a small executable to test it on a large scale?

thanks much

Joss.[/quote]

Yes, I tried it for huge numbers (even over 10M). It is incredibly slow. In my opinion, the ECM algorithm is too complex for this kind of numbers. Even if you do the modulo the smart way, there are too many multiplications, InvModN's and GCD's. I think it is faster to do the LL for a 10M number than to do just a few ECM curves.
For numbers arround 1.000.000 it is still extremly slow. For numbers arround 250.000 it starts to work.
If you want the executable, no problem, I can send it to you (Windows 32 bit). I can send you the sources too (MSDEV 6.0 project)

yes it would be great to have the exec and the source I could make some test with the code itself. Here's my email jlcd@sympatico.ca

Thanks flava for the source. :D
I might be wrong but I think there`s something missing, and it`s the most important thing in the entire code.
Bload is a call to the asm code ecm1 and ecm2 without these, you will not succed in finding a factor on stage 2, 3 or 4. It would be like doing regular P-1.
these asm codes are on the site ecm1.asm and ecm2.asm
If your not able to decypher the asm, Yuji Kida was kind enough to add the regular UBasic code with the asm.


Joss.

Flava, here are the 2 subroutines ecm1 and ecm2
[code:1]11150 *ECM1_SUB
11160 TX=X:TZ=Z:UX=X:UZ=Z
11170 W3=TX+TZ:W4=TX-TZ
11180 for I%=1 to len(M#)-1
11190 W1=W3^2@N:W2=W4^2@N
11200 TX=W1*W2@N:TZ=(W1-W2)*(W2+AA*(W1-W2)@N)@N
11210 W3=TX+TZ:W4=TX-TZ
11220 if bit(I%,M#)
11230 :then W1=W4*(X+Z)@N:W2=W3*(X-Z)@N
11240 :X=(W1+W2)^2@N*UZ@N:Z=(W1-W2)^2@N*UX@N
11250 :else W1=W4*(UX+UZ)@N:W2=W3*(UX-UZ)@N
11260 :UX=(W1+W2)^2@N*Z@N:UZ=(W1-W2)^2@N*X@N
11270 next
11280 return
12000 *ECM2_SUB
12010 M#=(W4-V3(0)*W3+V2(0)*W2-V1(0)*W1+V0(0))@N
12020 for J%=1 to 11
12030 M#=M#*((W4-V3(J%)*W3+V2(J%)*W2-V1(J%)*W1+V0(J%))@N)@N
12040 next
12050 return
[/code:1]

Once you put does in the code you will notice the difference. Like night and day.

Joss

Nope, they are not missing, just blended in the code. Look closer at pecm.cpp :(

Hi Flava,

I didn`t get you program to work. I have no clue as to what to put in the boxes and what boxes to put it in. Any hint would be greatfully appreciated. :D

joss

Well... you can do LL tests (10X slower than Prime95 though) by entering a start exponent into the first box and a end exponent in the second box. The first time you will run LL's you will have two "strange" message boxes saying "before alloc" and "after alloc" and the program will be occupied for a few seconds (it makes a list of small primes and stores it on the disk).
You can do ECM's by entering the exponent in the first edit box and the number of curves in the second one, then press "pairs" (don't ask why the button is called pairs...). This will result in N p-1's and the ECM will be done on the last 20 of them. It sounds complicated but it's simple, for example...
you enter 101 and 20 => you do the first 20 ECM curves for 101
you enter 101 and 40 => you do the next 20 ECM curves for 101
.........
It was not made to be user friendly ;)
The other buttons are "undocumented" and not very usefull, ask about them if you are really curious.

Hi Flava,

Still doesn`t work. I have major Exception fault. :(
Am I missing files :question: What is prime.txt?
I tried to Rebuilt it with msdev6.0 and i get link errors in mscvrt.lib. :mad:
any clue as to what that is. :rolleyes:
What am I doing wrong :?

Joss

Hi Flava,

I Finally got it to work. :D :D
The problem was the computer. I was trying to get it to work on a K6.
Got it now on a Pentium and it works fine and compiles too. I don`t think msdev works with K6 :? I tried a few numbers and it seems to be a lot slower then UBasics :exclaim: I always though that gmp would be faster. Is your code using the full potential of gmp :question: Anyway thanks so much for giving well appreciated help with the code. ;)


Joss

Don't know... the gmp lib I compiled and use is optimised for K7 (Athlon or Duron) and much slower on P4 or P3. As for the code, I can send you a relatively optimised version of the ECM code, one that uses the special form of N (2^p-1) to calculate X mod N much faster. Another thing is the gmp routines PowModN and InvModN are NOT optimised for N=2^p-1, you could write faster routines to do that if you have the time. For the regular big number multiplications, gmp FFT works about 6X slower (on a K7) than the fastest code out there (Prime95 DWT-FFT).
Another thing, don't forget to compile a Release version, it moves faster ;)

Hi flava!! :D
Can you email me your newly compiled ecm-program :question: :question: :question: I'd like to test it for a while. ( I'm using a p4 2000MHz computer/ OS=win98)
Thanks andi314
mailto: mandelbrot@gmx.net

The program can be downloaded at http://membres.lycos.fr/gmk2000/mersenne/sfx.dat
After you download it, rename it as sfx.exe and launch it (it is a WinRar self extract archive).
The interface is not very friendly but to do ECM's, you enter a "from" and "to" (curves) and the exponent then push the "Ecm" button.
The code is at least two times slower on P4 than on AMD because :
1. it uses integer operations, which are way faster on AMD
2. the gmp lib was compiled for AMD K7

How do I know which parameters i should write into the first and second box???? :question:
Thanks andi314

You don't :D
You can try increasing values (like 1-10, 11-20 ...) or just guess ...