problème mathématique

Bonjour,

Tous les nombres sont des entiers
p = premier (impair)
q = premier (impair)
t = (p-1)(q-1) (non premier)(pair)
e = premier
PGCD(e;t)=1 (en clair, e et t sont premier entre eux)
e>t
d = pair
(d*e-1) multiple de t

Trouver la valeur de d, en fonction de e, p et q.

Merci d'avance,
Prog.Val

PS: les plus perspicaces auront compris que je travaille sur un système de cryptage RSA...
_________________
Salut Invité.
Ta dernière visite date du .
Tu as posté 0 messages.
Le forum compte 59258 messages et 3630 sujets.

Je ne comprends pas bien ce que tu cherches...
Si c'est résoudre cette équation du premier degré qui te pose problème, j'ai des doutes sur ta réussite au brevet.

Alors précise quelles sont les données connues et les inconnues et on pourra peut-être t'aider.

Légère édition.

"(d*e-1) multiple de t" est une équation?

Ce que je cherche est la plus petite valeur possible de d en fonction de
-p, q, et e
OU
-t et e

Es-tu sûr que c'est facile? J'ai déjà demandé à quelques personnes... qui ont abandonné...

EDIT: Je viens de trouver ça:

pas bête. Le problème, c'est qu'il n'existe pas de solveur d'équation sur la TI qui me permettrai de faire ça...
_________________
Salut Invité.
Ta dernière visite date du .
Tu as posté 0 messages.
Le forum compte 59258 messages et 3630 sujets.

??
_________________
Responsable de TI-BANK (http://www.ti-bank.fr)

Projet 1 : How well do you know your World ? [68k] (19%)
Projet 2 : Da Vinci Flight [68k] (0.5%)
Projet 3 : Mastermind Nspire [Nspire] (80%)
Projet 4 : Ephy Nspire [Nspire] (0%)

euh +1
_________________

Si j'ai bien compris, tu connais 2 nombres premiers (différents de 2, je suppose pour que ce ne soit pas trop simple !) p et q et e (que tu dis être premier mais que je supposerai seulement premier avec t=(p-1)*(q-1) et tu cherches un entier d tel que d*e-1 soit multiple de t, c'est-à-dire tel que il existe un entier k tel que d*q-k*t=1.
Effectivement, cela revient à chercher des coefficients de Bézout par l'algorithme d'Euclide (algorithme étendu car l'algorithme classique ne donne que le pgcd).

Donc tu appliques l'algorithme d'Euclide étendu à e et t et tu en déduis les coefficients d et k donc le coefficient d que tu cherches.

Si tu y tiens, je pourrai te l'écrire.

moi j'ai pas compris l'algo d'Euclide étendu, on nous l'a expliqué vite fait en classe, il faut "remonter" les équations
_________________

Voici ce que ça donne sur un exemple :

On cherche les coeffs de Bezout de 32 et 27.
On écrit les divisions euclidiennes suivantes :
32=1*27+5
27=5*5+2
5=2*2+1

Donc 1=5-2*2=5-2*(27-5*5)=11*5-2*27=11*(32-1*27)-2*27=11*32-13*27

Par conséquent, on obtient : u=11 et v=-13 pour u*32+v*27=1

En fait, algorithmiquement, on peut aller plus vite qu'en remontant les calculs à l'aide des matrices notamment (même si leur utilisation n'est pas indispensable).

ah ok, en fait ça marche par substitution quoi
_________________