mersenneforum.org  

Go Back   mersenneforum.org > Factoring Projects > FermatSearch

Reply
 
Thread Tools
Old 2018-12-21, 07:30   #276
Gary
 
Gary's Avatar
 
"Gary"
Aug 2015
Texas

5×11 Posts
Default

Quote:
Originally Posted by ET_ View Post
December 19th, 2018
New Fermat factor from FermatSearch!
1075441212722595 . 2135+1 is a Factor of F132!!!
Peter Strasser discovered the seventh Fermat factor of this year! He used George Woltman's mmff program running on his home computer.
Congratulations to Peter from FermatSearch, for his second factor!
-
Congratulations Peter!!!

Last fiddled with by ET_ on 2018-12-21 at 08:42
Gary is offline   Reply With Quote
Old 2019-01-29, 10:31   #277
ET_
Banned
 
ET_'s Avatar
 
"Luigi"
Aug 2002
Team Italia

22·1,193 Posts
Default

January 28th, 2019
New Fermat factor from FermatSearch!
1527888802614951 . 2120+1 is a Factor of F118!!!
Peter Strasser discovered the first Fermat factor of this year! He used George Woltman's mmff program running on his home computer
Congratulations to Peter from FermatSearch, for his third factor!
ET_ is offline   Reply With Quote
Old 2019-01-29, 11:32   #278
feromant
 
"Roman"
Dec 2016
Everywhere

2·13 Posts
Default

Quote:
Originally Posted by ET_ View Post
January 28th, 2019
New Fermat factor from FermatSearch!
1527888802614951 . 2120+1 is a Factor of F118!!!
Peter Strasser discovered the first Fermat factor of this year! He used George Woltman's mmff program running on his home computer
Congratulations to Peter from FermatSearch, for his third factor!
Congratulations Peter!!!
feromant is offline   Reply With Quote
Old 2019-03-26, 04:15   #279
Gary
 
Gary's Avatar
 
"Gary"
Aug 2015
Texas

5×11 Posts
Default A new factor from FermatSearch

I would like to report the following new Fermat factor:

332,436,749 * 2^9865 + 1 divides F9863

This was discovered March 23 using pmfs on a HPE Superdome X system.

In each year from 2013 to 2018 no more than 7 new factors were found. So far in 2019 we are on the same pace: 2 factors in ~3 months. But who knows, maybe we will all get lucky and find many new factors. Might we match the 16 new factors discovered in 2012?
Gary is offline   Reply With Quote
Old 2019-03-29, 12:53   #280
mathwiz
 
Mar 2019

3×43 Posts
Default

Quote:
Originally Posted by Gary View Post
I would like to report the following new Fermat factor:

332,436,749 * 2^9865 + 1 divides F9863

This was discovered March 23 using pmfs on a HPE Superdome X system.

In each year from 2013 to 2018 no more than 7 new factors were found. So far in 2019 we are on the same pace: 2 factors in ~3 months. But who knows, maybe we will all get lucky and find many new factors. Might we match the 16 new factors discovered in 2012?
Nice find!

Curious which range(s) you have fully searched?
mathwiz is online now   Reply With Quote
Old 2019-03-31, 15:59   #281
Gary
 
Gary's Avatar
 
"Gary"
Aug 2015
Texas

5×11 Posts
Default

Quote:
Originally Posted by mathwiz View Post
Nice find!

Curious which range(s) you have fully searched?
Thanks mathwiz!

That depends on what you mean by "fully". For every range assigned to me in the fermatsearch.org Merge Tables, I have tested each Proth number (k * 2^n + 1) that survives the sieve to see if it divides any classic Fermat number. I have NOT tested to see if it divides any GFN or xGFN, since (as I understand it) that usually involves first testing to see if the Proth number is prime or PRP, which my program does not do.
Gary is offline   Reply With Quote
Old 2019-03-31, 17:23   #282
R. Gerbicz
 
R. Gerbicz's Avatar
 
"Robert Gerbicz"
Oct 2005
Hungary

58B16 Posts
Default

