Algoritmi di Primalità

1

Facoltà di Ingegneria Informatica

Corso di Laurea in Ingegneria Informatica

ALGORITMI E ARCHITETTURE PER I SISTEMI CRITTOGRAFICI

Professor Bertoni

Francesco RinarelliMatteo Verzillo

POLITECNICO DI MILANO

2

TEST DI PRIMALITA’ E GENERATORI DI NUMERI PRIMI

Francesco Rinarelli & Matteo Verzillo

INTRODUZIONE

In questo elaborato vengono presentati i principali test di primalità utilizzati nei sistemi crittografici più conosciuti.

Il documento redatto è stato suddiviso in 5 sezioni, ognuna delle quali dedicata a test che hanno una base teorica comune:

• il crivello di Eratostene;

• il test probabilistico di Miller – Rabin;

• il crivello quadratico;

• i test classici (test n-1, test n+1);

• i test generali (test Goldwasser-Kilian, il test APR, il test AKS).

3

IL CRIVELLO DI ERATOSTENE


È un algoritmo, scoperto da Eratostene, per la generazione di numeri primi che risale al 240 a.C.

Si basa su un’idea molto semplice, che modificata di recente, ha fatto sì che diventasse il più usato generatore di numeri primi.

Si tratta di un crivello, ovvero di un setaccio, che riceve in input un intervallo di numeri interi e, per passi successivi, vi elimina tutti i numeri composti.

4



• si scriva l’elenco dei numeri interi da 2 a N;

• si prenda l’intero più piccolo presente nella lista e lo si etichetti come primo;

• si cancelli il primo trovato e tutti i suoi multipli presenti nella lista, inoltre se esso è si ritorni al secondo punto, altrimenti l’algoritmo termina e i numeri primi sono tutti quelli etichettati come tali più tutti quelli ancora presenti nell’elenco.

L’ALGORITMO

N

5



Il primo miglioramento introdotto consiste semplicemente nello sfruttare una conoscenza a priori che si ha riguardo ai numeri primi: non possono essere numeri pari. È per questo motivo che la prima variante all’algoritmo precedente è quella di farlo iniziare da 3 invece che da 2 e di dargli in pasto solo i numeri dispari presenti nell’intervallo che si vuole analizzare.

Le modifiche introdotte permettono quindi un risparmio di risorse del 50% (o di poco inferiore).

MIGLIORAMENTI SUCCESSIVI [1/2]

6



Il secondo miglioramento proposto è un poco più complesso e si basa sul seguente lemma:

Sia M >= 1 un numero intero. Se p è un numero primo, allora o p|M oppure GCD(p, M) = 1.

Questo lemma è particolarmente utile: si prenda ad esempio M = 30. Esso può essere scomposto nei primi 2, 3, 5. Gli altri primi minori di M sono 1, 7, 11, 13, 17, 19, 23, 29. Perciò tutti i numeri maggiori di M che non appartengono alle seguenti progressioni aritmetiche: 1+30k, 7+30k, 11+30k, 13+30k, 17+30k, 19+30k, 23+30k, 29+30k non sono certamente primi (poiché sicuramente multipli di 2, 3, 5). In questo modo si riduce ulteriormente la richiesta di memoria dell’algoritmo (nel nostro caso 8 bit ogni 30 numeri).

MIGLIORAMENTI SUCCESSIVI [2/2]

7



Il crivello di Eratostene è un generatore che determina i numeri primi compresi nell’intervallo [3, M].

Ma le esigenze, nel caso dei sistemi crittografici, sono di determinare un numero primo di dimensione molto grande. Il crivello di Eratostene, così come è, soddisferebbe questa esigenza in tempi estremamente lunghi, occorre quindi modificare ulteriormente l’algoritmo nel seguente modo:

• Si prende in ingresso un intervallo di numeri interi molto grandi in cui è plausibile che si trovi un numero primo (o pochi numeri primi).

• Si eliminano tutti i numeri multipli di numeri primi piccoli.

• Sui numeri rimanenti (cioè quelli che potrebbero essere primi) si applicano i test di primalità che presenteremo più avanti.

COME SFRUTTARE IL GENERATORE

8

RABIN-MILLER (1976 - 1980)


• È un algoritmo probabilistico: termina sempre ma ha probabilità non nulla di terminare scorrettamente (Montecarlo Test).• È anche uno “schema di approssimazione” (probabilistico): è infatti possibile, aumentando il numero di iterazioni dell’algoritmo, ridurre in modo arbitrario la probabilità di errore.• Il test RM si basa su un certificato (probabilistico) di primalità, calcolabile in tempo polinomiale.• RM estende il classico test degli pseudoprimi derivante dal piccolo test di Fermat, perché estrae informazione utile non solo dal risultato finale ma anche dalla fase di elevamento a potenza (secondo il metodo square and multiply).

