numeri primi | compscient

Archive for the ‘numeri primi’ Category

Verifica di primalità: altre due parole

18 aprile 2012

Nel mio secondo post di questa piccola serie ho detto che esistono 3 differenti strategie per verificare la primalità di un numero: una dedicata a numeri piccoli, una per numeri grossi e, l’ultima, per numeri particolari. Nel seguito mi sono dedicato solo alla seconda, e questo post vuole iniziare a sistemare il problema: parlerò di algoritmi per la prima delle due classi di numeri.

Siamo nel caso in cui i numeri sono piuttosto piccoli e quindi non è particolarmente utile creare tutto l’impianto necessario per il test di Miller-Rabin, ci possiamo accontentare di qualcosa di più semplice.

Il primo metodo che può venire in mente sono le divisioni successive: proviamo a dividere un numero per ogni numero minore della sua radice quadrata. È un metodo molto naïve, con complessità esponenziale, e non è particolarmente interessante.

I Crivelli

I crivelli forniscono un metodo per filtrare insiemi di numeri attraverso un criterio. In particolare, noi vorremmo che l’insieme filtrato contenga solo numeri primi. Prendiamo quindi l’insieme dei numeri naturali da 2 a N. Nel nostro esempio scegliamo N = 30.

{2, 3, 4, 5, 6, 7, 8, 9, … 30}

Partiamo dal primo numero, cioè 2. Lo segnamo come primo ed eliminiamo tutti i suoi multipli: 4, 6, 8, …

{2, 3, 5, 7, 9, 11, … 30}

Andiamo al numero successivo, 3, segnamo anch’esso come primo e eliminiamo i suoi multipli, che sono 6, 9, 12…

{2, 3, 5, 7, 11, 13, 17, 19, 23, 25, 29}

A questo punto passiamo a 5 (il 4 è già stato eliminato), e ripetiamo il processo di eliminazione dei multipli. Ci fermiamo quando arriviamo al numero appena minore di $\sqrt N$ . Nell’esempio ci siamo fermati appena dopo il 5, perché $\sqrt 30 \approx 5.47$ ; alla fine abbiamo ottenuto l’insieme: {2, 3, 5, 7, 11, 13, 17, 19, 23, 29}, che sono proprio tutti i numeri primi minori di 30.

Questo appena descritto è il crivello di Erastotene: il metodo più antico e semplice per generare numeri primi. È un algoritmo piuttosto efficiente, ma occupa abbastanza spazio; si nota che fino ai 10 milioni funziona abbastanza bene. L’algoritmo può essere migliorato in vari modi, per esempio utilizzando le ruote o segmentando il crivello: ovvero dividere l’insieme in pezzi di dimensione minore, da sottoporre al crivello separatamente.

Pochi anni fa è stato ideato il crivello di Atkin: è un metodo che conta le soluzioni a certe equazioni per verificare se un numero è primo. Si scopre che non è particolarmente veloce rispetto al semplice crivello di Erastotene: anche se veramente ottimizzato le prestazioni rimangono piuttosto allineate.

Il funzionamento di questi metodi di generazione dei numeri primi è stato spiegato molto bene da zar nel suo blog (crivello di Erastotene, crivello di Atkin 1 e 2).

Ora abbiamo generato un milione di numeri primi: possiamo verificare se un numero minore di 10¹² è primo semplicemente provando a dividerlo per questi numeri. Chiaramente, una volta che si ha una lista di primi, diventa piuttosto efficiente verificare se un numero è primo.

Purtroppo, come abbiamo visto, non possiamo generare liste arbitrariamente lunghe di numeri primi in maniera efficiente. L’unico modo che abbiamo oggi per verificare se un numero generico (senza proprietà particolari) è primo in modo veloce è usare il test di Miller-Rabin.

Pubblicato su matematica, numeri primi | Leave a Comment »

Primes è in P

5 aprile 2012

