UNIVERSITÀ DEGLI STUDI ROMA TRE FACOLTÀ DI SCIENZE M.F.N.

Sintesi della Tesi di Laurea in Matematica presentata da

Alessandro Cerquini

Il crivello del campo numerico

Relatore

Prof.ssa Francesca Tartarone

ANNO ACCADEMICO 2002 - 2003 Ottobre 2003

Classificazione AMS : 11A51, 11Y05, 94A60, Parole Chiave : TEORIA COMPUTAZIONALE DEI NUMERI, FATTO-RIZZAZIONE, CRITTOGRAFIA.

Teorema 0.0.1. [Teorema Fondamentale dell’Aritmetica] ([2, pag. 390]) Sia n ≠ 0 un intero. Allora n si può scrivere come prodotto di un numero finito di numeri primi come segue:

n = cp_{1} ⋯ p_{k},

dove c = ±1, i p_{i} sono interi primi positivi, e k ≥ 0. Questa espressione è unica a meno dell’ordine dei fattori primi.

La ricerca di un algoritmo per la determinazione di una tale fattorizzazione è uno storico problema della Matematica. Per esempio, ecco come Gauss, nel suo celebre Disquisitiones Arithmeticae (1801), sottolineava l’importanza di capire se un numero è composto e, in questo caso, di trovare la sua fattorizzazione: “Problema, numeros primos a compositis dignoscendi, hosque in factores suos primos resolvendi, ad gravissima ac utilissima totius arithmeticae pertinere, et geometrarum tum veterum tum recentiorum industriam ac sagacitatem occupavisse, tam notum est, ut de hac re copiose loqui superfluum foret … Praetereaque scientiae dignitas requirere videtur, ut omnia subsidia ad solutionem problematis tam elegantis ac celebris sedulo excolantur.”

Tuttavia, ancora oggi, tale ricerca non ha prodotto risultati soddisfacenti. Nel senso che non è ancora stato trovato un algoritmo con tempo di esecuzione polinomiale; cioè, un algoritmo il cui numero di passi necessari per terminare è una funzione polinomiale delle cifre dell’intero da fattorizzare.

Nonostante ciò, negli ultimi trent’anni sono stati fatti molti passi in avanti. Nel 1975, difatti, è stato presentato da J. Brillhart e M.A. Morrison, il Metodo delle frazioni continue (§1.2.1), ovvero il primo algoritmo per la fattorizzazione degli interi ad avere complessità sub-esponenziale (v. Appendice A). Tale algoritmo spostò il limite per il numero delle cifre decimali dell’intero da fattorizzare da 20 a 50. Da allora si è fatta molta strada. Difatti, successivamente il Crivello quadratico (§1.2.2), ideato da C. Pomerance nel 1982, e il Metodo delle curve ellittiche ([11, §7.4]), ideato da H. W. Lenstra Jr. nel 1985, hanno più che raddoppiato tale limite.

In questa trattazione descriveremo il Crivello del campo numerico, ovvero quello che, attualmente, è il più veloce algoritmo per la fattorizzazione di un generico intero . Tra i vari testi consultati, si è scelto di seguirne, in particolar modo, tre: [5], [11], [31].

Il crivello del campo numerico, in breve NFS (dall’inglese Number Field Sieve), è attualmente l’unico metodo in grado di fattorizzare interi con più di 150 cifre decimali senza fattori primi “piccoli”. L’idea chiave che sta alla base di questo algoritmo è l’utilizzo di numeri lisci (v. Definizione 1.2.16) in un opportuno anello numerico diverso da ℤ. Tale idea è stata proposta per la prima volta da John Pollard nel 1988. Da allora molti matematici hanno contribuito con vari suggerimenti allo sviluppo dell’algoritmo.

L’NFS è, senza dubbio, un algoritmo molto complicato. Strutturalmente è simile al crivello quadratico (potremmo quasi dire che ne è una generalizzazione), ma, a differenza di quest’ultimo, fa uso di molti parametri da ottimizzare e, inoltre, poggia su una teoria molto meno elementare. Difatti, per dimostrarne la validità (così come per comprenderne il funzionamento) avremo bisogno di richiamare alcuni risultati di Algebra Commutativa e Teoria Algebrica dei Numeri.

