Numeri primi: concetti-chiave e peculiarità

1

teodorocristiano@tiscali.it

Numeri primi

Creazione e verifica di numeri primi relativamente grandi

(Production and Verification of quite large prime numbers)

3000000000000000000000000000000000000000000000000000000000000000000000000000000001 è primo?

Sommario: l’articolo propone ed illustra un algoritmo dedicato a verificare se un numero è primo o composto.

A tale scopo viene realizzato un programma scritto in Qbasic, in grado di verificare non solo la primalità di un numero, ma questione ancora più interessante, a generare numeri primi. Per quel che riguarda l’effettivo algoritmo scelto, si è preso in considerazione l’algoritmo di Rabin – Miller, che è di tipo probabilistico, ma con il quale si riesce a riconoscere con una probabilità alta a piacere da sfiorare praticamente la certezza ed in tempi accettabili anche con l’uso di un PC non eccessivamente sofisticato, se un numero è primo.

Perché l’argomento preso in esame sia di qualche interesse nella teleinformatica, con applicazioni in particolare in campo crittografico, con il programma realizzato si prendono in considerazione soprattutto numeri relativamente grandi, costituiti da diverse decine o addirittura da qualche centinaio di cifre.

Nell’articolo si pone l’accento sulle maggiori difficoltà e sulle principali problematiche che si incontrano nella realizzazione dell’algoritmo e quindi del programma. Poiché vengono trattati anche numeri grandi, l’effettuazione delle quattro operazioni aritmetiche può essere eseguita solo tramite opportune istruzioni in modo di poter lavorare in aritmetica a precisione multipla.

In particolare, per l’operazione della divisione, che rispetto alle altre tre operazioni elementari risulta più complessa da programmare, è stato realizzato ed impiegato un metodo originale. Per l’impiego efficace dell’algoritmo considerato occorre generare un opportuno insieme di numeri casuali di diverso ordine di grandezza.

Viene anche illustrato l’uso della aritmetica modulare: in effetti solo con l’ausilio di tale tipo di aritmetica si possono eseguire i calcoli necessari; calcoli che altrimenti implicherebbero nelle operazioni aritmetiche un’enorme quantità di cifre non più gestibili anche con l’utilizzo dell’aritmetica a precisione multipla.

È pur vero che esistono pacchetti matematici, quali MATHEMATICA, MAPLE, ecc., che, tra i tantissimi campi della matematica cui sono dedicati, risolvono in modo brillante anche l’argomento trattato nel presente articolo, ma è altrettanto vero che essi forniscono ovviamente scarse informazioni e delucidazioni sulle soluzioni realizzate ed impiegate, e sulle problematiche che si sono dovute affrontare e superare per ottenere i risultati desiderati.

Nell’articolo vengono illustrati alcuni risultati per numeri di varia grandezza in due Tabelle, una relativa alla verifica della primalità o meno di un numero, l’altra relativa alla creazione di un numero primo, con l’indicazione dei tempi necessari di calcolo lavorando in QBASIC.

Si mettono in evidenza anche i tempi di calcolo estremamente grandi che sarebbero necessari se venissero utilizzati metodi classici (crivello di Eratostene, Divisioni successive, ecc.). Sono inoltre mostrati alcuni esempi relativi a risultati ottenuti nella creazione e nella verifica di numeri primi. Infine viene riportato il listato del programma.

Abstract: the aim of this paper is to suggest and to illustrate an algorithm dedicated to verify the number primality. For this purpose we have implemented a program in Qbasic language enabled to verify the primality also of quite large numbers and, argument more interesting, to produce primes composed by several tens of digits or some hundreds of digits.

To deal with large prime it is an essential topic in several scientific and technical fields, specifically in the modern cryptography applied to communication. The paper stresses the bigger difficulties and the main problems in the program implementation, specially in carrying out multiple precision arithmetic for the four arithmetical operations, in particular for the division.

We use the Rabin – Miller probabilistic algorithm and we are able to identify the numbers primality or to produce primes with the requested probability in acceptable time also using an unpretentious PC. For the effective utilization of this algorithm it is essential to produce a suitable set of random numbers having different order of magnitude.