Fino ad ora abbiamo visto due algoritmi probabilistici: fino al 2003 erano l’unica strada per controllare numeri grandi in modo abbastanza veloce. Poi A, K e S (le iniziali di 3 matematici indiani) annunciarono un nuovo test di primalità, che è “veloce” e non probabilistico.

Un breve intermezzo: P vs NP

P e NP sono due insiemi, che contengono problemi matematici. P contiene i problemi per cui è veloce trovare una soluzione, mentre NP è l’insieme dei problemi per cui è semplice controllare una soluzione. Più precisamente, possiamo dire che i problemi in P hanno una soluzione che impiega un tempo polinomiale per terminare, mentre NP usa tempo polinomiale per controllare se una soluzione è corretta. Il tipico esempio di problema NP è il sudoku: data una soluzione si controlla facilmente se è corretta, ma è più lento trovare una soluzione.

Fermi tutti!

Da quello che ho detto fino ad ora sembrerebbe che P è la classe dei problemi “facili”, mentre NP significa “difficili”. In effetti la tesi di Cobham dice qualcosa del genere, ma non è proprio esatto.

Trovare una soluzione per un problema NP è lento solo in alcuni casi:

siamo nel caso pessimo
i numeri sono troppo grossi
vogliamo una soluzione esatta
(a quanto si sa)

Se però possiamo rinunciare a qualcosa, per esempio quindi ci accontentiamo di una soluzione approssimata, è possibile risolvere il problema velocemente.

L’ultimo punto è piuttosto interessante: un problema viene messo in NP quando non si può dimostrare che è in P, però la dimostrazione potrebbe esistere.

Inoltre, non sappiamo nemmeno qual è la relazione tra P e NP: è un problema del millennio. In realtà, quindi, tutti i problemi potrebbero avere una soluzione in tempo polinomiale. Al momento, comunque, non si crede sia così. [Continua…]

L’algoritmo vero e proprio

Si basa su una osservazione piuttosto semplice, che fra l’altro abbiamo già (parzialmente) dimostrato parlando del test di Fermat. Si nota che

$(x-a)^p \equiv x^p - a \pmod p$ se a è coprimo a p.

Questa condizione permette di stabilire con certezza se p è primo o meno. La cosa importante da notare è che x è una variabile libera, cioè non deve mai essere sostituita con un numero, si deve invece espandere la potenza col binomio di Newton e confrontare tutti i termini.

E qui sorge il problema: ci sono troppi termini da controllare, sviluppando il binomio si ottengono p+1 termini. Per ridurre il numero di confronti si calcola il resto anche rispetto ad un binomio del tipo $x^r-1$ , dove r è un numero primo “piccolo”, in modo da ottenere solo r+1 termini.

La nuova identità si può scrivere così (con un leggero abuso di notazione):

$(x+a)^p \mod (p, x^r-1) = x^p + a \mod (p, x^r-1)$

Questa è ancora vera se p è primo, perché calcolare il resto sia a destra sia a sinistra ovviamente non modifica il risultato, ma si deve verificare se è vero anche il viceversa. Purtroppo si scopre che non è così: ci sono alcuni valori di p, non primi, che verificano l’uguaglianza.

AKS hanno dimostrato che se si sceglie un valore di r “giusto” allora è necessario provare solo pochi valori di a per essere certi della primalità. Inoltre è possibile determinare esattamente quanto è “pochi” (che è nell’ordine del logaritmo di p).

Un pregio di questo algoritmo è la dimostrazione, infatti quella fornita dai tre matematici è piuttosto semplice. Purtroppo il test ha alcuni difetti:

non è semplicissimo da implementare e
è lento.

Nonostante appartenga alla classe polinomiale, non fa bella figura rapportato agli altri test di cui ho parlato. Abbiamo visto che il tempo di esecuzione del test di Miller-Rabin dipende dalla potenza terza del numero di cifre in n (cioè è $\log^3(n)$ ); la versione originale di AKS addirittura dalla 12esima, anche se alcuni miglioramenti hanno abbassato prima a 10 e poi a 6.

