Équation dans un anneau

Bonsoir,

for x in range(1009):
    if x**2 % 1009 == 10:
        print(x)

donne $x=162$ et $x=847$.

Cordialement,

Rescassol

Bonjour
L'entier $1009$ est un nombre premier. Je pense donc qu'un titre plus approprié aurait été ``Calcul d'une racine carrée dans un corps fini''. Soient $k$ un corps fini de caractéristique distincte de $2$, par exemple $k = \mathbb F_p$ avec $p \ne 2$, et $a \in k^*$. On veut tester si $a$ est un carré dans $k$ et si oui, fournir $x \in k$ tel que $x^2 = a$. La première étape est classique : il suffit de vérifier que $a^{q-1 \over 2} = 1$ dans $k$ où $q$ est le cardinal de $k$

En ce qui concerne la deuxième étape, il y a de nombreux algorithmes extrêmement efficaces. Je donne sans justification celui de Peralta (en fait Peralta en a fourni deux et peut-être même plus). On introduit la $k$-algèbre quotient :
$$
A = k[t] = {k[T] \over \langle T^2 - a \rangle} = k \oplus kt
$$
On prend $z \in k$ au hasard et on calcule dans $A$ (rappel : $q$ est le cardinal de $k$) :
$$
(t + z)^{q - 1 \over 2} =: ut + v \qquad (\star)
$$
Si $v \ne 0$, on recommence en tirant un autre $z$. Et si $v = 0$, alors BINGO : $x := au$ vérifie $x^2 = a$.

La probabilité d'échec est $1/2 - 3/(2q)$. Il faut bien sûr JUSTIFIER tout cela.

Je le fais ci-dessous avec un premier un petit peu grand pour éviter que Rescassol ne fasse une boucle. L'algorithme de Peralta est l'un des plus faciles à mettre en oeuvre à l'aide d'un système de Calcul Formel. Il faut bien sûr que l'exponentiation qui figure en $(\star)$ soit réalisée de manière efficace ; plusieurs algorithmes d'exponentation dichotomique existent à cet effet.

> p := NextPrime(Random(10^60, 10^70)) ;
> p ;
2520691243364850802392683345062485878247042198148568127985385710535839
> a := Random(1, p-1)^2 mod p ;
> a ;
1324682026938555366521631342489401350723268112521704072089746068004123
> k := GF(p) ;                          
> kT<T> := PolynomialRing(k) ;      
> A<t> := kT / ideal < kT | T^2 - a > ;             
> A ;                                               
Univariate Quotient Polynomial Algebra in t over Finite field of size 2520691243364850802392683345062485878247042198148568127985385710535839
with modulus t^2 + 1196009216426295435871052002573084527523774085626864055895639642531716
> uv := (t + Random(k))^ExactQuotient(p-1,2) ; 
uv ; 
1909862038721300635579952572080704299722351475301277948575201044102230*t
> x := a*Coefficient(uv,1) ;                        
> x ;
477223070361857948320228175608591542433617008859365577276493674702720
> x^2 - a ;
0

Hello (Gil Bill et df)
Du coup, je suis revenu des années en arrière et je propose une petite suite. Une remarque : je n'ai pas donné de références bibliographiques concernant le calcul d'une racine carrée dans un corps fini, mais il suffit de faire ``Square Roots in Finite Fields'' sous votre moteur de recherche préféré pour obtenir un certain nombre de pointeurs.

Le coup de $p \equiv 3 \bmod 4$ est ce que l'on appelle le cas hyper-facile de l'algorithme de Shanks. L'algorithme de Shanks (ou de Tonelli-Shanks) est un algorithme purement multiplicatif (par opposition à l'algorithme de Peralta).

Voici les étapes possibles pour une suite dite cas facile de l'algorithme de Shanks

1) On suppose que $p \equiv 5 \bmod 8$ de sorte que l'on peut écrire $p-1 = 2^2 \ r$ avec $r$ impair ($p-1$ est l'ordre du groupe $\mathbb F_p^{*}$). Contempler l'égalité pour $a \in \mathbb F_p^*$:
$$
a = \left(a^{r+1 \over 2}\right)^2 \ (a^r)^{-1}
$$
On a a fortiori $p \equiv 1 \bmod 4$. On suppose disposer d'un élément $i \in \mathbb F_p^*$ d'ordre 4 i.e. $i^2 = -1$. Pour $ a \in \mathbb F_p^*$, on a :
$$
a^r \in \{ i^0,\ i^1,\ i^2, i^3 \}
$$
Pourquoi ? Si de plus $a$ est un carré, $a^r$ ce n'est pas n'importe quelle puissance de $i$. Quid ?

