359. La multiplication modulo n selon la méthode de Head (1/2)

Dans ce contenu, $n$ désigne un entier naturel supérieur ou égal à $2.$

Vous notez $x$ et $y$ deux entiers naturels strictement inférieurs à $n$ dont vous souhaitez calculer le résidu du produit $xy$ modulo $n$ en manipulant des nombres entiers dont la valeur absolue est strictement inférieure à $2n.$ Vous direz alors qu’il n’y a pas de débordement.

Un premier lemme

Vous notez $T$ la partie entière du réel $\sqrt{n}+\frac{1}{2}\comma$ c’est-à-dire :

\boxed{T = \left\lfloor \sqrt{n}+1/2 \right\rfloor.}

Notez que $1\leq \sqrt{2}+\frac{1}{2}\leq \sqrt{n} + \frac{1}{2}.$ Comme $T$ est par définition le plus grand entier inférieur ou égal à $\sqrt{n} + \frac{1}{2}$ vous déduisez que $1\leq T.$

Vous posez ensuite :

\boxed{t = T^2-n.}

D’une part :

T\leq \sqrt{n}+\frac{1}{2}.

Comme ces deux réels sont positifs, en élevant au carré, il vient :

\begin{align*} T^2 &\leq \left(\sqrt{n}+\frac{1}{2}\right)^2\\ &\leq n+\frac{1}{4}+\sqrt{n}. \end{align*}

En retranchant $n\comma$ vous déduisez :

\begin{align*} T^2-n &\leq \frac{1}{4}+\sqrt{n}\\ t &\leq \frac{1}{4}+\sqrt{n}. \end{align*}

Par définition de $T\comma$ l’entier $T+1$ est strictement supérieur à $\sqrt{n} + \frac{1}{2}$ d’où :

\begin{align*} \sqrt{n}+\frac{1}{2} & \lt T+1 \\ \sqrt{n}&\lt T+\frac{1}{2}\\ \sqrt{n}+\frac{1}{4}&\lt T + \frac{3}{4}. \end{align*}

En cumulant les inégalités obtenues, vous obtenez :

t\lt T+\frac{3}{4}.

Or, $T+\frac{3}{4} \lt T+1$ du coup $t\lt T+1.$ Comme $t$ et $T$ sont deux entiers, il vient :

\boxed{t\leq T.}

D’autre part :

\begin{align*} \sqrt{n} + \frac{1}{2} &\lt T+1\\ \sqrt{n}-\frac{1}{2}&\lt T. \end{align*}

Comme $n\geq 2$ vous avez $\sqrt{n}\geq 1$ et $\sqrt{n}-\frac{1}{2}$ est un nombre positif. En élevant au carré, il vient :

\begin{align*} n+\frac{1}{4}-\sqrt{n} &\lt T^2\\ n-T^2 &\lt \sqrt{n}-\frac{1}{4}. \end{align*}

Or :

\begin{align*} \sqrt{n}-\frac{1}{2}&\lt T \\ \sqrt{n}&\lt T +\frac{1}{2}\\ \sqrt{n}-\frac{1}{4} &\lt T +\frac{1}{4}. \end{align*}

En cumulant ces inégalités, vous déduisez :

\begin{align*} n-T^2\lt T+\frac{1}{4}\\ -t \lt T+\frac{1}{4}. \end{align*}

Comme $T+\frac{1}{4} \lt T+1$ vous avez :

-t\lt T+1.

Comme $-t$ et $T+1$ sont des entiers vous obtenez :

\boxed{-t\leq T.}

En résumé, la valeur absolue de l’entier $t$ est majorée par l’entier positif $T\comma$ ce qui s’écrit :

\boxed{\vert t \vert \leq T.}

Deux autres lemmes

D’une part :

T\leq \sqrt{n}+\frac{1}{2}.

D’autre part :

T-1\leq \sqrt{n}-\frac{1}{2}.

Les entiers $T$ et $T-1$ étant positifs, par produit, il vient :

T(T-1)\leq n-\frac{1}{4}.

Du coup :

\boxed{T(T-1)\lt n.}

Ensuite, partant de $T\leq \sqrt{n}+\frac{1}{2}$ et en élevant au carré deux réels positifs vous avez :

T^2\leq n+\frac{1}{4}+\sqrt{n}.

Comme $8 \lt 9$ il vient en prenant la racine carrée $2\sqrt{2}\lt 3$ et donc $\frac{3+2\sqrt{2}}{4}\lt \frac{6}{4}$ d’où $\frac{3+2\sqrt{2}}{4}\lt \frac{3}{2}\lt 2 \leq n.$ Par suite :

