Enigme logarithme discret

[ouagaouaga]

Bonjour,

J`ai un probleme que j`ai presque du mal a resoudre.

a,b,c, x sont des entiers naturels > 1
pgcd(a,b)=1
pgcd(a,c)=1
pgcd(b,c)=1

On me donne :

a^x=b mod c

Exemple : 2^x=11 mod 101

Je connais a,b et c.
Je cherche a connaitre 2^(x-1)=? mod 101

Est-ce possible por ce cas? Les nombres etant petits on peut s`en sortir par la force brute.
Est-ce possible peu importe la taille en termes de chiffres des valeurs de a,b, et c? Y a-t-il une solution generale?

Merci.

[Skullkid]

Bonjour, en faisant tous les calculs modulo c, comme a et c sont premiers entre eux, a est inversible d'inverse avec l'indicatrice d'Euler. Donc dès que tu sais calculer , ce qui revient à peu près à connaître la décomposition de c en facteurs premiers, tu peux calculer .

Dans ton exemple, comme , et .

[ouagaouaga]

Merci beaucoup pour ces precisions.
Tant que l`on sait c est un nombre premier il est facile de calculer phi(c) et donc de resoudre 2^(x-1).
Avec un c compose il devient difficile de le factoriser si c`est un nombre type RSA.
Quant a savoir a quoi est egal (x-1) c`est le trou noir je pense.

[ouagaouaga]

Pour a=2
j`ai une solution plus simple :

2^x=11 mod 101

Comme 11 est un nombre impair je rajoute a 11 le nombre 101 =112 et je divise par 2 cela me donne 56.

Mieux encore pour chaque equation :

2^x = b mod c

c doit etre un nombre premier impair
b impair

2^(x-1) = (b+c)/2

On peut continuer pour 2^(x-1) pour obtenir 2^(x-2)
Si (b+c)/2 est impair on lui rajoute le nombre c et on divise par 2 sinon on divise par 2

Cela donne la suite suivante :
56
28
14
7
54
27
64
32
16
8
4
2
1

La suite finissant toujours par 1 on arrete et on sait que si 2^x = 11 mod 101 cela implique x=13

Bien sur si x est de grande taille on ne va pas s`amuser a descendre de rang (x-1,x-2,x-3,etc...) jusqu`a atteindre une puissance de 2 (64 qui correspond a 2^6 et qui se manifeste apres 7 iterations qui donne x=7+6=13).
Il y a un petit raccourci assez complexe mais trouvable a mettre en place pour resoudre facilement de maniere generale l`equation 2^x = b mod c
Saurez-vous trouver ce fameux raccourci qui vous permettrait de toucher la medaille Fields ou la medaille Abeel?

[ouagaouaga]

J`oublie une chose importante a vous signaler vous avez tout pour resoudre de maniere definitive l`enigme de la suite de Collatz.
Vous prenez n`importe quel grand nombre premier c (10000000000000000000000000000000000 de chiffres si vous voulez).
Vous choisissez un nombre entier b tel que : 0< b < c
si b est impair vous le rajoutez a c et vous divisez par 2 : (b+c)/2
Si b est pair vous le divisez par 2 et vous continuez avec le nombre obtenu en appliquant la meme procedure.
Vous aurez une suite qui finira ineluctablement par 1.
Cette suite n`est que la suite des modulos 2^x mod c (x correspondant a 2^x=b mod c).

c=1783

2^x = 1394 mod 17831394

1394 (2^x mod 1783)
697 (2^(x-1) mod 1783)
1240 etc...
620
310
155
969
1376
688
344
172
86
43
913
1348
674
337
1060
530
265
1024
512
256
128
64
32
16
8
4
2
1

Il est facile ensuite d`en deduire que x=30 en comptant le nombre d`iterations jusqu`au nombre 2.

[ouagaouaga]

Dans la suite de Collatz chaque fois qu`un nombre est impair vous le mulipliez par 3 et vous rajoutez 1.
Cela equivaut a rajouter un nombre impair a un impair :

k est impair
u(1)=3k+1
Or 3k+1-k=2k+1

Exemple k=13
13 est impair
U(1)=13*3+1=40
Or 40-13=27
On obtient 40 pair on divise par 2 etc..

On revient a mon cas ou on a chaque fois un nombre impair different d`ou les differences de vol etc...
Dans mon cas on rajoute un nombre premier impair (fixe) aussi grand soit-il et on obtient une suite qui conduit necessairement a 1
On peut choisir c impair compose mais la on ne sait quand le cycle interviendra.
On est sur qu`il est plus court que pour un nombre premier impair.

Pour c=9

2^x=5 mod 9

On aura une suite courte :