We explain also the first principles of modular arithmetic because actually only using this arithmetic we can to carry out the indispensable computation, otherwise impossible. Mathematical Software packages are available (MATHEMATICA, MAPLE, etc.) which can powerfully solve the matter of this paper.

But they provide poor explanations as regards the feasible solutions. In the paper we illustrate a few outcomes for numbers of different magnitude inside two Tables, one pertinent to primality verify, and the other relevant the primes production with regard to Qbasic computation time.

We also point out the extremely computation high time using classical methods and algorithms (Sieve of Eratosthenes, Trial Division, etc.). We show as well some examples regarding the production and verification output. At last we display the program list. 1

2

1 - Introduzione

Il presente articolo è dedicato ai numeri primi relativamente grandi.

Parleremo infatti di numeri primi costituiti anche da diverse decine di cifre (20, 50, 70, 100, 150, 300 e più cifre.....), calcolabili in modo esatto solo con l’aritmetica a precisione multipla.

L’intento è quello di mostrare come si possa costruire un programma, nel caso specifico usando un linguaggio evoluto quale il Qbasic, per verificare in tempi brevi se numeri anche di valore sufficientemente elevato sono primi o composti e, argomento ancor più interessante, per creare numeri primi relativamente grandi.

I numeri che tratteremo saranno naturalmente degli interi dispari e potranno essere formati a partire da poche cifre sino a 500 cifre.

L’algoritmo utilizzato è quello noto nella teoria dei numeri come test di primalità di Rabin – Miller [1], [2], [3].

Perché utilizzare questo tipo di test e non usufruire invece di uno dei metodi classici: Crivello di Eratostene, Divisioni successive, ecc.?

La risposta è semplice: questione di tempo di calcolo per arrivare al risultato.

Poniamo il caso di prendere in esame numeri composti da due soli fattori abbastanza grandi, ad esempio dello stesso ordine di grandezza (numeri che chiameremo composti difficili) o numeri che effettivamente sono primi.

Con i metodi classici, la verifica della primalità o meno di un numero è necessariamente legata all’algoritmo della sua scomposizione in fattori, per cui se il numero è effettivamente primo od un composto difficile i tempi di verifica o peggio, i tempi per la creazione di primi, già per numeri costituiti da sole 14 cifre risultano più lunghi di quelli ottenibili con l’impiego del suddetto tipo di test.

Figuriamoci per numeri di 50 e più cifre: questi tempi diventerebbero spaventosamente lunghi.

Si vuole qualche dato?

Si consideri in modo ottimistico anche per un PC abbastanza potente di impiegare solo un centesimo di secondo per la verifica della primalità o meno di un numero di 14 cifre (che in effetti sia un primo o un composto difficile) utilizzando il metodo delle divisioni successive (trial division) con divisori, oltre a 2 ed a 3, della forma 6h ± 1 con:

 

−

p 1 +

  1

h = 1,2,3,4,.........., , metodo questo che risulta essere uno dei più efficienti fra quelli classici [4].

 

6

 

Ebbene, estrapolando questo tempo per il calcolo di quelli relativi a numeri ancora più grandi, si otterrà per tali tipi di numeri, i seguenti tempi t di calcolo:

• t = 10 secondi per un numero di 20 cifre
• t > 11.57 giorni per un numero di 30 cifre
• t > 3171 anni per un numero di 40 cifre
• t > 31 miliardi di anni per un numero di 54 cifre

Sì, si è letto bene: 31 miliardi di anni!

Per rendersi conto di quanto sia incomparabilmente lungo questo tempo, si immagini di aver terminato alla data attuale la verifica o la creazione di un numero di 54 cifre; ebbene, si sarebbero dovuti iniziare i calcoli molto tempo prima del Big Bang, cioè “molto prima” della nascita (14 miliardi di anni?) dell’attuale Universo.

Utilizzando invece l’algoritmo ed il test impiegati nel programma illustrato i tempi di calcolo per la verifica o la creazione diventano irrisori a paragone dei precedenti.

Ad esempio, utilizzando un comune PC dotato di microprocessore a 2 GHz e 512 MB di RAM per la verifica riguardante un generico numero di 77 cifre del tipo composto difficile o effettivamente primo il tempo risulta non superiore a 6 secondi (vedi tabella n° 1); per la creazione di un numero primo sempre di 77 cifre i tempi di elaborazione risultano e un po’ più lunghi ma sempre contenuti in media entro 8 secondi.