Da un punto di vista più pratico, possiamo aggiungere che per essere eseguito su un computer, l’NFS necessita (per numeri molto grandi) della capacità di gestire grosse quantità di dati, e di una potenza di calcolo enorme. Insomma, implementarlo con successo sul proprio computer di casa non è davvero un’operazione semplice! Per raggiungere i risultati di seguito citati sono stati necessari, a volte, centinaia di computer e la collaborazione di decine di persone.

Tutte le ultime fattorizzazioni record ottenute portano la firma del crivello del campo numerico. Tra queste, citiamo la fattorizzazione di RSA-160 (2003), la fattorizzazione del numero di Cunningham 2^{773} + 1 (2000) e la fattorizzazione di F_{9}, il nono numero di Fermat, (1990) (v. capitolo 4). Al contrario del primo numero, gli ultimi due hanno una forma speciale che può essere sfruttata dall’algoritmo.

Prima del crivello del campo numerico, il miglior algoritmo per la fattorizzazione di un generico intero era (come già detto) il crivello quadratico, il cui tempo di esecuzione congetturato è, per n che va all’infinito, L_{n}[1/2, 1+o(1)] dove :

L_{n}[u, v] := exp (v( log n)^{u}( log log n)^{1−u}).

Per l’NFS, invece, il tempo di esecuzione congetturato è

L_{n}[1/3, (64/9)^{1/3} + o(1)].

L’esponente u = 1/3 è la principale novità dell’NFS. Difatti, come abbiamo visto sopra, nel caso del crivello quadratico si ha u = 1/2; ma non solo, anche nel metodo delle frazioni continue e nel metodo delle curve ellittiche si ha u = 1/2. Addirittura, per molto tempo, si è creduto che quest’ultimo valore fosse un limite insuperabile per la complessità degli algoritmi di fattorizzazione. Al crivello del campo numerico va anche, quindi, il merito di aver confutato questa “poco stimolante” congettura. Di seguito descriviamo brevemente le caratteristiche principali dell’NFS.

Introduzione al metodo

Sia n un intero dispari e diverso dalla potenza di un numero primo. L’NFS riesce a calcolare un fattore proprio di n. Più precisamente, l’NFS trova una coppia (u, v) ∈ U(ℤ_{n}) × U(ℤ_{n}) tale che:

u^{2} ≡ v^{2} (mod n),

con u ≢ ±v (mod n). In questo caso, MCD(u − v, n) (così come MCD(u + v, n)) è un fattore proprio di n (se per assurdo non lo fosse si giungerebbe alla contraddizione che u ≡ v (mod n) oppure u ≡ −v (mod n)). In realtà, la ricerca di tale coppia (u, v) è realizzata senza tenere conto della condizione u ≢ ±v (mod n). Infatti, si ha che più della metà delle coppie (u, v) tali che u^{2} ≡ v^{2} (mod n), verificano anche la condizione u ≢ ±v (mod n), la quale risulta quindi “trascurabile” (v. Corollario 1.2.2).

Crivello quadratico

Ricordiamo che se B ∈ ℝ, allora si dice che x ∈ ℤ è B-liscio se ogni suo divisore primo è minore o uguale di B. Anche nell’algoritmo del crivello quadratico si fattorizza n trovando una coppia (u, v) con le proprietà sopra descritte. Più precisamente l’algoritmo del crivello quadratico determina un sottoinsieme {x_{1}, …, x_{n}} ⊂ ℤ tale che ∏_{i=1}^{n}(x_{i}^{2} − n) è un quadrato in ℤ. In questo caso, basta prendere u := \sqrt{∏_{i=1}^{n}(x_{i}^{2} − n)} e v := ∏_{i=1}^{n} x_{i}, per avere la coppia (u, v) cercata. Come segue dal Lemma 1.2.17, per trovare tale insieme {x_{1}, …, x_{n}} è sufficiente avere a disposizione un’opportuna quantità di interi x_{i} tali che (x_{i}^{2} − n) è B-liscio.

