Encore des racines carrées
Bonsoir
Il est écrit que, si $p$ est un nombre premier de la forme $4k+1$, alors $\frac{p-1}{2}!$ est congru à une racine de $x^2\equiv -1\pmod p$.
Pareillement, si $p$ est un nombre premier de la forme $4k+1$, existe-t-il une solution "simple" à $y^2\equiv \frac{p-1}{2}!$ ou $-\frac{p-1}{2}!\pmod p\ $ ?
("simple" = sans devoir passer, par exemple, par l'algorithme de Tonelli-Shanks. Et en laissant de côté le cas certainement marginal où $\frac{p-1}{2}!$ ou $-\frac{p-1}{2}!$ sont congrus à un carré d'arithmétique élémentaire, comme le sont $4$, $9$, $16$, $25$, $36$ ...)
Merci d'avance.
[LaTeX fournit la commande \pmod{p} qui donne $\pmod p$. ;-) AD]
Il est écrit que, si $p$ est un nombre premier de la forme $4k+1$, alors $\frac{p-1}{2}!$ est congru à une racine de $x^2\equiv -1\pmod p$.
Pareillement, si $p$ est un nombre premier de la forme $4k+1$, existe-t-il une solution "simple" à $y^2\equiv \frac{p-1}{2}!$ ou $-\frac{p-1}{2}!\pmod p\ $ ?
("simple" = sans devoir passer, par exemple, par l'algorithme de Tonelli-Shanks. Et en laissant de côté le cas certainement marginal où $\frac{p-1}{2}!$ ou $-\frac{p-1}{2}!$ sont congrus à un carré d'arithmétique élémentaire, comme le sont $4$, $9$, $16$, $25$, $36$ ...)
Merci d'avance.
[LaTeX fournit la commande \pmod{p} qui donne $\pmod p$. ;-) AD]
Connectez-vous ou Inscrivez-vous pour répondre.
Réponses
Alors je ne sais pas si la première assertion fait partie de la question, mais dans le doute, tu peut interpréter $\frac{(p-1)}{2}!$ comme $(-1)^{\frac{p-1}{2}}\frac{(p-1)!}{\frac{(p-1)}{2}!}$ (en remplaçant $k$ par $p-k$ dans la définition de la factorielle). Donc tu obtiens :
\[\frac{(p-1)}{2}!^2=(-1)^{\frac{p-1}{2}}\frac{(p-1)}{2}!\frac{(p-1)!}{\frac{(p-1)}{2}!}=(-1)^{\frac{p-1}{2}}(p-1)!=(p-1)! \pmod{p}\]
Car on a $p=1\pmod{4}$, tu peut alors conclure par le théorème de Wilson, tu as que $\frac{(p-1)}{2}!$ est une racine de $-1$ modulo $p$.
J'espère que ça te sera utile
Regarde le cas $p=5$.
On groupe les inversibles de $\mathbb{Z}/(p\mathbb{Z})$ par paquets de la forme $\{ x,-x,x',-x' \}$, où $x'$ est l'inverse de $x$.
On montre que deux paquets différents n'ont pas d'intersection.
Par exemple si $p=13$, les paquets sont $\{ 1, 12 \}$, $\{ 2, 6, 7, 11 \}$, $\{ 3, 4, 9, 10 \}$ et $\{ 5, 8 \}$.
En général un paquet a quatre éléments. Les exceptions potentielles sont
(1) $x \equiv -x$ qui implique $x' \equiv -x'$ et $x \equiv 0$.
Ce cas ne se présente jamais parce que l'on travaille avec les inversibles de $\mathbb{Z}/(p\mathbb{Z})$.
(2) $x \equiv x'$ qui implique $x^2 \equiv 1$ et $x^2 \equiv 1$ ou $-1$.
Ce cas se présente toujours.
(3) $x \equiv -x'$ qui implique $x^2 \equiv -1$.
Ce cas se présente si, et seulement si $-1$ est un carré modulo $p$.
Si l'on compte les inversibles de $\mathbb{Z}/(p\mathbb{Z})$ par paquets, on a
$$
p-1 = 4+4+4 ... +4+2 + \text{(éventuellement)}\; 2
$$
On constate que "éventuellement" a lieu si, et seulement si $p-1$ est un multiple de 4.
D'où le THEOREME
$-1$ est un carré modulo $p$ si, et seulement si $p$ est de la forme $4k+1$.
Si $p=13$, on a $5^2\equiv 8^2\equiv12$.
Même si tu changeais de pseudo, je pourrais te reconnaître rien qu'à ta manière de t'exprimer : ``truc est congru à une racine de $x^2 \equiv -1 \bmod p$''. Au lieu de $\text{truc}^2 \equiv -1 \bmod p$.
Mais ce n'est pas la question.
Au fait, est ce que tu veux que je te dise franchement ce que je pense de $\text{truc} = \left({p-1 \over 2}\right)!$ ? Tu me diras que ce n'est pas non plus la question. Mais c'est ma réponse. Car dans l'autre fil (qui s'est terminé en eau de boudin, comme on dit par chez moi, au prétexte que tu ne voulais pas jouer au super-jeu que j'avais préparé pour toi), j'ai bien vu ton espèce de fascination pour $ \left({p-1 \over 2}\right)!$. Fascination est un tantinet excessif. Mais je crois voir que cela te fait vachement plaisir de disposer d'une expression close pour une racine carrée de $-1$ quand $p \equiv 1 \bmod 4$. Je me trompe ?
Je vais essayer de trouver un tout petit truc à dire d'intelligent concernant ta question (tenir dans sa main une vraie racine quatrième de 1 quand le temps le permet. POUF-POUF : je voulais dire une vraie racine huitième de l'unité i.e. un $y$ tel que $y^4 \equiv -1 \bmod p$). Ce n'est pas sûr que j'y arrive. Et bien sûr, j'ai bien compris : point d'algorithme, ni celui de Shanks-Toenni, ni celui de Pierre ou Paul.
On se comprend un peu ?
Bon week-end.
En fait, quand $-1$ est un carré, trouver une racine carrée de $-1$ ne me pose pas trop de souci.
Mais je m'aperçois que je me suis trompée en écrivant mon message, hier soir ! Mille excuses !
Pour bien me faire comprendre, je vais prendre un exemple numérique, ce sera plus facile pour moi :
Soit $p=281$, c'est-à-dire un nombre premier de la forme $8k+1$ (et pas $4k+1$).
La formule $\frac{281-1}{2}!\pmod{281}$ me donne une racine carrée de $280\pmod{281}$ : C'est $53$.
Ma question est : Y a-t-il moyen de calculer tout aussi facilement une racine carrée de $53$ ?
Merci d'avance et encore pardon pour l'erreur.
Il n'y avait PAS d'erreur dans ton post initial. C'est seulement maintenant que tu te mélanges les pinceaux entre $-1$ et un $x$ qui vérifie $x^2 = -1 \bmod p$. Et à ton avis, cela vient d'où le fait que tu te mélanges les pinceaux ?
Tout part du théorème de Wilson: si $p$ est premier:$\overline{(p-1)!}=-\overline{1}$ dans les inversibles de $\mathbb{Z}/p\mathbb{Z}$.
Pour $k=1,...,r,$ on a:
\begin{equation}
r+k \equiv -r+k-1 \mod p \\
r+k \equiv -(r-(k-1)) \mod p
\end{equation} Ensuite
\begin{equation}
(p-1)!=1.2.3...r.(r+1)...(r+r) \equiv r!(-1)^rr(r-1)...1=(-1)^r(r!)^2 \mod p
\end{equation}
Si $p \equiv 1 \mod 4$, $p=4n+1$, $r=\frac{p-1}{2}=2n$ et donc: $(-1)^r=1$ et $\displaystyle (p-1)! \equiv (r!)^2 \mod p$, ce qui donne $\overline{r!}^2 = -\overline{1}$ d'après Wilson. Les deux seules solutions sont $-\overline{1}$ et $-\overline{r!}$.
p.s : dommage pour le dernier fil de Gil Bill (équation dans un anneau) qui laisse d'intéressantes questions en suspens !
Bonne journée...
@ claude quitté :
Je remarque que dans mon dernier message je semble vouloir opposer $4k+1$ à $8k+1$, ce qui est évidemment une stupide erreur puisque $8k+1=4k'+1$. Est-ce là que je m'emmêle les pinceaux ?
En résumé, voilà comment je vois les choses :
Modulo un nombre premier $p$ :
trouver une racine carrée d'un carré (évidemment) que j'appelle $a$ ci-dessous semble chose facile ou pas selon les circonstances.
Ainsi, si $p$ est de la forme $4k+3$ ou $8k+5$, c'est facile, dans le sens où il existe une méthode simple conduisant à la solution.
En revanche, si $p$ est de la forme $8k+1$, on dirait que les choses se compliquent. Mais, dans ce dernier cas, il y a malgré tout deux exceptions, dont la première est pour ainsi dire triviale :
1) Calculer les racines carrées de $a=1$ est facile puisque c'est $1$ et $-1$.
2) Calculer les racines carrées de $a=-1$ est aussi simple puisque c'est $\frac{p-1}{2}!$ et $-\frac{p-1}{2}!$
Est-ce bien exact ?
Maintenant, ce que j'aimerais savoir, c'est s'il existe encore l'une ou l'autre exception quand $p$ est de la forme $8k+1$. En particulier, j'aimerais savoir si calculer une racine carrée de $a=\frac{p-1}{2}!$ ou $a=-\frac{p-1}{2}!$ fait partie de ces apparemment trop rares exceptions.
Encore merci.
J'ai commencé à te répondre de la manière la plus précise possible. Mais j'ai fait une fausse manip et j'ai tout perdu. Je n'ai pas le courage de recommencer ce soir. Peut-être demain.
Ici je fais juste un petit montage de la NON utilité de $\big( {p-1 \over 2}\big)!$ pour le CALCUL d'une racine carrée de $-1$ lorsque $p \equiv 1 \bmod 4$. Ce qu'il faut regarder, ce sont les temps de calculs. Et me faire un peu confiance, car euh, ... les calculs, je connais deux ou trois petits trucs.
En tirant $y$ au hasard dans $\mathbb F_p$ et en posant $x = y^{p-1 \over 4}$.
Et maintenant avec $\big( {p-1 \over 2})!$.
Même chose avec un premier $p$ plus grand mais cette fois seulement avec la première méthode !
J'ai joué au même jeu que Claude avec Sage — au lieu de Magma, sauf erreur ? Les mesures au chronomètres sont comparables.
La méthode « tirer un élément au hasard jusqu'à tomber sur un générateur » aboutit en quelques essais et quelques centièmes de microsecondes.
La méthode de calcul de la factorielle prend 2 min 45.
Étonnant ? Il est nettement plus rapide de calculer la factorielle en invoquant « x = (i*x) %p » plutôt que de calculer dans le corps à $p$ éléments : 1 min 38.
Tu dis ``jusqu'à tomber sur un générateur''. C'est bien ce que tu veux dire ? Et pas ``jusqu'à tomber sur un non carré''?
Et je m'aperçois que j'ai oublié d'expliquer un truc : je tire $y$ au hasard. Et si $y$ n'est pas un carré, c'est le bonheur. En effet, on alors $y^{p-1 \over 2} \ne 1$ (ne pas être un carré) i.e. $y^{p-1 \over 2} = -1$. Si bien qu'en posant $x = y^{p-1 \over 4}$, on a $x^2 = -1$.
Autre chose : oui, je viens de vérifier que x := (i * x) mod p, c'est deux fois plus rapide que de calculer dans $\mathbb F_p$.
Merci de répondre avec autant de précision à mes questions.
Edit : Bon, sur l'essai suivant, la racine carrée produite provient d'un $y$ qui engendre un groupe d'indice $3$ de $\mathbf{F}_p^*$. Cela illustre, conformément à la remarque de Claude, qu'il y a plus de $y$ qui conviennent que de générateurs de $\mathbf{F}_p^*$.
Maintenant, je m'emballe peut-être.
On verra demain.
A moins que je ne me trompe :
Si $y$ est un non-carré :
- alors $y^{\frac{p-1}{4}}$ est une racine carrée de $-1$
- et $y^{\frac{p-1}{8}}$ est une racine carrée de $y^{\frac{p-1}{4}}$.
C'est bien ce que je souhaitais obtenir !
(A noter que, suite à une remarque de Soland, j'ai rectifié mon message initial en vue de bien préciser que $p-1$ devait être divisible par $8$).
Etes-vous d'accord ?
Maintenant, si on pose $y^{\frac{p-1}{8}}=n$, alors on a (presque) immédiatement les 4 racines 4-ièmes de $-1$ : $\{n,-n,n^{-1},-n^{-1}\}$
OUI, OUI, OUI, OUI.
J'étais sur le point de t'écrire pour te dire que $\left( {p-1 \over 2}\right)!$, ``cela nuit gravement à la santé''. Car d'une part cela ne sert à rien pour le calcul et surtout cela ne facilite pas le fait de prendre un certain recul STRUCTUREL. Oui, tout le sel de l'affaire est dans le polynôme $X^4 + 1$.
Et je t'ai même préparé un magnifique cadeau. Mon programme s'appelle GilBill.magma, si si, je t'assure. Et j'ai dû l'exécuter plusieurs fois pour avoir plusieurs tirages. Car un seul tirage, cela fait louche, cela sent l'arnaque. Regarde les temps de calculs.
Et si on continuait ? Petit résumé de la situation pour un nombre premier $p$, sachant que ci-dessous, cela se passe dans $\mathbb F_p = \Z/p\Z$ :
$$
\begin {array} {c}
p \equiv 1 \bmod 4 : \hbox {il existe $x$ tel que $x^2 = -1$ (prendre $x = y^{p-1 \over 4}$ avec $y$ non carré)} \\
p \equiv 1 \bmod 8 : \hbox {il existe $x$ tel que $x^4 = -1$ (prendre $x = y^{p-1 \over 8}$ avec $y$ non carré)} \\
p \equiv 1 \bmod 16 : \hbox {il existe $x$ tel que $x^8 = -1$ (prendre $x = y^{p-1 \over 16}$ avec $y$ non carré)} \\
\vdots \\
p \equiv 1 \bmod 2^k : \hbox {il existe $x$ tel que $x^{2^{k-1}} = -1$ (prendre $x = y^{p-1 \over 2^k}$ avec $y$ non carré)} \\
\end {array}
$$
J'espère que tu es d'accord.
Eh, bien, figure toi que maintenant tout est prêt pour le calcul d'une racine carrée dans $\mathbb F_p$ quelque soit le premier impair $p$. Je veux dire par là que pour $a \in \mathbb F_p^*$ carré, on peut élaborer un algorithme (efficace) qui calcule une racine carrée de $a$. Bien sûr, le fait que $a$ soit un carré se teste via $a^{p-1 \over 2} = 1$.
Il s'agit de l'algorithme de Shanks (ou Shanks-Tonelli).
On peut étudier cela si tu veux. Bien sûr, on ne fera PAS un coupé-collé de trucs trouvés sur le Net. On fera un ``truc à nous''. Je ne sais pas encore trop quoi (le truc à nous) mais ce n'est pas un problème. Comme parfois, dans les échanges, cela ne se passe pas toujours comme prévu (= comme JE le prévois), préférable que je ne prépare pas trop à l'avance.
Tu noteras que je suis en PLEIN dans le sujet du fil : Encore des racines carrées (et même toujours des racines carrées).
A toi.
Mais c'était une blague ! Ratée certes mais une blague quand même !
J'aurais peut-être dû écrire: "tu as semé la MORT et la DESOLATION sur ce fil" pour être sûr d'éviter toute ambiguïté.
Mais peu importe: je n'interviens plus du tout et vous épargne mes copiés-collés trouvés sur le net, promis-juré !
(Il y avait aussi des copiés-collés de cours cela dit...)
Bonne journée !
...
Tu n'y es pas du tout, ce n'est pas cela qui ..
Je constate qu'échanger sur un forum, c'est parfois délicat. Même avec des personnes de bonne foi ; évidemment, je parle de toi, Gil Bill, et moi (pas des autres qui s'étripent pour des choses souvent futiles).
Et je constate que parfois je lis trop vite (suis je le seul ?). J'avais proposé à Gil Bill un jeu (devinette) in http://www.les-mathematiques.net/phorum/read.php?3,1563074,1563932#msg-1563932 pour introduire Shanks (je ne voulais pas faire la totale) et j'ai cru qu'elle ne le voulait pas (jouer), cf http://www.les-mathematiques.net/phorum/read.php?3,1563074,1564044#msg-1564044. Mais en relisant ce post que je pointe, je vois qu'elle me demandait juste une précision. Hum, j'ai l'impression que ce paragraphe est clair comme du jus de boudin.
Bref, je savais plus quoi dire, quoi faire dans l'autre fil http://www.les-mathematiques.net/phorum/read.php?3,1563074,1564044#msg-1564044. Et donc j'ai fermé ma gu.ule.
Mais Gil Bill est tenace : elle (?) a relancé un autre fil (celui-ci) où l'on sent une adoration des racines carrées. Et là, je ne vois plus comment faire autrement : il faut absolument lui payer pour Noël un extracteur de racines carrées dans les corps $\mathbb F_p$.
J'ai eu beaucoup de mal à retrouver l'autre fil ``Equation dans un anneau''. Entre ceux qui ont un devoir à faire pour demain et ceux qui .. je zappe.
...
Seulement, il y a quinze jours cela aurait été parfait (tu as remarqué que j'étais alors prête à jouer au jeu que tu avais imaginé. Mais comme tu n'as pas continué, je n'ai pas osé insister), alors que maintenant ça tombe plutôt mal car, avec la fin d'année qui approche, je commence à ne plus avoir un moment à moi ni de temps à consacrer aux mathématiques.
J'espère que tu ne m'en veux pas. Peut-être une autre fois ?
Encore merci pour tout.
Mais non, je ne t'en veux pas du tout. Quelle idée. C'est de ma faute (j'ai cru que ... alors que ..) Dans la vie, cela s'appelle un rendez-vous manqué : on a rendez-vous, mais on se trompe d'heure, voire de jour ou de rue ...etc..
Et je comprends parfaitement que tu ne disposes plus de temps maintenant : les choses de la vie, c'est quand même plus important que les racines carrées dans $\mathbb F_p$ et l'algorithme de Shanks.
Bon courage à toi pour cette fin d'année. Et peut-être qu'en 2018, tu ouvriras un fil avec le mot clé ``Racines carrées et algorithme de Shanks''. Qui sait ?