Ci si può domandare ora quale importanza d’interesse applicativo possono avere, oltre quello puramente speculativo, numeri primi o composti difficili così grandi.

Una risposta è da ricercarsi nel campo della crittografia, campo che ha delle applicazioni molto interessanti nella teleinformatica e che si sta sviluppando in modo sempre più notevole, man mano che cresce la necessità di trasmettere a distanza in maniera protetta e sicura qualsiasi tipo d’informazione.

In effetti alcuni sistemi crittografici, fra i più robusti, si basano su algoritmi in cui risulta indispensabile la possibilità di verificare e soprattutto di creare in tempi sufficientemente contenuti numeri primi casuali costituiti da diverse decine di cifre (80, 154, 161, 308, 312, 350 cifre e oltre) per formare con essi dei composti difficili. 2

3

Basti pensare alla importanza che assume la verifica e la creazione di numeri di questo tipo per la costruzione delle chiavi, pubblica e segreta, nell’algoritmo RSA, il più noto e diffuso sistema crittografico a chiave pubblica.

Prima però di descrivere il programma realizzato occorre dire qualcosa in merito all’algoritmo impiegato e per illustrarlo occorre fornire qualche nozione tratta dalla teoria dei numeri.

Si cercherà di usare una terminologia non troppo specialistica.

Algoritmo di Rabin - Miller

2 -

Un numero p intero dispari è detto pseudoprimo forte alla base b (dove b è un intero) se, posto p sotto la forma p = 1 + 2^k · q con q dispari, viene soddisfatta una delle seguenti condizioni:

q

b

a) il resto della divisione di per p ha valore 1 o valore p - 1

oppure, non avendo il resto tali valori,

b) proseguendo con il calcolo si ottiene un resto di valore p - 1 nella divisione per p di uno dei seguenti termini:

( )

−

k 1

2 3 4

2 q 2 q

2 q 2 q 2 q

b b

b b b

, , , , ...................................

Ebbene, considerato un numero p dispari, il summenzionato test di Rabin -Miller consiste nel controllare se p è uno pseudoprimo forte per diverse basi, ciascuna delle quali è un numero intero scelto in modo casuale nell’intervallo numerico da 2 a (p-1); se p non risulta essere uno pseudoprimo forte, in riferimento anche ad una sola delle basi scelte, il numero p è certamente composto; se invece il numero p risulta pseudoprimo forte per tutte le basi scelte, si dimostra che esso è probabilmente primo, con una probabilità che non lo sia

1

minore di , dove “nb” è il numero delle basi considerate [5].

nb

4

Se ad esempio si effettua la verifica della primalità di un numero scegliendo un numero nb di basi pari a 25 e si riscontra che esso risulta essere pseudoprimo forte per tutte e 25 le basi scelte, lo si può considerare senz’altro primo. 1, minore cioè di 0.000000000000001,

Infatti la probabilità che non lo sia è minore di 25

4 1

equivalente a dire che esso è primo con una probabilità maggiore di (1 - ) , cioè maggiore di

25

4

0.999999999999999).

Per rendersi conto di come si possa tranquillamente ritenere primo un numero che abbia superato il test con 25 basi, si può fare la seguente considerazione:

la probabilità che il computer tratti in modo errato qualche bit fra la mole enorme di bit manipolati nei calcoli elementari, a causa di possibili disturbi (rumore) sul suo hardware si dimostra essere molto più alta del valore 0.000000000000001 suddetto, cioè della probabilità che il numero in esame dichiarato primo sia in realtà composto.

Un esempio banale ma più efficace può essere il seguente: giocando al superenalotto è risaputo quanto sia

1

difficile vincere; ciò perché la probabilità di indovinare i 6 numeri è molto piccola (pari a =

622614630

0.0000000016); ebbene questa così piccola probabilità è in effetti molto più elevata (più di un milione di volte) della probabilità che il numero dichiarato primo sia invece composto.

Ma si ritorni al test: ci si limiterà prima a illustrare un programma relativo a numeri sufficientemente piccoli da poter essere trattati con la sola aritmetica a doppia precisione disponibile su qualsiasi PC.

