Math
LINKS
CONTACTS


 

Numeri di Fermat

 

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)

E' altresí possibile ottimizzare ulteriormente l'algoritmo definendo x=2j, con j dipendente da n.
Per implementare il test si procede nel modo seguente:

Sia

x2=A.2n+B 

Sia
A=q.k+r con 0 ≤ r < k;

In tal modo è possibile determinare rapidamente q ed r, quando k è un numero in singola precisione.
Quindi,
x2 = B-q+r.2n (mod k.2n+1)

il resto viene ottenuto semplicemente. (The Art Of Computer Programming, vol 2, Donald E. Knuth).


 

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

Sia
R=2Z/N (R=96bit indica l'accuratezza del calcolo)

 
L'algoritmo utilizzato per il calcolo sarà
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 < ∞.)

In fase di inizializzazione del programma eseguiamo alcune operazioni: sappiamo ad esempio che 3 divide k = 2(mod 3), 5 divide k=1(mod 5), 7 divide k=4(mod 7), etc.
E' quindi possibile utilizzare una efficiente versione del crivello di Eratostene per definire tali valori come compositi:

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.

e cosí via.

Paul Jobling ha indicato un algoritmo particolarmente efficiente per trovare i valori di k0 che soddisfino la condizione

k0. 2n+1=0 (mod p).

Eglii dichiara che
"Esiste un approccio indipendente dalla grandezza di p ed ha una efficienza che è O(log n): la sua velocità è fissa e indipendente dalla grandezza di p"


p | k0 .2n+1 ==> - k0 = 2-n (mod p)
2-n = (1/2)n, e 1/2 (mod p) = (p+1)/2.

Pertanto sarà sufficiente eseguire una esponenziazione sinistra-destra (left-to-right exponentiation) modulo p di (p+1) / 2 alla potenza di n.

Ad esempio, sia

n=13 e p=17:

Allora
(p+1)/2 = 9, e 913 (mod 17)

può essere ricavato tramite left-to-right exponentiation pari a 8. Quindi, se
k0 = - 8(mod 17), 

allora
17 | k0 .213+1. 

E infatti 17 divide (-8+17).213+1, (9+17).213+1, e cosí via


 

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,

in cui A, B, and C siano costanti (in alcuni casi è possibile porre A o C a zero).
I punti di questa curva ellittica sono le soluzioni dell'equazione, con uno o più punti definiti come "punti all'infinito" e denotati come 0.
Possiamo prendere il punto all'infinito come elemento identità: In tal modo, l'algoritmo per sommare due punti
(x1,y1), (x2,y2)
sulla curva è rappresentato da:
 

E questo è quanto riguarda le curve ellittiche, le soluzioni di

y^2 = x^3 + A*x^2 + B*x + C
e la legge del gruppo.
Possiamo fare in modo che le variabili x e y rappresentino numeri reali, razionalio persino complessi.
Ciò che rende interessante questi gruppi dal nostro punto di vista è il nostro modo di eseguire calcoli aritmetici moduo p quando p è un numero primo.
Ricordiamo infatti che la moltiplicazione modulo p comporta un gruppo di p-1 elementi. Eseguire somme sulle curve ellittiche modulo p porta ad un gruppo con p-1+r elementi, ove r rappresenta un intero qualsiasi, positivo o negativo, tra -2(√(p)) e +2√(p). Se p ha 30 cifre, anche p-1+r ha 30 cifre, e le prime 15 cifre sono uguali.
Noi non conosciamo p, il nostro fattore ignoto, ma possiamo comunque le nostre operazioni sul gruppo modulo N e calcolare il MCD alla fine nella speranza di trovarlo.
Le operazioni sui gruppi sono leggermente più complesse delle semplici moltiplicazioni modulo N, ma il metodo funziona allo stesso modo: scegliamo i limiti B1 e B2 ed un punto arbitrario sulla curva, calcoliamo il punto aggiunto a se stesso m volte nello stage 1, quindi prendiamo il risultato e lo calcoliamo aggiungendolo a se stesso q volte per ciascun primo q tra B1 e B2: a quel punto avremo trovato p se l'ordine del gruppo p-1+r sarà (B1,B2)-smooth.
Le operazioni sui gruppi sono corca 6 volte più complesse della semplice moltiplicazione, ma il vantaggio dell'ECM consiste nel fatto che, se non troviamo un fattore, possiamo cambiare il gruppo relativo anziché estendere i limiti della ricerca. Ricordiamo infatti che la forma di Weierstrass era
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.
L'unico svantaggio consiste nel fatto che, se p fosse un fattore di un numero di Mersenne 2^n - 1, noi sapremmo già che n è uno dei fattori di p-1. Nel caso dei numeri di Fermat, invece, non conosciamo alcun fattore di p-1+r, sebbene sia possibile scegliere una parametrizzazione che renda p-1+r che abbia un fattore relativamente piccolo. Per tale ragione, in questi casi il metodo di fattorizzazione P-1 offre un vantaggio qualora si ricerchino fattori di 20-25 cifre, ma via via che i fattori aumentano di peso, il metodo delle curve ellittiche guadagna un vantaggio significativo.

Copyright © MoreWare 2000 ... Last update: Sep. 2013