INTRODUZIONE

9



• Viene scelta una base casuale a per la verifica della congruenza indicata dal piccolo teorema di Fermat.• Il valore p-1, dove p è l’intero dispari da testare, viene scomposto nella forma 2tu, dove t è il numero di zeri iniziali nella rappresentazione binaria di p, e u, ovviamente, intero e dispari.• a viene elevato per u, successivamente viene iterato un elevamento al quadrato (t volte).• Ad ogni iterazione, viene verificato che:

• Se ai = au*2^i = 1 mod p, ai-1 = 1,-1 mod p• at = ap-1 = 1 mod p

• In caso contrario, RM termina restituendo composite.• Al termine, l’algoritmo restituisce probably prime.

L’ALGORITMO - LE FASI

10



• Tutti i numeri primi passano il test.• Alcuni numeri (detti pseudoprimi forti) passano il test. RM può sbagliare la sua decisione con probabilità 0.25.• Per abbassare la probabilità di errore, basta eseguire più test indipendenti: allora la probabilità che un numero sia primo dopo k tentativi è:

OSSERVAZIONI

.14

14

4

11primo è

k

k

kk

k nP

• La complessità dell’algoritmo, utilizzando metodi di moltiplicazione veloce, è O(log2+εp).

• È possibile tramutare RM in un test deterministico, sotto l’ipotesi di validità di GRH (Generalized Riemann Hypothesis). Basterebbe iterare il ciclo principale per tutte le basi da 2 a log2p.

11

IL CRIVELLO QUADRATICO


Ideato agli inizi degli anni ’80 da Pomerance, è uno dei principali algoritmi di fattorizzazione per numeri interi.

L’algoritmo è utilizzato indirettamente come test di (non)primalità, in quanto fornisce in tempo subesponenziale un certificato di compostezza per i numeri in ingresso.

È stato utilizzato con successo per rompere il cifrario RSA a 128 bit.

12



L’idea che sta alla base di questo metodo di fattorizzazione è dovuta a Fermat.

Dal prodotto notevole:

L’ALGORITMO

bababa 22

considerato nel campo Z/nZ, si deduce che, se vale:

mod e 22 nbabababa allora gcd(a-b, n) è un fattore non banale di n (cioè è diverso da +1 e -1 e da se stesso).

Però la ricerca estensiva di tali coppie di numeri avrebbe un costo troppo alto. Si sfruttano quindi congruenze modulari di numeri particolari per ottenere la congruenza vista sopra. Questi numeri vengono detti lisci ed hanno la proprietà di essere composti solo da primi piccoli. Vengono utilizzati dei crivelli quadratici al fine di trovare tali numeri.

13



Si consideri il numero n da fattorizzare:

• Si supponga B = { p1, p2, …, pB } una factor base, ovvero un insieme di primi piccoli.

• Sia C un insieme di dimensione poco superiore a quella di B e si supponga di aver ottenuto #C congruenze del tipo:

L’ALGORITMO

Cjnpppx Bjjj

Bj #1per mod21

212

gli xj vengono trovati attraverso un crivello quadratico, vengono cioè selezionati quei numeri per cui ogni fattore α del suo quadrato appartiene a B.

14



L’ALGORITMO

• Per ogni xj si consideri il vettore: BBjjj Za 21 2mod , ,2mod Si cerchi un sottoinsieme M delle equazioni tale per cui gli aj sommati modulo 2 diano il vettore (0, …, 0).

• Se questo sottoinsieme esiste allora il prodotto degli x j corrispondenti userà ogni fattore di B un numero pari di volte. Perciò:

Mpxnpppxxx kh ,con mod221

221

• Detto xtot il prodotto degli xj e ptot il prodotto dei primi scelti da B, un fattore non banale di n si calcola trovando gcd(xtot – ptot, n).

15



UN ESEMPIO SEMPLIFICATO

Consideriamo n = 15770708441. Sia B = {2, 3, 5, 7, 11, 13} la factor base.

Consideriamo le tre congruenze: (8340934156)² = 3 × 7 mod n (12044942944)² = 2 × 7 × 13 mod n (2773700011)² = 2 × 3 × 13 mod n

Se prendiamo il prodotto di queste tre congruenze, abbiamo: (8340934156 × 12044942944 × 2773700011)² = (2 × 3 × 7 × 13) ² mod n

Riducendo l'espressione nella parentesi modulo n, abbiamo (9503435785)² = (546)² mod n

