F22 factored!

unconnected · 2010-03-26, 17:56

Yesterday Buckle have found first factor of F22: 64658705994591851009055774868504577 !

Congratulations!

Batalov · 2010-03-26, 18:11

...cofactor status?

Andi47 · 2010-03-26, 18:16

Quote:

Originally Posted by unconnected

Yesterday Buckle have found first factor of F22: 64658705994591851009055774868504577 !

Congratulations!

Congrats!

This year seems to be a very good one for Fermat factors!!

rajula · 2010-03-26, 18:23

Congratulations to David Bessell!!

I am not that surprised that you were to one to find the factor with the massive amount of work you have done!

ET_ · 2010-03-26, 19:23

Quote:

Originally Posted by rajula

Congratulations to David Bessell!!

I am not that surprised that you were to one to find the factor with the massive amount of work you have done!

Tjos will be a wonderful year for Fermat factors and ECM!

Luigi

rogue · 2010-03-26, 19:40

Quote:

Originally Posted by unconnected

Yesterday Buckle have found first factor of F22: 64658705994591851009055774868504577 !

Congratulations!

What software was used to find the factor?

ewmayer · 2010-03-26, 20:01

Very nice ... note that it would have needed a p-1 with stage 1 bound just over 10^9 (specifically, >= 1045429261) and stage 2 bound >= 52795084261 to find this factor.

rekcahx · 2010-03-26, 20:45

Quote:

Originally Posted by Batalov

...cofactor status?

Just now, I'm runing some checks for cofactor, but I've to get some sleep.

henryzz · 2010-03-26, 21:14

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)

Mini-Geek · 2010-03-26, 21:28

Interesting idea. I don't know how useful it'd be in application, (especially for Mersenne numbers, where I know that you only do a small amount of TF after P-1, and individual candidates are quickly checked) but I see no reason why it wouldn't be correct.

To put it another way:
When P-1 factoring has proven that any potential k in k*2^n+1 or 2kp+1 must be smoother than certain bounds, you can skip checking k's that are smoother than those bounds.

R.D. Silverman · 2010-03-27, 00:21

Quote:

Originally Posted by Batalov

...cofactor status?

The title was "f22 factored", rather than just "f22 factor found", so I
presume that the cofactor is prime.

Either that, or the OP does not know the meaning of the word
"factored"

2010-03-26, 17:56	#1
unconnected May 2009 Russia, Moscow 2⁵·79 Posts	F22 factored! Yesterday Buckle have found first factor of F22: 64658705994591851009055774868504577 ! Congratulations!

2010-03-26, 21:28	#10
Mini-Geek Account Deleted "Tim Sorbera" Aug 2006 San Antonio, TX USA 1000010101011₂ Posts	Interesting idea. I don't know how useful it'd be in application, (especially for Mersenne numbers, where I know that you only do a small amount of TF after P-1, and individual candidates are quickly checked) but I see no reason why it wouldn't be correct. To put it another way: When P-1 factoring has proven that any potential k in k2^n+1 or 2kp+1 must be smoother than certain bounds, you can skip checking k's that are smoother than those bounds. Last fiddled with by Mini-Geek on 2010-03-26 at 21:33*

Similar Threads
Thread	Thread Starter	Forum	Replies	Last Post
RSA-220 factored	ixfd64	Factoring	2	2016-05-24 16:01
RSA-210 factored	ryanp	Factoring	6	2013-11-26 09:33
Factored vs. Completely factored	aketilander	Factoring	4	2012-08-08 18:09
F33 is factored !!	Raman	Factoring	4	2010-04-01 13:57
RSA-100 factored!	ewmayer	Math	5	2003-05-14 15:08

2010-03-26, 18:11	#2
Batalov "Serge" Mar 2008 Phi(4,2^7658614+1)/2 242A₁₆ Posts	...cofactor status?

2010-03-26, 18:23	#4
rajula "Tapio Rajala" Feb 2010 Finland 3²·5·7 Posts	Congratulations to David Bessell!! I am not that surprised that you were to one to find the factor with the massive amount of work you have done!

2010-03-26, 20:01	#7
ewmayer ∂²ω=0 Sep 2002 República de California 10110100111100₂ Posts	Very nice ... note that it would have needed a p-1 with stage 1 bound just over 10^9 (specifically, >= 1045429261) and stage 2 bound >= 52795084261 to find this factor.

2010-03-26, 21:14	#9
henryzz Just call me Henry "David" Sep 2007 Cambridge (GMT/BST) 2×2,897 Posts	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)