20080620, 09:17  #1 
Banned
"Luigi"
Aug 2002
Team Italia
2×7^{4} Posts 
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 
20080621, 00:07  #2 
Apr 2004
3×61 Posts 
what are you looking for??
Are you looking for primes, or factors??

20080621, 08:40  #3 
Banned
"Luigi"
Aug 2002
Team Italia
11302_{8} Posts 

20080622, 23:03  #4  
Mar 2003
New Zealand
2205_{8} Posts 
Quote:
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^(n1) + b^2^(n1), a^2^(n2) + b^2^(n2), etc. This takes 2n2 modular squarings (or n1 squarings if b=1), compared to n2 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 n1 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. 

20080623, 07:59  #5  
Banned
"Luigi"
Aug 2002
Team Italia
2·7^{4} Posts 
Quote:
Luigi 

Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
New Generalized Fermat factors  Batalov  Factoring  149  20170220 12:06 
Generalized Fermat numbers (in our case primes)  pepi37  Conjectures 'R Us  4  20151009 14:49 
Pseudoprimality Hypothesis for Specific Class of Generalized Fermat Numbers  primus  Miscellaneous Math  1  20150325 22:18 
Generalized Fermat factors  why?  siegert81  Factoring  1  20110905 23:00 
Generalized Fermat Prime Search?  pacionet  Lounge  3  20060125 15:40 