Lemma 1.2.17. Sia B ∈ ℝ. Se m_{1}, m_{2}, …, m_{k} sono interi positivi B-lisci e se k > π(B), dove π(B) è il numero dei primi nell’intervallo [2, B], allora esistono m_{i_{1}}, m_{i_{2}}, …, m_{i_{t}} con 1 ≤ i_{1} < i_{2} < … < i_{t} ≤ k tali che il loro prodotto è un quadrato.

La ricerca degli x ∈ [a, b] ⊂ ℤ (con a, b interi qualsiasi) tali che x^{2} − n è B-liscio può essere portata a termine velocemente per mezzo di un crivello. Nell’NFS si segue una strategia simile a quella appena vista, ma si sostituisce ℤ con un opportuno anello numerico.

Anelli numerici

Diremo che un campo K è numerico se è un’estensione finita di ℚ. Inoltre, diremo che un anello R è numerico se è un sottoanello di un campo numerico. Sia f ∈ ℤ[X] un polinomio monico irriducibile di grado d ≥ 1. Sia α ∈ ℂ una radice di f. Allora definiamo ℤ[α] nel modo seguente:

ℤ[α] := {p(α) : p(X) ∈ ℤ[X]}.

Si verifica facilmente che ℤ[α] è un anello. Naturalmente ℤ[α] è contenuto nel campo ℚ(α). Quindi, dato che ℚ(α) è un’estensione di grado d di ℚ, e cioè è un campo numerico, possiamo concludere che ℤ[α] è un anello numerico. Gli anelli numerici che vengono utilizzati nel crivello del campo numerico sono del tipo di ℤ[α].

Definizione 2.3.13. Sia R un anello numerico e sia K il campo dei quozienti di R. Allora diremo che R è un ordine in K se è un sottoanello (con unità) dell’anello degli interi O_{K} tale che l’indice del gruppo additivo di R nel gruppo additivo di O_{K} è finito.

ℤ[α], essendo un’estensione intera di ℤ, è contenuto in O_{ℚ(α)}. Inoltre, si ha che l’indice [O : ℤ[α]] è finito (v. Proposizione 2.4.7). Quindi ℤ[α] è un ordine in ℚ(α).

Proposizione 2.4.7. Sia f ∈ ℤ[X] monico e irriducibile di grado d, sia α ∈ ℂ una radice di f e sia O l’anello degli interi di ℚ(α). Allora abbiamo che

Δ(f) = [O : ℤ[α]]^{2} · Δ,

dove Δ(f) è il discriminante di f e Δ è il discriminante di ℚ(α).

La strategia

Sia m ∈ ℤ tale che f(m) ≡ 0 (mod n), allora l’applicazione

\begin{aligned}ϕ : & ℤ[α] & ⟶ & ℤ_{n} \\ & α & ⟼ & m (mod n) \end{aligned}

è un omomorfismo di anelli. Quindi se p(X) ∈ ℤ[X] è tale che:

\begin{matrix}p(α) = γ^{2} & in ℤ[α] \\ p(m) = y^{2} & in ℤ \end{matrix}

allora (u, v) := (ϕ(γ), y) è la coppia cercata. Difatti, dato che ϕ è un omomorfismo si ha che:

ϕ(γ)^{2} ≡ ϕ(γ^{2}) = ϕ(p(α)) ≡ p(ϕ(α)) = p(m) = y^{2} (mod n).

Inizializzazione

Il primo punto da affrontare è la determinazione di f ∈ ℤ[X] monico e irriducibile per cui esista m ∈ ℤ tale che f(m) ≡ 0 (mod n). Si procede nel modo seguente: si sceglie d ∈ ℤ grado del polinomio f, si pone m = ⌊n^{1/d}⌋ e si scrive n in base m:

n = c_{s}m^{s} + c_{s−1}m^{s−1} + … + c_{0}.

Ponendo f = c_{s}x^{s} + c_{s−1}x^{s−1} + … + c_{0}, abbiamo trovato un polinomio tale che f(m) = n ≡ 0 (mod n). Spesso ci si riferisce al metodo sopra descritto con il nome di “metodo della base-m”.

Lemma 3.3.1. Sia n, d ∈ ℤ, con d > 1, e sia m = ⌊n^{1/d}⌋. Se n > \frac{2}{(2^{1/d}−1)^{d}} allora n < 2m^{d}.

