Ivan Shishkin, Rye (1878)

Problems/Field

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. 1–10First steps / middle schoolPremiers pas / collège
  2. 11–25Beginner / high schoolDébutant / lycée
  3. 26–50Intermediate / undergraduateIntermédiaire / licence
  4. 51–70Advanced / graduateAvancé / master
  5. 71–90Expert / specializedExpert / spécialisé
  6. 91–100Research levelNiveau recherche
These levels are approximate guides.Ces niveaux sont des repères approximatifs.
·
ReviewedReviewed by Sequoia
·
Français

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

Soit pp un nombre premier impair, s∈N∗s\in\mathbb{N}^{*} et q=psq=p^{s} tel que q≡−1mod  4.q\equiv -1\mod 4. On définit l’ensemble des carrés non nuls par Sq={ x2∣x∈Fq∖{ 0 } }S_{q}=\set{x^{2}\mid x\in \mathbb{F}_{q}\setminus\set{0}}. Soit a∈Fq∖{ 0 }a\in \mathbb{F}_{q}\setminus\set{0}, on dit que x∈Fqx\in\mathbb{F}_{q} est un aa-miroir si (x,x−a,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

Download: BibTeXJSON

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
Σ=∑x∈Fq((xq)+1)((x+aq)+1)((x−aq)+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)Où (yq)\left(\dfrac{y}{q}\right) désigne le symbole de Legendre, c’est à dire (yq):=yq−12=1\left(\dfrac{y}{q}\right):=y^{\frac{q-1}{2}}=1 si y∈Sq,y\in S_{q}, (yq)=−1\left(\dfrac{y}{q}\right)=-1 si y∉Sqy\notin S_{q} et y≠0y\neq 0 et (0q)=0\left(\dfrac{0}{q}\right)=0. L’hypothèse q≡−1mod  4q\equiv -1\mod 4 est équivalente au fait que −1-1 n’est pas un carré dans Fq.\mathbb{F}_{q}. En effet, q−12\dfrac{q-1}{2} est un entier impair donc (−1q)=(−1)q−12=−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)((x−aq)+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,x−ax,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)où δ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
Σ=∑x∈Fq1+∑x∈Fq(xq)+∑x∈Fq(x+aq)+∑x∈Fq(x−aq)+∑x∈Fq(x(x+a)q)+∑x∈Fq(x(x−a)q)+∑x∈Fq((x−a)(x+a)q)+∑x∈Fq(x(x−a)(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=x−ay=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 q−12\dfrac{q-1}{2} carrés non nuls et q−12\dfrac{q-1}{2} non carrés, Σ2=q−12×1+q−12×(−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 (x−2q)=1\left(\dfrac{x^{-2}}{q}\right)=1 ce qui donne
    Σ5=∑x≠0(1+ax−1q)\Sigma_{5}=\sum_{x\neq 0}\left(\dfrac{1+ax^{-1}}{q}\right)Mais l’application x↦ax−1x\mapsto ax^{-1} étant une bijection de Fq×\mathbb{F}_{q}^{\times} l’application x∈Fq×⟼1+ax−1x\in\mathbb{F}_{q}^{\times}\longmapsto 1+ax^{-1} atteint tous les éléments de Fq\mathbb{F}_{q} sauf 11. On compte donc q−12−1\dfrac{q-1}{2}-1 carrés et q−12\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=∑y∈Fq(−y(−y+a)(−y−a)q)=∑y∈Fq(−y(y−a)(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)=q−3−4δ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.