Questo file in rete: http://www.elegio.it/doc/tn/metodo-lineare-congruente.html

Premessa ( contro un mondo di spioni e delatori assoldati dalle agenzie delle tasse di qualunque Stato per togliere a chi lavora e dare a chi invece no... poverino... )

Quello che scrivo qui è ipernoto agli esperti di teoria dei numeri Ma non è noto alla gente comune ( inclusi i diplomati di un qualche istituto tecnico o i laureati anche in materie scientifiche ).

L'utilizzo pratico di quello che ho scritto qui, cercando di non usare nessun gergo di settore, è la crittografia elementare basata su questo semplice trucco: ogni lettera visualizzata in un documento HTML o XHTML in realtà è un numero UNICODE ( vedere per esempio calcolatrice/archivio-utili-201308.html#n004 ). Se dunque si genera una sequenza di numeri pseudocasuali e si aggiunge ad ogni carattere del testo il numero e si calcola il resto della divisione di questo numero complessivamente pseudocasuale, si ottiene un altro carattere anche lui stampabile senza problema ma tale da rendere incomprensibile il testo.

Ovviamente bisogna adottare vari accorgimenti per non rischiare di generare numericamente un carattere pericoloso perché considerato di controllo dall' HTML.

Qui mi dedico solo al problema di come generare sequenze di numeri pseudocasuali diversi da quelli classici che gli SPIONI potrebbero indovinare.

Sottolineo questo fatto ovvio: chi vuole creare un documento criptato può avvalersi di molti aiutanti che lui può considerare assolutamente fidati ma... non può essere certo della loro fedeltà attuale o futura... Quanti camerieri si sono arricchiti pubblicando libri sulle faccende private dei loro datori di lavoro ! Dunque... anche se rudimentale, un qualsiasi metodo ( algoritmo ) aggiunto a quelli facilmente acquistabili e noti a tutti ... vuol dire essere prudenti e la prudenza, in certi casi, non è mai troppa...

Ovviamente consiglio di fare uso almeno di un programma gratuito per lavorare con grandi numeri interi adatti alla crittografia. Vedere http://www.elegio.it/max/ dove parlo di Maxima con cui è facilissimo controllare se un numero è un numero primo ( digitare primep(257) per controllare se 257 è primo ) e trovare quale è la sua più piccola radice primitiva ossia il più piccolo intero che, moltiplicato per un altro intero genera un intero ( resto della divisione del risultato ) sempre diverso per tanti passi quanto è il valore del numero primo utilizzato. Per esempio in maximese mod(3^257,257) dà ancora esattamente 3 come risultato... ( basta scrivere zn_primroot(257) per scoprire che in questo caso la più piccola radice primitiva di 257 è 3 ).

Generazione di numeri pseudocasuali

Spesso si desidera disporre di sequenze di numeri pseudocasuali senza particolare pretesa sull'effettivo grado di casualità ma almeno tali da non rendere immediatamente percepibile, ad occhio il criterio di generazione della sequenza.

