ECM Factoring

jocelynl · 2003-01-24, 14:06

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

jocelynl · 2003-01-29, 14:51

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.

philmoore · 2003-01-30, 00:29

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

jocelynl · 2003-01-30, 00:51

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.

Joe O · 2003-04-01, 17:56

Quote:

Originally Posted by jocelynl

I`ll 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.

ewmayer · 2003-04-02, 17:07

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

jocelynl · 2003-04-04, 15:28

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?

flava · 2003-04-04, 18:40

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

jocelynl · 2003-04-05, 19:00

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.

flava · 2003-04-06, 12:49

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?

jocelynl · 2003-04-07, 00:26

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.

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-30, 00:29	#3
philmoore "Phil" Sep 2002 Tracktown, U.S.A. 2137₈ 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-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. 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.

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

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 1110110₂ 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 100C. 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=100C and goback to *loop let me know if it's not clear.

2003-04-06, 12:49	#10
flava Feb 2003 166₈ 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 2×131 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.