Bonsoir,

Je dois réaliser un programme simulant un cryptosystème type RSA.

Dans une des fonctions le composant, j'ai la congruence suivante à résoudre :

e*d = 1 [(p-1)*(q-1)]        (= : "congru à")

avec p et q connus, on recherche alors e et d compris entre ]1,(p-1)*(q-1)[ satisfaisant cette relation.

pour cela j'ai défini c=e*d et j'ai déterminé une valeur de c appartenant à l'intervalle correspondant et satisfaisant la congruence ci dessus.

Mon problème est pour la suite, en effet je dois trouver un diviseur de c tel que ce diviseur et le quotient appartiennent à l'intervalle ]1,(p-1)*(q-1)[

sauf que p et q sont des nombres premiers appartenant à l'intervalle [10^3;10^8] donc la valeur de (p-1)*(q-1) atteint facilement des ordres de grandeurs supérieurs à 10^12.

Le programme que j'ai réalisé est alors bien trop long pour trouver de tels e et d.

Avez vous des idées ? Merci.

Montre ton code, ton problème est donc le temps dans la recherche de nombres premiers ?

Comme e et d appartiennent à [2,m-1], j'ai définit c comme le produit e*d. J'ai cherché alors c appartenant à l'intervalle voulu pour que c soit congru à 1 modulo m.

J'ai ensuite cherché un diviseur de c proche de la moitié de notre intervalle ]1;m[ auquel e et d doivent appartenir

mais cela est lent, et j'ai l'impression que ça ne marche pas à tous les coups

Merci de ton aide

from random import *

def deterED(p,q):

     m=(p-1)*(q-1)

     c=randint(m+2,(m-1)**2)

     if c%m!=1:

          c=c-(c%m)+1

     i=int(m/2)

     while c%i!=0:

          i+=1

     e=i

     d=c//i

     return (e,d)

Effectivement ce qui doit être long est le test de primalité, je pense que tu devrais chercher en python les algorithmes tel que le crible d'ératosthène pour rendre cette recherche plus rapide...

C'est pas du test du primalité qu'il est question, j'ai deja mes nombres premiers grace a un autre programme, mais de la recherche des diviseurs de c