In definitiva il gioco non vale la candela: è un metodo di interesse principalmente teorico, ma il test di Miller-Rabin è migliore per progetti reali.

Nel prossimo post parlerò brevemente di altri modi per verificare la primalità.

Tag:algoritmi, p vs np
Pubblicato su algoritmi, matematica, numeri primi | Leave a Comment »

Il test di Miller-Rabin

24 marzo 2012

Nel post precedente abbiamo visto il teorema di Fermat e il test conseguente; abbiamo anche notato che sbaglia per alcuni numeri (detti numeri di Carmichael). Il test di Miller-Rabin, che vedremo oggi, migliora questo aspetto.

La versione originale è deterministica, e dipende da una congettura matematica tutt’ora aperta, quindi non è molto interessante per gli informatici, ma è stata modificata da Rabin per ottenere un test probabilistico.

Un breve intermezzo

Prima di esporre il criterio di Miller-Rabin, introduciamo un piccolo lemma, completo di una semplice dimostrazione.

Lemma $x^2 \equiv 1 \pmod p$ ha solo due soluzioni (+1 e -1) se p è primo e maggiore di 2.

Dimostrazione. L’equazione è equivalente a:
$(x+1)(x-1) \equiv 0 \pmod p$ .
Che, tradotto, vuol dire che $(x+1)(x-1)$ è un multiplo di p. Segue che p divide (x+1) oppure p divide (x-1) ma non entrambi, perché se così fosse, p dividerebbe anche la differenza $(x+1)-(x-1) = 2$ , ma p è chiaramente dispari. Ci sono due casi:

(x+1) è multiplo di p: $(x+1) \equiv 0 \pmod p$ quindi $x = -1 \pmod p$
(x-1) è multiplo di p: $(x-1) \equiv 0 \pmod p$ , $x = +1 \pmod p$

Otteniamo la soluzione banale $x = \pm 1$ .

Facciamo un paio di esempi: scegliendo p = 15, l’equazione ammette 4 soluzioni:

1 infatti $1^2 = 1 \pmod {15}$ , e questa è la prima soluzione banale
4: $4^2 = 16 = 1 \pmod {15}$
11: $11^2 = 121 = 1 \pmod {15}$
14: $14^2 = 196 = 1 \pmod {15}$ cioè la seconda soluzione banale

Se invece scegliamo p = 9, notiamo che non è vero il contrario:

$x^2 \equiv 1 \pmod 9$ ammette come uniche soluzioni $x = \pm 1 \pmod 9$ a cui corrispondono i valori 1 e 8, eppure 9 non è primo.

Test di Miller-Rabin

Dopo la dimostrazione del lemma, possiamo finalmente introdurre il nostro secondo test.

Criterio di Miller-Rabin. Sia p un primo dispari e a un intero minore di p. Si calcoli t e u in modo che $p - 1 = 2^t \cdot u$ (con u dispari). Allora una di queste due condizioni è vera:

$a^u \equiv 1 \pmod n$ oppure
uno tra $a^{u}, a^{2u}, a^{4u}, ... a^{2^{t-1}u}$ è congruente a -1 in modulo p.

Giustificazione/spiegazione: consideriamo la successione, dove ogni termine è il quadrato del precedente:

$a^u, a^{2u}, a^{4u}, ..., a^{2^{t-1}u}$ .

Separatamente prendiamo anche il quadrato dell’ultimo termine: $a^{2^t u}$ . Dalla definizione notiamo che questo termine è $a^{p-1}$ , e ricordando il teorema di Fermat, sappiamo che $a^{p-1} \equiv 1 \pmod p$ .

Quindi, visto che l’ultimo termine è 1 si hanno due casi:

il primo termine è 1, e quindi tutti i quadrati sono 1.
un termine nella successione è uguale a 1. Per il lemma precedente, il termine immediatamente prima (la sua radice quadrata) deve essere 1 oppure -1.

Chiamiamo pseudo-primi forti i numeri composti che passano k iterazioni del test di Miller-Rabin. Con una sola iterazione si può dimostrare che la probabilità che un numero composto sia dichiarato primo è minore di 1/4 (cioè almeno 3/4 dei numeri che passano il test sono primi).

