Generalized Fermat Numbers

[ET_]

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

[Harvey563]

Are you looking for primes, or factors??

[ET_]

Originally Posted by Harvey563

Are you looking for primes, or factors??

prime factors

Luigi

[geoff]

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.

[ET_]

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