Fibonacci sequence in J

31 luglio 2013

We can write the usual Fibonacci algorithm in J very easily, using almost the same notation as we usually do in Python. This function continues to generate fibonacci’s numbers as long as the last number is lower than 10. When the last number is greater than 10, it returns the list with the computed numbers

fibo =: 3 : 'if. (_1 { y) < 10 do. fibo (y , (_2 { y + _1 { y)) else. y end.'

This function is correct, but it’s hardly nice, according to J’s standards. In this post I’ll apply some transformations to make it better.

First of all, let’s try to remove the if.

In order to remove the if, we should use the gerund ` (tie), which creates a list of two functions, and the @. (agenda) which selects the item in a list corresponding to its right argument (its left argument must be a gerund). Both argument of the gerund ` must be verbs, so we must use ] to return the argument y (this is a first step at tacit-ization).

We reach this form, which is wrong. The result of @. is a function, and we should call it with y as argument.

fibo =: 3 : '(] ` helper) @. ((_1 { y) < 10)'

Adding a y solves our problem:

fibo =: 3 : '((] ` helper) @. ((_1 { y) < 10) y)'

To the definition of helper! Helper is just needed to create a function with a “localized” parameter from the previous definition, (it needed y in three different points)

helper =: 3 : 'fibo (y , (_2 { y + _1 { y))'

Helper is not tacit, and, for now, we’re cool with that.
We try to make fibo tacit, for now. This is simpler: the first part is already done!

fibo =: 3 : '((] ` helper) @. (10 > (_1 { y)) y)'

Just flipped < to > and switched its arguments

fibo =: 3 : '((] ` helper) @. (10 > _1&{)'

Made the right branch of @. point free using bond (&). Now the whole fibo is tacit

