ECM Factoring - Page 2

flava · 2003-04-08, 09:29

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

jocelynl · 2003-04-09, 00:50

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?

flava · 2003-04-09, 19:21

Quote:

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

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

jocelynl · 2003-04-10, 01:16

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

flava · 2003-04-10, 23:05

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.

jocelynl · 2003-04-11, 00:48

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

flava · 2003-04-11, 09:07

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?

S80780 · 2003-04-11, 10:17

Hi, flava!

Under ftp://mersenne.org/gimps/ 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

smh · 2003-04-11, 11:22

Quote:

Originally Posted by flava

Where can I find the factorisation status of Mersenne numbers so I can test it for more&bigger exponents?

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

philmoore · 2003-04-11, 17:22

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

flava · 2003-04-15, 20:46

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

2003-04-11, 17:22	#21
philmoore "Phil" Sep 2002 Tracktown, U.S.A. 3×373 Posts	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.)

2003-04-08, 09:29	#12
flava Feb 2003 2×59 Posts	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) ...

2003-04-09, 00:50	#13
jocelynl Sep 2002 2×131 Posts	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?

2003-04-10, 01:16	#15
jocelynl Sep 2002 2×131 Posts	Flava have a look at this code and try it in UBASIC copy paste. and add the 2 ubb files (asm code). http://www3.sympatico.ca/jlcd

2003-04-10, 23:05	#16
flava Feb 2003 2×59 Posts	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.

2003-04-11, 00:48	#17
jocelynl Sep 2002 106₁₆ Posts	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

2003-04-11, 09:07	#18
flava Feb 2003 2·59 Posts	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?

2003-04-11, 10:17	#19
S80780 Jan 2003 far from M40 5³ Posts	Hi, flava! Under ftp://mersenne.org/gimps/ 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

2003-04-15, 20:46	#22
flava Feb 2003 2×59 Posts	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