\begin{align*} &\frac{3+2\sqrt{2}}{4}\lt n\\ &\frac{1+2+2\sqrt{2}}{4}\lt n\\ &\left(\frac{1+\sqrt{2}}{2}\right)^2\lt n\\ &\frac{1+\sqrt{2}}{2}\lt \sqrt{n}\\ &1+\sqrt{2} \lt 2\sqrt{n}\\ &\sqrt{2}\lt 2\sqrt{n}-1\\ &2\lt (2\sqrt{n}-1)^2\\ &0 \lt (2\sqrt{n}-1)^2-2\\ &0 \lt 4n-4\sqrt{n}-1\\ &1+4\sqrt{n} \lt 4n\\ &1/4+\sqrt{n} \lt n\\ &n+1/4+\sqrt{n} \lt 2n\\ &T^2 \lt 2n. \end{align*}

Le second résultat est établi :

\boxed{T^2\lt2n.}

Effectuez deux divisions euclidiennes

L’entier $x$ est positif et l’entier $T$ est strictement positif. Il existe un quotient $a\geq 0$ et un reste $b\in\llbracket 0, T-1\rrbracket$ tels que :

x = aT+b.

Si l’entier $a$ était strictement supérieur à $T\comma$ alors $a$ serait supérieur ou égal à $T+1$ et par produit, $aT$ serait supérieur ou égal à $T^2+T.$ Comme $b$ est positif, vous auriez $x\geq T^2+T.$ Comme $-t\leq T$ il vient $n-T^2\leq T$ et $n\leq T^2+T.$ Par cumul d’inégalités vous auriez $x\geq n$ ce qui contredit le fait que $x$ est strictement inférieur à $n.$

Par suite :

\boxed{0\leq a \leq T.}

En effectuant le même raisonnement sur l’entier $y$ vous déduisez l’existence d’un entier $c$ et d’un reste $d\in\llbracket 0, T-1\rrbracket$ tels que :

