In rete: www.elegio.it/doc/tn/altaprecisione_modulare.html ( aggiornamento del 20160204 )

Alta precisione

Questa 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 {?} mentre CIFRX vale {?} e tale valore, modificato, non deve mai superare 15 visti i limiti intrinsici di Javascript nel rappresentare variabili intere.
Dato il valore posseduto da CIFRX uso la base {?}, un valore relativamente piccolo rispetto a quanto consentirebbe JavaScript. Uso solo potenze di 10 in modo da poter leggere e interpretare il numero senza dover fare complicate conversioni di rappresentazione.

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.

Specifica dei dati di ingresso

Gli spazi bianchi tra le cifre vengono ignorati perché, in tal modo, è più facile scrivere numeri molto grandi.
Modificare il dato che interessa e poi cliccare in un punto qualsiasi della pagina ma esternamente al campo modificato.

: per aggiornare aa
: per aggiornare bb
: per aggiornare mm
Aggiornamenti applicati : 0

Che calcolo vuoi fare?

Primi sperimentabili:
  1. 11111111111111111111111 con radice primitiva 11
  2. 11111111111111111111117 con radice primitiva 2
  3. 11111111111111111111201 con radice primitiva 12
  4. 11111111111111111111251 con radice primitiva 3
  5. 12345678901111111111133 con radice primitiva 2
  6. 1024000000000007 con radice primitiva 5
  7. 90000000000000000000001 con radice primitiva 11
  8. 40000000000001 con radice primitiva 3
  9. 12345678901234567891 con radice primitiva 2
  10. 122333444455555666666033 con radice primitiva 10
  11. 1122334455667788990013 con radice primitiva 5
  12. 1122334455667788990012307 con radice primitiva 2


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:

  • Livello 6: 89, 63419, 127139, 405269, 810809, ..., 181774409
  • Livello 7: 1122659, ..., 183561929
  • Livello 8: 19099919
  • Livello 9: 85864769
  • 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....
    [ ;-) ].

    Vedere anche:

  • Qualche nozione di crittografia per quanto poco ne sappia io...
  • http://www.elegio.it/utili/
  • http://www.elegio.it/omnia/
  • http://www.elegio.it/doc/tn/vigenere_pi.html
  • http://www.elegio.it/doc/tn/
  •