5 (5+9=14 14/2=7
7 (7+9=16 16/2=8)
8 (8/2=4
4 (4/2=2)
2 (2/2=1)
1

En y mettant plus de rigueur on aurait demontre la suite de Collatz.
Nul besoin de pousser les calculs a 10^1000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000 pour confirmer que la suite de Collatz finira toujours par 2^k, 2^(k-1)....8,4,2,1

[Ben314]

Salut,
Comme tu semble râler que personne ne regarde ton truc, je m'y colle...

Il y a clairement une énorme erreur de logique élémentaire dans ton raisonnement concernant la suite de Collatz :
S'il est parfaitement vrai (et complètement évident) que, quelque soit le modulo M choisi, la suite de Collatz modulo M va retomber sur 1 au bout d'un certain temps, y compris si le modulo est très très grand, cela n'implique absolument pas que la suite vu dans l'ensemble des nombres entiers retombe sur 1.

Pour te donner un exemple complètement con, si tu prend la suite Un définie par U0=1 et U(n+1)=U(n)+1, alors quelque soit le modulo M choisi, aussi grand soit-il, cette suite vue modulo M fini par donner 0 à un moment donné alors que très clairement, dans l'ensemble des entiers, elle ne donne jamais 0.

C'est une erreur archi classique de logique des personnes qui n'ont jamais fait de math. :
- Si un entier A est congru à 1 modulo M pour tout entier M alors A est égal à 1 : ça c'est vrai, il suffit de prendre M plus grand que A.
- Donc, dans la suite de Collatz, s'il existe un entier N tel que, pour tout entier M, on ait U_N congru à 1 modulo M alors U_N=1 : ça c'est vrai en vertu du point précédent.
- Par contre, si quelque soit le modulo M, il existe un entier N tel que U_N est congru à 1 modulo M, ben ça prouve pas du tout qu'il existe un N tel que U_N est égal à 1 car l'entier N dépend de M.
Or, sauf erreur, c'est ce dernier truc que tu as "démontré"

[ouagaouaga]

Merci d`avoir repondu meme si le sujet fondamental ici est la solution du logarithme discret.
Collatz n`etant qu`une consequence.
Il me semble que tu n`as pas bien l`argument de l`analogie.
On ne calcule pas de modulo dans la suite de Collatz.
Si le nombre est impair on multiplie par 3 et on rajoute 1.
Cela c`est Collatz.
Qu`est-ce que l`on fait dans Collatz on rajoute (addition au lieu de multiplication) un nombre impair a un nombre impair.
3k+1-k=2k+1 qui est necessairement impair.
Dans Collatz ce nombre ajoute est variable. Il change a chaque fois.
Dans mon algo qui concerne 2^x mod c , on rajoute a chaque fois un nombre fixe et on finira ineluctable par tomber sur un nombre impair y tel que (y+c)/2 soit une puissance de 2.
Dans mon algo il n`y pas de vol. Parce que c est fixe. Dans Collatz ce nombre similaire a mon c est variable d`ou les vols. Ca monte ca monte et cela redescend.
Comment prouver que Collatz finit par toujours par un quelque soit le nombre pris au depart? En prouvant que le vol et les differentes variations cachent en fait une descente inelustable qui est lie au fait que l`on divise par 2 quand le nombre est pair.
Mieux encore en supposant a>2 (a-3) il y a une autre formule dont j`ai la solution qui conduira a des puissances de 3 descendantes (3^k,3^(k-1),.....,27,9,3,1. Sauf que les conditions a tester sont : si le nombre est divisible par 3 on divise par 3 sinon on rajoute un nombre specifique dependant de c (je n`entre pas dans le detail). Je peux le faire pour n`importe quel a (1521341331^x par exemple ou on divise par ce nombre 1521341331 si le nombre est divisible par ce nombre sion on rajoute un nombre specifique etc...).
A mon avis tu n`as pas tres bien lu ce que j`ai ecrit. Ton erreur majeure.
Relis, essaie de comprendre et ensuite parle de logique etc...
Il faut d`abord bien comprendre ce que j`ai ecrit avant de denoncer une erreur de logique.

[ouagaouaga]

Juste un petit detail biographique.
Il y a plus de 40 ans j`avais fait un Deug MASS a Jussieu. On m`accuse de n`avoir jamais fait de maths!? J`ai 7 freres et soeurs ils sont tous maths (ingenieurs et +).
J`ai ete oblige pour des raisons materielles de quitter et de travailler tres tot pour reprendre ensuite des etudes dans un autre domaine (agriculture).
En plus, j`ai travaille longtemps sur les problemes d`epistemologie et des structures cognitives (Piaget vous connaissez?).
Je dispose de temps libre et j`ai cesse de travailler comme salarie il y a quelques decennies deja.
Je ne m`interesse pas qu`aux mathematiques. J`ai plusieurs centres d`interet dans ma vie reelle.
Ce sont juste les dernieres "salves" et je lance uniquement des idees. Aux jeunes d`exploiter ces idees.
J`ai quelques annees a vivre vu que ma sante me condamne a vivre aux mieux 3 annees.
Que feriez-vous a ma place?
J`ai meme souvent du mal a me concentrer ou a memoriser (Alzheimer tape peut-etre a ma porte?)
Je pense d`ailleurs arreter Internet et me remettre exclusivement a la lecture et a l`ecriture sans echanges avec quiconque.
Bref desole pour cette parenthese (inutile et egoiste surtout).