\left\{\begin{align*} &y = cT+d\\ &0\leq c\leq T. \end{align*} \right.

Effectuez le produit $xy$

Vous partez des relations suivantes :

\left\{\begin{align*} x&=aT+b\\ y&=cT+d. \end{align*} \right.

Après multiplication, vous avez :

\begin{align*} xy &= acT^2+(ad+bc)T+bd\\ &= ac(T^2-n)+(ad+bc)T+bd+nac\\ &= act+(ad+bc)T+bd+nac. \end{align*}

Modulo $n$ il en résulte que :

xy\equiv act+(ad+bc)T+bd.

Obtenez le résidu de $ad+bc$ modulo $n$

Il est rappelé ce qui suit :

\left\{\begin{align*} &0\leq a \leq T\\ &0\leq d \leq T-1. \end{align*} \right.

Par produit, vous obtenez :

0\leq ad \leq T(T-1) \lt n.

De même :

\left\{\begin{align*} &0\leq b \leq T-1\\ &0\leq c \leq T. \end{align*} \right.

Par produit, vous obtenez :

0\leq bc \leq T(T-1) \lt n.

Par somme, le nombre $ad+bc$ appartient à l’ensemble $\llbracket 0, 2n-1\rrbracket.$ Vous restez bien avec une valeur strictement inférieure à $2n.$

Si $ad+bc$ appartient à l’ensemble $\llbracket 0, n-1\rrbracket$ vous posez $z = ad+bc.$

Sinon, $ad+bc$ appartient à l’ensemble $\llbracket n, 2n-1\rrbracket$ et par suite $ad+bc-n$ appartient à $\llbracket 0, n-1\rrbracket.$ Vous posez $z = ad+bc-n.$

Dans les deux cas, vous avez un nombre $z$ appartenant à l’ensemble $\llbracket 0, n-1\rrbracket$ de sorte que, modulo $n$ la congruence suivante est vérifiée :

z\equiv ad+bc.

Modulo $n$ vous avez montré que :

xy\equiv act+zT+bd.

Effectuez une troisième division euclidienne

Il est rappelé que :

\left\{\begin{align*} &0\leq a \leq T\\ &0\leq c \leq T. \end{align*} \right.

Le produit $ac$ est positif et il est inférieur ou égal à $T^2.$ Comme il a été vu que $T^2\lt2n\comma$ vous êtes assuré de pouvoir effectuer ce produit sans atteindre ni dépasser $2n.$

Une fois ce produit effectué, vous n’allez pas le réduire modulo $n$ mais vous allez effectuer la division euclidienne de $ac$ par $T.$ Il existe un quotient $e\geq 0$ et un reste $f\in\llbracket 0, T-1\rrbracket$ tels que :

ac = eT+f.

Comme $f$ est positif et comme $ac\leq T^2$ il vient :

eT\leq T^2.

Comme $T\gt0$ en divisant vous obtenez :

\boxed{0\leq e\leq T.}

Du coup :

\begin{align*} xy&\equiv act+zT+bd\\ &\equiv (eT+f)t+zT+bd\\ &\equiv ft+(et+z)T+bd. \end{align*}

Effectuez une réduction modulo $n$

Vous majorez la valeur absolue de $et$ comme suit :

\begin{align*} \vert et\vert &\leq \vert e \vert \times \vert t \vert\\ &\leq T\times T\\ &\leq T^2. \end{align*}

Comme $T^2\lt2n$ il n’y a pas de débordement. Ainsi, $et \in\llbracket 1-2n, 2n-1\rrbracket.$ Parmi les quatre nombres $et\comma$ $et-n\comma$ $et+n$ et $et+2n$ il y en a un qui est égal au résidu de $et$ modulo $n.$

Comme $z$ est égal à son propre résidu modulo $n\comma$ la somme du résidu de $et$ et de $z$ appartient à $\llbracket 0, 2n-2\rrbracket.$ Quitte à lui soustraire $n\comma$ vous déduisez sans débordement la valeur du résidu $v$ modulo $n$ de $et+z.$ Il en résulte que :

xy \equiv ft+vT+bd.

Effectuez une quatrième division euclidienne

Vous divisez $v$ par $T.$ Il existe un quotient $g\geq 0$ et un reste $h\in\llbracket 0, T-1\rrbracket$ tels que :

v = gT+h.

Si $g\gt T\comma$ alors $g\geq T+1$ et $gT\geq T^2+T$ donc $v\geq T^2+T.$ Or il a été vu que $T^2+T\geq n$ donc $v\geq n$ ce qui contredit le fait que $v\in\llbracket 0, n-1\rrbracket.$ Donc :

\boxed{0\leq g\leq T.}

Vous en déduisez que :

\begin{align*} xy &\equiv ft+vT+bd\\ &\equiv ft+(gT+h)T+bd\\ &\equiv ft+gT^2+hT+bd\\ &\equiv ft+g(T^2-n)+hT+bd\\ &\equiv ft+gt+hT+bd. \end{align*}

Concluez

Il a été vu que :

\begin{align*} &0\leq f\leq T-1\\ &\vert t \vert \leq T. \end{align*}

Par produit $\vert ft \vert$ est inférieur ou égal à $T(T-1)$ et comme $T(T-1)\lt n$ vous avez $\vert ft \vert \lt n$ ce qui prouve que le résidu modulo $n$ de $ft$ est calculable sans débordement.

De même :

\begin{align*} &0\leq g\leq T\\ &\vert t \vert \leq T. \end{align*}

Par produit $\vert gt \vert$ est inférieur ou égal à $T^2$ et comme $T^2\lt2n$ vous avez $\vert gt \vert \lt 2n$ ce qui prouve que le résidu modulo $n$ de $gt$ est calculable sans débordement.

En poursuivant :

0\leq h\leq T-1.

Par produit $hT$ est inférieur ou égal à $T(T-1)$ et comme $T(T-1)\lt n$ vous avez $hT\lt n$ ce qui prouve que $hT$ est déjà égal à son propre résidu modulo $n.$

Enfin, vous avez :

\begin{align*} &0\leq b\leq T-1\\ &0\leq d\leq T-1\leq T. \end{align*}

Par produit $bd$ est inférieur ou égal à $T(T-1)$ et comme $T(T-1)\lt n$ vous avez $bd\lt n$ ce qui prouve que $bd$ est déjà égal à son propre résidu modulo $n.$

Vous calculez ensuite sans débordement le résidu modulo $n$ de $ft+gt.$ La somme des résidus de $ft$ et de $gt$ appartient à $\llbracket 0, 2n-2\rrbracket\comma$ et le résidu cherché est soit égal à cette somme, soit égal à cette somme diminuée de $n.$

Puis vous calculez le résidu modulo $n$ de $(ft+gt)+hT$ en effectuant la somme des deux résidus précédents quitte à soustraire une fois $n.$

En définitive, vous calculez le résidu modulo $n$ de $((ft+gt)+hT)+bd$ en effectuant la somme du résidu de $(ft+gt)+hT$ et du résidu de $bd\comma$ sans débordement, quitte à soustraire $n$ encore une fois si nécessaire.

Comme $xy\equiv ft+gt+hT+bd$ modulo $n$ vous avez bien obtenu le résidu du produit $xy$ modulo $n$ en restant toujours avec des nombres dont la valeur absolue est strictement inférieure à $2n.$