Se n e d rispettano le ipotesi del lemma, allora f è un polinomio monico di grado d. Ciò è sufficiente per quanto concerne la determinazione di f; infatti, se f è riducibile, diciamo f = gh, allora abbiamo già trovato una fattorizzazione non banale di n, precisamente n = g(m)h(m), e l’algoritmo termina, in caso contrario abbiamo trovato il polinomio f monico e irriducibile che cercavamo.

Il crivello

Ma in che modo determinare p(X) ∈ ℤ[X] tale che p(α) è un quadrato in ℤ[α] e p(m) è un quadrato in ℤ? Risulta conveniente lavorare con polinomi del tipo:

q(X) := ∏_{(a,b)∈S}(a − bX)

in cui a e b sono interi coprimi ed S è un opportuno sottoinsieme di ℤ × ℤ. Infatti, in questo caso, la verifica che q(m) sia un quadrato in ℤ è equivalente alla ricerca di elementi (a − bm) che sono B-lisci (come è stato mostrato per il crivello quadratico); e inoltre, la verifica che q(α) sia un quadrato in ℤ[α] è facilitata dalla presenza degli elementi del tipo di (a − bα) con a e b interi coprimi. Osservazione 2.4.10. Sia K = ℚ(α) un campo numerico di grado d su ℚ e sia (a − bα), con a, b ∈ ℚ, un elemento di K. Se f = ∑_{i=0}^{d} c_{i}X^{i} ∈ ℚ[X] è il polinomio minimo di α (che per definizione è monico), allora si ha che:

N(a − bα) = b^{d}f(a/b).

Dove N(a − bα) è la norma di (a − bα) (v. §2.4). È, quindi, possibile collezionare coppie (a, b) di interi coprimi tali che sia (a − bm) che N(a − bα) sono B-lisci. Per fare ciò basta setacciare, come nel crivello quadratico, l’insieme T definito come segue:

T := {(a, b) ∈ ℤ × ℤ : 0 < |a| < M_{2}, 0 < b < M_{1}}, dove M_{1} ed M_{2} sono opportuni interi.

Primi che dividono a-bα

Da ora in avanti con primo di ℤ[α] intenderemo un ideale primo 𝔭 di ℤ[α] diverso da zero. Sia 𝔭 un primo di ℤ[α]; allora F = ℤ[α]/𝔭 è un campo finito (v. Teorema 2.3.16 e Proposizione 2.3.19).

Definizione 2.7.1. Sia 𝔭 un primo di ℤ[α]. Allora diremo che n è il grado di 𝔭 se F = ℤ[α]/𝔭 è un’estensione di grado n del suo sottocampo fondamentale.

Proposizione 2.7.2. Sia 𝔭 un primo di ℤ[α]. Allora 𝔭 è un primo di grado 1 di ℤ[α] se e soltanto se esiste un omomorfismo π : ℤ[α] → 𝔽_{p} tale che ker π = 𝔭.

Poiché π è completamente definito una volta dati p ed r_{p} = π(α), ha senso utilizzare la notazione

𝔭 ∼ (p, r_{p})

per indicare che 𝔭 = ker π. Cioè 𝔭 di grado 1 è univocamente determinato dalla coppia (p, r_{p}) dove p è un numero primo e r_{p} è una radice di f (mod p).

Definizione 2.7.3. Sia x ∈ ℤ[α]. Allora diremo che un primo 𝔭 di ℤ[α] divide x se x ∈ 𝔭.

Proposizione 2.7.5. Sia 𝔭 un primo di ℤ[α] e sia a − bα un elemento di ℤ[α] tale che a e b sono interi coprimi. Allora 𝔭 divide a − bα se e soltanto se 𝔭 è un primo di grado 1, diciamo 𝔭 ∼ (p, r_{p}), con r_{p} ≡ ab^{−1} (mod p) e con p intero primo che divide N(a − bα).

Osservazione 2.7.6. Dalla precedente Proposizione segue anche che se p | N(a − bα) allora (p, ab^{−1} (mod p)) è l’unico primo di ℤ[α] che divide p e (a − bα). C’è, quindi, una corrispondenza biunivoca tra i primi che dividono N(a − bα) e i primi che dividono (a − bα).

