Tesina n. 1:

Tesina n. 1:

Costruire un programma che

- accetta in input dall’utente un numero di cifre decimali n

- sceglie random un numero naturale p di n cifre decimali, e lo testi con il test di primalità di Rabin-Miller (il test deve essere ripetuto un numero k di volte, con k indicato dall’utente); se il test non è superato, ripetere la scelta random fino ad ottenere un numero p che superi il test e sia dichiarato “primo”

- trova una radice primitiva a modulo p (algoritmo di Gauss)

- basandosi sui valori di a,p, implementa un sistema crittografico di El-Gamal (l’utente immette un messaggio numerico x compreso fra 1 e (p-1) e il programma calcola il messaggio cifrato y, verificando che la decifratura di y sia proprio x)

(per calcolare la riduzione delle potenze modulo un intero, implementare la routine di esponenziazione modulare)

Prova orale:

1) Esporre almeno 2 dei seguenti argomenti:

- Proprietà delle operazioni di somma e prodotto in Z

- Numeri di Fibonacci e complessità dell’algoritmo delle divisioni successive - Sottogruppi di un gruppo e Teorema di Lagrange

- Sottogruppo ciclico, Teorema di Eulero-Fermat e Piccolo Teorema di Fermat 2) Esporre almeno 1 dei seguenti argomenti:

- Test di primalità ingenuo e test di primalità di Wilson - Test di primalità probabilistico di Rabin-Miller

3) Esporre almeno 2 dei seguenti argomenti:

- Algoritmo di Gauss per il calcolo di una radice primitiva modulo (n primo)

- Algoritmo per il calcolo della parte intera della radice n-esima, e test per le potenze perfette

- Algoritmo di fattorizzazione di Pollard - Algoritmo di fattorizzazione di Fermat 4) Esporre almeno 2 dei seguenti argomenti:

- Sistema crittografico RSA

- Sistema crittografico di ElGamal - Scambio di chiavi di Diffie-Hellman

5) Esporre almeno 2 dei seguenti argomenti:

- Codici

- Disegni e 2 disegni

- Piani proiettivi e quadrati latini ortogonali

Tesina n. 2:

Costruire un programma che

- accetta in input dall’utente un numero di cifre decimali n

- sceglie random un numero naturale p di n cifre decimali, e lo testi con il test di primalità di Rabin-Miller (il test deve essere ripetuto un numero k di volte, con k indicato dall’utente); se il test non è superato, ripetere la scelta random fino ad ottenere un numero p che superi il test e sia dichiarato “primo”

- trova una radice primitiva a modulo p (algoritmo di Gauss)

- basandosi sui valori di a,p, implementa un sistema di scambio di chiavi di Diffie-Helmann (l’utente A immette un numero x, l’utente B immette un numero y, il programma calcola separatamente la chiave di A e la chiave di B e verifica che siano effettivamente uguali)

(per calcolare la riduzione delle potenze modulo un intero, implementare la routine di esponenziazione modulare)

Prova orale:

1) Esporre almeno 2 dei seguenti argomenti:

- Proprietà delle operazioni di somma e prodotto in Z

- Numeri di Fibonacci e complessità dell’algoritmo delle divisioni successive - Sottogruppi di un gruppo e Teorema di Lagrange

- Sottogruppo ciclico, Teorema di Eulero-Fermat e Piccolo Teorema di Fermat 2) Esporre almeno 1 dei seguenti argomenti:

- Test di primalità ingenuo e test di primalità di Wilson - Test di primalità probabilistico di Rabin-Miller

3) Esporre almeno 2 dei seguenti argomenti:

- Algoritmo di Gauss per il calcolo di una radice primitiva modulo (n primo)

- Algoritmo per il calcolo della parte intera della radice n-esima, e test per le potenze perfette

- Algoritmo di fattorizzazione di Pollard - Algoritmo di fattorizzazione di Fermat 4) Esporre almeno 2 dei seguenti argomenti:

- Sistema crittografico RSA

- Sistema crittografico di ElGamal - Scambio di chiavi di Diffie-Hellman

