mersenneforum.org  

Go Back   mersenneforum.org > Great Internet Mersenne Prime Search > Math

Reply
 
Thread Tools
Old 2003-01-24, 14:06   #1
jocelynl
 
Sep 2002

2·131 Posts
Default 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
jocelynl is offline   Reply With Quote
Old 2003-01-29, 14:51   #2
jocelynl
 
Sep 2002

2·131 Posts
Default

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.
jocelynl is offline   Reply With Quote
Old 2003-01-30, 00:29   #3
philmoore
 
philmoore's Avatar
 
"Phil"
Sep 2002
Tracktown, U.S.A.

2·13·43 Posts
Default 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
philmoore is offline   Reply With Quote
Old 2003-01-30, 00:51   #4
jocelynl
 
Sep 2002

2·131 Posts
Default

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.
jocelynl is offline   Reply With Quote
Old 2003-04-01, 17:56   #5
Joe O
 
Joe O's Avatar
 
Aug 2002

3·52·7 Posts
Default

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.
Joe O is offline   Reply With Quote
Old 2003-04-02, 17:07   #6
ewmayer
2ω=0
 
ewmayer's Avatar
 
Sep 2002
Rep├║blica de California

2·7·829 Posts
Default 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
ewmayer is offline   Reply With Quote
Old 2003-04-04, 15:28   #7
jocelynl
 
Sep 2002

2·131 Posts
Default

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?
jocelynl is offline   Reply With Quote
Old 2003-04-04, 18:40   #8
flava
 
flava's Avatar
 
Feb 2003

2·59 Posts
Default

I can test it for big numbers if you want. Just tell me what exactly shoud I code. Feel free to email me.
flava is offline   Reply With Quote
Old 2003-04-05, 19:00   #9
jocelynl
 
Sep 2002

2×131 Posts
Default

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.
jocelynl is offline   Reply With Quote
Old 2003-04-06, 12:49   #10
flava
 
flava's Avatar
 
Feb 2003

7616 Posts
Default

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?
flava is offline   Reply With Quote
Old 2003-04-07, 00:26   #11
jocelynl
 
Sep 2002

1000001102 Posts
Default

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.
jocelynl is offline   Reply With Quote
Reply

Thread Tools


All times are UTC. The time now is 17:04.

Fri Feb 26 17:04:49 UTC 2021 up 85 days, 13:16, 0 users, load averages: 2.21, 2.06, 1.88

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2021, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.