Divertissement (5)

Bonsoir, claude quitté, et grand merci d'intervenir.

Je me doute que la programmation informatique peut venir facilement à bout de ce problème. Mais, comme je n'y connais rien du tout en programmation, pourrais-tu me dire au bout de combien d'opérations la machine te donne un résultat ?

Bonne soirée !

@ claude quitté :

Je sais que le gouffre qui me sépare des spécialistes en cette matière est sans fond.

C'est ce qui doit expliquer mon enthousiasme, peut-être exagéré aux yeux des autres, quand je vois que j'arrive à résoudre le problème posé - et quelques autres exactement du même genre - en un nombre de calculs que l'on peut compter sur les doigts d'une main.

En 1993 ? Je n'avais pas encore vu le jour.
:-)

Bravo, claude quitté d'avoir compris ce que j'avais en tête et bravo JLT de l'avoir traduit en calculs ! (calculs dont j'avais écrit qu'on pouvait les compter sur les doigts d'une main.)

Juste une question :
Si la théorie connaît cette méthode pour ce type de problème précis, où la trouver ? J'en cherche des traces sur la toile, mais sans succès. En même temps, je ne sais pas vraiment où chercher. Je cherche surtout du côté de "logarithme discret - nombres premiers de Mersenne".

Encore bravo et merci d'avoir joué !
Sneg.

Merci, JLT, pour ces précieuses précisions. C'est très instructif et cela fait plaisir de voir que quelqu'un s'intéresse à mon "énigme".

@ claude quitté :

Voici comment j'interprète avec mes mots l'explication de nodgim :

Pour $p$ premier de la forme $p=2^k-1$, c'est-à-dire premier avec $2$, on a :
d'une part, $2^k\equiv 1 \pmod{p}$, vu la forme de $p$,
et d'autre part, $2^{p-1}\equiv 1\pmod{p}$, d'après le petit théorème de Fermat.
Donc, si $k\leq p-1$, alors $k$ est un diviseur de $p-1$, en vertu de la citation que j'ai notée entre guillemets dans mon message précédent et qui est tirée des Disquisitiones Arithmeticae de Gauss, en effet. Afin de respecter l'orthographe employée par Gauss, ou plus exactement celle de son traducteur, j'ai même écrit le mot "exposants" sans la lettre "t", mais AD a préféré corriger…

En ce moment, je ne suis pas sur mon ordinateur, mais, dès que j'en aurai le temps, je posterai mes notes personnelles concernant ce problème. Ainsi, tu pourras, si tu le souhaites, faire dessus toutes les remarques que tu jugeras nécessaires.

A+

@ claude quitté :

En règle générale, les mathématiciens professionnels sont plutôt critiques envers mes petits travaux, qu'ils qualifient, au mieux, de "bricolage". Tu n'es donc pas le seul à pinailler. C'est la raison pour laquelle je garde maintenant mes démonstrations pour moi. Mais pour toi, je vais quand même faire une exception, sachant à l'avance que ça finira quand même mal pour moi. Voici donc ci-dessous, extraite de mes notes personnelles, ma solution à cette énigme.

D'après l'énoncé du problème, on a $7^x\equiv 2\pmod{p}$, pour $p$, premier, valant $2$.$147$.$483$.$647$.
D'autre part, d'après le petit théorème de Fermat, on a $7^{p-1}\equiv 1\pmod{p}$.
Enfin, d'une façon générale, $1\equiv p+1\pmod{p}$. Et, ici, $p+1=$ $2$.$147$.$483$.$648=2^{31}$. (Cette décomposition en facteurs premiers s'effectue facilement au moyen d'une simple calculette capable d'afficher dix chiffres.)

Ainsi, ce qu’il y a de particulier dans ce problème c’est que $p$ soit un nombre premier de Mersenne, conjugué au fait que la racine primitive modulo p élevée à la puissance $x$ soit congrue à une puissance de $2$. Et c’est ce qui rend la résolution de ce problème particulière, c’est-a-dire particulièrement simple :

On a : $1\equiv p+1\equiv 2^{31}\equiv (7^{x})^{31}\equiv 7^{31x}\pmod{p}$.
Et si $7^{31x}\equiv 1\pmod{p}$, alors $31x\equiv 0\pmod{p-1}$. (Voir ce que Gauss écrit au n°48 de ses Disquisitiones Arithmeticae.)

(Pardonne-moi, claude quitté, de citer encore une fois Gauss, mais - en guise de réponse au point 4 de ton dernier message - si je le fais, c'est pour m'éviter de devoir démontrer une chose qui a déjà été démontrée ailleurs et bien mieux que je ne pourrais le faire.)

Ce qui entraîne :
$31x=(p-1)y$ $(y\in \mathbb{Z})$
$x=\frac{(p-1)y}{31}$
$x=69$.$273$.$666$ $y$ (facilement calculable avec la calculette).

Dans l'intervalle des entiers compris entre $1$ et $p-1$ où $x$ est recherché, ce dernier peut donc prendre 31 valeurs différentes. Mais pour $a=69$.$273$.$666$, on a, ou bien $x=a$, ou $x=2a$, ou $x=3a$, … , ou $x=31a$, le "ou" étant exclusif car un seul de ces exposants est tel que $7^x\equiv 2\pmod{p}$. En effet, ces 31 exposants $a, 2a, ... , 31a$ sont tous inférieurs ou égaux à $p-1=31a$, et toutes les puissances entières strictement positives de $7$ inférieures ou égales à $7^{(p-1)}$ sont incongrues modulo p, vu que $7$ est une racine primitive modulo p.