Chute. Pour $a$ carré dans $\mathbb F_p^*$, on pose :
$$
x = a^{r+1 \over 2} \qquad \fbox {Alors ou bien $a = x^2$ ou bien $a = (ix)^2$}
$$
Bilan : si $a$ est un carré, on sait calculer une racine carrée de $a$. Modulo le fait de disposer de $i$ tel que $i^2 = -1$.

2) Toujours dans le cas $p \equiv 5 \bmod 8$, je dis que Gil Bill dispose d'un $i \in \mathbb F_p^*$ tel que $i^2 = -1$ (suite à un certain fil). De quoi je parle ?

Conclure.

Pour prendre du recul :

3) Soit $G$ un groupe commutatif fini d'ordre $N = 2^k \ r$ avec $r$ impair. On définit :
$$
G_0 = \{ x \in G \mid x^{2^k} = 1 \}, \qquad \qquad G_1 = \{ y \in G \mid y^r = 1 \}
$$
Il faut montrer que $G$ est le produit direct de $G_0$ et $G_1$ au sens où $G = G_0G_1$ et $G_0 \cap G_1 = \{1\}$. Pour un $a \in G$ donné, il est recommandé d'obtenir la décomposition $a = a_0 a_1$ dans $G = G_0G_1$.

4) Soit $a \in G$. Alors $a$ est un carré dans $G$ si et seulement si $a_0$ est un carré dans $G_0$.

@df
Pourquoi $2$ comme exposant ? (je parle du 2 de de $i^2$). Parmi $\{0, 1, 2, 3\}$, certains nombres sont pairs et d'autres sont impairs (là, je ne me mouille pas). Do you see what I mean ? Et en prenant par exemple $a = 1$ (qui est un carré), alors $a^r$, cela fait $1$.

Bon je retente avec le cas 8k+5:

Si $q=8k+5$, $q-2 \equiv 3 \pmod 8$, donc l'un des facteurs premiers de $q-2$ est de la forme $8k+3$ ou $8k-3$.
Si on note $p'$ ce facteur, on a $q \equiv 2 \pmod {p'}$, et par suite:

