Versione polinomiale del piccolo teorema di Fermat

La versione polinomiale del piccolo teorema di Fermat afferma che, se $ n $ è primo, allora per ogni intero $ a $ coprimo con $ n $, vale l'identità \[(x + a)^n \equiv x^n + a \pmod{n}\]

Si tratta di una estensione del classico piccolo teorema di Fermat, secondo cui, per ogni numero primo $ p $ e per ogni intero $ a $:

\[ a^p \equiv a \pmod{p} \]

Questa proprietà è usata spesso nei test di primalità, perché se un numero non la soddisfa, allora non può essere primo.

L'idea è che invece di usare semplici numeri, posso generalizzare il teorema ai polinomi.

Se $ n $ è un numero primo, allora per ogni intero $ a $, la seguente identità è sempre vera:

\[ (x + a)^n \equiv x^n + a \pmod{n} \]

Questa è la versione polinomiale del piccolo teorema di Fermat.

Se trovo un numero $ n $ che non soddisfa questa identità per un certo $ a $, allora sicuramente il numero $ n $ non è primo.
Se invece la verifica è soddisfatta, allora $ n $ potrebbe essere primo, ma servono altre verifiche perché alcuni numeri composti potrebbero comunque soddisfarla per certe scelte di $ a $.

Nota. In altre parole, se $ n $ è primo, il polinomio $ (x + a)^n $, ridotto modulo $ n $, si scompone senza generare nuovi coefficienti indesiderati, semplificandosi a $ x^n + a $. Questo riflette il comportamento del Piccolo Teorema di Fermat per i numeri, estendendolo ai polinomi.

È la base teorica del test AKS, che usa una versione più efficiente per decidere se un numero è primo.

Un esempio pratico
Una tecnica di calcolo rapido

Un esempio pratico

Prendo il caso in cui $ n = 5 $ (che è un numero primo) e scelgo $ a = 2 $. Considero il polinomio:

\[ (x + 2)^5 \]

Espando usando il binomio di Newton:

\[ (x + a)^n = \sum_{k=0}^{n} \binom{n}{k} x^{n-k} a^k \]

In questo caso $ a=2 $ e $ n= 5 $.

\[ (x + 2)^5 = x^5 + \binom{5}{1} x^4 \cdot 2 + \binom{5}{2} x^3 \cdot 2^2 + \binom{5}{3} x^2 \cdot 2^3 + \binom{5}{4} x \cdot 2^4 + \binom{5}{5} \cdot 2^5 \]

Nota. Il coefficiente binomialesi calcola con la formula \[ \binom{n}{k} = \frac{n!}{k!(n-k)!} \]

Ora calcolo i coefficienti modulo $ 5 $:

$ \binom{5}{0} = \frac{5!}{0!(5-0)!} = 1 \equiv 1 \pmod{5} $
$ \binom{5}{1} = \frac{5!}{1!(5-1)!} = 5 \equiv 0 \pmod{5} $
$ \binom{5}{2} = \frac{5!}{2!(5-2)!} = 10 \equiv 0 \pmod{5} $
$ \binom{5}{3} = \frac{5!}{3!(5-3)!} = 10 \equiv 0 \pmod{5} $
$ \binom{5}{4} = \frac{5!}{4!(5-4)!} = 5 \equiv 0 \pmod{5} $
$ \binom{5}{5} = \frac{5!}{5!(5-5)!} = 1 \equiv 1 \pmod{5} $

Sostituisco questi valori:

\[ (x + 2)^5 = 1 \cdot x^5 + 0 \cdot x^4 \cdot 2 + 0 \cdot x^3 \cdot 2^2 + 0 \cdot x^2 \cdot 2^3 + 0 \cdot x \cdot 2^4 + 1 \cdot 2^5 \]

\[ (x + 2)^5 \equiv x^5 + 2^5 \pmod{5} \]

\[ (x + 2)^5 \equiv x^5 + 2 \pmod{5} \]

Ho ottenuto esattamente la formula della versione polinomiale:

\[ (x + a)^n \equiv x^n + a \pmod{n} \]

Questo dimostra che, quando $ n $ è primo, tutti i termini intermedi scompaiono modulo $ n $, lasciando solo $ x^n + a $, proprio come previsto dalla teoria.

Esempio 2

Se considero $ n = 9 $, che non è un numero primo, la versione polinomiale del Piccolo Teorema di Fermat non è garantita.

