(1) In base al piccolo teorema di Fermat, per effettuare il calcolo basta conoscere il valore di b^{c} (mod p − 1). Questo richiede un numero di operazioni dell’ordine O(log c log^{2} p− 1) = O(log^{3} p) e fornisce un intero h compreso tra 0 e p − 1. Per trovare a^{h} (mod p) sono adesso necessarie ancora O(log^{3} p) operazioni. In tutto, il tempo necesario é dato dalla somma di questi due tempi, che é ancora O(log^{3} p).

(2) Un modulo adatto devecessere prodotto di 2 primi p e q tali che sia pq > 22^{3} = 10648 e inoltre p − 1 e q − 1 non devono essere multipli di 3. Dato che \sqrt{10648} < 104, un modo per scegliere i due primi é quello di cercare i due piú piccoli primi maggiori di 104 che rispettino l’altra condizione. Sono adeguati 107 e 113, nel qual caso il modulo é 107 · 113 = 12091.

(3) In questo algoritmo, si scrive lo sviluppo binario dell’esponente 26 = (11010)_{2}. Inoltre, si calcolano i successivi quadrati di 3 (mod 17), ciascuna volta elevando a quadrato il precedente, fino alla potenza di 2 massima contenuta in questo sviluppo (in questo caso si tratta di 2^{4}). Si trova

3^{0} = 1 (mod 17)
3^{1} = 3 (mod 17)
3^{2} = 9 (mod 17)
3^{4} = 13 (mod 17)
3^{8} = 16 (mod 17)
3^{1}6 = 1 (mod 17).

Pensando al significato della rappresentazione binaria di un numero intero, é chiaro che, a questo punto, basta moltiplicare fra di loro tutti i quadrati successivi in corrispondenza delle cifre 1 di questo sviluppo. Pertanto si ha:

3^{26} = 3^{2+2^{3}+2^{4}} = 9 · 16 · 1 = 8(mod 17).

(4) Sia S la somma vinta da Alvaro, espressa in milioni. Pertanto, abbiamo S intero e 0 < S < 5000. I dati del problema equivalgono al sistema di congruenze:

\{ \begin{matrix}S = 6 (mod 7) \\ S = 2 (mod 12) \end{matrix}

Questo sistema ha un’unica soluzione compresa tra 0 e 84 (teorema cinese del resto), che vale 62. Le altre soluzioni sono congrue a 62 modulo 84. In questo modo, la vincita minima é appunto di 62 milioni. La massima si ottiene cercando il piú grande numero minore di 5000 che sia congruo a 62 modulo 84.

(5) quickies i. 2^{2000} íl piú piccolo numero con oltre 2000 cifre. Utilizzando il teorema dei numeri primi, si trova la stima \frac{2^{2000}}{log 2^{2000}} per il numero di primi minori di 2000. Quindi la probabilitá richiesta é:

\frac{1}{2000 log 2} ≈ 0.00072.

ii. Dato che 2q + 1 é primo, φ(2q + 1) = 2q. Visto che q é un primo dispari e visto che la φ é moltiplicativa su numeri coprimi, si ha

φ(2q) = φ(2) φ(q) = 1 · (q − 1) = q − 1,

Typeset by AMS-TEX

dato che q é un numero primo. iii. L’esponente di cifratura deve essere coprimo con φ(n). Dato che φ(43) = 42 = 2·3·7 e che φ(331) = 330 = 2 · 3 · 5 · 11, l’esponente minimo é 13. iiii. Il fatto che n sia un modulo per RSA significa che esso é il prodotto di due primi dispari p e q. L’equazione x^{2} = 1(mod m) equivale al sistema di congruenze

\{ \begin{matrix}x^{2} = 1 (mod p) \\ x^{2} = 1 (mod q) \end{matrix}

Ciascuna delle due equazioni di questo sistema ha 2 radici in 𝔽_{p}. Combinando tali radici nei 4 modi possibili si ottengono tutte e sole le soluzioni modulo m.