CTX - 06 - Numeri Particolari

Data: [2018-03-22 gio]

---

In questa lezione abbiamo introdotto varie classi di numeri particolari. Abbiamo inoltre trattato l'algoritmo per l'esponenziazione modulare e l'algoritmo di Fermat per la fattorizzazione di interi.

Quasi tutte le applicazioni e metodologie della crittografia moderna necessitano una soluzione efficiente al seguente problema, che prende il nome di esponenziazione modulare: dati \(b, n, m \in \mathbb{N}\), vogliamo calcolare il valore \(b^n \mod m\).

A prima vista il problema potrebbe sembrare computazionalmente difficile da risolvere: dobbiamo infatti calcolare \(n\) potenze di \(b\), \(b^1\), \(b^2\), ..., \(b^n\). Anche riducendo di volta in volta i vari fattori \(b^i\) modulo \(m\) per \(i = 1...n\), dovremmo comunque eseguire \(n\) moltiplicazioni, ottenendo una complessità di \(O(n\log^2{b})\), che risulta essere esponenziale.

Per fortuna però esiste un modo più ingegnoso, che utilizza una strategia divide \& conquer, per ottenere il risultato desiderato: Scriviamo \(n\) in base \(2\), ovvero calcoliamoci le varie cifre \(n_{k-1}, n_{k-2}, ..., n_0 \in \{0, 1\}\) tali che

\[n = n_0 + 2n_1 + 2^2n_2 + ... + 2^{k-2}n_{k-2} + 2^{k-1}n_{k-1}\]

Riscrivendo \(n\) in questo nuovo modo otteniamo

\[\begin{split} b^n \mod m &\equiv b^{n_0 + 2n_1 + 2^2n_2 + ... + 2^{k-2}n_{k-2} + 2^{k-1}n_{k-1}} \mod m \\ &\equiv b^{n_0}b^{2n_1}b^{2^2n_2}...b^{2^{k-1}n_{k-1}} \mod m \\ &\equiv (b^{n_0} \mod m)(b^{2n_1} \mod m)(b^{2^2n_2} \mod m)...(b^{2^{k-1}n_{k-1}} \mod m) \\ \end{split}\]

Notiamo subito che il problema diventa più gestibile: adesso dobbiamo effettuare \(k = O(\log n)\) moltiplicazioni. Per quanto riguarda i vari fattori, sapendo che \(n_i \in \{0, 1\}\), in realtà l'unica cosa che dobbiamo calcolare sono i vari \(b^{2^i}\), per \(i = 1,..,k-1\), per poi selezionare solamente quelli in cui \(n_i\) = 1 e moltiplicarli tra loro.

Riportiamo quindi due algoritmi, uno che risolve il problema in modo iterativo, e l'altro che lo risolve in modo ricorsivo.

Fattorizzare un generico numero naturale \(n \in \mathbb{N}\) è un problema di cui ancora non si conosce una soluzione per il caso generico che sia polinomiale. Detto questo, se è possibile scrivere \(n\) in forme particolari, allora conosciamo determinati modi di fattorizzarlo.

Ad esempio, dato \(b \in \mathbb{Z}\), abbiamo le seguenti identità

\[\begin{split} b^n - 1 = (b - 1)(b^{n-1} + b^{n-2} + ... + b + 1) \\ b^n + 1 = (b + 1)(b^{n-1} - b^{n-2} + ... - b + 1) \end{split}\]

La prima è vera per ogni \(n\) mentre la seconda è vera per \(n\) dispari. Infatti, per quanto riguarda la prima, scrivendo \(b^n - 1\) in base \(b\) otteniamo

\[\begin{split} b^n - 1 &= (\underbrace{b-1, b-1, ..., b-1}_{n-1 \text{ cifre}})_b\\ &= (b-1)(\underbrace{1, 1, ..., 1}_{n-1 \text{ cifre}})_b \\ &= (b-1)(b^{n-1} + b^{n-2} + ... + b + 1) \\ \end{split}\]

