Zprime

From Wikinfo

Il mondo ha bisogno dei pazzi, di coloro che nel personale di un proprio mondo, riescono a lasciarsi andare sopra le menti comuni. Se non ci fossero i pazzi non ci sarebbe il progresso, perché questo sarebbe limitato nell'insieme di coloro che ricercano per un premio, di coloro che non vedono realmente le cose. Credo che se ogni legge studiata fosse stata resa vittima di un brevetto permanente, oggi dovremmo pagare qualcuno per imparare, e questo toglierebbe capacità al progresso. Onore a chi ricerca e dedica la propria vita per un piccolo passo, e alle fiamme chiunque si lodi di onori altrui.

—Flavio Bianchetti, Riflessioni

zPrime è un algoritmo ricercato dal vicentino Flavio Bianchetti (15 Gennaio 1988 - ) per determinare se un numero è primo oppure non lo è. Tuttavia, come poi verrà descritto, può essere anche considerato allo stesso modo del crivello di Eratostene come un procedimento per il calcolo delle tabelle di numeri primi fino ad un certo numero n prefissato.

Contents 1 Le origini 1.1 Il nome 1.2 L'idea 2 L'algoritmo 2.1 Analisi degli step 2.2 Logica degli step 3 Caratteri di demerito 4 Implementazione dell'algoritmo

Le origini

Il nome

Il nome dell'algoritmo deriva dall'unione del prefisso "z", tipico di tutti i progetti proposti da Flavio Bianchetti, e dalla parola "Prime". Il suffisso sta a ricordare la lettera iniziale del nick del suo ideatore, zPlus; la parola annessa deriva invece da "prime numbers", il corrispondente inglese all'italiano "numeri primi".

L'idea

zPrime è stato voluto come algoritmo per la ricerca dei due numeri primi, fattori di un numero ottenuto dalla moltiplicazione di questi, ignoti. Successivamente il suo significato è stato esteso alla capacità di decidere se un certo numero è certamente primo oppure certamente non lo è. Data poi la veloce convergenza dell'algoritmo è possibile utilizzarlo in alternativa al crivello di Eratostene per il calcolo di una tabella di numeri primi in un range prefissato (a, b) dove a e b sono i due estremi del range.

L'algoritmo

zPrime ricerca i due fattori massimi che moltiplicati tra loro producano il numero desiderato, in questo modo è veloce la determinazione di un numero non primo. Osservando se uno dei due fattori è uguale 1, si è trovato che quel numero è primo. E' da notare come zPrime non sia un algoritmo di fattorizzazione del numero, ma di determinazione della natura prima del numero; non restituirà quindi la lista dei fattori primi che lo producono, ma solo i due fattori massimi che bastano per dimostrare che un certo numero è primo oppure non lo è.

Gli step dell'algoritmo:

• scelta di un certo numero n per il quale determinare il tipo
• calcolo di
• inizializzazione di α = trunc(n) e β = α + 1
• calcolo di γ = αβ
• se γ > n allora α viene decrementato di una unità e poi si torna a ricalcolare γ
• se γ < n allora β viene incrementato di una unità e poi si torna a ricalcolare γ
• se γ = n allora l'algoritmo è riuscito a determinare i due massimi valori che moltiplicati permettono di ottenere n, e quindi si è scoperto se il numero è primo oppure no.

Analisi degli step