5) Esporre almeno 2 dei seguenti argomenti:

- Codici

- Disegni e 2 disegni

- Piani proiettivi e quadrati latini ortogonali

Tesina n. 3:

Costruire un programma che

- accetta in input un numero naturale n>1

- cerca un fattore non banale di n con l’algoritmo di fattorizzazione di Fermat (per verificare se un numero è quadrato perfetto, implementare la routine che testa se un numero è potenza m-esima, dove l’esponente m è fissato ma generico, e applicarla per m=2)

- cerca un fattore non banale di n con l’algoritmo di fattorizzazione  di Pollard (renderlo flessibile rispetto alla scelta del “seme” e del polinomio dai quali è generata la successione numerica)

Prova orale:

1) Esporre almeno 2 dei seguenti argomenti:

- Proprietà delle operazioni di somma e prodotto in Z

- Numeri di Fibonacci e complessità dell’algoritmo delle divisioni successive - Sottogruppi di un gruppo e Teorema di Lagrange

- Sottogruppo ciclico, Teorema di Eulero-Fermat e Piccolo Teorema di Fermat 2) Esporre almeno 1 dei seguenti argomenti:

- Test di primalità ingenuo e test di primalità di Wilson - Test di primalità probabilistico di Rabin-Miller

3) Esporre almeno 2 dei seguenti argomenti:

- Algoritmo di Gauss per il calcolo di una radice primitiva modulo (n primo)

- Algoritmo per il calcolo della parte intera della radice n-esima, e test per le potenze perfette

- Algoritmo di fattorizzazione di Pollard - Algoritmo di fattorizzazione di Fermat 4) Esporre almeno 2 dei seguenti argomenti:

- Sistema crittografico RSA

- Sistema crittografico di ElGamal - Scambio di chiavi di Diffie-Hellman

5) Esporre almeno 2 dei seguenti argomenti:

- Codici

- Disegni e 2 disegni

- Piani proiettivi e quadrati latini ortogonali

Tesina n. 4:

Costruire un programma che

- accetta in input dall’utente un numero di cifre decimali n

- sceglie random un numero naturale p di n cifre decimali, e lo testi con il test di primalità di Rabin-Miller (il test deve essere ripetuto un numero k di volte, con k indicato dall’utente); se il test non è superato, ripetere la scelta random fino ad ottenere un numero p che superi il test e sia dichiarato “primo”

- ripete il procedimento precedente per trovare un altro numero q di n cifre decimali da dichiarare “primo”

- basandosi sui valori di p,q, implemen un sistema crittografico RSA (sono calcolate chiave pubblica e privata, e quando l’utente immette un messaggio numerico x, il programma calcola il messaggio cifrato y, verificando che la decifratura di y sia proprio x)

(per calcolare la riduzione delle potenze modulo un intero, implementare la routine di esponenziazione modulare)

Prova orale:

1) Esporre almeno 2 dei seguenti argomenti:

- Proprietà delle operazioni di somma e prodotto in Z

- Numeri di Fibonacci e complessità dell’algoritmo delle divisioni successive - Sottogruppi di un gruppo e Teorema di Lagrange

- Sottogruppo ciclico, Teorema di Eulero-Fermat e Piccolo Teorema di Fermat 2) Esporre almeno 1 dei seguenti argomenti:

- Test di primalità ingenuo e test di primalità di Wilson - Test di primalità probabilistico di Rabin-Miller

3) Esporre almeno 2 dei seguenti argomenti:

- Algoritmo di Gauss per il calcolo di una radice primitiva modulo (n primo)

- Algoritmo per il calcolo della parte intera della radice n-esima, e test per le potenze perfette

- Algoritmo di fattorizzazione di Pollard - Algoritmo di fattorizzazione di Fermat 4) Esporre almeno 2 dei seguenti argomenti:

- Sistema crittografico RSA

- Sistema crittografico di ElGamal - Scambio di chiavi di Diffie-Hellman

5) Esporre almeno 2 dei seguenti argomenti:

- Codici

- Disegni e 2 disegni

- Piani proiettivi e quadrati latini ortogonali