Per la seconda invece basta notare che, se \(n\) è dispari, allora \((-1)^n + 1 = 0\), e dunque \(-1\) è radice di \(b^n + 1\). Dal teorema di ruffini concludiamo che \(b - (-1) = b + 1 \mid b^n + 1\) ed effettuando la divisione si ottiene l'altro fattore.

---

Proposizione: Sia \(b \in \mathbb{Z}_m^*\) tale che \(MCD(b, m) = 1\) e siano \(a, c \in \mathbb{N}\) con \(d = MCD(a, c)\). Allora,

\[\begin{cases} b^a \equiv 1 \mod m \\ b^c \equiv 1 \mod m \\ \end{cases} \implies b^d \equiv 1 \mod m\]

Dimostrazione: Infatti, se \(d = MCD(a, c)\), allora \(\exists \alpha, \beta \in \mathbb{Z}\) tali che \(d = \alpha a + \beta c\).

Sostituendo,

\[\begin{split} b^d &\equiv b^{\alpha a + \beta c} \mod m \\ &\equiv (b^a)^{\alpha}(b^c)^{\beta} \mod m \\ &\equiv 1^{\alpha}1^{\beta} \mod m \\ &\equiv 1 \mod m \end{split}\]

\[\tag*{$\blacksquare$}\]

Abbiamo poi il seguente corollario, che ci da importanti informazioni sui possibili fattori di numeri della forma \(b^n - 1\)

Corollario: Sia \(p\) un numero primo e sia \(b^n - 1\) un intero. Se \(p \, | \, b^n - 1\), allora una delle seguenti cose deve essere vera

• \(p \,| \, 2^d - 1\), con \(d\) fattore proprio di \(n\), ovvero \(d \, | \, n\) con \(d > 1\).

• \(p \equiv 1 \mod n\). Se poi \(n\) è dispari e \(p > 2\), allora \(p \equiv 1 \mod 2n\).

Dimostrazione: Sia \(d := MCD(n, p-1)\). Dire che \(p \, | \, b^n - 1\) equivale a dire che \(b^n \equiv 1 \mod p\). Inoltre, dal teorema di Fermat, sappiamo che \(b^{p-1} \equiv 1 \mod p\). Dalla proposizione appena dimostrata segue che \(b^d \equiv 1 \mod p\), ovvero che \(p \, | \, b^d - 1\).

Distinguiamo ora vari casi:

• Se \(d \neq n\), allora è vero il caso 1), in quanto \(p | \, b^d - 1\) con \(d\) fattore proprio di \(n\).

• Se \(d = n\), dato che \(n = MCD(n, p-1)\) abbiamo che \(n \, | \, p-1\), ovvero \(p \equiv 1 \mod n\).

• Infine, se \(n\) è dispari, \(p > 2\) e \(p \equiv 1 \mod n\), allora \(n \, | \, p-1\). Ma \(n\) è dispari, e \(p-1\) è pari: ne segue che \(p-1\) deve necessariamente contenere, oltre ai fattori di \(n\), un fattore \(2\), e quindi contiene anche il fattore \(2n\). Detto altrimenti, abbiamo che \(2n \, | \, p-1\), ovvero \(p \equiv 1 \mod 2n\).

\[\tag*{$\blacksquare$}\]

Per vedere l'utilità di questo alquanto bizzarro risultato procediamo con un esempio.

---

Esempio: Vogliamo stabilire se il numero \(2097151 = 2^{21} - 1\) è primo.

Il corollario ci dice che, se \(p\) è un numero primo che divide \(2^{21} -1\), allora o \(p\) divide il numero \(2^d - 1\), con \(d\) fattore proprio di \(21\), oppure \(p \equiv 1 \mod 42\). Notiamo poi che i fattori propri di \(21\) sono \(d = 1, 3, 7\). Inoltre \(2^1 - 1 = 1\), \(2^3 - 1 = 7\) e \(2^7 - 1 = 127\). Escludendo l'\(1\), che non ci da alcuna informazione, notiamo che \(7\) e \(127\) sono entrambi primi, e gli unici primi che dividono i primi sono i primi stessi! Ovvero, se \(2^{21} - 1\) ha un fattore primo, allora o questo fattore è \(7\), o è \(127\), oppure è congruo ad \(1\) modulo \(42\)! Dividendo si scopre poi che \(2^{21} - 1\) è divisibile sia per \(7\) che per \(127\), ottenendo