Per ragioni estetiche (semplicità di formulazione) viene spesso usato il metodo moltiplicativo congruente che si basa su questa semplice formula di generazione (scritta in JavaScript ed in cui l'operazione "%" indica il resto della divisione) :

rd = (rd*rp)%pp

Qui si può sperimentare questa formula applicata usando i seguenti valori: pp=2930000000003, rp=2048 e partendo con rd = 1.

Altro esempio utile può essere questo in cui si sono invece usati i seguenti valori: pp=1024000000000007, rp=5 e partendo ancora con rd = 1.

Il piccolo difetto ( ovviabile usando Maxima ) del metodo moltiplicativo congruente sta nel fatto che bisogna disporre di un numero primo (pp) e di un numero così detto "radice primitiva rispetto a pp" ossia di un intero appropriato tale per cui la ripetuta moltiplicazione modulo pp generi la sequenza di numeri più lunga possibile, ossia di pp−1 passi. Non tutti i numeri sono radici primitive di un dato primo per cui prima di usare una coppia rp, pp, bisogna accertare che il numero rp sia effettivamente radice primitiva del primo pp assegnato: in caso contrario la sequenza di numeri pseudocasuale potrebbe avere un ciclo breve o brevissimo ovvero verrebbero generati solo alcuni dei numeri disponibili, compresi tra 1 e pp−1 inclusi.

Se viceversa si desidera generare una sequenza di numeri casuali sicuramente lunga in modo ottimale e senza la necessità di effettuare difficili ricerche di numeri primi e di radici primitive ad essi associate, si può ricorrere al così detto metodo lineare congruente, non basato sulla sola moltiplicazione ma anche sull'addizione di una opportuna costante.

Comunque con Maxima basterebbe scrivere, per esempio,

/* Piccoli primi */
np:0;
for j:1 step 1 thru 60000 do(
primo:j*2+1,
if primep(primo) then(
np:np+1,
proot:zn_primroot(primo),
if proot>60 then disp(concat((2*j+1),
"] Primo con radice primitiva ",proot),primo)
))$print(np);

per scoprire una infinità di numeri primi giganteschi ma facili da gestire e ricordare e corredati dalla loro più piccola radice primitiva...

I primi con la più piccola radice primitiva piuttosto grossa sono abbastanza insoliti. Ho fatto una piccola indagine con Maxima:

/*
Il primo 110881 ha come radice primitiva 69
Il primo 760321 ha come radice primitiva 73
Il primo 5109721 ha come radice primitiva 94
Il primo 17551561 ha come radice primitiva 97
Il primo 29418841 ha come radice primitiva 101
Il primo 33358081 e 39244921 hanno come radice primitiva 107
*/

Per curiosità e per farsi una idea della capacità di Maxima ( o di Mathematica ) di trattare numeri enormi,   2·9⁹¹+1   ossia   152354696091732784678579455441231123500849602804790393448003131489914274686066076039203   è primo ed ha, come radice primitiva 5.

Metodo lineare congruente

Si basa sulla seguente espressione:

rd = (rd*bb+rd+cc)%mm    ; dove 0 < bb < mm−1;

Si noti qui che mm non è necessariamente un numero primo ma può essere un numero qualsiasi di cui però si conoscano i fattori primi. Ad esempio 100, 1000, 10000 hanno comunque due soli fattori primi ossia 2 e 5 e dunque è possibile assegnare ad mm anche una potenza qualsiasi di 10.

Perché la sequenza del metodo moltiplicativo congruente sia la più lunga possibile, ( ossia duri mm passi includendo anche lo zero) bisogna che le costanti bb e cc soddisfino ad alcune facili condizioni ossia:

• cc deve essere primo rispetto ad mm ossia non deve avere nessun fattore in comune con mm. Ad esempio se mm è una potenza di 10 occorre che cc non sia nè pari nè divisibile per 5. Il numero 1 è considerato primo rispetto a qualsiasi altro intero.
• Se mm non è primo allora bb deve essere divisibile per ogni primo che divide mm. Dunque se mm è una potenza del 10 allora bb deve essere divisibile per 2 e per 5.
• Se mm è divisibile per 4 anche bb deve essere divisibile per 4. In altre parole, escluso il caso senza interesse di mm=10, se mm è una potenza di 10 allora bb deve essere divisibile per 20.

Un noto e diffuso generatore di numeri pseudocasuali è il seguente: mm = 256*256*256*256; cc = 1; bb = 69068; ed in effetti obbedisce alle condizioni ora indicate perché mm ha un unico fattore primo ossia 2 mentre bb è divisibile per 4 e per il resto scelto in modo che la sequenza di numeri casuali che viene prodotta soddisfi vari test di misura della casualità ossia sia una buona sequenza quasi realmente casuale.

Provare qui il metodo lineare congruente applicato con i valori suddetti:

È bene ribadire: una terna appropriata di interi bb, cc, mm produce una sequenza ottimale per il metodo lineare congruente ma non genera necessariamente una buona sequenza pseudo casuale. Tuttavia il metodo lineare congruente è utile in tutti quei casi in cui occorra passare per tutti i valori interi non negativi di un intervallo dato senza seguire l'ordine naturale.