Ivan Shishkin, Rye (1878)

Problems/FieldUnreviewed

Dénombrement des aa-miroirs de Fq\mathbb{F}_{q}

by FiniteField·
62
Difficulty scaleÉchelle de difficulté

This score reflects both the level of the required concepts and the difficulty of the solution.Ce score tient compte à la fois du niveau des notions nécessaires et de la difficulté de la résolution.

  1. 110First steps / middle schoolPremiers pas / collège
  2. 1125Beginner / high schoolDébutant / lycée
  3. 2650Intermediate / undergraduateIntermédiaire / licence
  4. 5170Advanced / graduateAvancé / master
  5. 7190Expert / specializedExpert / spécialisé
  6. 91100Research levelNiveau recherche
These levels are approximate guides.Ces niveaux sont des repères approximatifs.
·
Français

Showing the Français version because no English translation exists yet. Add that translation.

Unreviewed. This problem has not been reviewed by trusted users yet.

Soit pp un nombre premier impair, sNs\in\mathbb{N}^{*} et q=psq=p^{s} tel que q1mod4.q\equiv -1\mod 4. On définit l’ensemble des carrés non nuls par Sq={x2xFq{0}}S_{q}=\set{x^{2}\mid x\in \mathbb{F}_{q}\setminus\set{0}}. Soit aFq{0}a\in \mathbb{F}_{q}\setminus\set{0}, on dit que xFqx\in\mathbb{F}_{q} est un aa-miroir si (x,xa,x+a)Sq3.(x,x-a,x+a)\in S_{q}^{3}.
Déterminer le nombre de aa-miroirs de Fq.\mathbb{F}_{q}.

I solved itMark it doneAdd to my listKeep it in your list

References

  1. Il s'agit d'une partie d'un devoir maison que je donnais à mes étudiants en M2 cryptographie dans le cadre d'un cours sur les courbes elliptiques. Vous retrouverez l'énoncé complet du DM (plus complet) ici : https://fabiennarbonne.fr/wp-content/uploads/2025/05/dm-ce.pdf
Details

Export references

Hints

2

Hint 1

Open this only if you want a small nudge before looking at the solutions.

Solutions

1
Reveal solutionsAre you sure? Give it a try first.

Solution by FiniteField

Discussions0 useful votes