\[2097151 = 7 \cdot 127 \cdot 2359\]

Ora non sappiamo se \(2359\) è primo o no. Sapendo però che \(2359\) non divide ne \(7\) ne \(127\), allora, se fosse primo, dovrebbe necessariamente essere congruo a \(1\) modulo \(42\). Si scopre subito che

\[2359 \equiv 7 \mod 42\]

Non rispettando la condizione necessaria fornita dal corollario, possiamo affermare che \(2359\) \textit{non} è un fattore primo, ed infatti lo si fattorizza come \(2359 = 7 \cdot 337\), ottenendo la fattorizzazione

\[2097151 = 7^2 \cdot 127 \cdot 337\]

Notiamo infine che \(337 \equiv 1 \mod 42\), il che rispetta il fatto che \(337\) non divide ne \(7\) ne \(127\).

---

I numeri di Mersenne sono numeri della forma

\[M_p := 2^p - 1, \quad \text{con $p$ primo}\]

I primi numeri di mersenne sono

\(\begin{split} M_2 &= 3 \\ M_3 &= 7 \\ M_5 &= 3, \\ M_{11} &= 2047 \end{split}\)

Notiamo che i primi \(3\) numeri di mersenne sono tutti primi. Per quanto riguarda il quarto, osserviammo che \(2047 = 2^{11} - 1\). Se \(p\) primo divide \(2047\) allora, dato che \(11\) è primo e non ha fattori propri \(> 1\), deve necessariamente essere che \(p \equiv 1 \mod 22\). Notiamo poi che \(\sqrt{2047} \approx 45\). Il più piccolo fattore primo di \(2047\), se esiste, deve necessariamente essere \(\leq 45\) e congruo ad \(1\) modulo \(22\). Gli unici valori possibili sono quindi \(p = 23\) e \(p = 45\). Infatti, si da il caso che \(p = 23\) divide \(2047 = 23 \cdot 89\). Quindi \(M_{11}\) non è primo.

Generalmente però i numeri della forma \(M_p\) con \(p\) primo tendono ad essere primi. I numeri di mersenne furono studiati da Marin Mersenne, matematico francesce vissuto in Francia tra il 1588 e il 1648. Mersenne è particolarmente famoso per la sua corrispodenza epistolare con i più grandi matematici dell'epoca, tra cui troviamo anche Fermat. Nei suoi studi Mersenne affermò che \(M_p\), con \(p < 256\) fosse primo se e solo se \(p\) fosse uno tra i seguenti numeri primi:

\[p = 2, 3, 4, 7, 13, 17, 19, 31, 67, 127, 257\]

In realtà successivamente si scoprì che \(M_p\) non è primo per \(p = 67, 257\), ed è primo anche per \(p = 61, 89, 107\).

---

Osservazione 1: Recentemente è stato scoperto un algoritmo, l'algoritmo AKS, in grado di stabilire deterministicamente se un numero \(n\) è primo o no con un costo \(O(\log^{11}{n})\). Per i numeri di mersenne però esiste un algoritmo polinomiale, l'algoritmo di Lucas-Lehmer, in grado di stabilire, sempre in modo deterministico, se \(M_p\) è primo o no. Essendo molto specializzato poi, l'algoritmo di Lucas-Lehmer risulta essere più efficiente rispetto all'algoritmo AKS.

Osservazione 2: I dieci numeri primi più grandi scoperti dall'essere umano sono tutti primi di mersenne. Il più grande fra questi fu scoperto nel gennaio del \(2016\) ed ha approssimatamente \(22.000.000\) di cifre decimali!

---

Un numero della forma \(2^m + 1\) può essere primo? Se \(m\) è dispari, allora, per l'identità mostrata all'inizio di questa lezione, abbiamo che