Generalmente il test viene ripetuto k volte, con vari valori di a scelti casualmente. Quindi la probabilità che un numero composto passi il test di Miller-Rabin decresce all’aumentare di k, ed è minore di ${(\frac{1}{4})}^k$ (vedi nota 1). Scegliendo k = 50 (ripetendo cioè il test 50 volte) la probabilità che un numero composto venga dichiarato primo diventa minore della probabilità che il computer abbia effettuato un errore di calcolo.

Il codice, in Python, è qui sotto.

def _bits_of_n(n):
    bits = bin(n)[2:]
    t = 0
    for i in reversed(bits):
        if i == '0':
            t = t+1
        else:
            break
    u = n//(2**t)
    return (u, t)

def witness(a, n, u, t):
    x = pow(a, u, n)
    for i in range(1, t):
        xp = x
        x = (xp * xp) % n
        if x == 1 and xp != 1 and xp != n-1:
            return True
    x = (x * x) % n
    if x != 1:
        return True
    return False

import random

def miller_rabin(n, s):
    u, t = _bits_of_n(n-1)
    for i in range(s):
        a = random.randint(2, n-1)
        if witness(a, n, u, t):
            return False #sicuramente composto
    return True          #forse primo

Il tempo di esecuzione di questo algoritmo dipende dal metodo usato per calcolare le potenze, che è di norma logaritmico: complessivamente l’algoritmo risulta polinomiale.

Nota finale

In realtà questo valore non è del tutto esatto. Noi conosciamo la probabilità condizionata che il test ritorni “primo” se n è composto (che è 1/4). Si può calcolare in maniera più precisa ricorrendo alla formula di Bayes e alle probabilità totali. Dati i due eventi N = “il numero n è primo” e T = “n passa k iterazioni del test”, possiamo calcolare la probabilità:
$\displaystyle P(\overline{N}|T) = \frac{\log n - 1} {4^k + \log n - 1}$

Tag:algoritmi, miller-rabin, numeri primi, programmazione, python
Pubblicato su algoritmi, matematica, numeri primi, programmazione, python | Leave a Comment »

Fermat: un teorema e un test.

15 marzo 2012

Fermat è molto conosciuto per un particolare motivo: l’ultimo teorema di Fermat (che, guarda caso, fino a non molto tempo fa non era né un teorema né l’ultimo). Ha un enunciato molto semplice: $x^n + y^n = z^n$ non ha soluzioni per n > 2. La soluzione però è decisamente complessa, infatti è stato provato solo nel 1996 da Wiles, più di tre secoli dopo la morte di Fermat.

Fortunatamente, quindi, non è quello che ci serve per i numeri primi. Infatti è più utile il “piccolo” teorema di Fermat.

Piccolo Teorema: Se p è un numero primo, $a^p \bmod p = a$ , per ogni valore di a.

Dimostrazione: Per dimostrare questo teorema possiamo ricorrere all’induzione su a.

Se $a = 0: 0^p \bmod p = 0$

Supponiamo valido per a, e dimostriamo per a+1:

$(a+1)^p \bmod p = a + 1$

Ricorrendo al binomio di Newton, possiamo sviluppare il primo membro:

$\displaystyle \sum_{k=0}^p \dbinom{p}{k} a^k 1^{p-k} = \sum_{k=0}^p \dbinom{p}{k} \cdot a^k$

Se p è un numero primo, $\binom{p}{k}$ per $0 < k < p$ è sempre un multiplo di p, come si può vedere anche nel triangolo di Tartaglia. Il resto della divisione di ognuno di questi termini per p è, di conseguenza, 0.

Arriviamo quindi a:

$\dbinom {p}{0} \cdot a^0 + \dbinom {p}{p} \cdot a^p = 1 + a^p \pmod p$

Torniamo nell’equazione originaria:

$1 + a^p \bmod p = 1 + a$ .