Dunque dalla fattorizzazione di N(a−bα) è possibile determinare quali primi di ℤ[α] dividono (a − bα). Esempio 2.7.8. Cerchiamo i primi che dividono 7 − 22i in ℤ[i]. Poiché:

N(7 − 22i) = 7^{2} + 22^{2} = 533 = 13 · 41

ci sono solo due primi, 𝔭_{1} e 𝔭_{2}, che dividono 7 − 22i. Precisamente:

𝔭_{1} = (13, 7 · 22^{−1} (mod 13)) = (13, 8)
𝔭_{2} = (41, 7 · 22^{−1} (mod 41)) = (41, 32).

Definizione 2.7.9. Siano a, b interi coprimi, sia p un intero primo e sia r_{p} una radice di f (mod p). Allora si definisce l’applicazione e_{p,r_{p}}(a − bα) nel modo seguente:

e_{p,r_{p}}(a − bα) = \{ \begin{matrix}ord_{p}(N(a − bα)) & se a ≡ br_{p} (mod p) \\ 0 & altrimenti. \end{matrix}

Indichiamo con B_{1} l’insieme degli interi primi minori di B e con B_{2} l’insieme dei primi (p, r_{p}) di grado 1 di ℤ[α] tali che p ≤ B (insiemi chiamati base di fattori). Cioè:

B_{1} := {p ∈ ℤ : p è primo , p ≤ B} = {p_{1}, …, p_{π(B)}};
B_{2} = {𝔭 ∈ Spec(ℤ[α]) : 𝔭 ∼ (p, r_{p}), p ∈ B_{1}, f(r_{p}) ≡ 0 (mod p)}.

Allora è possibile associare ad ogni coppia (a, b), tale che (a − bm) e (a − bα) sono B-lisci, un vettore ottenuto come concatenazione di tre vettori. Precisamente definiamo v⃗(a − bα) come la concatenazione dei tre vettore v⃗_{1}, v⃗_{2} e v⃗_{3}. Dove:

• v⃗_{1} è un vettore con un unica coordinata posta uguale ad 1 se (a − bm) è negativo e posta uguale a zero se (a − bm) è positivo; • v⃗_{2} := (ord_{p_{1}}(a − bm), …, ord_{p_{#B_{1}}}(a − bm)), dove p_{i} ∈ B_{1};

• v⃗_{3} := (e_{𝔭_{1}}(a − bα), …, e_{𝔭_{#B_{2}}}(a − bα)), dove 𝔭_{i} ∈ B_{2};

Dunque, una volta determinate 1 + #B_{1} + #B_{2} + 1 relazioni, segue dalla dimostrazione del Lemma 1.2.17 che è possibile trovare S ⊂ T tale che :

∏_{(a,b)∈S}(a − bm) è un quadrato in ℤ;

∑_{(a,b)∈S} e_{p,r_{p}}(a − bα) ≡ 0 (mod 2) ∀ (p, r_{p}) ⊂ ℤ[α].

L’applicazione e_{p,r_{p}} può essere estesa ad un omomorfismo di gruppi su tutto ℚ(α)^{∗} (dove ℚ(α)^{∗} := ℚ(α) \ {0} è il gruppo moltiplicativo di ℚ(α)).

L’omomorfismo l_{𝔭}

Proposizione 2.8.2. Sia R un ordine in un campo numerico K. Allora per ogni 𝔭 ∈ Spec(R), esiste, ed è unico, un omomorfismo di gruppi l_{𝔭,R} : K^{∗} → ℤ tale che:

1)  l_{𝔭,R}(β) ≥ 0  ∀ β ∈ R, β ≠ 0
2)  l_{𝔭,R}(β) > 0 ⟺ β ∈ 𝔭  ∀ β ∈ R, β ≠ 0
3) l_{𝔭,R}(β) ≠ 0 per un numero finito di primi 𝔭 ∀ β ∈ K^{∗}
4)  ∏_{𝔭⊂R}N(𝔭)^{l_{𝔭,R}(β)} =| N(β) |  ∀ β ∈ K^{∗}.

Quando R = ℤ[α] scriveremo semplicemente l_{𝔭} al posto di l_{𝔭,ℤ[α]}. Ebbene, si ha che l_{𝔭} estende e_{p,r_{p}} (v. Corollario 2.8.4). Dunque:

∑_{(a,b)∈S} e_{p,r_{p}}(a − bα) ≡ 0 (mod 2) ⇒ ∑_{(a,b)∈S} l_{𝔭}(a − bα) ≡ 0 (mod 2) ⇒

l_{𝔭}( ∏_{(a,b)∈S}(a − bα)) ≡ 0 (mod 2) ⇒ l_{𝔭}(q(α)) ≡ 0 (mod 2)

Cioè q(α) ∈ V := {x ∈ ℚ(α)^{∗} : l_{𝔭}(x) ≡ 0 (mod 2) ∀ 𝔭 ∈ ℤ[α]} (si verifica che V è un sottogruppo di ℚ(α)^{∗}).

Punti critici

Ci sono eventuali 4 ostacoli da superare affinché, dato q(α) ∈ V, si possa determinare un quadrato in ℤ[α].

1. ℤ[α] potrebbe non essere l’anello degli interi O di ℚ(α). In questo caso, ℤ[α] non è un Dominio di Dedekind, e quindi non vale il Teorema sulla fattorizzazione unica degli ideali (Teo. 2.5.14). Dunque, anche se l_{𝔭}(q(α)) ≡ 0 (mod 2) ∀ 𝔭 ∈ Spec(ℤ[α]) non si ha che q(α)O è il quadrato di un ideale.

2. Seppure q(α)O fosse il quadrato di un qualche ideale 𝔠, quest’ultimo potrebbe non essere principale.

3. Anche se q(α)O fosse il quadrato di un qualche ideale principale γO, avremmo solo che q(α) = uγ^{2}, con u elemento invertibile di O.

4. Quand’anche avessimo che q(α) = γ^{2} in O, potrebbe accadere che γ ∉ ℤ[α].

Osservazione 3.5.1. Sottolineiamo che, nel caso in cui ℤ[α] è un PID, i problemi 1,2 e 4 sono subito risolti. Il seguente Lemma ci aiuta a risolvere l’ultimo dei quattro problemi sopra descritti.

Lemma 3.5.2. Sia f ∈ ℤ[X] monico e irriducibile di grado d e sia α ∈ ℂ una radice di f. Sia O l’anello degli interi di ℚ(α) e sia β ∈ O. Allora f′(α) · β ∈ ℤ[α].

Il seguente Teorema, invece, dà una stima quantitativa dei primi 3 punti critici.

Teorema 3.5.4. Siano d, n ∈ ℤ tali che d ≥ 2 e n > d^{2d^{2}}. Allora si ha che dim_{𝔽_{2}} V/ℚ(α)^{∗2} < log_{2} n.

Test quadratico probabilistico

Naturalmente, x ∈ V appartiene anche a ℚ(α)^{∗2} se e soltanto se χ(x) = 1 per ogni χ ∈ Hom(V/ℚ(α)^{∗2}, 𝔽_{2}) (N.B.: 𝔽_{2} è rappresentato in notazione moltiplicativa). Quindi, una volta trovato un sistema G di generatori di Hom(V/ℚ(α)^{∗2}, 𝔽_{2}), è possibile testare che x ∈ V è un quadrato controllando che χ(x) = 1 per ogni χ ∈ G.

Lemma 3.6.1. Siano k, e ∈ ℤ non negativi e sia E un 𝔽_{2}-spazio vettoriale di dimensione k. Allora la probabilità che un insieme di k + e elementi di E scelti a caso sia un sistema di generatori di E è maggiore di 1 − 2^{−e}.

Quindi, segue dal Teorema 3.5.4 e dal Lemma 3.6.1 che, scelti a caso log_{2} n+k applicazioni χ_{i} ∈ Hom(V/ℚ(α)^{∗2}, 𝔽_{2}), se x ∈ V è tale che χ_{i}(x) = 1 per ogni i = 1, …, log_{2} n + k, allora la probabilità che x ∈ ℚ(α)^{∗2} è 1 − 2^{k}. Ma come scegliere casualmente elementi in Hom(V/ℚ(α)^{∗2}, 𝔽_{2})? Con il simbolo di Legendre (v. Appendice B). Difatti, si verifica che, per ogni 𝔭 ∈ Spec(ℤ[α]) di grado 1, è possibile definire un’applicazione lineare su V tale che ristretta a ℤ[α]\𝔭 coincida con l’applicazione χ_{𝔭} definita come segue.

Definizione 3.6.2. Sia 𝔭 = ker π ∼ (p, r_{p}) un primo di grado 1 di ℤ[α] e sia x ∈ ℤ[α] \ 𝔭. Allora si definisce:

\begin{aligned}χ_{𝔭} : & ℤ[α] \ 𝔭 & ⟶ & \{±1\} \\ & x & ⟼ & (\frac{π(x)}{p}), \end{aligned}

dove (\frac{·}{p}) è il simbolo di Legendre.

Estrazione di radice quadrata

Trovato p(X) ∈ ℤ[X] tale che p(α) = γ^{2} in ℤ[α] e tale che p(m) = y^{2} in ℤ, per concludere, è necessario calcolare γ = \sqrt{p(α)} e y = \sqrt{p(m)}. Per il calcolo della y non c’è alcun problema, mentre per il calcolo di γ è necessario disporre di un algoritmo per l’estrazione di radice in ℤ[α]. Esistono diversi metodi in proposito, per una descrizione dei quali rimandiamo a [5], [10], [21], [25].

Complessità

Scelto B = exp ((8/9)^{1/3} (log n)^{1/3}(log log n)^{2/3}), M_{1} = B, M_{2} = B e d = (3 log n/ log log n)^{1/3} si ha che il tempo di esecuzione dell’NFS è

exp ((c + o(1)) ( log n)^{1/3}( log log n)^{2/3}),

con c = (64/9)^{1/3} ≃ 1.922999. Inoltre, sempre con tale scelta di B, M_{1}, M_{2} e d, si ha che il limite superiore per la grandezza dei numeri da setacciare è:

exp (((64/3)^{1/3} + o(1)) ( log n)^{2/3}( log log n)^{1/3}).

Bibliografia

[1] Leonard M. Adleman. Factoring numbers using singular integers. In Proceedings of the twenty-third annual ACM symposium on Theory of computing, pages 64–71. ACM Press, 1991.

[2] Michael Artin. Algebra. Prentice Hall Inc., Englewood Cliffs, NJ, 1991.

[3] M. F. Atiyah and I. G. Macdonald. Introduction to commutative algebra. Addison-Wesley Publishing Co., Reading, Mass.-London-Don Mills, Ont., 1969.

[4] David M. Bressoud. Factorization and primality testing. Undergraduate Texts in Mathematics. Springer-Verlag, New York, 1989.

[5] J. P. Buhler, H. W. Lenstra, Jr., and Carl Pomerance. Factoring integers with the number field sieve. In The development of the number field sieve, volume 1554 of Lecture Notes in Math., pages 50–94. Springer, Berlin, 1993.

[6] E. R. Canfield, Paul Erdős, and Carl Pomerance. On a problem of Oppenheim concerning “factorisatio numerorum”. J. Number Theory, 17(1):1–28, 1983.

[7] Stefania Cavallar, Bruce Dodson, Arjen K. Lenstra, Walter M. Lioen, Peter L. Montgomery, Brian Murphy, Herman te Riele, Karen Aardal, Jeff Gilchrist, Gerard Guillerm, Paul C. Leyland, Joel Marchand, Francois Morain, Alec Muffett, Chris Putnam, Craig Putnam, and Paul Zimmermann. Factorization of a 512-bit RSA modulus. In Theory and Application of Cryptographic Techniques, pages 1–18, 2000.

[8] Henri Cohen. A course in computational algebraic number theory, volume 138 of Graduate Texts in Mathematics. Springer-Verlag, Berlin, 1993.

[9] Don Coppersmith. Modifications to the number field sieve. J. Cryptology, 6(3):169–180, 1993.

[10] Jean-Marc Couveignes. Computing a square root for the number field sieve. In The development of the number field sieve, volume 1554 of Lecture Notes in Math., pages 95–102. Springer, Berlin, 1993.

[11] Richard Crandall and Carl Pomerance. Prime numbers. Springer-Verlag, New York, 2001. A computational perspective.

[12] Jody Esmonde and M. Ram Murty. Problems in algebraic number theory, volume 190 of Graduate Texts in Mathematics. Springer-Verlag, New York, 1999.

[13] Carl Friedrich Gauss. Disquisitiones arithmeticae. Springer-Verlag, New York, 1986. Translated and with a preface by Arthur A. Clarke, Revised by William C. Waterhouse, Cornelius Greither and A. W. Grootendorst and with a preface by Waterhouse.

[14] Robert W. Gilmer. Multiplicative ideal theory. Queen’s Papers in Pure and Applied Mathematics, No. 12. Queen’s University, Kingston, Ont., 1968.

[15] G. J. O. Jameson. The prime number theorem, volume 53 of London Mathematical Society Student Texts. Cambridge University Press, Cambridge, 2003.

[16] Neal Koblitz. A course in number theory and cryptography, volume 114 of Graduate Texts in Mathematics. Springer-Verlag, New York, second edition, 1994.

[17] Serge Lang. Algebraic number theory. Addison-Wesley Publishing Co., Inc., Reading, Mass.-London-Don Mills, Ont., 1970.

[18] Serge Lang. Algebra, volume 211 of Graduate Texts in Mathematics. Springer-Verlag, New York, third edition, 2002.

[19] A. K. Lenstra, H. W. Lenstra, Jr., M. S. Manasse, and J. M. Pollard. The factorization of the ninth Fermat number. Math. Comp., 61(203):319– 349, 1993.

[20] H. W. Lenstra, Jr. Algorithms in algebraic number theory. Bull. Amer. Math. Soc. (N.S.), 26(2):211–244, 1992.

[21] Peter L. Montgomery. Square roots of products of algebraic numbers. In Mathematics of Computation 1943–1993: a half-century of computational mathematics (Vancouver, BC, 1993), volume 48 of Proc. Sympos. Appl. Math., pages 567–571. Amer. Math. Soc., Providence, RI, 1994.

[22] Peter L. Montgomery. A block Lanczos algorithm for finding dependencies over GF(2). In Advances in cryptology—EUROCRYPT ’95 (Saint-Malo, 1995), volume 921 of Lecture Notes in Comput. Sci., pages 106–120. Springer, Berlin, 1995.

[23] B. Murphy. Polynomial selection for the number field sieve integer factorisation algorithm, 1999.

[24] Brian Murphy and Richard P. Brent. On quadratic polynomials for the number field sieve. In Computing theory ’98 (Perth), volume 20 of Aust. Comput. Sci. Commun., pages 199–213. Springer, Singapore, 1998.

[25] Phong Nguyen. A Montgomery-like square root for the number field sieve. In Algorithmic number theory (Portland, OR, 1998), volume 1423 of Lecture Notes in Comput. Sci., pages 151–168. Springer, Berlin, 1998.

[26] Giulia Maria Piacentini Cattaneo. Algebra. Zanichelli, 1996.

[27] J. M. Pollard. The lattice sieve. In The development of the number field sieve, volume 1554 of Lecture Notes in Math., pages 43–49. Springer, Berlin, 1993.

[28] Carl Pomerance. Smooth numbers and the quadratic sieve. 2000.

[29] Kenneth H. Rosen. Elementary number theory and its applications. Addison-Wesley, Reading, MA, fourth edition, 2000.

[30] Edoardo Sernesi. Geometria 1. Bollati Boringhieri, 1989.

[31] Peter Stevenhagen. The number field sieve. 2000.

[32] Ian Stewart and David Tall. Algebraic number theory. Chapman and Hall Mathematics Series. Chapman & Hall, London, second edition, 1987.

[33] Douglas R. Stinson. Cryptography. CRC Press Series on Discrete Mathematics and its Applications. Chapman & Hall/CRC, Boca Raton, FL, second edition, 2002. Theory and practice.

[34] Edwin Weiss. Algebraic number theory. McGraw-Hill Book Co., Inc., New York, 1963.