\[2^m + 1 = (2 + 1)(2^{m-1} - 2^{m-2} + ... -2 + 1)\]

e quindi \(3 \, | \, 2^m + 1\). Se \(m\) è pari ma contiene un fattore dispari, allora possiamo scrivere \(m = 2^ik\), con \(k\) dispari. Sostituendo,

\[2^m + 1 = 2^{2^ik} + 1 = (2^{2^i})^k + 1 = (2^{2^i} + 1)((2^{2^1})^{k-1} - .... + 1)\]

e quindi nuovamente \(2^{2^i} \, | \, 2^m\). Ma allora \(2^m + 1\) è primo solo quando \(m\) è pari e non contiene nessun fattore dispari, ovvero \(m = 2^n\).

I numeri della forma \(2^{2^i} + 1\) vengono chiamati numeri di Fermat, e si denotano con il seguente simbolo

\[F_n = 2^{2^n} + 1\]

Alcuni numeri di fermat sono:

\(\begin{split} F_0 &= 3 \\ F_1 &= 5 \\ F_2 &= 17 \\ F_3 &= 257 \\ F_4 &= 65537 \\ \end{split}\)

I primi \(5\) numeri di fermat sono tutti primi. Per quanto riguarda \(F_5\), Fermat stesso mostra che \(641 \, | \, F_5\). Infatti, notando che \(641 = 2^4 + 5^4\) e \(640 = 5 \cdot 2^7\), abbiamo che

\[\begin{split} 2^{(2^5)} + 1 &= 2^{32} + 1\\ &= 2^42^{28} + 1 \\ &= (641 - 5^4)2^{28} + 1 \\ &= 641 \cdot 2^{28} - 5^42^{28} + 1 \\ &= \underbrace{641 \cdot 2^{28} - \underbrace{(5 \cdot 2^7)^4 + 1}_{\text{divisibile per 641}}}_{\text{divisibile per 641}} \\ \end{split}\]

Sui numeri di Fermat, data la loro crescità più che esponenziale, non si molto.

L'algoritmo di Fermat rappresenta una raffinazione del crivello di Eratostene. Detto questo, la complessità risulta comunque esponenziale.

Sia \(n = st\), con \(n\) dispari, \(s \geq t\). Vogliamo \(a, b\) tali che

\(\begin{cases} a + b = s \\ a - b = t \\ \end{cases}\)

Notiamo che la soluzione esiste sempre ed è unica. La soluzione infatti è la seguente

\[a = \frac{s + t}{2}, \quad b = \frac{s - t}{2}\]

Sostituendo, mi posso scrivere \(n\) come

\[n = st = (a + b)(a - b) = a^2 - b^2\]

Questo vuol dire che, fissato un \(n\), posso mettere in biiezione le fattorizzazioni di \(n\), con i modi di scrivere \(n\) come differenza tra quadrati. L'algoritmo di Fermat si basa proprio su questa osservazione, in quanto verifica, cercando tra tutti gli interi \(x \geq \sqrt{n}\), se \(x^2 - n\) è un quadrato. In tal caso infatti abbiamo una fattorizzazione \(n = (x + y)(x - y)\).

Notiamo poi che, per fattorizzazioni banali della forma \(n = n \cdot 1\), abbiamo che

\[x = \frac{n+1}{2} \quad, \quad y = \frac{n-1}{2}\]

Ricapitolando, troviamo il seguente algoritmo

Notiamo che verificare se un numero è un quadrato può essere effettuato in tempo polinomiale. Il problema è che dobbiamo comunque effettuare \(O(n - \sqrt{n})\) moltiplicazioni, e quindi il costo totale risulta esponenziale. Detto questo, se \(n\) non è primo e i suoi divisori sono vicini al \(\sqrt{n}\), allora l'algoritmo di Fermat è molto meglio rispetto al crivello di eratostene.

Segue un teorema interessante.

Teorema (di Wilson): Sia \(p \in \mathbb{N}\), allora

\[p \text{ è primo} \iff (p-1)! \equiv -1 \mod p\]

