MATEMATICA APPLICATA 2  TEST 4/8  Roma, 14 Novembre 2000.

COGNOME . . . . . . . . . . . . . . . . . . . . . . . . . . NOME . . . . . . . . . . . . . . . . . . . . . . . . . . MATRICOLA . . . . . . . . . . . . . . . . . . . . . . . . . .

Risolvere gli esercizi accompagnando le risposte con spiegazioni chiare ed essenziali. Inserire le risposte negli spazi predisposti. NON SI ACCETTANO RISPOSTE SCRITTE SU ALTRI FOGLI. Ogni esercizio vale 7.5 punti.

1. Si scriva un unico programma in Pari che dati m ∈ N e a ∈ Z/mZ determini se m a. è pseudo primo; b. è pseudo primo Euleriano; c. è pseudo primo forte.

2. Dimostrare che se m ≡ 3 mod 4 è pseudo primo Euleriano in base a allora è anche pseudo primo forte in base a.

3. Sia q un numero primo tale che q ≡ 2 mod 3. Dimostrare che, se 4^{q} ≡ 1 mod (2q + 1), allora 2q + 1 è primo.

4. Sia m = 65.

i. Determinare tutte le soluzioni di x^{2} ≡ −1 mod m; ii. Determinare due basi a_{1} e a_{2} tali che 65 è uno pseudo primo forte in base a_{1}, in base a_{2} ma non in base a_{1}a_{2}. iii. Cosa possiamo dedurre sull’insieme delle basi forti S(65)

5. (Quickies): Scrivere solo la risposta delle seguenti domande: i. Si scriva la successione di Miller Rabin modulo 49 delle seguenti basi: 2, 7, 25, 13. ii Determinare dei fattori non banali di 10002200057; iii. Determinare dei fattori non banali di 30001600021;

i.

ii.