ECM Factoring - Page 3

jocelynl · 2003-04-15, 23:29

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.

flava · 2003-04-16, 19:06

Quote:

Originally Posted by 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.

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)

jocelynl · 2003-04-16, 20:28

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

jocelynl · 2003-04-17, 01:01

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.

jocelynl · 2003-04-17, 01:29

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

flava · 2003-04-17, 05:45

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

jocelynl · 2003-04-17, 11:10

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

flava · 2003-04-17, 15:21

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.

jocelynl · 2003-04-18, 00:49

Hi Flava,

Still doesn`t work. I have major Exception fault. :(
Am I missing files

What is prime.txt?
I tried to Rebuilt it with msdev6.0 and i get link errors in mscvrt.lib.

any clue as to what that is.

What am I doing wrong :?

Joss

jocelynl · 2003-04-18, 15:29

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

I always though that gmp would be faster. Is your code using the full potential of gmp

Anyway thanks so much for giving well appreciated help with the code. ;)

Joss

flava · 2003-04-18, 21:46

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 ;)

2003-04-15, 23:29	#23
jocelynl Sep 2002 100000110₂ Posts	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.

2003-04-16, 20:28	#25
jocelynl Sep 2002 262₁₀ Posts	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

2003-04-17, 01:01	#26
jocelynl Sep 2002 2·131 Posts	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.

2003-04-17, 01:29	#27
jocelynl Sep 2002 2·131 Posts	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=W1W2@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@NUZ@N:Z=(W1-W2)^2@NUX@N 11250 :else W1=W4(UX+UZ)@N:W2=W3(UX-UZ)@N 11260 :UX=(W1+W2)^2@NZ@N:UZ=(W1-W2)^2@NX@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

2003-04-17, 05:45	#28
flava Feb 2003 2×59 Posts	Nope, they are not missing, just blended in the code. Look closer at pecm.cpp :(

2003-04-17, 11:10	#29
jocelynl Sep 2002 2×131 Posts	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

2003-04-17, 15:21	#30
flava Feb 2003 1110110₂ Posts	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.

2003-04-18, 00:49	#31
jocelynl Sep 2002 2×131 Posts	Hi Flava, Still doesn`t work. I have major Exception fault. :( Am I missing files What is prime.txt? I tried to Rebuilt it with msdev6.0 and i get link errors in mscvrt.lib. any clue as to what that is. What am I doing wrong :? Joss

2003-04-18, 15:29	#32
jocelynl Sep 2002 2·131 Posts	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 I always though that gmp would be faster. Is your code using the full potential of gmp Anyway thanks so much for giving well appreciated help with the code. ;) Joss

2003-04-18, 21:46	#33
flava Feb 2003 1110110₂ Posts	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 ;)