Questo significa che l'identità potrebbe non valere per tutti i valori di $ a $. Vediamo cosa succede con un esempio pratico.

\[ (x + a)^9 \equiv x^9 + a \pmod{9} \]

Ad esempio, espando $ (x + 2)^9 $ usando il binomio di Newton.

\[ (x + 2)^9 = \sum_{k=0}^{9} \binom{9}{k} x^{9-k} 2^k \]

Poi calcolo i coefficienti binomiali modulo 9:

$ \binom{9}{0} = 1 $
$ \binom{9}{1} = 9 \equiv 0 \pmod{9} $
$ \binom{9}{2} = 36 \equiv 0 \pmod{9} $
$ \binom{9}{3} = 84 \equiv 3 \pmod{9} $
$ \binom{9}{4} = 126 \equiv 0 \pmod{9} $
$ \binom{9}{5} = 126 \equiv 0 \pmod{9} $
$ \binom{9}{6} = 84 \equiv 3 \pmod{9} $
$ \binom{9}{7} = 36 \equiv 0 \pmod{9} $
$ \binom{9}{8} = 9 \equiv 0 \pmod{9} $
$ \binom{9}{9} = 1 $

Ora scrivo lo sviluppo modulo 9:

\[ (x + 2)^9 = x^9 + 0x^8 + 0x^7 + 3x^6 2^3 + 0x^5 + 0x^4 + 3x^3 2^6 + 0x^2 + 0x + 2^9 \]

\[ (x + 2)^9 = x^9 + 3x^6 \cdot 8 + 3x^3 \cdot 64 + 512 \]

Poi riduco modulo 9:

$ 3 \cdot 8 = 24 \equiv 6 \pmod{9} $
$ 3 \cdot 64 = 192 \equiv 3 \pmod{9} $
$ 512 \equiv 8 \pmod{9} $

Quindi ottengo:

\[ (x + 2)^9 \equiv x^9 + 6x^6 + 3x^3 + 8 \pmod{9} \]

Ho trovato dei termini extra ($ 6x^6 + 3x^3 + 8 $), quindi l'identità non vale:

\[ (x + 2)^9 \equiv x^9 + 2 \pmod{9} \]

Questo mostra che la versione polinomiale del Piccolo Teorema di Fermat non è verificata per $ n = 9 $, confermando che $ 9 $ non è primo.

Nota. Se $ n $ fosse stato primo, i coefficienti intermedi $ \binom{n}{k} $ sarebbero stati tutti divisibili per $ n $, quindi $ 0 $ modulo $ n $), lasciando solo $ x^n + a $. Ma per $ n = 9 $, alcuni coefficienti non sono nulli modulo 9, quindi l'identità non regge.

Una tecnica di calcolo rapido

Il test originale di primalità suggerisce di verificare la condizione:

\[ (x + a)^n \equiv x^n + a \pmod{n} \]

Questo test è corretto ma ha un costo computazionale molto elevato perché il polinomio $ (x + a)^n $ ha $ n+1 $ coefficienti, che diventano rapidamente troppi per numeri grandi.

Inoltre, ogni coefficiente binomiale $ \binom{n}{k} $ va calcolato modulo $ n $ ed espandere il polinomio è costoso in termini di tempo.

Come ridurre i coefficienti da controllare?

L’idea per accelerare il test è lavorare in un anello quoziente, ovvero in $ \mathbb{Z}_n[x] / (x^r - 1) $, anziché in $ \mathbb{Z}_n[x] $.

Questo significa che invece di controllare l'uguaglianza in tutti i coefficienti del polinomio $ (x + a)^n $, la verifico solo in un sottoinsieme ridotto.

In altre parole, invece di verificare:

\[ (x + a)^n \equiv x^n + a \pmod{n} \]

In tutto $ \mathbb{Z}_n[x] $, controllo solo che valga modulo un polinomio più piccolo, del tipo:

\[ (x + a)^n \equiv x^n + a \quad \text{in } \mathbb{Z}_n[x] / (x^r - 1) \]

Dove $ r $ è un valore molto più piccolo di $ n $, scelto opportunamente.

Perché questo mi aiuta? Invece di calcolare tutti gli $ n + 1 $ coefficienti di $ (x + a)^n $, ne calcolo solo $ r $. Quindi, riduce il numero di coefficienti da gestire. Se $ r $ è piccolo rispetto a $ n $, il calcolo diventa polinomiale in $ \log n $.

