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

Ce contenu prolonge un autre article, dont il reprend les notations.

Pour en savoir davantage, allez lire le contenu rédigé dans l'article 359.

Soit à calculer le résidu modulo $15007$ du produit $12345\times 6789.$ Vous souhaitez éviter le calcul direct du produit $12345\times 6789.$

En utilisant la méthode de Head, vous allez faire intervenir des nombres dont la valeur absolue est strictement inférieure à $30014.$

Calculez $T$ et $t$

Par définition, $T$ est égal à :

T = \left\lfloor \sqrt{15007}+\frac{1}{2}\right\rfloor.

D’une part $120^2 =14400$ et d’autre part $130^2 =16900.$ Vous avez donc l’encadrement :

120\lt\sqrt{15007}\lt130.

Il reste à déterminer un encadrement plus précis. Vous calculez $125^2=15625.$ Il est donc démontré que :

120\lt\sqrt{15007}\lt125.

Vous poursuivez avec $122^2 =(120+2)^2 = 14400+480+4 =14884$ d’où :

122\lt\sqrt{15007}\lt125.

Puis $123^2 =(122+1)^2 = 14884+122+123 =14884+200+45 =15084+45 =15129$ d’où :

122\lt\sqrt{15007}\lt123.

Enfin, $122{,}5^2 =15006{,}25$ ce qui montre que :

122{,}5\lt\sqrt{15007}\lt123.

En ajoutant $\frac{1}{2}$ il vient :

123\lt\sqrt{15007}+\frac{1}{2}\lt123{,}5\lt124.

Par conséquent, $123$ est le plus grand entier inférieur ou égal à $\sqrt{15007}+\frac{1}{2}.$ Donc :

\boxed{T = 123.}

Comme $t = T^2-15007 =15129-15007=122$ vous déduisez :

\boxed{t = 122.}

Les deux premières divisions euclidiennes

Vous constatez que :

\begin{align*} 12345 &= 100\times 123+45\\ 6789 &= 55\times 123+24. \end{align*}

Vous notez $a = 100\comma$ $b = 45\comma$ $c = 55$ et $d = 24$ de sorte que :

\begin{align*} 12345 &= a\times T+b\\ 6789 &= c\times T+d. \end{align*}

Dans la suite, toutes les congruences sont écrites modulo $15007.$ En développant le produit $(aT+b)(cT+d)$ et en utilisant le fait que $T^2\equiv t$ modulo $15007$ vous avez :

12345\times 6789 \equiv act+(ad+bc)T+bd.

Le résidu de $ad+bc$ modulo $15007$

Vous avez :

\begin{align*} ad+bc &= 100\times 24+45\times 55\\ &= 2400 + 2500-25\\ &=4900-25\\ &=4875. \end{align*}

Ce nombre étant strictement inférieur à $15007\comma$ c’est son propre résidu. En posant $z = 4875$ vous déduisez :

12345\times 6789 \equiv act+zT+bd.

Effectuez une troisième division euclidienne

Vous calculez le produit $ac.$

ac = 5500.

Vous effectuez la division euclidienne de ce nombre par $T.$

5500 = 44\times 123 + 88.

Vous posez $e =44$ et $f = 88$ pour avoir $ac = eT+f.$

D’où :

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

Calculez le résidu de $et+z$ modulo $15007$

D’une part :

et = 44\times 122 = 5368.

D’autre part :

et+z = 5368 + 4875=10243.

Ce nombre est strictement inférieur à $15007$ donc modulo $15007$ il vient :

et+z\equiv 10243.

En posant $v = 10243$ vous avez obtenu :

12345\times 6789 \equiv ft+vT+bd.

Effectuez une quatrième division euclidienne

Vous divisez $v$ par $T$ ce qui fournit :

10243 = 83\times 123+34.

Vous posez $g = 83$ et $h = 34$ pour avoir $v = gT+h.$

Alors modulo $15007$ vous avez :

\begin{align*} 12345\times 6789 &\equiv ft+(gT+h)T+bd\\ &\equiv ft+gT^2+hT+bd. \end{align*}

Or, $T^2\equiv t$ modulo $15007$ d’où :

12345\times 6789 \equiv ft+gt+hT+bd.

Concluez

Vous calculez $ft$ comme suit :

ft = 88\times 122 = 10736.

Vous calculez ensuite $gt$ et l’ajoutez à $ft.$

\begin{align*} gt &= 83\times 122=10126\\ ft+gt &= 10736+ 10126=20862. \end{align*}

Comme le résultat dépasse $15007$ vous formez le résidu de $ft+gt$ modulo $15007.$

\begin{align*} ft+gt&\equiv 20862 – 15007\\ &\equiv 5855. \end{align*}

Vous calculez ensuite $hT$ et l’ajoutez au résidu de $ft+gt$ modulo $15007.$

\begin{align*} hT &= 34\times 123= 4182\\ (ft+gt)+hT &\equiv 5855 + 4182 \\ &\equiv 10037. \end{align*}

Enfin, vous calculez $bd$ et l’ajoutez au résidu précédent.

\begin{align*} bd &= 45\times 24 = 1080\\ ((ft+gt)+hT)+bd &\equiv 10037 + 1080 \\ &\equiv 11117. \end{align*}

Comme $0\leq 11117 \lt 15007\comma$ il s’agit bien du résidu cherché. Finalement, modulo $15007$ vous avez :

\boxed{12345\times 6789 \equiv 11117.}