F22 factored!

[Merfighters]

Originally Posted by alpertron

Congratulations!!!

So in this year it was found the first known prime factor of F14 and a 7x-digit factor by ECM (demonstrating that the Playstation consoles are very useful for this task), which are very important discoveries in Computational Number Theory.

And the first known prime factor of F22, too.

[ccorn]

Originally Posted by Buckle

[Fri Mar 26 07:10:39 2010]
ECM found a factor in curve #1, stage #2
Sigma=8776953345765668, B1=1000000, B2=100000000.
UID: Buckle/NetworkMan, F22 has a factor: 64658705994591851009055774868504577, AID: C8CD1E588F7C58B514C621A586054979

David Bessell
(No relation to Uncle Friedrich)

Congratulations!

EC group order: 2^3 * 3 * 5 * 11 * 23 * 193 * 4451 * 862231 * 886069 * 898769 * 3610531

So B1 is very close. If I understand the papers on GMP-ECM correctly, the large B2 does not hinder the factor from being detected quite early in stage 2.

[Mini-Geek]

Originally Posted by ccorn

So B1 is very close. If I understand the papers on GMP-ECM correctly, the large B2 does not hinder the factor from being detected quite early in stage 2.

Actually, I'm almost positive that regardless of where in the B1 to B2 range the largest factor lies, it will only be found at the end of Step 2, when the GCD is run.

[akruppa]

It could be found earlier. Computing roots of the polynomials involves curve arithmetic in Weierstrass coordinates where inversions could fail. However, this is very unlikely to happen if the order of the end-of-stage-1 point isn't unusually small. Almost all "real world" factors found in ECM stage 2 are indeed found by the GCD at the end.

Alex

[henryzz]

Originally Posted by henryzz

I think I may have thought of a way to speed up the search for factors of fermat numbers. Currently when people search for fermat factors they test if numbers of the form k*2^n+1 are factors of the fermat number. They only try possible factors that are either proven prime or have at least been trial factored themselves in order to maximize throughput.

Now for my idea:
Since the 2^n can easily be taken care of specially in P-1, we know that if P-1 has been run on the fermat number then the k of any factor must have a factor(or maybe more than one) that evades the bounds of the P-1. Surely if we eliminated candidates that would have been already found with P-1 then that would eliminate a lot of the candidate factors from testing. Is anything like this done already or am I missing something?

If this idea works then maybe it could also be applied to the search for factors of mersenne numbers(factors of the form 2kp+1)

I have come to the conclusion that this method is nearly useless currently for fermat numbers as the largest fermat number we can run P-1 on is ~F30. Most of the Fermat numbers upto there have had sufficient ecm done on them to make this method useless.
I do think that the method could save some effort in factoring mersenne numbers. I will look into that further.

[jasonp]

Originally Posted by henryzz

I have come to the conclusion that this method is nearly useless currently for fermat numbers as the largest fermat number we can run P-1 on is ~F30. Most of the Fermat numbers upto there have had sufficient ecm done on them to make this method useless.
I do think that the method could save some effort in factoring mersenne numbers. I will look into that further.

I did manage to run P-1 stage 1 to a bound of 300k on F31. It unsurprisingly did not find a factor.

[Batalov]

Did you load the -go group order with tons of twos?

> echo "(2^4096+1)/114689" | ecm -pm1 100
GMP-ECM 6.2.3 [powered by GMP 4.3.0] [P-1]
Input number is (2^4096+1)/114689 (1228 digits)
Using B1=100, B2=270, polynomial x^1, x0=2755417790
Step 1 took 4ms
Step 2 took 32ms
#==> not found
 
> echo "(2^4096+1)/114689" | a.out -pm1 -go "2^15" 100
GMP-ECM 6.2.3 [powered by GMP 4.3.0] [P-1]
Input number is (2^4096+1)/114689 (1228 digits)
Using B1=100, B2=270, polynomial x^1, x0=354142156
Step 1 took 0ms
Step 2 took 32ms
********** Factor found in step 2: 63766529
Found probable prime factor of  8 digits: 63766529
Composite cofactor ((2^4096+1)/114689)/63766529 has 1221 digits
 
#2^15 is an overshot, ooops... going down to 2^13, found one, found another
 
> echo "(2^4096+1)/114689/63766529/26017793" | a.out -pm1 -go "2^13" 10000
GMP-ECM 6.2.3 [powered by GMP 4.3.0] [P-1]
Input number is (2^4096+1)/114689/63766529/26017793 (1213 digits)
Using B1=10000, B2=632208, polynomial x^1, x0=176100325
Step 1 took 40ms
Step 2 took 96ms
********** Factor found in step 2: 190274191361
Found probable prime factor of 12 digits: 190274191361
Composite cofactor ((2^4096+1)/114689/63766529/26017793)/190274191361 has 1202 digits

[jasonp]

Originally Posted by Batalov

Did you load the -go group order with tons of twos?

This didn't use GMP-ECM, it used custom code that I wrote which used integer Fast Galois Transforms. Stage 1 used a single pre-multiplied product of all the powers of primes less than 300k along with left-to-right binary exponentiation, so all that was needed was huge multiple-precision squarings and modular multiplies by 3.

The pre-multiplied product included 2^64 as a factor.

The core integer library was announced here, though the actual P-1 factoring code was never posted (it's both embarrassing and useless, though there's a forum thread I can't seem to find where I talked about it).

PS: found it

[henryzz]

Originally Posted by henryzz

I have come to the conclusion that this method is nearly useless currently for fermat numbers as the largest fermat number we can run P-1 on is ~F30. Most of the Fermat numbers upto there have had sufficient ecm done on them to make this method useless.
I do think that the method could save some effort in factoring mersenne numbers. I will look into that further.

I have run a test on using this test to filter candidates for tfing ~40M. I picked P-1 bounds that are good for that level but are reasonably common. The bounds were: B1: 455000 B2: 7735000.
I trial factored(slowly and very inefficiently!!) the ks for 10,000 factor candidates between two bit levels. The candidates I tried are reasonably near the beggining of each bit level.

Bit range       Candidates remaining out of 10000
69-70             6589                               
68-69             6363                               
67-68             6016                               
66-67             5755                               
65-66             5480                               
64-65             5175                               
63-64             4955                               
62-63             4688                               
61-62             4338                               
60-61             4075

The reduction isn't as much as I had hoped, but the idea may still have some merit. 1/3rd of the work will be saved for tfing from 69-70.
This method might appeal more to projects like Operation Billion Digits
The values of k are lower for them as the exponents are larger.
These results don't include any tf of the candidates themselves. How far does Prime95 do this?

Anyone got any opinions on whether this is worth doing? How much overhead would this add to tf?

Congratulations. I wish we'd known this back in 1993 when I spent a lot of time and effort proving F22 was composite - I may have picked another prime candidate instead!

Good work.