mersenneforum.org > Math ECM Factoring
 Register FAQ Search Today's Posts Mark Forums Read

 2003-01-24, 14:06 #1 jocelynl   Sep 2002 2·131 Posts 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
 2003-01-29, 14:51 #2 jocelynl   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. Im 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.
 2003-01-30, 00:29 #3 philmoore     "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 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
 2003-01-30, 00:51 #4 jocelynl   Sep 2002 2·131 Posts 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 Bs are useless to evaluate. Like odd Bs also if kro(B,prime)<>1 --- prime is not a quadratic residue of B and if prime@(m@12) is odd. if its 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. Ill provide you later the small modification I made to the ECM code provided in the UBasic package.
2003-04-01, 17:56   #5
Joe O

Aug 2002

3·52·7 Posts

Quote:
 Originally Posted by jocelynl Ill provide you later the small modification I made to the ECM code provided in the UBasic package.
I'd be interested as well!
Joe O.

2003-04-02, 17:07   #6
ewmayer
2ω=0

Sep 2002
República de California

2·7·829 Posts
Re: ECM Factoring

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

 2003-04-04, 15:28 #7 jocelynl   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 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?
 2003-04-04, 18:40 #8 flava     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.
 2003-04-05, 19:00 #9 jocelynl   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 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.
 2003-04-06, 12:49 #10 flava     Feb 2003 7616 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?
 2003-04-07, 00:26 #11 jocelynl   Sep 2002 1000001102 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.