Numeri introspettivi
Dato un numero primo \( p \) , un intero positivo \( r \) e un polinomio \( f(x) \in \mathbb{Z}[x] \), si dice che un intero \( m \) è introspettivo per \( f(x) \) modulo \( p \) relativamente a \( r \) se vale la seguente relazione: \[
(f(x))^m \equiv f(x^m) \mod (x^r - 1, p) \]
In altre parole, l'elevazione alla potenza \( m \) del polinomio \( f(x) \) equivale alla sostituzione di \( x \) con \( x^m \) nello stesso polinomio, quando si lavora nell'anello quoziente \( \mathbb{Z}_p[x]/(x^r - 1) \).
L'anello quoziente \( \mathbb{Z}_p[x]/(x^r - 1) \) vuol dire che i polinomi si trovano in un ambiente ciclico, dove \( x^r \equiv 1 \).
Quindi il polinomio è come se "girasse intorno" dopo ogni passo di lunghezza \( r \).
Nota.Questa proprietà è essenziale nell'algoritmo AKS per la verifica della primalità, dove si utilizza il concetto di introspettività per determinare se un numero è primo in modo efficiente.
Un esempio pratico
Considero un numero primo \(p = 2\), un intero \( r=3 \) e il polinomio \(f(x) = x^2 + 1\) in \(\mathbb{Z}_2[x]\).
In questo caso in \(\mathbb{Z}_2\) si ha \(1 + 1 = 0\). Questo significa che alla fine delle operazioni si riduce tutto modulo \((p,\,x^3 - 1)\), ossia in \(\mathbb{Z}_2[x]/(x^3 - 1)\).
Da notare che nella riduzione \(\mathbb{Z}_2[x]/(x^3 - 1)\) vale la relazione \(x^3 \equiv 1\).
Scelgo come candidato \(m = 2\) e verifico se vale la seguente relazione:
\[ \bigl(f(x)\bigr)^m \;=\; f\bigl(x^m\bigr) \quad\text{in } \mathbb{Z}_2[x]/(x^3 - 1) \]
ossia
\[ \bigl(f(x)\bigr)^2 \;=\; f\bigl(x^2\bigr) \quad\text{in } \mathbb{Z}_2[x]/(x^3 - 1) \]
Per prima cosa calcolo \(\bigl(f(x)\bigr)^2\) sapendo che \(f(x) = x^2 + 1\) in \(\mathbb{Z}_2[x]\).
\[ \bigl(f(x)\bigr)^2 = (x^2 + 1)^2 \]
\[ \bigl(f(x)\bigr)^2 = x^4 + 2x^2 + 1 \]
In \(\mathbb{Z}_2[x]\) poiché \(1 + 1 = 0 \mod 2\) e \(2 \equiv 0 \mod 2\).
\[ \bigl(f(x)\bigr)^2 = x^4 + 0 \cdot x^2 + 1 \]
\[ \bigl(f(x)\bigr)^2 = x^4 + 1 \]
Riduco \(x^4 + 1\) modulo \(x^3 - 1\).
In \(\mathbb{Z}_2[x]/(x^3 - 1)\) vale l'equivalenza \( x^3 \equiv 1 \).
\[ \bigl(f(x)\bigr)^2 = x^3 \cdot x + 1 \]
\[ \bigl(f(x)\bigr)^2 = 1 \cdot x + 1 \]
\[ \bigl(f(x)\bigr)^2 = x + 1 \]
A questo punto calcolo \(f(x^2)\).
\[ f(x^2) \;=\; (x^2)^2 + 1 \;=\; x^4 + 1 \]
Di nuovo, in \(\mathbb{Z}_2[x]/(x^3 - 1)\), ho \(x^3 \equiv 1\). Quindi
\[ f(x^2) \;\equiv\; x^3 \cdot x + 1 \]
\[ f(x^2) \;\equiv\; 1 \cdot x + 1 \]
\[ f(x^2) \;\equiv\; x + 1 \]
In conclusione \(\bigl(f(x)\bigr)^2 \equiv f\bigl(x^2\bigr)\)
\[ \bigl(f(x)\bigr)^2 \;\equiv\; x + 1 \ \ \ \text{in } \mathbb{Z}_2[x]/(x^3 - 1) \]
\[ f(x^2) \;\equiv\; x + 1 \ \ \ \text{in } \mathbb{Z}_2[x]/(x^3 - 1) \]
Pertanto, il numero intero \(m=2\) è introspettivo per il polinomio \(f(x) = x^2+1\) modulo \(p=2\) e relativamente a \(r=3\).
Note
Alcune note e proprietà utili sui numeri introspettivi.
- Introspettività del primo stesso
Un numero primo \( p \) è sempre introspettivo rispetto a sé stesso per qualsiasi intero \( r \). - Chiusura sotto prodotto
Se due numeri sono introspettivi per un polinomio \( f(x) \), allora il loro prodotto è ancora introspettivo rispetto a \( f(x) \). - Chiusura sotto somma
Se un numero è introspettivo per due polinomi distinti, allora è introspettivo anche per la loro somma.
E così via.