fibo =: ((] ` helper) @. (10 > _1&{)

Now, let’s try to transform helper.

helper =: 3 : 'fibo2 (y , (_2 { y + _1 { y))'

First of all, we realize that _1 { y + _2 { y can be written as +/ @ (_1 _2 { y) and we bond the parameter y as we did before

G =: +/ @ ((_1 _2)&{)

Now we recognize, in helper, the form

y, (G y)

Which is a simple y f (g y) monadic hook. We can write it as

(, G)
helper =: fibo @ (, (+/ @ ((_2 _1)&{)))

Now, at this point we can plug helper in fibo, to get:

fibo =: (] ` (fibo @ (, (+/ @ ((_2 _1) & {))))) @. (10 > _1&{)

We can even hide the recursion using the fixed-point verb (or power).

Note that the fixpoint used in J is different from the usual fix in Haskell (defined as fix f = f (fix f)), since this one is a combinator, while the J version is more like the built-in iterate, with the only exception that it stops when two different iteration of the function give the same results.

fibo =:  ((, +/ @ ((_2 _1) & {)) ^: (10 > _1&{)) ^:_

This version is quite nice, and it’s not too cryptic.

Annunci

Donne nel mezzo e ritardi agli appuntamenti

5 maggio 2012
In questo post descriverò alcune tecniche di attacco per i cifrari a chiave pubblica, per mostrare che è purtroppo non basta una bella teoria matematica per creare un sistema sicuro. I primi due attacchi che vedremo sono attacchi all’implementazione, che non si basano su problemi di costruzione di un cifrario e quindi sono attacchi a cui è vulnerabile qualunque cifrario a chiave pubblica; ne vedremo anche altri per cui invece si sfruttano tecniche matematiche per fattorizzare dei numeri non scelti in maniera corretta, che quindi sono rivolti in particolar modo a RSA.

Man in the middle

Per questa tipologia di attacco Eve deve avere controllo totale del sistema di comunicazione (senza che Alice e Bob lo sappiamo, ovviamente). L’attaccante quindi, può leggere, modificare e aggiungere dati a quelli che sono in corso di trasmissione. Questa assunzione è abbastanza ragionevole in alcune circostanze: per esempio Eve può inserirsi come donna nel mezzo in una connessione wireless.

Il più semplice attacco di questo tipo prevede che, quando Alice cerca la chiave pubblica di Bob, Eve invii la sua. In questo modo lei può leggere i messaggi che Alice crede di inviare a Bob.

Un attacco più complicato

Qui Eve deve fingere di essere una terza parte fidata, per esempio un’autorità per la verifica dell’identità delle parti. In questo modo Eve può chiedere ad Alice di decifrare testi “casuali”: la decodifica di un messaggio è prova di identità, visto che può avvenire solo con la chiave privata.

  1.  Eve intercetta un messaggio T, ottenuto criptando M, che Bob sta inviando e lo modifica, calcolando T_i
    T_i = k^e T \pmod n
    con k scelto casualmente
  2. Alice lo decifra, e invia il risultato ad Eve
    M_i = T_i^d \pmod n = (k^e T)^d \pmod n = k M \pmod n
    Eve ha riottenuto M, visto che conosce k.
È importante che Alice creda che il messaggio ricevuto sia inviato proprio da Eve. Non sospetta che un messaggio di Bob sia stato modificato. Questo attacco sfrutta il fatto che Alice è quello che si chiama comporta come un oracolo, ovvero decifra tutto ciò che le arriva e invia una risposta.
Tutti i protocolli di comunicazione sono vulnerabili al man in the middle, ma si possono introdurre delle semplici verifiche per renderlo inutilizzabile, come codici segreti, un secondo canale (sicuro) di verifica oppure delle autorità che autenticano entrambe le parti in una conversazione.
Quest’ultima tecnica viene usata in HTTPS: esistono delle autorità che mantengono le liste di chiavi pubbliche fidate: in questo modo se Alice cerca la chiave pubblica di Bob interroga appunto la terza parte fidata, che la fornisce cifrata cifrata. La chiave per decifrare è salvata nel browser o direttamente nel computer.

Attacchi a tempo

Questo è un attacco piuttosto moderno, ideato nel 1995. Se l’attaccante conosce sufficientemente bene l’hardware di Alice ed è in grado di misurare con molta precisione il tempo che lei impiega a decifrare diversi messaggi conosciuti, potrebbe riuscire a calcolare il valore dell’esponente privato, d, esattamente, e quindi decifrare tutti i messaggi destinati ad Alice.

Si sfrutta l’algoritmo di Montgomery, che è lo standard per calcolare la potenza in RSA. In generale è piuttosto efficiente, ma è costruito in modo da compiere una sottrazione in più ogni volta che compare un 1 nella codifica binaria dell’esponente (cioè di d). Quando i numeri sono grandi questa sottrazione diventa piuttosto lenta; quindi il tempo impiegato in più ogni volta che compare un 1 può diventare significativo.
L’attacco quindi consiste nel creare tanti messaggi convenienti, e misurare i tempi impiegati per decifrarli; in questo modo l’attaccante può arrivare a ricostruire la chiave privata un bit alla volta.
È un tipo di attacco molto elegante perché non è necessario conoscere né i dettagli dell’implementazione né come fattorizzare un numero, serve semplicemente sapere che la potenza è calcolata tramite i quadrati ripetuti.
Attacchi di questo tipo vengono usati con successo contro smartcard, dei dispositivi hardware per la codifica, riuscendo a rompere la chiave da 512 bit con 350000 misurazioni.
Proteggersi da questi attacchi è piuttosto semplice, e di norma si inseriscono dei ritardi negli algoritmi in modo che il tempo impiegato sia indifferente dalla codifica binaria dell’esponente.

Un attacco matematico

Se p e q sono stati scelti in maniera corretta, l’unico modo per fattorizzare n è impiegare un algoritmo di fattorizzazione generale, che hanno complessità esponenziale. In questo caso, quindi, non si può fare molto: la fattorizzazione di un numero di 2000 bit necessita di troppo tempo per essere praticabile. Di conseguenza ci concentriamo sui casi in cui c’è stato qualche errore.

Se p e q sono vicini

Per generare p e q potrebbe sembrare una buona idea estrarre p casualmente e poi trovare q calcolando p+2, p+4, … finché si ottiene un numero primo. Però quando p e q sono vicini, si nota che è particolarmente efficiente il metodo di fattorizzazione di Fermat, ovvero la differenza di due quadrati. Questo metodo funziona bene solo per numeri vicini, nei casi generali è più lento della fattorizzazione tramite divisioni successive.

Si scrive n come prodotto di due numeri, vicini:
n = (x+y)(x-y) = x^2 - y^2
(x+y) = p; (x-y) = q
Si ottiene:

\displaystyle x = \frac {p+q} {2} e \displaystyle y = \frac {p-q} {2}
\displaystyle n = x^2-y^2 = {(\frac {p+q} {2})}^2 - {(\frac {p-q} {2})}^2

Con la differenza p-q piccola (vicina allo 0), \frac {p+q} {2} sarà poco più grande della \sqrt n.

Partiamo quindi da t, l’intero inferiore alla \sqrt n e controlliamo quando t^2 - n è un quadrato perfetto (cioè \sqrt{t^2-n} è intero), aumentando t ogni volta. Se i fattori p e q sono sufficientemente vicini arriveremo presto ad una soluzione: si riesce a calcolare p = t + \sqrt{t^2-n} e q = t - \sqrt{t^2-n}.

L’unico modo per essere protetti contro questo attacco è avere p – q grande; di solito si sceglie q maggiore di p + \sqrt p: in questo modo la fattorizzazione di Fermat diventa troppo lenta.

La prossima volta concluderemo il viaggio nella crittografia facendo una breve incursione nella fisica e introdurremo la crittografia quantistica.

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 1012 è 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.


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:

  1. siamo nel caso pessimo
  2. i numeri sono troppo grossi
  3. vogliamo una soluzione esatta
  4. (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:

  1. non è semplicissimo da implementare e
  2.  è 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à.

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:
  1. (x+1) è multiplo di p: (x+1) \equiv 0 \pmod p quindi x = -1 \pmod p
  2. (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:

  1. a^u \equiv 1 \pmod n oppure
  2. 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:
  1.  il primo termine è 1, e quindi tutti i quadrati sono 1.
  2. 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

  1. 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}

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 104 (e 750 minori di 107) 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 107).

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.

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).

Leggi il seguito di questo post »

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.