 mersenneforum.org Generalized Fermat Numbers
 Register FAQ Search Today's Posts Mark Forums Read 2008-06-20, 09:17 #1 ET_ Banned   "Luigi" Aug 2002 Team Italia 10010110011102 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   2008-06-21, 00:07 #2 Harvey563   Apr 2004 101101112 Posts what are you looking for?? Are you looking for primes, or factors??    2008-06-21, 08:40   #3
ET_
Banned

"Luigi"
Aug 2002
Team Italia

10010110011102 Posts Quote:
 Originally Posted by Harvey563 Are you looking for primes, or factors?? prime factors Luigi   2008-06-22, 23:03   #4
geoff

Mar 2003
New Zealand

13·89 Posts Quote:
 Originally Posted by ET_ 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.   2008-06-23, 07:59   #5
ET_
Banned

"Luigi"
Aug 2002
Team Italia

2×29×83 Posts Quote:
 Originally Posted by geoff 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  Thread Tools Show Printable Version Email this Page Similar Threads Thread Thread Starter Forum Replies Last Post Batalov Factoring 149 2017-02-20 12:06 pepi37 Conjectures 'R Us 4 2015-10-09 14:49 primus Miscellaneous Math 1 2015-03-25 22:18 siegert81 Factoring 1 2011-09-05 23:00 pacionet Lounge 3 2006-01-25 15:40

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

Tue May 18 10:31:13 UTC 2021 up 40 days, 5:12, 0 users, load averages: 2.19, 1.89, 1.64