Index of /g_w_reynolds/gfn
Name Last modified Size Description
![[DIR]](/icons/back.gif)
Parent Directory 29-Sep-2009 18:54 -
![[TXT]](/icons/text.gif)
CHANGES.txt 30-Dec-2008 15:39 1k
MD5SUM.txt 30-Dec-2008 15:39 1k
![[ ]](/icons/compressed.gif)
gfn-gmp.zip 30-Dec-2008 15:39 17k
gfn128.zip 30-Dec-2008 15:39 16k
gfn192.zip 30-Dec-2008 15:39 17k
gfn256.zip 30-Dec-2008 15:39 18k
gfn320.zip 30-Dec-2008 15:39 16k
gfn384.zip 30-Dec-2008 15:39 17k
gfn448.zip 30-Dec-2008 15:39 17k
gfn512.zip 30-Dec-2008 15:39 18k
gfn576.zip 30-Dec-2008 15:39 18k
gfn62.zip 07-Oct-2008 14:00 16k
gfn640.zip 30-Dec-2008 15:39 19k
gfn704.zip 30-Dec-2008 15:39 19k
gfn768.zip 30-Dec-2008 15:39 20k
gfn8.txt 25-Mar-2007 20:13 2k
This directory contains some programs that I am using to search for factors
k*2^n+1 of generalised Fermat numbers a^2^m + b^2^m, 2 <= a <= 12, b < a.
See the website http://www.rrz.uni-hamburg.de/RRZ/W.Keller/GFNfacs.html
for more information about this project.
I have developed these programs for my own use, and so they might not be
very user friendly or portable. The binaries require x86-64 Linux, but the
source should compile on x86-64 Mac without change.
There are currently 14 programs for different sized factors that use GMP
MPN functions and/or x86-64 assembly in the critical loop:
Archive Binary Factor range
-------------------------------------------------
gfn62.zip gfn62 11 < k*2^n+1 < 2^62
gfn64 11 < k*2^n+1 < 2^64
gfn128.zip gfn128 2^64 < k*2^n+1 < 2^128
gfn192.zip gfn192 2^128 < k*2^n+1 < 2^192
gfn256.zip gfn256 2^192 < k*2^n+1 < 2^256
gfn320.zip gfn320 2^256 < k*2^n+1 < 2^320
gfn384.zip gfn384 2^320 < k*2^n+1 < 2^384
gfn448.zip gfn448 2^384 < k*2^n+1 < 2^448
gfn512.zip gfn512 2^448 < k*2^n+1 < 2^512
gfn576.zip gfn576 2^512 < k*2^n+1 < 2^576
gfn640.zip gfn640 2^576 < k*2^n+1 < 2^640
gfn704.zip gfn704 2^640 < k*2^n+1 < 2^704
gfn768.zip gfn768 2^704 < k*2^n+1 < 2^768
There is also a slower but more portable version that uses GMP MPZ
functions in the critical loop. This one works on 32-bit machines (and
would probably work on Windows if I could get GMP to cross-compile):
Archive Binary Factor range
-------------------------------------------------
gfn-gmp.zip gfn-gmp-* 11 < k*2^n+1
For best results it may be necessary to adjust the values of SIEVE_BLOCK and
NUM_PRIMES in the source and recompile.
Command line arguments:
-----------------------
gfn k0 k1 n
will search for all factors k*2^n+1 with odd k in the range k0 <= k <= k1
that divide some GFN a^2^m + b^2^m with 1 <= b < a <= 12 (excluding some
redundant cases). Factors are appended to `factors.txt' as well as printed
to the screen.
Maths:
------
Since (a^2^m+b^2^m)*(a^2^(m-1)+b^2^(m-1))*...*(a^2+b^2)*(a+b)*(a-b)
= (a^2^(m+1)-b^2^(m+1)),
and all factors of a^2^m+b^2^m are of the form k*2^n+1 for some n > m,
then given particular a,b,k,n, k*2^n+1 divides a^2^m+b^2^m for some m only
if a^2^n = b^2^n (mod k*2^n+1).
Algorithm:
----------
Input k0,k1,n
For each odd k in k0 <= k <= k1
If k*2^n+1 is not divisible by a small prime
If 2^(k*2^n) = 1 (mod k*2^n+1)
{
For each q in {1,2,3,5,7,11}
A[q] <-- q^2^n (mod k*2^n+1)
For each r in {4,6,8,9,10,12}
{
Choose s,t<r such that s*t=r
A[r] <-- A[s]*A[t] (mod k*2^n+1)
}
For each pair A[i],A[j] where i>j, gcd(i,j)=1, (i,j)!=(4,1),(9,1),(9,4)
If A[i] = A[j]
For m from 1 to n-1
If i^2^m + j^2^m = 0 (mod k*2^n+1)
Report that k*2^n+1 divides a^2^m+b^2^m
}
Thanks to:
----------
Alexander Kruppa, for the 64-bit Montgomery multiplication code in his
program factorcyc.c, a copy of which is required to compile gfn64. I have
not included the code here, but there are instructions in gfn62.c explaining
which parts of factorcyc.c are needed.
Pierrick Gaudry, for the Montgomery multiplication code in GMP-ECM upon
which the modular multiplication routines in gfn128,gfn192,gfn256 are based.