Heureusement, quelque chose évite de devoir passer en revue chacune de ces 31 valeurs de $x$ jusqu'à tomber sur la bonne, et rend à nouveau simples les calculs. C'est l'affirmation suivante :
Puisque l'une des 30 puissances de $7$ parmi $7^{a}, 7^{2a}, … , 7^{30a}$ est congrue modulo p à $2$
(à noter que $7^{31a}$ est exclue du lot puisque $7^{31a}\equiv 7^{p-1}\equiv 1\pmod{p}$),
il s'ensuit que les 31 puissances que sont $7^{a}, 7^{2a}, ... , 7^{31a}$ sont toutes congrues modulo p à une puissance de $2$ dont aucune n’est congrue à une autre.
(à noter que $7^{31a}\equiv 1\equiv 2^{0}\pmod{p}$).

[La - longue - démonstration de cette affirmation figure dans mes notes manuscrites, mais je ne l'ai pas encore retranscrite sur mon ordinateur, pardonne-moi. C'était amusant à faire, mais j'ai dû consacrer un certain temps rien qu'à ce point important de mon petit travail, j'avoue. Peut-être les mathématiciens professionnels trouveront-ils cela facile.]

Ceci permet de terminer rapidement les calculs, de cette façon :

On choisit une puissance de $7$ parmi $7^{a}$, $7^{2a}$, … , $7^{30a}$ au hasard, sachant que, quelle qu'elle soit, elle sera de toute façon congrue à une puissance de $2$ modulo p. Ici, comme je suis une fille simple, je choisis la puissance $7^{a}$ et introduis dans un logiciel de calcul la commande suivante :

$$mod(7^{a}, p)$$
Réponse : $512$, soit, en factorisant, $2^9$.

Ce résultat permet de dresser le tableau suivant, où la solution apparaît clairement :

$$\begin {array}{|c|c|c|c|c|c|c|c|c|}
\hline
\wedge & a & 2a & 3a & 4a & 5a & 6a & 7a & \phantom{1} \\
\hline
7 & 2^9 & 2^{18} & 2^{27} & 2^5 (*) & 2^{14} & 2^{23} & 2 (**) & \pmod{p} \\
\hline
\end{array}$$

$(*)$ $7^{4a}\equiv 7^{3a}\times 7^{a}\equiv 2^{27}\times 2^{9}\equiv 2^{36}\equiv 2^{31}\times 2^5\equiv 1\times 2^5\equiv 2^5\pmod{p}$
$(**)$ $7^{7a}\equiv 7^{6a}\times 7^{a}\equiv 2^{23}\times 2^{9}\equiv 2^{32}\equiv 2^{31}\times 2^1\equiv 1\times 2^1\equiv 2\pmod{p}$

[A noter qu'on peut s'éviter ce dernier travail en introduisant simplement dans un logiciel de calcul, par exemple WolframAlpha, la commande suivante :
solve $9x-31y=1$ for $x$ and $y$ integers
Réponse : $x=31n+7$ and $y=9n+2$ and $n\in \mathbb{Z}$.
La solution souhaitée est la plus petite valeur strictement positive de $x$, c'est-à-dire $7$.]

L'$x$ recherché vaut $7a=7\times 69$.$273$.$666=$ $484$.$915$.$662$.

Remarque, en réponse au point 3 de ton dernier message, claude quitté :
Quand le module $p$ est un nombre premier de la forme $2^k-1$, toute puissance de $2$ inférieure à $2^k$ - à savoir $2^1$, $2^2$, … , $2^{k-1}$ - est inférieure à $p$. Donc, la valeur de son résidu modulo $p$ est égale à sa valeur propre, qui n'est jamais égale à $1$. Et cela, contrairement à $2^k$ qui est congru à $1$ modulo $p$ puisque $2^k-1\equiv 0 \pmod{p}$ (tout nombre non nul est divisible par lui-même). Par conséquent, quand le module $p$ est un nombre premier de la forme $2^k-1$, $k$ est l'ordre modulo $p$ de $2$. Je ne l'ai pas mentionné parce que cela me semblait évident. En toute rigueur, j'aurais dû. Dans ce problème, le fait que $31$ soit l'ordre de $2$ modulo $p$ justifie le tableau, les explications introduites par les astérisques $(*)(**)$ ainsi que la commande saisie sur WoframAlpha.

Pourquoi escalader une montagne si un hélicoptère peut nous déposer facilement au sommet ?
Pour l'exploit.

Dans ce fil, "l'exploit" consiste à résoudre des problèmes liés au logarithme discret sans recourir à de grands moyens de calcul.

Ainsi, le problème initial de ce fil consistait à trouver $x$, le plus petit entier strictement positif tel que $\alpha^x\equiv 2 \pmod{p}$, où $\alpha$ était une certaine racine primitive modulo $p=2^{31}-1=$ un nombre premier de Mersenne.
Et cela, en ne saisissant dans un logiciel de calcul pas plus d'une commande.

Dans ce message, il s'agit de trouver $x$, le plus petit entier strictement positif tel que $\alpha^x\equiv 2 \pmod{p}$, où $\alpha=46073$ est une racine primitive modulo $p=65537=$ un nombre de Fermat premier. (Comment parler des nombres premiers de Mersenne sans parler des nombres premiers de Fermat ?)
Et cela, en ne saisissant dans un logiciel de calcul pas plus de deux commandes.

Je souhaite un peu de fraîcheur à celles et ceux qui habitent dans des régions particulièrement chaudes de France.
Sneg.
(Mon pseudo veut dire "neige". Si ça peut rafraîchir un peu l'atmosphère...)

Bravo, JLT, et merci d'avoir une dernière fois bien voulu jouer avec moi sur ce fil.