Don't take life too seriously: it's just a temporary situation

Primi forti (II)

Teoria dei numeri 

Un numero primo p si dice “forte” se:

  • p – 1 ha un fattore primo grande q;

  • q – 1 ha un fattore primo grande (rispetto a q);

  • p + 1 ha un fattore primo grande.

Generalmente per “fattore primo grande” rispetto a n s’intende maggiore della radice quadrata di n, ma spesso ci s’accontenta di molto meno.

Per esempio, 173 è un primo forte perché:

  • il massimo fattore primo di 172 è 43, maggiore della radice quadrata di 173;

  • il massimo fattore primo di 42 è 7, maggiore della radice quadrata di 43;

  • il massimo fattore primo di 174 è 29, maggiore della radice quadrata di 173.

 

La definizione deriva dal fatto che per alcuni algoritmi di scomposizione i fattori primi di questo tipo sono più difficili da trovare, quindi un numero che sia il prodotto di due primi forti è molto più difficile da scomporre.

Tuttavia, dato che sono stati sviluppati algoritmi di scomposizione che non hanno questa caratteristica e che trovare primi forti di molte cifre richiede tempo, la raccomandazione di utilizzare solo prodotti di primi forti nelle applicazioni crittografiche è stata abolita.

 

Il metodo più semplice per trovarli è scegliere un primo r delle dimensioni desiderate, cercare un intero non troppo grande n tale che q = nr + 1 sia primo, quindi cercare un intero non troppo grande m tale che p = mq + 1 o p = mq + 1 siano primi. A questo punto però bisogna scomporre p + 1 o p – 1 per verificare che il massimo fattore primo sia abbastanza grande e questo può richiedere molto tempo; spesso se la scomposizione si rivela troppo difficile si preferisce ricominciare con nuovi valori di m o n.

Un metodo migliore è trovare un primo q come sopra, poi un primo s con circa lo stesso numero di cifre e trovare i minimi interi m e k, che risolvano l’equazione mq + 1 = p = ks – 1: se p è primo, è forte, altrimenti ri cambianno r, q o s e si riprova.

Negli anni, dato l’interesse per le applicazioni crittografiche, sono stati sviluppati vari metodi efficienti per la ricerca di primi forti, poi nel 1999 Rivest e Silverman illustrarono il problema della scomposizione e i nuovi metodi apparsi negli anni precedenti in un articolo, che fece scemare l’interesse verso i primi forti.

 

I primi forti minori di 1000 sono: 43, 67, 173, 277, 283, 317, 347, 523, 557, 619, 709, 743, 787, 823, 941, 947, 997.

Naturalmente i numeri primi usati nelle applicazioni crittografiche serie sono enormi, di centinaia o addirittura migliaia di cifre.

Contattami

Potete contattarmi al seguente indirizzo bitman[at]bitman.name per suggerimenti o segnalazioni d'errori relativi a questo articolo.