Quindi calcolando gcd(9503435785-546, 15770708441) troviamo il fattore 115759 di n.

16

I TEST CLASSICI: “N-1” ED “N+1”


• I test classici sono test che utilizzano teoremi noti della teoria dei numeri, per applicarli a classi di numeri particolari, in modo da ottenere alte prestazioni computazionali. Non sono test general purpose, perché in generale la loro complessità può essere abbondantemente superpolinomiale.

• Il più grande numero primo conosciuto, con quasi 8 milioni di cifre, è stato trovato da uno di questi algoritmi. È infatti un numero di una categoria particolare, i primi di Mersenne (primi della forma 2i -1)

• Il nome di questi test deriva dal fatto che per alcune classi di numeri (come quella di Mersenne) l’intero immediatamente precedente o successivo è fattorizzabile in tempo sublineare.

INTRODUZIONE

17



• Sono test per cui è molto facile trovare la scomposizione dell’intero precedente al numero da testare.

• Teorema Sia n>1. Se per ogni fattore primo q di n-1 valgono

a. an-1 1 mod n

b. a(n-1)/q ≠ 1 mod n

allora n è primo

• La tecnica adottata da questo tipo di test è in verità comune a molti se non tutti i più rilevanti algoritmi per la verifica di primalità: l’obiettivo è individuare un campo le cui dimensioni implichino, quando queste siano in una certa relazione con n, la primalità. Cfr. Goldwasser-Kilian

I TEST N-1

18



• Uno schema primitivo di algoritmo si ricava in modo immediato dal teorema precedente:

a. Per un intero dispari n da testare, si trova una fattorizzazione completa del suo precedente.

b. Per ogni fattore qi si verificano le due condizioni del teorema.

• Si tratta di uno schema molto oneroso, in generale. Tuttavia si prendano in considerazione i numeri di Fermat (22^n+1) o i numeri della forma h2k+1. Per tali classi il teorema precedente si restringe fino a consentire l’utilizzo di algoritmi pienamente polinomiali, perché la fattorizzazione completa di n-1 non è richiesta.

I TEST N-1

19



• Sono test che considerano la fattorizzazione dell’intero successivo al numero da vagliare. La teoria sottostante è tuttavia leggermente più sofisticata rispetto al caso precedente.

• Si definisce come sequenza di Lucas il sistema alle differenze del secondo ordine

• U(m) = pU(m-1) - qU(m-2), U(0) = 0, U(1) = 1

• V(m) = pV(m-1) - qV(m-2) , V(0) = 2, V(1) = p

• Tali variabili possono essere visti come i coefficienti della m-esima potenza delle radici di x2-px+q mod n (dove p2-4q non deve essere un quadrato modulo n)

I TEST N+1

20



• È possibile formulare (e dimostrare) un teorema di forma del tutto analogo a quello per i test “n-1”, per poter trovare un certificato di primalità (la condizione, come prima, è sufficiente ma non necessaria).

• Teorema Sia n>1. Se per ogni fattore r di n+1 esistono p e q tali che

• U è la variabile definita precedentemente tramite p e q

• p2-4q non è un residuo quadratico in n

• U(n+1) 0 mod n

• U((n+1)/r) ≠ 0 mod n

allora n è primo.

I TEST N+1

21



• Qual è l’utilità di strumenti come le successioni di Lucas?

• Esistono proprietà vantaggiose per U e V:

• U(2m) = U(m)V(m)

• V(2m) = V2(m) – 2qm

• Se il numero da testare è un numero di Mersenne, della forma 2n-1, il test di Lucas-Lehmer può fornire un certificato di primalità in tempo lineare. Con alcune varianti di questo stesso test è stato trovato il più grande primo conosciuto (7*106 cifre). Le applicazioni critografiche sono più limitate, anche perché LL non è in grado di fornire certificati di compostezza.

I TEST N+1

22

IL TEST GOLDWASSER – KILIAN


Ideato nel 1986 è il primo test di primalità che fornisca un certificato sfruttando le proprietà delle curve ellittiche in campo finito.

IL NUCLEO DELL’ALGORITMO

Si prenda in considerazione una curva ellittica En(A, B): Y2 = X3 + AX + B definita su Z/nZ, con discriminante Δ = 4A3 + 27B2 ≠ 0 e n non divisibile per 2 o 3.

Sussiste il seguente teorema:

Sia En(A, B) una curva ellittica definita su Z/nZ, n primo con 2, 3 e 4A3+27B2, se esistono:

1. un punto M che appartiene a En(A, B), M ≠ I;

2. un intero q, primo e strettamente maggiore di n1/2+1+2n1/4, tale che qM=I;

allora n è primo.

