20030124, 14:06  #1 
Sep 2002
2·131 Posts 
ECM Factoring
Hi all,
I just made some test with ecm and P1 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 P1 factoring. for every curve. There is also no need to test odd and nonquadratic 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 P1 
20030129, 14:51  #2 
Sep 2002
2·131 Posts 
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.

20030130, 00:29  #3 
"Phil"
Sep 2002
Tracktown, U.S.A.
2·13·43 Posts 
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 P1 factoring. for every curve. There is also no need to test odd and nonquadratic residue curves. What do you mean, the residue of the P1 factoring? Are you referring to the eightdigit number in hexadecimal that the program prints out at the end of a P1 factoring attempt? (I thought that was just a checksum word, but I could be wrong.) And what do you mean, odd and nonquadratic 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 
20030130, 00:51  #4 
Sep 2002
2·131 Posts 
Hi Phil,
Have a look How I do P1 [code:1]B=3:Prime=1:N=2^M1 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. 
20030401, 17:56  #5  
Aug 2002
3·5^{2}·7 Posts 
Quote:
Joe O. 

20030402, 17:07  #6  
∂^{2}ω=0
Sep 2002
República de California
2·7·829 Posts 
Re: ECM Factoring
Quote:
Thanks, Ernst 

20030404, 15:28  #7 
Sep 2002
2·131 Posts 
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 p1 is 100. so i do 100 p1 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 p1. 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? 
20030404, 18:40  #8 
Feb 2003
2·59 Posts 
I can test it for big numbers if you want. Just tell me what exactly shoud I code. Feel free to email me.

20030405, 19:00  #9 
Sep 2002
2×131 Posts 
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 p1. 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. 
20030406, 12:49  #10 
Feb 2003
76_{16} Posts 
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? 
20030407, 00:26  #11 
Sep 2002
100000110_{2} Posts 
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. 