Questa pagina illustra parte della matematica e degli
algoritmi utilizzati per una efficiente ricerca dei fattori relativi ai numeri di Fermat.
I Numeri di Fermat hanno una forma matematica molto elegante:22m+1.
I primi 5 numeri F0=3, F1=5, F2=17, F3=257,
F4=65537 sono tutti primi. Avendo scoperto questo
particolare, Pierre de Fermat assunse che tutti i numeri di questo tipo
fossero primi. Aveva torto. Nel 1732 dopo quasi un secolo, Eulero
dimostrò elegantemente che F5 aveva un fattore: 641 e quindi
non era primo.
In 3 secoli sono stati trovati più di 300 divisori. E' stato provato che tutti i divisori dei
numeri di Fermat hanno la forma: k.2n+1, dove n≥ m+2.
Questo corollario è stato utilizzato per scoprire nuovi divisori dei
numeri di Fermat. A causa della rarefazione di tali divisori, e della
difficoltà nel calcolarli, la persona che scoprisse un nuovo fattore
ottiene di diritto un posto nella storia della Matematica.
Wilfrid Keller mantiene una lista accurata e dettagliata di tutti i fattori noti
di Fermat con i relativi scopritori.
Il mio sito FermatSearch gestsce dal 2000 la ricerca a livello mondiale di questi fattori.
1. Aritmetica modulare
Esiste un algoritmo semplice per valutare Fm=0 (mod k.2n+1):
Dato x=2, sarà sufficiente eseguire al più n-2 iterazioni del tipo:
x=x2 mod (k.2n+1)
Sia
x2=A.2n+B
A=q.k+r con 0 ≤ r < k;
x2 = B-q+r.2n (mod k.2n+1)
2. Algoritmo rapido per N = k.2n + 1 < 95 bit
Si inizia con l'algoritmo di calcolo:
Sia
kbit = log2k, e Z = kbit + n + 96
R=2Z/N (R=96bit indica l'accuratezza del calcolo)
x=x2 mod N
Sq=x2 (6 moltiplicazioni)
A=trunc(Sq*R) (6 moltiplicazioni, Sq con i bit più significativi)
B=A*N/2Z (6 moltiplucazioni)
x=Sq-B (bit meno significativi di Sq)
3. Crivello di Eratostene
L'efficienza dell'algoritmo di base non risulta eccezionale, tuttavia occorre osservare come non sia ncessario eseguire i calcoli per ciascun valore di k.
E' infatti possibile escludere un gran numero di valori di k utilizzando una versione specifica del Crivello di Eratostene.
Sia p un numero primo.
E' noto che
se p divide k.2n+1 allora p divide anche (k+j.p).2n+1 (0 ≤ j < ∞.)
Azzera tutti i bit di un vettore
3 divide k=2 (mod 3), quindi setta i bit 2, 5, 8, etc.
5 divide k=1 (mod 5), quindi setta i bit 1, 6, 11, etc
7 divide k=4 (mod 7), quindi setta i bit 4, 11, 18, etc.
Paul Jobling ha indicato un algoritmo particolarmente efficiente per trovare i valori di k0 che soddisfino la condizione
k0. 2n+1=0 (mod p).
p | k0 .2n+1 ==> - k0 = 2-n (mod p)
2-n = (1/2)n, e 1/2 (mod p) = (p+1)/2.
Ad esempio, sia
n=13 e p=17:
(p+1)/2 = 9, e 913 (mod 17)
k0 = - 8(mod 17),
17 | k0 .213+1.
4. Metodo delle curve ellittiche (ECM)
Cos'è una curva ellittica? "La maggior parte" delle equazioni di secondo grado in due variabili rappresentano sezioni coniche, ove con "la maggior parte", ci si riferisce a casi non degeneri come l'equazione y^2 - x^2 = 0 .
"La maggior parte" delle equazioni di terzo e quarto grado in due variabili possono essere associate ad una struttura che le trasforma in curve ellittiche. (Si possono qui escludere quei casi in cui il discriminante dell'equazione sia pari a zero).
Nei casi validi giungiamo ad un metodo per "sommare" punti sulla curva, vale a dire combinare due punti sulla curva per ottenerne un terzo in modo che la combinazione rispetti la regola associativa, esista un elemento identità, e ciascun elemento abbia un inverso.
Parlare di curve ellittiche in questi termini viene semplificato dal fatto che sia possibile modificare le variabili per trasformare l'equazione in ciò che è nota come la forma di Weierstrass:
y^2 = x^3 + A*x^2 + B*x + C,
(x1,y1), (x2,y2)sulla curva è rappresentato da:
y^2 = x^3 + A*x^2 + B*x + Cin tre punti o rappresenta una retta verticale. Due di tali punti sono rappresentati da
(x1,y1) e (x2,y2).Sia (x3,y3) il terzo punto.
y^2 = x^3 + A*x^2 + B*x + Crisulta pari in y, tale punto è anche sulla curva. Qualora la retta abbia pendenza vertcale, definire la somma come il punto O all'infinito. Tale caso si verificherà solo quando
(x2,y2) = (x1,-y1).
(x,y) + O = (x,y)e
O + O = Otermina la definizione).
E questo è quanto riguarda le curve ellittiche, le soluzioni di
y^2 = x^3 + A*x^2 + B*x + Ce la legge del gruppo.
y^2 = x^3 + A*x^2 + B*x + C.Per costanti differenti A, B, e C avremo curve differenti, vale a dire gruppi differenti e ordini differenti p-1+r per ciascun dato p. Se quindi un gruppo non fosse abbastanza smooth, possiamo sempre cambiare r cambiando in modo random A, B, e C, e tentare di nuovo.