Dimostrazione: Dimostriamo prima il lato (\(\implies)\): Notiamo che nel prodotto \((p-1)! = 1 \cdot 2 \cdot 3 \cdot ... \cdot (p-2) \cdot (p-1)\), oltre a \(1\) e \(p-1\), che sono gli inversi di se stessi, tutti gli altri hanno un inverso distinto. Questo segue dal fatto che se \(p\) è primo, allora le soluzioni dell'equazione \(x^2 \equiv 1 \mod p\) sono \(x \equiv \pm 1 \mod p\). Ma allora possiamo accoppiare ciascun elemento preso da \(2, ..., p-2\) con il proprio inverso, che nuovamente è preso da \(2, ..., p-2\), riuscendo ad annullare il contributo di entrambi i numeri sul prodotto totale. Gli unici superstiti a questo processo di autodistruzione sono \(1\) e \(p-1\), da cui,

\[\begin{split} (p-1)! &\equiv 1 \cdot 2 \cdot 3 \cdot ... \cdot (p-2) \cdot (p-1) \mod p \\ &\equiv 1 \cdot (p-1) \mod p \\ &\equiv (p-1) \mod p \\ &\equiv -1 \mod p \end{split}\]

Per il lato inverso (\(\Leftarrow\)) invece proviamo il contrapositivo: supponiamo che \(p = ab\) fattorizzazione non banale, con \(a, b > 1\) e quindi \(a, b < p-1\). Ma allora \((p-1)!\) sicuramente conterrà anche \(a\) e \(b\), e quindi

\[p = ab \, | \, (p-1)! \implies (p-1)! \equiv 0 \mod p\]

\[\tag*{$\blacksquare$}\]

Il teorema di Wilson, anche se teoricamente ci da una condizione necessaria e sufficiente affinchè un numero \(p\) sia primo, non viene utilizzato nella pratica in quanto il calcolo di \((p-1)!\) risulta, come visto nella terza lezione, estremamente costoso dal punto di vista computazionale.

Definiamo le seguenti funzioni

\[\begin{split} \sigma (n) := \text{somma dei divisori positivi di $n$} \\ \tau (n) := \text{numero dei divisori positivi di $n$} \\ \end{split}\]

Ovvero,

\[\begin{split} \sigma (n) &= \sum_{0 < d \, | \, n} d = \sum_{0 < d \, | \, n} id(d) \\ \tau (n) &= \sum_{0 < d \, | \, n} 1 = \sum_{0 < d \, | \, n} f(d), \quad \text{con } f(d) := 1, \forall d \in \mathbb{N} \end{split}\]

Notiamo che, dato che le funzioni \(id\) e \(f\) sono banalmente moltiplicative, per il Lemma dimostrato nella quinta lezione abbiamo che anche \(\sigma (n)\) e \(\tau (n)\) sono moltiplicative. Possiamo quindi calcolarle facilmente a seconda dei vari casi:

• Se \(n = p^a\), allora

  \[\begin{split} \sigma (p^a) &= 1 + p + p^2 + ... + p^a = \frac{p^{a+1} - 1}{p - 1} \\ \\ \tau (p^a) &= 1 + 1 + 1 + ... + 1 = a + 1 \\ \end{split}\]

• Se \(n = p_1^{a_1}p_2^{a_2}...p_h^{a_h}\), allora

  \[\begin{split} \sigma (n) &= \sigma (p_1^{a_1}p_2^{a_2}...p_h^{a_h}) = \prod_{i = i}^h {\sigma (p_i^{a_i})} = \prod_{i = 1}^h \frac{p_i^{a_i + 1} - 1}{p_i - 1} \\ \\ \tau (n) &= \tau (p_1^{a_1}p_2^{a_2}...p_h^{a_h}) = \prod_{i = 1}^h \tau (p_i^{a_i}) = \prod_{i = 1}^h (a_i + 1) \end{split}\]

---

Definizione: Un numero \(n\) si dice numero perfetto se e solo se

\[\sigma (n) = 2n\]