Question sur le modulo

[me_ww]

bonsoir,

Je ne suis que en debut de seconde mais j'ai besoin d'une aide qui conserne les modulos... Je voudrais savoir comment calculer les facteur d'un modulo voila un exmple de calcule sur le quel je reste :hein: :

6 x d % 224 = 1

d = nombre à calculer devent le quel je bloque;
% = modulo (signe informatique C/C++)

le resulta doit etre = 1 donc voila si qql a une metode merci d'avance

[haydenstrauss]

donc en fait en mathématique sa revient a :

6d=1 mod 224
donc

6d=1+224k

k un entier

donc (6d)/(224k)=1

si tu trouve pas je t'aiderai un peu plus

oublie pas kon connais c'est d quil faut aider

[Aguila]

Euh... je crois plutôt que c'est:

6d mod 224 = 1

Donc on a 224|6d-1, où autrement dit il existe k entier tel que 6d-1=k*224. Et sauf erreur il n'y a pas de solution pour cette équation.

[haydenstrauss]

je croi que le omodule c'est 224 maintenant si c'est pas sa aguilera a raison

[haydenstrauss]

Euh... je crois plutôt que c'est:

6d mod 224 = 1

Donc on a 224|6d-1, où autrement dit il existe k entier tel que 6d-1=k*224. Et sauf erreur il n'y a pas de solution pour cette équation.

6d mod 224 = 1

je comprend pas ça veu rien dire la

[rene38]

Bonsoir

Euh... je crois plutôt que c'est:6d mod 224 = 1
Donc on a 224|6d-1, où autrement dit il existe k entier tel que 6d-1=k*224. Et sauf erreur il n'y a pas de solution pour cette équation.

Hors informatique, en mathématiques j'écrirais
Quant à la conclusion, ( n'a pas de solution) elle ne comporte pas d'erreur : elle découle de la parité des 2 membres

[haydenstrauss]

donc en fait en mathématique sa revient a :

6d=1 mod 224
donc

6d=1+224k

k un entier

donc (6d)/(224k)=1

si tu trouve pas je t'aiderai un peu plus

oublie pas kon connais c'est d quil faut aider

ouais je suis trop con :

6d=1+224k

k un entier

donc (6d)/(224k)=1

la réponse c :

6d=1+224k

k un entier

donc (6d)/(1+224K)=1

donc 1/d=(6)/(1+224K) donc

d=1/ [(6)/(1+224K) ]=(1+224k)/(6)


ouais donc la réponse contient un parametre k d=1/ [(6)/(1+224K) ]=(1+224k)/(6) est toujours vrament quelquesoi k appartenant a N

[rene38]

d=1/ [(6)/(1+224K) ]=(1+224k)/(6) est toujours vrament quelquesoi k appartenant a N

Pas très clair ...
Plus simplement, et étant des entiers,
est pair quel que soit l'entier
est pair quel que soit l'entier donc est impair quel que soit l'entier .
L'équation dans d'inconnue n'a donc aucune solution.

[me_ww]

Eu.. ok bon primo je me suis trompe dans l'énonce 224 doit etre le resulta de (p-1)(q-1) ; p et q 2 nombres premier. alors que pour former 224 j'ai pris 17 et 15...

donc si j'ai repris 2 autres nombres et l'operation est donc :

23 x d % 4752 = 1 ou 23d mod 4752 ; 4752 = (67-1)(73-1)

et dosio n'oubliez que je ne suis que en debut de seconde et que je ne suis pas une bete en maths donc soyait un max claire et expliquez bien vos calcule.^^

[haydenstrauss]

je ne crois pasetre capable de resoudre sa mais faire en seconde c'est lamentable c'est trop dure

[haydenstrauss]

donne l'énoncé exacte stp au complet stp :)

[me_ww]

ba on va dire que je suis en seconde mais que ça c'est pas un exercice de cours... j'ai est besoin pour de la cryptographie, RSA si qql un conné.

alors l'enoncer on va dire que c'est :


-Prendre deux nombres premiers p et q (de taille à peu près égale). Calculer n = pq.
-Prendre un nombre e qui n'a aucun facteur en commun avec (p-1)(q-1). [oops je me suis trompé ici ]
-Calculer d tel que ed mod (p-1)(q-1) = 1

Bon meme si 23 x d % 4752 = 1 est faut on va dire e = 54 :

54 x d % 4752 = 1

mais je ne sais toujour pas comment calculer d.

[haydenstrauss]

regarde mon premier poste :

54d=1+4752k

enfin si ce que tu veux dire est :

54d=1 modulo 4752

[me_ww]

trouve moi d plz en faisant bien tous les calcules intermedière avec des comentere et tous plz ... pcq la je désespere quoi

[haydenstrauss]

trouve moi d plz en faisant bien tous les calcules intermedière avec des comentere et tous plz ... pcq la je désespere quoi

le probleeme c'est que 23 x d % 4752 = 1

je ne comprend pas cce que sa ve dire moi j'ai vu des truc de ce ce style:

ab.c= Z mod R

avec . operation qqconque mais jamais

23 x d % 4752 = 1

a moi que sa veuille dire que :

1/23= d mod 4752

donc di moi ce qui te semble conréspondre:

1/23= d mod 4752
ou
54d=1 modulo 4752?

[abcd22]

Salut,
on va noter (p-1)(q-1) = M pour simplifier. Si e et M n'ont aucun facteur commun, il existe des entiers relatifs d et u tels que ed + uM = 1 (autrement dit, ed = 1 mod M). Pour trouver d et u on utilise l'algorithme d'Euclide étendu, qui permet de calculer le PGCD de deux nombres (ici le PGCD de e et M est 1 par hypothèse).
Si e M c'est pareil sauf qu'on commence par diviser e par M)

