Est-il possible de choisir des entiers n, m, c et un nombre assez
important (1 million) d'entiers differents x_i de sorte que: (x_i)^m =
c mod n pour tout i ?
Cette action est irreversible, confirmez la suppression du commentaire ?
Signaler le commentaire
Veuillez sélectionner un problème
Nudité
Violence
Harcèlement
Fraude
Vente illégale
Discours haineux
Terrorisme
Autre
Francois Grieu
écrit:
Est-il possible de choisir des entiers n, m, c et un nombre assez important (1 million) d'entiers differents x_i de sorte que: (x_i)^m = c mod n pour tout i ?
Le problème est mal posé. Il faut au moins dire: d'entiers x_i differents (modulo n) sinon il n'y a qu'a fixer n>0, x_0 arbitraire, x_i = x_0 + i*n, c = x_0^m mod n, et le tour est joué. En cryptographie, cette solution trivale pourrait se convertir en une attaque.
Même avec cette restriction, oui, cela est possible, au moins si l'on peut choisir n; je crois voir une solution pour n = 20364840299624512075310661735. Si m, c et/ou n sont imposés, le problème est plus difficile, souvent impossible mathématiquement ou pratiquement.
Je ne dirais pas comment on résoud cet ammusant exercice à un inconnu complet.
François Grieu
sansnompatronymique@yahoo.fr écrit:
Est-il possible de choisir des entiers n, m, c et un nombre assez
important (1 million) d'entiers differents x_i de sorte que:
(x_i)^m = c mod n pour tout i ?
Le problème est mal posé. Il faut au moins dire:
d'entiers x_i differents (modulo n)
sinon il n'y a qu'a fixer n>0, x_0 arbitraire,
x_i = x_0 + i*n, c = x_0^m mod n, et le tour est joué.
En cryptographie, cette solution trivale pourrait se convertir
en une attaque.
Même avec cette restriction, oui, cela est possible, au moins
si l'on peut choisir n; je crois voir une solution pour
n = 20364840299624512075310661735.
Si m, c et/ou n sont imposés, le problème est plus difficile,
souvent impossible mathématiquement ou pratiquement.
Je ne dirais pas comment on résoud cet ammusant exercice
à un inconnu complet.
Est-il possible de choisir des entiers n, m, c et un nombre assez important (1 million) d'entiers differents x_i de sorte que: (x_i)^m = c mod n pour tout i ?
Le problème est mal posé. Il faut au moins dire: d'entiers x_i differents (modulo n) sinon il n'y a qu'a fixer n>0, x_0 arbitraire, x_i = x_0 + i*n, c = x_0^m mod n, et le tour est joué. En cryptographie, cette solution trivale pourrait se convertir en une attaque.
Même avec cette restriction, oui, cela est possible, au moins si l'on peut choisir n; je crois voir une solution pour n = 20364840299624512075310661735. Si m, c et/ou n sont imposés, le problème est plus difficile, souvent impossible mathématiquement ou pratiquement.
Je ne dirais pas comment on résoud cet ammusant exercice à un inconnu complet.
François Grieu
Francois Grieu
écrit:
Est-il possible de choisir des entiers n, m, c et un nombre assez important (1 million) d'entiers x_i differents [on comprendra différents modulo n] de sorte que: (x_i)^m = c mod n pour tout i ?
J'ajoute que le problème du titre (où le module n et l'exposant m sont égaux) est une variante encore plus amusante, qui AHMA peut aussi se résoudre.
François Grieu
sansnompatronymique@yahoo.fr écrit:
Est-il possible de choisir des entiers n, m, c et un nombre assez
important (1 million) d'entiers x_i differents [on comprendra
différents modulo n] de sorte que:
(x_i)^m = c mod n pour tout i ?
J'ajoute que le problème du titre (où le module n et l'exposant m
sont égaux) est une variante encore plus amusante, qui AHMA peut
aussi se résoudre.
Est-il possible de choisir des entiers n, m, c et un nombre assez important (1 million) d'entiers x_i differents [on comprendra différents modulo n] de sorte que: (x_i)^m = c mod n pour tout i ?
J'ajoute que le problème du titre (où le module n et l'exposant m sont égaux) est une variante encore plus amusante, qui AHMA peut aussi se résoudre.
