In rete: www.elegio.it/doc/tn/altaprecisione_modulare.html ( aggiornamento del 20160204 )
Alta precisioneQuesta pagina contiene una microlibreria JavaScript che consente di fare calcoli in algebra modulare utilizzando interi in multipla precisione. Di questa libreria esiste anche una versione Fortran particolarmente adatta a calcoli intensivi piuttosto che dimostrativi.Ovviamente il pregio di Javascript è quello di essere disponibile gratuitamente in ogni ambiente di calcolo se si dispone di un navigatore non troppo obsoleto (Tipo Internet Explorer 5 o più, Netscape, Firefox, ( https://support.mozilla.org/it/ ) Opera, Amaya etc...). Dunque gli algoritmi scritti in JavaScript servono per scopi didattici-illustrativi ma la traduzione degli algoritmi in un altro linguaggio non interpretato, quale il Fortran, Java, Pascal, C++ o C# etc., è molto semplice, visto le molte somiglianze che JavaScript ha con i più diffusi linguaggi compilabili.
Nella libreria usata in questa pagina, un intero modulare è un vettore con l'elemento 0
costituente la cifra meno significativa e con cifre tutte non negative.
Modificando le costanti CIFRE e CIFRX si può modificare sia la lunghezza dei vettori usati
come interi sia il numero di cifre significative usate in ogni elemento.
Ora CIFRE vale {
Dato il valore posseduto da CIFRX uso la base { La piccola libreria qui proposta possiede, come suo pregio fondamentale, la semplicità e dunque la facile riprogrammabilità nel linguaggio che si preferisce usare per qualsivoglia ragione soggettiva. Nell'effettuare il prodotto tra interi, non viene fatto uso dell'algoritmo notoriamente, asintoticamente più veloce ossia quello basato sulla trasformata veloce di Fourier perché ciò avrebbe comportato un rilevante aumento della complessità di questa microlibreria. In pratica, comunque, si può constatare che questa libreria è ragionevolmente veloce per fare controlli sulla primalità di interi non piccolissimi, fino ad oltre la trentina di cifre decimali, ossia per interi comunque adeguati per sperimentazioni didattiche. Alcuni numeri primi da sperimentare: (1019−1)/9 ossia 19 uni consecutivi in base 10 è primo, con radice primitiva 3 o 317 oppure 19 o 1917 (calcolo fatto usando la funzione MultiplicativeOrder di Mathematica ), e così pure (1023−1)/9 ossia 23 uni consecutivi in base 10, con radice primitiva 11 o 113 o 117. È primo anche 1024·1012+7 ossia 1024000000000007 e una sua radice primitiva è 5 o una qualsiasi potenza dispari di 5 visto che è un primo di Sophie Germain (come lo è 11 ma non 13... Sono primi rari con frequenza proporzionale al quadrato del numero di cifre significative che posseggono mentre i primi in genere hanno frequenza linearmente proporzionale al numero di cifre significative che posseggono. Tra un miliardo e 10 miliardi i primi di Sophie Germain sono circa solo lo 0.3 % ) . È inoltre primo 109+7 con radice primitiva 5, e 1015+37 con radice primitiva 2 o 8 o 32 o 512 o 2048 o 8192 o 32768 etc... Un primo utile quando si lavora in quadruplice precisione in Fortran è 1030+57. Ecco, d'altra parte, qualche pseudoprimo forte da mettere alla prova: 1373653, 12327121, 25326001, 161304001, 960946321, 1157839381, 3215031751, 2152302898747, 3474749660383, 341550071728321. Tra i numeri primi di una certa utilità, penso che meritino attenzione quelli che fanno parte di sequenze di primi di Sophie Germain dove la sequenza è fatta da numeri primi che sono primi anche quando li si raddoppia e si aggiunge una unità per ottenere un altro dispari. Una sequenza notevole è quella costituita da 89, 179, 359, 719, 1439, 2879 tutti primi. Tranne il numero di inizio, ossia in questo caso 89, tutti gli altri sono primi di Sophie Germain e dunque sono numeri che si prestano ad essere usati in crittografia visto che il logaritmo discreto risulta di calcolo estremamente difficile poiché non risulta applicabile il classico algoritmo di Silver, Pohlig ed Hellman. Ecco qualche sequenza notevole (dove per livello si intende il numero di primi consecutivi generati a partire dal più piccolo: Naturalmente le sequenze di questo tipo sono tanto più rare quanto più sono lunghe e la pagina demo in versione Fortran della microlibreria di algebra modulare include appunto una subroutine pensata per l'individuazione di tali sequenze insolite. Noto, a proposito di crittografia, che mai e poi mai bisogna dormire sugli allori e credere che un metodo sia sicuro. È dunque sempre meglio usare barriere multiple e cercare di non provocare la curiosità, passando inosservati. Chi confidasse sulla insormontabile difficoltà del calcolo del logaritmo discreto dovrebbe cercare in rete i nomi di Damian Weber and Thomas Denny che sono riusciti a fare cose che 10 anni prima sarebbero sembrate... stratosferiche. Dunque meglio non rischiare di incocciare il genio dei decrittatori e soprattutto... cercare di non dare nell'occhio.... [ ;-) ]. |