In questa pagina raccogliamo qualche programma in C/C++ o PARI/GP: naturalmente non abbiamo alcuna pretesa di completezza, né abbiamo velleità stilistiche. Si tratta semplicemente di un servizio ai nostri Lettori che potranno utilizzare il nostro codice sorgente come base per fare di meglio. Per esempio, come esercizio consigliamo di riscrivere tutto il codice C/C++ utilizzando la libreria CLN (Class Library for Numbers) per trattare interi arbitrari.

Script PARI/GP

Questi sono gli script dati nel Capitolo 9, nell'ordine in cui compaiono nel testo. Si riferiscono alla versione 2.1.4 di PARI/GP.

1. Verifica di congetture
   • Congettura di Goldbach §9.5, pagina 262
   • Congettura di Hardy e Littlewood §9.5, pagina 265
2. Codifica e decodifica con RSA §9.6.2, pagina 271; vedi anche il §5.9
3. Criteri di primalità
   • Metodo AKS §9.6.3, pagina 276; vedi anche il Teorema 6.4.2.
   • Metodo AKS-seconda versione si riferisce alla versione aggiornata del Teorema 6.4.2, si veda l'Errata
   • Verifica se l'input è un generatore §9.6.3; funzione ausiliaria nell'Algoritmo AKS
   • Verifica se l'input è potenza di un primo §9.6.3; funzione ausiliaria nell'Algoritmo AKS
   • Test di Miller-Rabin §9.6.3, pagina 278; vedi anche il Teorema 3.8.4
4. Algoritmi di fattorizzazione
   • Algoritmo di Fermat §9.6.3, pagina 279; vedi anche il §6.5.2
   • Algoritmo di Fermat-Lehman §9.6.3, pagina 280; vedi anche il §6.5.2
   • Metodo p − 1 di Pollard §9.6.3, pagina 281; vedi anche il §6.5.5

Alcuni degli script precedenti possono essere un po' migliorati usando delle caratteristiche di versioni piú recenti di PARI/GP. In particolare i seguenti possono essere usati a partire dalla versione 2.2.9.

1. Codifica e decodifica con RSA §9.6.2, pagina 271; vedi anche il §5.9

1. Legge di gruppo
   Legge moltiplicativa di gruppo in Z_N §1.2-1.3, pagine 21-32.
2. Algoritmo di Euclide e formula di Bezout
   Algoritmo di Euclide esteso §2.2, pagine 35-36; vedi anche il §6.2, pagine 163-165.
3. Crittografia Classica
   • Metodo di Cesare §5.3, pagine 91-92.
   • Metodo di Vigenere §5.3, pagina 92.
4. Crittosistema di ElGamal
   Codifica e decodifica con ElGamal §5.11, pagina 149.
5. Tabelle di Primi
   • Crivello di Eratostene §6.3, pagine 165-166.
   • Crivello di Eratostene velocizzato §6.3, pagine 165-166.
6. Algoritmi di fattorizzazione
   Divisione per tentativi §6.5.1, pagina 175.
7. Metodo dei quadrati ripetuti
   Metodo dei quadrati ripetuti §6.9.2, pagine 195-196.

Programmi in C/C++

Questi programmi illustrano gli algoritmi descritti nel libro: per semplicità sono scritti in C++ standard, e per la maggior parte non richiedono l'uso di librerie esterne per i calcoli con interi a lunghezza arbitraria. Questo significa che, dal punto di vista delle applicazioni alla crittografia, questi programmi non sono molto realistici.

N. B. Avvertiamo che alcuni compilatori non accettano dichiarazioni di long long integer (o le trasformano tacitamente in long integer), e di conseguenza, in questo caso, i risultati ottenuti compilando i nostri programmi potrebbero discostarsi in modo anche rilevante da quelli indicati nel libro.
Inoltre, i valori assegnati staticamente ad alcune variabili potrebbero creare problemi di allocazione di memoria su alcuni computer. In questo caso consigliamo di diminuire i valori indicati nei nostri programmi.
Questi programmi sono stati provati con
g++ (GCC) 3.4.2
Copyright (C) 2004 Free Software Foundation, Inc.

1. Aritmetica di base Questa piccola libreria contiene le operazioni aritmetiche di base, e deve essere inclusa negli altri programmi.
   • Algoritmo di Euclide, §6.2
   • Algoritmo di Euclide esteso, §6.2
   • Moltiplicazione veloce modulo n, §6.9.1
   • Esponenziazione veloce modulo n, §6.9.2
   • Divisione con resto, §6.9.4
2. Ricerca di pattern in un testo Vedi la didascalia della Figura 5.3, §5.3
3. Codifica-decodifica RSA §5.9
4. Crivello di Eratostene §6.3
5. Algoritmi di fattorizzazione
   • divisione per tentativi §6.5.1
   • fattorizzazione alla Fermat §6.5.2
   • fattorizzazione alla Fermat-Lehman §6.5.2
   • metodo ρ di Pollard §6.5.4 (N.B.: Questo programma ha bisogno della libreria CLN).
   • crivello quadratico §6.6.1
6. Ricerca di un generatore modulo p: Algoritmo di Gauss §6.7
7. Calcolo del logaritmo discreto modulo p: Algoritmo di Shanks §6.8.1

1. Crivello di Eratostene
2. metodo ρ di Pollard (N.B.: Questo programma ha bisogno della libreria NTL).

Ultimo aggiornamento: 15.12.2010: 12:55:01.