23

IL TEST GOLDWASSER – KILIAN


L’ALGORITMO

• Sia p il numero da testare. Si seleziona una curva ellittica su Z/pZ, con parametri A e B casuali e discriminante non nullo. Sia poi Np l’ordine del gruppo ellittico Ep(A, B) trovato. Finché non si trova un gruppo con ordine di tipo 2q e con q probabile primo va ripetuta questa fase.

• Si verificano le condizioni del teorema sopra esposto, supponendo primo il q ricavato precedentemente. Se queste sussistono allora la primalità di p è certificata a condizione che q sia primo.

• Si ripete ricorsivamente l’algoritmo ponendo p=q, finché non si è certi che l’ultimo q trovato sia primo.

24

IL TEST APR


Sviluppato nel 1983 da Adleman, Pomerance e Rumely è il più veloce test tra quelli non polinomiali.

Si tratta di un test molto complesso e la sua implementazione è alquanto onerosa. Ecco uno dei principali motivi per cui non viene utilizzato per prodotti commerciali, ma piuttosto per studi teorici.

La sua complessità è O(lgnclglglgn).

25

IL TEST APR


L’algoritmo è piuttosto complicato poiché sfrutta proprietà molto complesse nella teoria dei campi ciclotomici, utilizza i numeri primoriali ed il Teorema del Resto Cinese (CRT).

Campo ciclotomico: estensione del campo dei numeri razionali generata da una radice dell'unità, ovvero generata da un numero che elevato alla n dà 1.

Primoriale: per n ≥ 2, il primoriale di n, indicato con n#, è il prodotto di tutti i numeri primi minori o uguali ad n.

CRT: se gli interi n1, n2, …, nk sono primi tra loro allora il sistema di congruenze simultanee:x = a1 (mod n1)x = a2 (mod n2). . .x = ak (mod nk)ha una soluzione unica modulo n = n1n2…nk.

L’ALGORITMO

26

AKS (Agrawal, Kayal, Saxena - 2002)


L’ALGORITMO

• Pubblicato da tre ricercatori indiani nell’Agosto 2002

• È il primo e ad ora unico test di primalità deterministico ad avere complessità polinomiale – senza appoggiarsi a congetture come GRH

• Il suo interesse è eminentemente teorico – in quanto dimostra che la classe di complessità dei test di primalità è in P -, ma non ha applicazioni in campo crittografico, a causa dell’alto grado del polinomio (12, o 18, anche se esistono congetture che lo porterebbero a 6).

• Come numerosi test più elementari, AKS utilizza un teorema che estende banalmente il piccolo teorema di Fermat: un intero è primo se e solo se vale, per un positivo a coprimo a p: (x + a)p = xp + a mod p

• La dimostrazione di correttezza utilizza concetti relativamente basilari della teoria dei numeri e dei campi finiti.

27



• Sia p l’intero dispari da testare. Si verifica innanzitutto che p non sia una potenza di un qualche numero primo.• Si determina il più piccolo numero primo r che non divida né p né alcuno dei numeri pi-1, per ogni i < log2p/log22. Se viene trovato un r divisore di p ovviamente l’algoritmo termina.• Per ogni intero a < r-1 si verifica che valga (x + a)p = xp + a nell’anello Z[x]/p. Se ciò non accade l’algoritmo termina.• Se l’algoritmo non è terminato precedentemente, p è primo.

L’ALGORITMO - LE FASI

IL TEOREMA ALLA BASE DI AKS

Sia p un intero dispari ed r un numero primo. Se (1) p non è divisibile per nessuno dei primi fino ad r; (2) L’ordine di p mod r è almeno log2p/log22; (3) per ogni a < r si ha (x + a)p = xp + a nell’anello Z[x]/p, allora p è primo.

28



OSSERVAZIONI

• La complessità di AKS deriva dalla stima della grandezza di r, che determina la lunghezza delle iterazioni più costose. Si trova che tale valore di r è O(log6p). Il costo computazionale totale è quindi O(log12+εp) se vengono utilizzate tecniche di moltiplicazione veloce.

• Da quando l’algoritmo è stato pubblicato ad oggi, la sua velocità è stata migliorata, con numerosi affinamenti, di un fattore 106. Tuttavia…

•Crandall and Papadopoulos, 2003: per testare la primalità di un numero di 30 cifre base 10, con Apple G4 a 1 Ghz, è necessario “circa 1 giorno”.

•Il più grande primo conosciuto ha 4*106 cifre.

•Per ottenere lo stesso risultato, su macchina equivalente, RM impiega pochi secondi.

Algoritmi di Primalità

Documents

Transcript of Algoritmi di Primalità