Voilà l'exercice que j'ai :

Et en fait dès la 1. je suis bloqué. En fait on a N1, N2, N3 trois entiers distincts deux à deux, tels que ;

m_1 = m^3 [N1]
m_2 = m^3 [N2]
m_3 = m^3 [N3]

Et on veut montrer qu'on peut calculer m^3 (mod N1*N2*N3).

Si N1, N2 et N3 étaient premiers entre eux, cela serait une conséquence directe du théorème des restes chinois, mais là le problème c'est qu'ils ne le sont pas forcément. Du coup, je vois pas comment faire...

Le 09 janvier 2017 à 22:29:18 bluepoint_ a écrit :
s'ils sont pas premiers entre eux tu peux les factoriser facilement pitchoun

Ben imaginons j'ai N1 = p1*q1, N2 = p2*q2, N3 = p3*q3, donc avec le système précédent, j'ai :

m^3 = m1 (mod p1)
m^3 = m1 (mod q1)
...
m^3 = m3 (mod p3)
m^3 = m3 (mod q3)

et dans les p_i, q_i, il peut très bien y avoir par exemple p1 = p3. Auquel, cas, si je "vire" tous les doublons dans le système, je me retrouve avec un certain système, et si j'applique le théorème des restes chinois, ben ça me donne pas m^3 = a (mod p1*q1*p2*q2*p3*q3) (avec a connu)... mais par exemple m^3 = a (mod p1*q1*p2*q2*q3) si p1 = p3, par exemple...

Je dois surement m'exprimer mal, j'espère que tu vas quand même comprendre ce qui me pose problème.

Et ça c'est en connaissant p1,q1,...,p3, q3, ce qui n'est pas forcément évident...

Le 09 janvier 2017 à 22:41:19 bluepoint_ a écrit :

j'espère que tu vas quand même comprendre ce qui me pose problème.

Je t'ai pas dit d'utiliser le théorème des restes chinois mais de factoriser tes Ni pour ce cas

Au risque de paraître bête, c'est-à-dire ? oO Je sais que N1, N2 et N3 s'écrivent N1 = p1*q1, N2 = p2*q2 et N3 = p3*q3, avec p_i et q_i premiers. Je comprends pas ce que je peux faire de plus avec mes NI (désolé si ça paraît con ).

Le 09 janvier 2017 à 22:45:11 bluepoint_ a écrit :
Fchtrkxw tu vas m'écrire NOIR SUR BLANC en une formule de math niveau collège le fait que N1 et N2 ne sont pas premiers entre eux.

Et la regarder fixement

Ben il existe d différent de 1 tel que d/N1 et d/N2.(ou pgcd(n1,n2) != 1)

Sauf que là N1 = p1q1 et N2 = p2q2, donc on a forcément soit p1=p2, soit p1=q2, soit q1=p2 ou q1=q2.

Le 09 janvier 2017 à 22:48:00 bluepoint_ a écrit :

.(ou pgcd(n1,n2) = d)

Bon ben tu sais ce qu'il te reste à calculer dans ce cas

Ben écoute, je le fais pas exprès, mais non je vois pas en quoi ça m'avance.
J'ai :

m^3 = m1 [N1]
m^3 = m2 [N2]
m^3 = m3 [N3]

et après si N1, N2 non premiers entre eux par exemple, alors pgcd(N1,N2) = d != 1.
et j'ai beau cherché, je vois pas comment je vais avoir m^3 modulo N1N2N3........

Le 09 janvier 2017 à 23:01:49 bluepoint_ a écrit :
d EST UN FACTEUR DE N1 ET N2 BOUGRE D'ORIGNAL

FACTEUR

FACTORISER

Ben ouais, donc N1 = dk, N2 = dk', avec k et k' entier différent de 1 et de N1 (respectivement N2). Si c'est ça que tu attendais j'avais déjà essayé, mais encore une fois ça m'aide pas à trouver mon m^3 mod N1N2N3.

gros niveau ta TS spé maths bluepoint

Le 09 janvier 2017 à 23:07:50 bluepoint_ a écrit :
FACTORISER

RSA

YA PAS COMME UN LIEN ?

Je vois pas du tout ce que tu veux dire... A la base d'accord, pour le code RSA, on prend un nombre N qu'on factorise en nombre premier N = P*Q, avec P et Q premiers. Et toute la difficulté avec de grands nombres N, c'est de trouver la factorisation en nombres premiers.

Donc là si j'ai pgcd(N1,N2) = d !=1, on peut trouver la factorisation de N1 facilement. Donc on connaîtra p1 et q1 tel que n1 = p1*q1, et pareil pour N2, on connaîtra p2 et q2 tel que N2 = p2*q2. Donc dans ce cas, je peux même connaître m, non ?

Pour ma défense je viens de regarder le cours sur le codage RSA juste avant de faire l'exercice.

Le 09 janvier 2017 à 23:14:19 ForceAthletique a écrit :
gros niveau ta TS spé maths bluepoint

Bah le pgcd est au programme et a force de trainer sur jvc il connais tous les bails du rsa

Le 09 janvier 2017 à 23:27:38 bluepoint_ a écrit :

Donc dans ce cas, je peux même connaître m, non ?

ALLÉLUIA

Oui, tu peux trouver directement m; ce qui était ton but initial (enfin du coup tu peux toujours calculer m^3 mod truc si ça t'amuses ensuite)

2 remarques quand même :

• Calculer le pgcd de N1 et N2 est rapide, ben oui, c'est idiot, mais si ça prenait le même temps que pour casser RSA l'attaque marcherait pas.
• ça marcherait pas pour des entiers RSA multiprimes, avec Ni=p*q*r*...... au lieu de Ni = *q, mais personne fait ça

Pfiouu, merci. En fait c'était évident, mais je sais pas, j'ai vu un système j'ai tout de suite pensé aux théorèmes des restes chinois, en oubliant le reste.

Pour la question 2, j'imagine que comme 1 <=m <= N1, 1<= m <= N2 et 1 <= m <= N3, on a forcément 1<= m^3 <= N1, N2, N3, et comme d'après la 1) on a m^3 = a (mod N1N2N3), et bien m^3 = a, sinon on aurait m^3 = a + k*N1N2N3 (k entier différent de 0) et donc soit m^3 >= N1 (N2 et N3 aussi), soit m^3 < 1.

Et donc pour la 3), vu qu'on a m_1 = m^3 [N1] (on pourrait utiliser aussi une des deux autres équations) et qu'on connait maintenant m^3 (qui est forcément entre 1 et N1), on a également m_1.

Est-ce bien cela ?

ça marcherait pas pour des entiers RSA multiprimes, avec Ni=p*q*r*...... au lieu de Ni = p*q, mais personne fait ça

D'ailleurs, tant que t'es là, en quoi c'est pas pertinent de faire un RSA avec plus de deux nombres premiers ? Le temps de calcul devient déraisonnable ?