mersenneforum.org  

Go Back   mersenneforum.org > Extra Stuff > Programming

Reply
 
Thread Tools
Old 2008-06-20, 09:17   #1
ET_
Banned
 
ET_'s Avatar
 
"Luigi"
Aug 2002
Team Italia

22·1,193 Posts
Default Generalized Fermat Numbers

Hi all,

I'm looking for some help needed to extend a program used to search Fermat numbers.

I'd like to add GFN search capabilities to it: any hints, caveats or efficiency issues?

Thank you!

Luigi
ET_ is offline   Reply With Quote
Old 2008-06-21, 00:07   #2
Harvey563
 
Harvey563's Avatar
 
Apr 2004

3×61 Posts
Question what are you looking for??

Are you looking for primes, or factors??


Harvey563 is offline   Reply With Quote
Old 2008-06-21, 08:40   #3
ET_
Banned
 
ET_'s Avatar
 
"Luigi"
Aug 2002
Team Italia

22·1,193 Posts
Default

Quote:
Originally Posted by Harvey563 View Post
Are you looking for primes, or factors??


prime factors

Luigi
ET_ is offline   Reply With Quote
Old 2008-06-22, 23:03   #4
geoff
 
geoff's Avatar
 
Mar 2003
New Zealand

22058 Posts
Default

Quote:
Originally Posted by ET_ View Post
I'm looking for some help needed to extend a program used to search Fermat numbers.

I'd like to add GFN search capabilities to it: any hints, caveats or efficiency issues?
Odd factors of GFNs a^2^m + b^2^m are of the form k*2^n+1, where n >= m+1.

To test whether k*2^n+1 divides the GFN a^2^m + b^2^m, compute X = a^2^n mod k*2^n+1 and Y = b^2^n mod k*2^n+1. If X=Y then k*2^n+1 divides one of a^2^(n-1) + b^2^(n-1), a^2^(n-2) + b^2^(n-2), etc. This takes 2n-2 modular squarings (or n-1 squarings if b=1), compared to n-2 squarings to check divisibility of the ordinary Fermat numbers 2^2^m+1.

It is much more efficient to check multiple GFNs at once: For example to check whether k*2^n+1 divides one of 2^2^m+1 or 3^2^m+1 takes n-1 squarings each to compute 2^2^n mod k*2^n+1 and 3^2^n mod k*2^n+1, but then you can check divisibility of 2^2^m + 3^2^m for free and it takes only one more modular multiplication each to check 6^2^m+1, 12^2^m+1, etc.

To check all 42 GFNs a^2^m + b^2^m with b < a <= 12 takes only a little more than 5 times the work of checking 2^2^m+1 alone. There is source code at http://www.geocities.com/g_w_reynolds/gfn/ that does this.
geoff is offline   Reply With Quote
Old 2008-06-23, 07:59   #5
ET_
Banned
 
ET_'s Avatar
 
"Luigi"
Aug 2002
Team Italia

22·1,193 Posts
Default

Quote:
Originally Posted by geoff View Post
Odd factors of GFNs a^2^m + b^2^m are of the form k*2^n+1, where n >= m+1.

To test whether k*2^n+1 divides the GFN a^2^m + b^2^m, compute X = a^2^n mod k*2^n+1 and Y = b^2^n mod k*2^n+1. If X=Y then k*2^n+1 divides one of a^2^(n-1) + b^2^(n-1), a^2^(n-2) + b^2^(n-2), etc. This takes 2n-2 modular squarings (or n-1 squarings if b=1), compared to n-2 squarings to check divisibility of the ordinary Fermat numbers 2^2^m+1.

It is much more efficient to check multiple GFNs at once: For example to check whether k*2^n+1 divides one of 2^2^m+1 or 3^2^m+1 takes n-1 squarings each to compute 2^2^n mod k*2^n+1 and 3^2^n mod k*2^n+1, but then you can check divisibility of 2^2^m + 3^2^m for free and it takes only one more modular multiplication each to check 6^2^m+1, 12^2^m+1, etc.

To check all 42 GFNs a^2^m + b^2^m with b < a <= 12 takes only a little more than 5 times the work of checking 2^2^m+1 alone. There is source code at http://www.geocities.com/g_w_reynolds/gfn/ that does this.
Thank you Geoff...

Luigi
ET_ 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
Generalized Fermat numbers (in our case primes) pepi37 Conjectures 'R Us 4 2015-10-09 14:49
Pseudoprimality Hypothesis for Specific Class of Generalized Fermat Numbers primus Miscellaneous Math 1 2015-03-25 22:18
Generalized Fermat factors - why? siegert81 Factoring 1 2011-09-05 23:00
Generalized Fermat Prime Search? pacionet Lounge 3 2006-01-25 15:40

All times are UTC. The time now is 23:53.

Sat Dec 5 23:53:53 UTC 2020 up 2 days, 20:05, 0 users, load averages: 1.78, 1.75, 1.73

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.