\begin{equation}
\displaystyle (\frac{q}{p'}) = (\frac{2}{p'}) = (-1)^{\frac{p'^2 - 1}{8}}.
\end{equation}

Or, si $p = 8k \pm 3$, alors $(p'^2-1)/8$ est impair et $q$ est non-résidu quadratique modulo $p$.

Je continue d'ânonner ! Mais au moins, est-ce dans le bon sens ?
...

@df
Tu étais bien parti dans ton PREMIER post sur cette histoire. D'abord $p-1 = 4r$ par définition même. Donc pour tout $b \in \mathbb F_p^*$, on a $(b^r)^4 = 1$ i.e. $b^r$ est dans $\{i^0,\ i^1,\ i^2,\, i^3 \}$. Supposons maintenant $a = b^2$; alors $a^r$ est une puissance paire de $i$ donc $a^r = i^0 = 1$ ou bien $a^r = i^2$. Dans les deux cas, $a^r$ est un carré EXPLICITE dans $\{i^0,\ i^1,\ i^2,\, i^3 \}$ (il suffit de faire un test).

Et en ayant contemplé la formule donnée au début de mon post, alors .. cela doit donner que $a$ est un carré EXPLICITE ..

@Gil Bill : tu peux fournir $i$ dans le cas $p \equiv 5 \bmod 8$, n'est ce pas ?

@claude: D'accord, j'ai bien compris. Merci beaucoup !
(Je cogite sur le 3)...)

@Gil Biil
Oui, c'est bien le fil dont tu parles. On y a écrit que la loi de réciprocité complémentaire pour le premier $2$ disait que $2$ est un carré modulo $p$ si et seulement si $p \equiv \pm 1 \bmod 8$. Et du coup, $2$ n'est pas un carré modulo $p$ si $p \equiv 3,5 \bmod 8$. Si bien que pour $p \equiv 5 \bmod 8$, en posant :
$$
i = 2^{p-1 \over 4} \quad \hbox {on a, modulo $p$,} \qquad i^2 = 2^{p-1 \over 2} = \left( {2 \over p} \right) = -1
$$

@Gil Biil, @df
Est ce que la chose vitale de la semaine (calcul d'une racine carrée d'un carré de $\mathbb F_p^*$) est acquise dans les cas faciles $p \equiv 3 \bmod 4$ d'une part et $p \equiv 5 \bmod 8$ d'autre part ?

Comment je vois la suite ? Eh bien, on marchait tranquillement le long du chemin ... Et tout d'un coup, un bolide à plus de 100 kms à l'heure. De quoi je parle ? De l'algorithme de Shanks fourni par df. Si vous le comprenez, c'est tant mieux. Mais mon intention n'était pas de faire la totale. Juste une INITIATION à l'algorithme de Shanks. Et la prochaine étape que j'avais prévue, c'est le cas $p \equiv 9 \bmod 16$ i.e. $p -1 = 2^3r = 8r$ avec $r$ impair. Mais contre les bolides, on ne peut pas lutter.

Bonjour,

@claude: oui le cas est bien compris pour $p \equiv 3 \mod 4$ et $p\equiv 5 \mod 8$...
Ce sont les cas résolus par Gauss semble-t-il, de même que le cas $8k+1$.
Je suis en train d'étudier ce dernier . Je le publierai tout à l'heure.

Pour en revenir à l'algorithme de Shank, si l'ordre de G est une puissance de 2 et si je t'ai bien lu, le $i$ convoité doit s'écrire en base 2.
...

Pour en revenir au cas $p=8k+5$.
Par le critère d'Euler : $$ a^{\tfrac{p-1}{2}} \equiv 1 \pmod p
$$ Donc $\displaystyle a^{\tfrac{p-1}{4}} \equiv \pm1 \pmod p$.

C'est une conséquence du petit théorème de Fermat. Si $p$ ne divise pas $a$ : \begin{equation}
a^{p-1} \equiv 1 \pmod p
\end{equation} D'où : \begin{equation}
(a^{(p-1)/2} - 1)(a^{(p-1)/2} + 1) \equiv 0 \pmod p
\end{equation} et: $a^{(p-1)/2} \equiv \pm 1 \pmod p$.

$\bullet~$Si $\displaystyle a^{\tfrac{p-1}{4}} \equiv 1 \pmod p$, alors en posant $x \equiv a^{k+1} \pmod p$, on a : $$
x^2 \equiv a^{2k + 2} \equiv a^{\tfrac{p+3}{4}} \equiv a^{\tfrac{p-1}{4}}.a \equiv a \pmod p
$$ $\bullet~$Si $a^{\tfrac{p-1}{4}} \equiv -1 \pmod p$, alors $x\equiv 2^{2k+1}a^{k+1}$ fournit une solution puisque : $$
x^2 \equiv 2^{4k+2}a^{2k+2} \equiv 2^{\tfrac{p-1}{2}} a^{\tfrac{p+3}{4}} \equiv \big(\frac{2}{p}\big).a^{\tfrac{p-1}{4}}.a \equiv -1.-1.a \equiv a \pmod p
$$ $a$ est résidu quadratique modulo $p$.
Il reste le cas $p \equiv 1 \pmod 8$ que l'on peut traiter par l'algorithme de Shank afin de s'épargner des calculs modulo des puissances de 2 de plus en plus élevées.

Pour la question 3), je me demandais si il ne fallait pas faire intervenir les sous-groupes de $\mathbb{F}_p^*$ dont l'ordre divise une puissance de 2.
Les "2-Sylow sous-groupes" de $\mathbb{F}_p^*$ pour ne pas les nommer.
...

bonjour @claude: je parlais de la question 3) de ce fil où tu parles du groupe commutatif fini G d'ordre $N=2^kr$, produit direct de $G_0$ et $G_1$.
En voulant faire le lien avec les carrés modulo $p$, je suis tombé sur les groupes de Sylow mais je me suis probablement égaré moi aussi.

Effectivement tu as semé la désolation dans ce fil !
...