On note m(a)m(a) le nombre de aa-miroirs. On va calculer de différentes manières la somme
Σ=xFq((xq)+1)((x+aq)+1)((xaq)+1)\Sigma=\sum_{x\in\mathbb{F}_{q}}\left(\left(\dfrac{x}{q}\right)+1\right)\left(\left(\dfrac{x+a}{q}\right)+1\right)\left(\left(\dfrac{x-a}{q}\right)+1\right)(yq)\left(\dfrac{y}{q}\right) désigne le symbole de Legendre, c’est à dire (yq):=yq12=1\left(\dfrac{y}{q}\right):=y^{\frac{q-1}{2}}=1 si ySq,y\in S_{q}, (yq)=1\left(\dfrac{y}{q}\right)=-1 si ySqy\notin S_{q} et y0y\neq 0 et (0q)=0\left(\dfrac{0}{q}\right)=0. L’hypothèse q1mod4q\equiv -1\mod 4 est équivalente au fait que 1-1 n’est pas un carré dans Fq.\mathbb{F}_{q}. En effet, q12\dfrac{q-1}{2} est un entier impair donc (1q)=(1)q12=1\left(\dfrac{-1}{q}\right)=(-1)^{\frac{q-1}{2}}=-1.
Premier calcul
On remarque que xx est un aa-miroir si et seulement si ((xq)+1)((x+aq)+1)((xaq)+1)=8\left(\left(\dfrac{x}{q}\right)+1\right)\left(\left(\dfrac{x+a}{q}\right)+1\right)\left(\left(\dfrac{x-a}{q}\right)+1\right)=8 car chaque symbole de Legendre vaudra alors 1.1. Au contraire, si x,xax,x-a ou x+ax+a est un non carré alors le produit vaudra 0.0. Il nous reste à déterminer le cas où l’un des trois est nul. Si x=0x=0 alors a-a et aa ne peuvent être tous les deux des carrés car alors aa=1\dfrac{-a}{a}=-1 serait également un carré ce qui est exclus. Pour x=ax=a et x=ax=-a on aura dans la somme les termes :
4δ2:=((aq)+1)((2aq)+1)+((aq)+1)((2aq)+1)=2(2a2q)+2=2((2q)+1)4\delta_{2}:=\left(\left(\dfrac{a}{q}\right)+1\right)\left(\left(\dfrac{2a}{q}\right)+1\right)+\left(\left(\dfrac{-a}{q}\right)+1\right)\left(\left(\dfrac{-2a}{q}\right)+1\right)=2\left(\dfrac{2a^{2}}{q}\right)+2=2\left(\left(\dfrac{2}{q}\right)+1\right)δ2\delta_{2} vaut 11 si 22 est un carré dans Fq\mathbb{F}_{q} et 00 sinon.
On obtient donc
Σ=8m(a)+4δ2.\Sigma=8m(a)+4\delta_{2}.Second calcul
On développe l’expression de Σ\Sigma ce qui nous donne
Σ=xFq1+xFq(xq)+xFq(x+aq)+xFq(xaq)+xFq(x(x+a)q)+xFq(x(xa)q)+xFq((xa)(x+a)q)+xFq(x(xa)(x+a)q)\Sigma=\sum_{x\in\mathbb{F}_{q}}1+\sum_{x\in\mathbb{F}_{q}}\left(\dfrac{x}{q}\right)+\sum_{x\in\mathbb{F}_{q}}\left(\dfrac{x+a}{q}\right)+\sum_{x\in\mathbb{F}_{q}}\left(\dfrac{x-a}{q}\right)+\sum_{x\in\mathbb{F}_{q}}\left(\dfrac{x(x+a)}{q}\right)+\sum_{x\in\mathbb{F}_{q}}\left(\dfrac{x(x-a)}{q}\right)+\sum_{x\in\mathbb{F}_{q}}\left(\dfrac{(x-a)(x+a)}{q}\right)+\sum_{x\in\mathbb{F}_{q}}\left(\dfrac{x(x-a)(x+a)}{q}\right)On note ces 88 sommes Σ1,,Σ8\Sigma_{1},\dots,\Sigma_{8} dans l’ordre de la somme. On a tout d’abord Σ1=q\Sigma_{1}=q et on remarque que, grâce au changement de variable y=x+ay=x+a ou y=xay=x-a les sommes Σ2,Σ3\Sigma_{2},\Sigma_{3} et Σ4\Sigma_{4} sont toutes les trois égales. On peut calculer simplement Σ1\Sigma_{1} de deux manières différentes.

  1. Puisque Fq\mathbb{F}_{q} contient q12\dfrac{q-1}{2} carrés non nuls et q12\dfrac{q-1}{2} non carrés, Σ2=q12×1+q12×(1)=0.\Sigma_{2}=\dfrac{q-1}{2}\times 1+\dfrac{q-1}{2}\times(-1)=0.
  2. Grâce au changement de variable y=xy=-x et le fait que (1q)=1\left(\dfrac{-1}{q}\right)=-1 on a Σ2=Σ2=0\Sigma_{2}=-\Sigma_{2}=0.
    Ainsi Σ2=Σ3=Σ4=0.\Sigma_{2}=\Sigma_{3}=\Sigma_{4}=0.
    Puisque le premier terme de la somme Σ5\Sigma_{5} est nul on peut sommer sur les inversibles de Fq\mathbb{F}_{q} et on peut très bien multiplier le terme de la somme par (x2q)=1\left(\dfrac{x^{-2}}{q}\right)=1 ce qui donne
    Σ5=x0(1+ax1q)\Sigma_{5}=\sum_{x\neq 0}\left(\dfrac{1+ax^{-1}}{q}\right)Mais l’application xax1x\mapsto ax^{-1} étant une bijection de Fq×\mathbb{F}_{q}^{\times} l’application xFq×1+ax1x\in\mathbb{F}_{q}^{\times}\longmapsto 1+ax^{-1} atteint tous les éléments de Fq\mathbb{F}_{q} sauf 11. On compte donc q121\dfrac{q-1}{2}-1 carrés et q12\dfrac{q-1}{2} non carré ce qui donne Σ5=1\Sigma_{5}=-1. Les sommes Σ6\Sigma_{6} et Σ7\Sigma_{7} se calculent de la même manière et valent chacune 1-1 aussi. Enfin, on fait le changement de variable y=xy=-x dans Σ8\Sigma_{8} ce qui donne
    Σ8=yFq(y(y+a)(ya)q)=yFq(y(ya)(y+a)q)=Σ8.\Sigma_{8}=\sum_{y\in\mathbb{F}_{q}}\left(\dfrac{-y(-y+a)(-y-a)}{q}\right)=\sum_{y\in\mathbb{F}_{q}}\left(\dfrac{-y(y-a)(y+a)}{q}\right)=-\Sigma_{8}.Donc Σ8=0\Sigma_{8}=0. On peut donc conclure en identifiant ces deux calculs
    m(a)=q34δ28.m(a)=\dfrac{q-3-4\delta_{2}}{8}.
Report

For an unclear, ambiguous, or possibly incorrect statement, please use the Discussion tab on the right. Report content that needs moderator intervention, such as dangerous, clearly non-mathematical, or plagiarized content.