L'hypothèse que e et (p-1)(q-1) n'aient aucun facteur commun est indispensable si tu veux trouver d tel que ed = 1 mod (p-1)(q-1), parce qu'en fait l'algorithme donne d et u tels que ed + u M = le dernier reste non nul dans la suite des divisions, et ce dernier reste non nul est le PGCD de e et (p-1)(q-1), il vaut 1 si et seulement si e et (p-1)(q-1) n'ont pas de facteur commun. On ne peut donc pas trouver d tel que 54 d = 1 mod 4752 : 2 divise 54 et 4752, et la première question que tu as posée n'avait pas de solution pour la même raison.
Par contre pour ton exemple avec p = 67, q = 73 et e = 23 ça marche, pour les calculs ça donne M = 4752 = 23x206 + 14 :
e = 23 = 14 + 9 :
14 = 9 + 5 :
9 = 5 + 4 :
5 = 4 + 1 :
sous forme de tableau ça donne

et on fait les calculs pour trouver d et u :
.
On a donc trouvé que (-1033)x23= 1 mod 4752, si on veut un nombre positif on peut prendre -1033 + 4752 = 3719.

[haydenstrauss]

bonne maitrise du latex entre une fonction tabular et eqnarray:)

[RadarX]

donne l'énoncé exacte stp au complet stp

Cest vrai qu'un gros probleme reste qu'il donne des enoncés tres tres suspects! :doh:

Pour ME WW, savoir qu'un premier postulat des maths pourrait etre bien definir notre probleme: ENONCE CLAIR!!!!! Alors a toi!

[abcd22]

Je trouve que ce qu'il dit dans le message 11 est clair, non ? Comme il l'a dit c'est le début de l'algorithme RSA, la génération des clés publique et privée (tiens j'ai appris dans cette page que le théorème de Bézout de l'arithmétique devrait s'appeler théorème de Bachet de Méziriac, c'est beaucoup plus classe quand même comme nom, mais c'est pas pratique à écrire dans les copies).