• calcolo della radice: calcolando la radice quadrata di un numero è istantaneamente osservabile se questo è un quadrato perfetto oppure no. In oltre, con n prodotto di due numeri e non quadrato perfetto, calcolando la radice quadrata è istantaneamente trovato un numero sicuramente compreso nell'intervallo ]α;β[.
• inizializzazione di α e β: questi due termini dipendono dall'unità minima che si intende considerare. Nel calcolo di numeri primi interi considereremo l'unità minima uguale a 1, quindi prendendo la parte intera di η ed il suo numero intero successivo, si conoscono i due valori prossimi ad η.
• calcolo del prodotto γ = αβ: il calcolo del prodotto permette di determinare se questo è uguale al numero di partenza, e quindi di capire se si è giunti alla conclusione di aver trovato i due fattori cercati.
• γ > n: se il prodotto "i"-esimo che abbiamo ora è maggiore del numero di origine, vuol dire che sicuramente il fattore più piccolo è troppo elevato, e quindi dev'essere decrementato.
• γ < n: analogamente a sopra, se il prodotto "i"-esimo è minore del numero di origine, è necessario incrementare il fattore maggiore.
• se γ = n: il caso di ugualianza sta a significare che l'algoritmo ha trovato i due fattori che stiamo cercando, che corrispondono ai due massimi possibili. In questo caso possiamo determinare se il numero è primo oppure no guardando il valore di α.

Logica degli step

E' necessario considerare la distanza λ come un segmento con estremo inferiore α, estremo superiore β e lunghezza β - α. L'estremo inferiore può solo essere decrementato, e quello superiore può essere solo incrementato. La lunghezza aumenta di una unità ad ogni cambio del valore di uno degli estremi, in questo modo si riesce sempre a rimanere in un intorno del numero di origine nel tentativo di ottenere i due fattori. Questo algoritmo converge rapidissimamente nel trovare i due fattori se questi sono sequenzialmente vicini, anche se molto grandi, per esempio:

A = 4215631267456
B = 4215631267498
n = AB = 17771546983329737517945088

α = 4215631267476
β = 4215631267477
γ = αβ = 17771546983325521886678052

è chiaro che in pochi step possiamo già ottenere il risultato: il numero non è primio ed in questo caso sia α che β coincideranno con i fattori di partenza. Nel caso di numero d'origine ottenuto dal prodotto di due numeri primi, l'algoritmo restituirà esattamente i due numeri primi che l'anno prodotto. Questo è da osservare in quanto metodo utilizzato negli algoritmi di cifratura come RSA che calcolano un numero come prodotto di due primi.

Caratteri di demerito

L'algoritmo, nonostante capace di convergere rapidamente (es: 999999999989 viene dichiarato primo in pochi secondi lavorando su una macchina di uso desktop comune con Intel Pentium 4 HTT single core 2.8GHz, ram 512MB DDR2 e hdd s-ata 7200rpm) è sconveniente nel caso di chiavi con differenza in valore assoluto tra i due fattori molto alta. Quindi risulterà più performante più i numeri hanno una distanza minore, mentre per contro una chiave costruita come prodotto tra il numero 3 ed un numero a molte più cifre risulterà più difficile da trovare. Oltre a questo, nonostante capace di convergere rapidamente al risultato, risulta lento nel determinare numeri primi molto grandi.

Implementazione dell'algoritmo

Note: C++ source code implementato con Dev-C++. Questa è una versione molto semplice che non tiene conto di tutti i numeri composti da più di 2 cifre che terminano per 0, 2, 4, 5, 6, 8, e di altri casi che permetterebbero di escludere numeri a priori.

<source lang="c">

1. include <iostream>
2. include <math.h>

using namespace std;

int main() {

 cout << "number (> 0 and < 2^32): ";
 unsigned int i;
 cin >> i;
 double rad = trunc(sqrt(i));
 unsigned int min = (unsigned int)rad;
 unsigned int max = min + 1;
 unsigned int p = min * min;

 if(p == i) {
   cout << i << " is a perfect square..." << endl;
   system("PAUSE");
   return 0;
 }

do {

 p = min * max;
 if(p < i) {
   max++;
   continue;
 }
 if(p > i) {
   min--;
   continue;
 }
 cout << "min: " << min << endl << "max: " << max << endl << i << ((min == 1) ? " is a prime number" :	" is NOT a prime number") << endl;
 system("PAUSE");
 return 0;
 } while(true);

} </source>