Radice primitiva modulo n: differenze tra le versioni

Versione delle 08:49, 30 apr 2023

Versione attuale delle 16:19, 17 giu 2023

(12 versioni intermedie di 6 utenti non mostrate)

Riga 1:

In [[aritmetica modulare]], ununa '''generatoreradice primitiva modulo <math>n</math>''' o '''radice primitivageneratore modulo <math>n</math>''' (o semplicemente '''generatore''') è un [[numero intero]] le cui potenze [[Aritmetica modulare|modulo]] <math>n</math> sono congruenti con i numeri [[coprimo|coprimi]] ad <math>n</math>.

Se <math>n\ge 1</math> è un [[Numero intero|intero]], i numeri [[coprimo|coprimi]] ad <math>n</math>, considerati modulo <math>n</math>, costituiscono un [[Gruppo (matematica)|gruppo]] rispetto all'operazione di moltiplicazione; esso viene generalmente indicato con <math>(\Z/n\Z)^*</math> oppure <math>\Z_n^*</math>. Esso è un [[gruppo ciclico]] se e solo se <math>n</math> è uguale a <math>2</math>, <math>4</math>, <math>p^k</math> o <math>2p^k</math> per un [[numero primo]] [[Numero dispari|dispari]] <math>p</math> e <math>k\ge 1</math>. Un generatore di questo gruppo ciclico è chiamato anche '''elemento primitivo di <math>\Z_n^*</math>'''.

Riga 7:

:<math>(\Z/14\Z)^*,</math>

sono le classi di congruenza di <math>1</math>, <math>3</math>, <math>5</math>, <math>9</math>, <math>11</math> e <math>13</math>. che sono [[coprimo|coprimi]] con <math>n = 14.</math>

Si ha che <math>3</math> è un generatore modulo <math>14</math>, perché 3² mod 14 = 9, 3³ mod 14 = 13, 3⁴ mod 14 = 11, 3⁵ mod 14 = 5 e 3⁶ =mod 114 (modulo= 14)1. L'unica altra radice primitiva modulo <math>14</math> è <math>5</math>.

I generatori modulo <math>n</math> rivestono un'importanza considerevole in [[crittografia]].

==Trovare i generatori==

Di seguito vi è una tabella che contiene i più piccoli generatori per diversi valori di <math>n</math><ref>{{OEIS|A046145}}</ref>:

{| class="wikitable"

Riga 39 ⟶ 38:

== Dimostrazione dell'esistenza di un generatore modulo ''p''^k, ''p'' dispari ==

La dimostrazione dell'esistenza del generatore procede dapprima provando che essa esiste per ogni numero primo <math>p</math>, poi dimostrando che, se <math>a</math> è una radice primitiva di <math>p</math>, allora o <math>a</math> o <math>p+a</math> è una radice primitiva di <math>p^2</math>, e che questa è poi radice primitiva anche di ogni potenza successiva di <math>p</math>. Infatti, sia <math>a</math> una radice primitiva modulo <math>p</math>. Allora, per definizione di radice primitiva

Riga 54 ⟶ 52:

:<math>a^{\phi(p^{k-2})}\equiv 1 \mod p^{k-2},</math>

ossia

ovvero

:<math>a^{\phi(p^{k-2})}=1+lp^{k-2},</math>

Riga 71 ⟶ 69:

== Funzioni simmetriche delle radici primitive modulo p ==

Indicando con <math>g</math> il generatore di <math>\Z_p^*</math> allora, per quanto precedentemente esposto, tutte le radici primitive modulo <math>p</math> si potranno esprimere come <math>g^i</math> dove <math>(i,\phi(p))=(i,p-1)=1.</math> .

Indicando con <math>g</math> il generatore di <math>\Z_p^*</math> allora, per quanto precedentemente esposto, tutte le radici primitive modulo <math>p</math> si potranno esprimere come <math>g^i</math> dove <math>(i,\phi(p))=(i,p-1)=1</math> .

Gauss nelle Disquisitiones Arithmeticae dimostrò agli articoli 80 ed 81 il valore (modulo <math>p</math> primo) della somma delle radici primitive di <math>\Z_p</math> e del loro prodotto.

Riga 115 ⟶ 112:

moltiplicando la (2) per <math>({\tfrac{1}{y}})^{\phi(p-1)}</math> otteniamo:

(2) <math>A_0 y^{\phi(p-1)} +A_1 y^{\phi(p-1)-1}+\ldots+A_{n-1} y+1\equiv 0 \pmod{p}</math> Sottraendo la (1) alla (2') otteniamo:

(3) <math>(A_0 -1) y^{\phi(p-1)} +(A_1 -A_{n-1}) y^{\phi(p-1)-1}+\ldots+(A_{n-1}- A_1) y+(1- A_0)\equiv 0 \pmod{p}.</math>

In particolare il termine <math>A_0</math> vale <math>(-1)^{\phi(p-1)}\prod_{(i,p-1)=1} g^i </math> dove p diverso da tre, pertanto per qualsiasi <math>p</math> primo e maggiore di <math>3</math> si ha che <math>\phi(p-1)</math> è pari e quindi <math>A_0 \equiv 1 \pmod{p}</math>. Sostituendo tale valore nella (3) otteniamo che l'equazione ha, quindi, grado <math>\phi(p-1)-1</math> e della quale due radici sono <math>y</math> e <math>y^{-1}</math>; considerando le altre radici primitive a due a due, l'una l'inverso dell'altra, otteniamo sempre la stessa equazione (3) e quindi, in sintesi, la (3) si annulla per tutte le <math>\phi(p-1)</math> radici primitive ed ha grado <math>\phi(p-1)-1</math>. Ma allora è identicamente nulla e quindi <math>A_i =A_{\phi(p-1)-i}</math>.

Riga 123 ⟶ 120:

Allora in base alle considerazioni precedenti sappiamo:

:<math>x^{\phi(p-1)} -\mu(p-1)x^{\phi(p-1)-1}+\ldots-\mu(p-1)x+1\equiv\prod_{(i,p-1)=1} (x-g^i) \pmod{p}.</math>

Riportiamo alcuni esempi di tali polinomi:

Riga 158 ⟶ 155:

Sia il polinomio delle radici di ordine <math>q</math> il seguente:

:<math>p_q(x)=x^{q-1}+M_{q-2}x^{q-2}\ldots+M_2x^2+M_1x+M_0,</math>

ma allora il polinomio delle radici di ordine <math>2q</math> (radici primitive) sarà:

:<math>p_{2q}(x)=x^{q-1}-M_{q-2}x^{q-2}\ldots+M_2x^2-M_1x+M_0,</math>

in quanto ogni coefficiente di <math>p_{2q}(x)</math> è somma di prodotti di <math>s</math> radici opposte a quelle di <math>p_q(x)</math>, quindi il segno dipende dalla parità di <math>s</math> .

Riga 172 ⟶ 169:

che sappiamo fattorizzare in:

:<math>x^q -1 \equiv (x-1)(x^{q-1}+x^{q-2}+\ldots+x^2+x+1) \pmod{p},</math>

è immediato rilevare che

Riga 180 ⟶ 177:

e per quanto detto prima otteniamo:

:<math>p_{2q}(x) \equiv x^{q-1}-x^{q-2}+\ldots+x^2-x+1 \pmod{p},</math>

che è il polinomio delle radici primitive.

Riga 190 ⟶ 187:

* [[Tom M. Apostol]] (1976): Introduction to Analytic Number Theory, Springer-Verlag, New York. ISBN 0-387-90163-9 (Capitolo 10).

== Voci correlate ==

*[[Congettura di Artin]]

== Collegamenti esterni ==

*{{Collegamenti esterni}}

{{Portale|matematica}}

[[Categoria:Aritmetica modulare]]