Questo allo scopo di mettere in evidenza le operazioni principali che realizzano il test, operazioni che poi si ritroveranno debitamente espresse in aritmetica a precisione multipla nell’effettivo programma dedicato ai numeri grandi il cui listato è riportato in coda all’articolo.

Il programma in pratica traduce in istruzioni del linguaggio Qbasic il test di Rabin-Miller esposto sopra.

Prima però di illustrarlo occorre dedicare un po’ d’attenzione a come effettuare il calcolo del resto della

q

b per p.

divisione di 3

4

Se si provasse ad effettuare il calcolo in modo tradizionale, cioè come è stato insegnato a scuola, si

q

b, quindi si effettuerebbe la divisione di tale valore per il

calcolerebbe prima l’effettivo valore del dividendo q

b

divisore p trovando quoziente e resto. Questo modo di procedere però, quando è un numero grande, non è più praticabile anche per valori modesti di b e di q.

Si consideri ad esempio il numero primo p = 829459 = 1 + 2 · 414729 (quindi con k = 1 e q = 414729)

414729

3

q

b 414729

3

per p, vale a dire il resto di; ma

Posto b = 3, si voglia trovare il resto della divisione di 829459

è un numero costituito da ben 197877 cifre, cifre che riempirebbero da cima a fondo più di 25 pagine come questa.

L’operazione di divisione con un dividendo così enorme è praticamente impossibile da effettuare anche utilizzando l’aritmetica a precisione multipla.

E allora quale altra via si può escogitare per trovare tale resto?

3 – Aritmetica modulare

A questo punto ci viene in aiuto l’aritmetica modulare ideata dal grande matematico C.F. Gauss.

Senza entrare troppo in merito a questo tipo di aritmetica, per la quale si rimanda ai Riferimenti [6], [7], basterà illustrare la seguente proprietà facilmente dimostrabile, riguardante i numeri interi.

·

a b) per un dato numero p risulta

Considerati due numeri a e b, il resto r della divisione del prodotto (

· r r

r r

essere il resto della divisione del prodotto ( ) per il numero p dove ed sono i resti trovati

a b

a b ·

r r

rispettivamente nelle divisioni di a per p e di b per p. Naturalmente, se il valore di ( ) fosse minore di

a b

·

r r

p il resto r sarebbe il prodotto stesso ( ).

a b · ·

a b r r

a b

Indicando tutto ciò sinteticamente scriveremo: resto di = resto di

p p

a b

r r

dove = resto di ; = resto di

a b

p p · 2

2 r

b r r b

b b

Ora, sfruttando tale proprietà, se b = a si ha: resto di = resto di = resto di;

p

p p

2

4 r

b b

r

Se poi si volesse trovare il resto di, chiamato il resto di si avrebbe:

2

p p

· ·

4 2 2

b b b r r

2 2

r = resto di = resto di = resto di.

4 p p p

Per mettere in evidenza l’importanza dell’applicazione della suddetta proprietà per semplificare i calcoli quando si voglia trovare il resto nella divisione per un dato numero della potenza di un altro numero, nel

19

17

riquadro viene mostrato in dettaglio il seguente esempio elementare: trovare il resto di. Si indicherà per

11

n

17

r

semplicità di esposizione con il resto di dove n è un intero qualsiasi; si ricordi inoltre

n 11 n

n 17

17

dall’aritmetica che, posto n = l + m, la generica potenza può essere espressa come segue: =

·

+ l m

l m 17 17

17 =

Come si può notare i calcoli mostrati nel riquadro sono molto semplici e si possono fare addirittura mentalmente.

19

17

Se provassimo ad ottenere il resto eseguendo direttamente il calcolo di dovremmo trovare prima il valore

11

19

17

effettivo di, che è un numero di ben 24 cifre, e poi effettuarne la divisione per 11, calcolando così il resto;.

è evidente la maggiore complessità di calcolo, anzi si può constatare che il nostro computer, pur utilizzando la

r, calcolato

doppia precisione per eseguire i suoi calcoli, fornirebbe un risultato errato per il valore di 19

invece sopra così facilmente. 4

5