Come scegliere r?

Per trovare un valore piccolo di $ r $ che mantenga la correttezza del test, un metodo pratico è il seguente:

Scelgo un candidato $ r $, ad esempio, un valore piccolo come $ r = 2, 3, 4, \dots $ purché $ r < n $.
Calcolo l’ordine di $ n $ modulo $ r $, cercando il più piccolo $ k $ tale che: \[ n^k \equiv 1 \pmod{r} \]
Se $ k $ è piccolo, allora $ r $ è una buona scelta. Viceversa, cerco un altro valore.

Una via alternativa. Se $ n $ è un numero molto grande, si può dimostrare che esiste un valore di $ r $ relativamente piccolo, dipendente da $ \log n $, tale che, se l’equazione è verificata per un numero sufficiente di valori di $ a $, allora $ n $ è primo. In particolare, si ha: \[ r \leq \lfloor 16 \log_2^2 n \rfloor + 1 \] Questa formula è utile principalmente per $ n $ molto grandi, poiché garantisce un valore di $ r $ significativamente inferiore a $ n $, rendendo il calcolo più efficiente. Tuttavia, per valori più piccoli di $ n $, potrebbe restituire un $ r $ maggiore di $ n $, risultando così inapplicabile.

Esempio pratico

Voglio verificare se $ n = 37 $ è primo. Invece di calcolare tutti i coefficienti di:

\[ (x + a)^{37} \]

Verifico solo se

\[ (x + a)^{37} \equiv x^{37} + a \quad \text{in } \mathbb{Z}_{37}[x] / (x^r - 1) \]

Per $ n = 37 $, posso scegliere $ r $ usando la formula logaritmica

$$ r \approx \lfloor 16 \log_2^2(37) \rfloor + 1 \approx 435 $$

Tuttavia, $ r=435 $ è più grande di $ n=37 $ e ovviamente non mi conviene usarlo.

In questo caso mi conviene cercare da me un numero $ r $ più piccolo, ad esempio $ r = 24 $

\[(x + a)^{37} \equiv x^{37} + a \quad \text{in } \mathbb{Z}_{37}[x] / (x^{24} - 1)\]

Questo significa che devo calcolare $ (x + a)^{37} $ modulo $ 37 $ e modulo il polinomio $ x^{24} - 1 $.

Perché ho scelto r=24? Devo trovare un buon valore $ r $ per $ n = 37 $. L'ordine moltiplicativo di $ 37 $ modulo $ 24 $ è $ k = 2 $ perché \[ 37^1 \equiv 13 \pmod{24}, \quad 37^2 \equiv 1 \pmod{24} \] Quindi $ k = 2 $ è molto più piccolo di $ r = 24 $ ed è molto basso. Questo vuole dire che usare $ r=24 $ è una buona scelta.

Poiché sto lavorando in $ \mathbb{Z}_{37}[x] / (x^{24} - 1) $ posso ridurre tutti gli esponenti di $ x $ modulo 24.

\[ x^{37} = x^{(24 + 13)} = x^{13} \quad \text{(perché $ x^{24} \equiv 1 $)} \]

Quindi l’equazione diventa:

\[ (x + a)^{37} \equiv x^{13} + a \pmod{37}, \quad \text{in } \mathbb{Z}_{37}[x] / (x^{24} - 1) \]

A questo punto devo verificare questa identità per diversi valori di $ a $ primi con $ 37 $ di solito si scelgono piccoli valori come $ a = 1, 2, 3 $.

Ad esempio con $ a = 1 $:

\[ (x + 1)^{37} \equiv x^{13} + 1 \pmod{37} \]

Se questa equazione è verificata per abbastanza valori di $ a $, allora posso concludere che $ 37 $ è primo.

In conclusione, grazie a questa scelta di $ r $, ho ridotto il numero di coefficienti da controllare da semplificando il test senza perdere correttezza.

Questo riduce enormemente il costo computazionale.

Nota. L’idea chiave è ridurre il numero di coefficienti da $ n+1 $ a un valore più piccolo $ r $, rendendo il test polinomiale in $ \log n $ invece che esponenziale. Questo è il principio fondamentale dietro l'algoritmo AKS, che rende possibile un test di primalità deterministico ed efficiente.

E così via.