$\square$

Inoltre si può riformulare nel modo seguente (dividendo per a, che è lecito se a è coprimo rispetto a p): $a^{p-1} \bmod p = 1$ .

Utilizzando quest’ultima formulazione possiamo creare un semplice test di primalità per numeri dispari: scegliamo infatti a = 2, che ovviamente è coprimo rispetto a tutti i numeri dispari, e usiamo l’enunciato per arrivare all’algoritmo:

def fermat(n):
    if pow(2, n-1, n) == 1:
        return True #forse primo
    return False    #sicuramente composto

Proviamolo con quale valore:

>>> fermat(97)
True
>>> fermat(524287)
True
>>> fermat(65245)
False

Bene, sembra funzionare. Alcune prove più attente ci fanno scoprire alcuni numeri composti che passano il test.

Chiamiamo pseudo-primo in base 2 ogni numero composto che passa il test di Fermat con a = 2 (quindi uno pseudo-primo è un errore del test). Qual è la frequenza di questi errori?
Fortunatamente è bassa: ci sono solo 22 valori minori di 10⁴ (e 750 minori di 10⁷) per cui il test sbaglia con a = 2 (i primi sono 341, 561, 645), però sono infiniti. Si nota anche (e si può dimostrare) che la frequenza degli pseudoprimi minori di un numero diventa sempre più bassa al crescere del numero.
La probabilità di errore può essere ulteriormente abbassata considerando anche altri valori di a (per esempio 3 o 5, sempre scelti in modo opportuno), però non è possibile annullarla totalmente. Esistono infatti dei numeri composti per cui è vera la condizione di Fermat per ogni valore di a. Si chiamano numeri di Carmichael, anche essi sono infiniti, ma per fortuna, molto rari (appena 255 minori di 10⁷).

Nonostante questi problemi, il test è piuttosto buono, ed è usato per esempio da PGP, un popolare programma crittografico, il cui utilizzo principale è incrementare la sicurezza delle comunicazioni tramite email.

Noi però non siamo soddisfatti; il prossimo test di primalità non si farà ingannare così facilmente.

Tag:binomio di newton, fermat, matematica, python, teorema
Pubblicato su algoritmi, matematica, numeri primi, programmazione | Leave a Comment »

Fatti interessanti sui numeri primi

5 marzo 2012

Ora che abbiamo visto a che cosa servono in pratica i numeri primi, possiamo elencare qualche fatto utile.

Definizione: Un numero primo è un numero maggiore di 1 che ha solo due divisori positivi (1 e se stesso). Un numero non primo è detto composto.

Si può dimostrare che i numeri primi sono infiniti, ed è piuttosto semplice, ma la domanda più interessante è come si distribuiscono all’interno dei naturali.

Il primo risultato in questo ambito è il teorema dei numeri primi, proposto da Gauss a 15 anni (o era un genio o aveva un ottimo agente pubblicitario).

(more…)

Tag:gauss, matematica, numeri primi, teorema
Pubblicato su algoritmi, matematica, numeri primi | Leave a Comment »

Crittografia: RSA e teoria dei numeri

29 febbraio 2012

Spesso è difficile trovare un uso pratico per la matematica pura. Naturalmente la matematica nacque per usi molto concreti, e presto si è sviluppata per descrivere fenomeni fisici, ma ci sono sempre state delle aree della matematica che sono state sviluppate pur senza avere un uso (i Veri Matematici sono strani). La teoria dei numeri è una di queste: non serve per calcolare le traiettorie dei proiettili o guidare navi, ma è sempre stata studiata da moltissimi matematici.

Infatti, probabilmente non è un caso se molti problemi aperti nella matematica di oggi riguardano questo campo: la congettura di Goldbach e la congettura dei primi gemelli sono caratterizzate da avere enunciati molto semplici, ma le dimostrazioni (o i controesempi) mancano ancora. Anche questo campo ha perso la purezza da veri matematici e, con l’arrivo dei computer, ha trovato un posto nelle applicazioni: la crittografia.