Quote:
Originally Posted by Gary View Post
I have NOT tested to see if it divides any GFN or xGFN, since (as I understand it) that usually involves first testing to see if the Proth number is prime or PRP, which my program does not do.
You could test basically in no time the generalized Fermat numbers (GFN), [and don't know what is xGFN, perhaps that is a^(2^n)+b^(2^n)], because you can make a cheap prp test if n is not that small:

what you are doing is:
let d=k*2^n+1 what survived the sieving process:
you calculate a(i)=2^(2^i) mod d, for say up to i<=n+30. (nobody saves the whole "a" array, only the last term).

for a cheap prp test you need only: res=2^(d-1)=a(n)^k mod d, ofcourse for a prp number you need res=1. For n~10000, k~1e30 the slowdown of the extra prp test is less than 0.5%, in general it is ~T*log(k)/n if the total running time was T.
R. Gerbicz is offline   Reply With Quote
Old 2019-04-02, 03:11   #283
Gary
 
Gary's Avatar
 
"Gary"
Aug 2015
Texas

5·11 Posts
Default

Quote:
Originally Posted by R. Gerbicz View Post
You could test basically in no time the generalized Fermat numbers (GFN), [and don't know what is xGFN, perhaps that is a^(2^n)+b^(2^n)], because you can make a cheap prp test if n is not that small:

what you are doing is:
let d=k*2^n+1 what survived the sieving process:
you calculate a(i)=2^(2^i) mod d, for say up to i<=n+30. (nobody saves the whole "a" array, only the last term).

for a cheap prp test you need only: res=2^(d-1)=a(n)^k mod d, ofcourse for a prp number you need res=1. For n~10000, k~1e30 the slowdown of the extra prp test is less than 0.5%, in general it is ~T*log(k)/n if the total running time was T.
Thanks for the suggestion Robert, and for walking me through the math. I am not a mathematician, so the explanation was very helpful. I will add this to the program the next time I am making changes.

It’s difficult to find a complete definition of all the GFN terminology on the web, but several researchers seem to be using the following:

Generalized Fermat Numbers (GFN or GF): GF(n,a) = a^(2^n) + 1
Extended Generalized Fermat Numbers (xGFN or xGF): xGF(n,a,b) = a^(2^n) + b^(2^n)

Someone please correct me if this is inaccurate.
Gary is offline   Reply With Quote
Old 2019-04-02, 09:48   #284
R. Gerbicz
 
R. Gerbicz's Avatar
 
"Robert Gerbicz"
Oct 2005
Hungary

3×11×43 Posts
Default

Quote:
Originally Posted by R. Gerbicz View Post
you calculate a(i)=2^(2^i) mod d, for say up to i<=n+30. (nobody saves the whole "a" array, only the last term).
That is excessive, for Fermat numbers you have to check up to i=n-2, because F_m has got divisors k*2^n+1 for n>=m+2.

Quote:
Originally Posted by Gary View Post
I will add this to the program the next time I am making changes.
Discovered later, but the real slowdown would be higher in your range, because you need also a^(2^i) mod a for a<=12 and i<n, if you want the vintage range for GFN,xGFN. If you are not obsessed with only Fermat factors, then the slowdown would be roughly 4 % with n~10000, sieving depth~50.

Don't see here a shortcut, only the "known" gain, let r(a)=a^(2^(n-30)) mod d, for prp we already know r(2), then
compute r(3),r(5),r(7),r(11) (so where the base is prime) and then with only one mulmod you can get the rest:
r(1)=1 (ofcourse)
r(4)=r(2)*r(2) mod d
r(6)=r(2)*r(3) mod d
r(8)=r(2)*r(4) mod d
r(9)=r(3)*r(3) mod d
r(10)=r(2)*r(5) mod d
r(12)=r(2)*r(6) mod d
[you need to do this in order, because you also reuse composite index, say r(4) for r(8)]
after that you know r(a) mod d for all a<=12.
Then for up to m=n-1 with only extra 12 (actually 11) mulmods per exponent, and in total 29*11 mulmods you
can get a^(2^i) mod d for a=1..12,i=n-30..n-1.

And at each i=(n-30)..(n-1) check to see if a^(2^i)+b(2^i) mod d = 0 for xGFN (basically checking only GFN gives no speedup).

ps. so you have to stop at i=n-1, and not at i=n-2 (like for Fermat number divisors).
R. Gerbicz is offline   Reply With Quote
Old 2019-12-11, 17:47   #285
ET_
Banned
 
ET_'s Avatar
 
"Luigi"
Aug 2002
Team Italia

22×1,193 Posts
Thumbs up New Fermat factor from Gary Gostin!

News from Gary Gostin!

I would like to report a new Fermat factor:



***** 15,249,465,809 * 2^2591 + 1 divides F2587



This was discovered running pmfs on an HPE Superdome X system.
Mankind has now discovered 350 factors of Fermat numbers! We should have a party!
ET_ is offline   Reply With Quote
Old 2019-12-12, 09:34   #286
LaurV
Romulan Interpreter
 
LaurV's Avatar
 
Jun 2011
Thailand

8,963 Posts
Default

Yeeee! Congrats!

LaurV is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
New Generalized Fermat factors Batalov Factoring 149 2017-02-20 12:06
Best case Fermat Factors yourskadhir Miscellaneous Math 5 2012-12-12 04:18
Generalized Fermat factors - why? siegert81 Factoring 1 2011-09-05 23:00
Weighted Fermat factors Top 20 Merfighters Factoring 0 2010-04-13 14:16
Fermat 12 factors already found? UberNumberGeek Factoring 6 2009-06-17 17:22

All times are UTC. The time now is 03:10.

Sat Dec 5 03:10:21 UTC 2020 up 1 day, 23:21, 0 users, load averages: 1.57, 1.51, 1.50

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2020, 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.