factorisation en nombre premier

[Paradigm]

Bonsoir à tous,

Le problème de la factorisation des grands entiers est a priori très difficile. L’efficacité de nombreux cryptosystèmes, comme le RSA( https://rdvlivefromtokyo.blogspot.co...ntication.html ), est basé sur cette difficulté présumée. Le problème de décider si un entier est premier ou non, est en fait beaucoup plus simple que celui de trouver les diviseurs premiers d’un entier composé.

Dès 1994, Peter Shor, chercheur américain, écrit un algorithme qui, s’il existait un ordinateur quantique susceptible de le mettre en oeuvre, permettrait de factoriser des nombres entiers en un temps exponentiellement plus rapide que les algorithmes classiques connus, et donc, deviendrait une menace pour la sécurité des protocoles de chiffrement basé sur cette difficulté de factorisation de un grand nombre en ses facteurs premiers.

Le principe de la résolution d’un problème de factorisation consiste à le transformer en un problème de recherche de période. En fait la tâche de trouver un facteur premier d’un nombre peut être réduite à la recherche de la période d’une fonction et cette période peut être obtenue efficacement en utilisant la transformée de Fourier quantique (QFT) : https://fr.wikipedia.org/wiki/Algorithme_de_Shor / https://en.wikipedia.org/wiki/Shor%27s_algorithm

Dans la partie classique de l'algorithme donné par wikipédia l'étape 3 mentionne : "Si PGCD(a, N) ≠ 1, alors c'est un facteur non trivial de N, donc effectué."

Si a n'est pas co-premier à N cela n'implique pas que le PGCD(a, N) ( bien qu'il soit un facteur de N) soit un nombre premier !? Et donc si il n'est pas premier on doit revenir à l'étape 1 pour choisir un autre nombre a < N.

Cordialement
-----

[Tryss2]

Si PGCD(a,N) est différent de 1, alors N = PGCD(a,N) x b, on applique alors l'algorithme à PGCD(a,N) et à b (qui sont des nombres bien plus petits)

[Paradigm]

Si PGCD(a,N) est différent de 1, alors N = PGCD(a,N) x b, on applique alors l'algorithme à PGCD(a,N) et à b (qui sont des nombres bien plus petits)

Quelle relation il y a t-il entre trouver les facteurs premiers de N et trouver les facteurs premiers de [PGCD(a,N) et b ] ? C'est à dire une fois que l'on a les facteurs premiers de PGCD(a,N) et à b comment arrive t-on aux deux facteurs premiers de N (N = p.q)?

Cordialement,

[minushabens]

si N est le produit de 2 nombres premiers (N=pq) alors un pgcd de N et x est 1,p,q ou N puisque ce sont les seuls diviseurs de N. Si c'est N ou 1 ça n'aide pas, autrement la factorisation est faite.

[A voir en vidéo sur Futura]

[Paradigm]

si N est le produit de 2 nombres premiers (N=pq) alors un pgcd de N et x est 1,p,q ou N puisque ce sont les seuls diviseurs de N. Si c'est N ou 1 ça n'aide pas, autrement la factorisation est faite.

OK Merci

Si je comprends bien, le plus grand commun diviseur de "a" et "b" est le produit de tous les facteurs premiers qui interviennent en "a" et "b". Du fait que dans le cas de l'algorithme RSA, N est choisi égale au produit de deux nombres premiers (N = p.q). Donc si on choisi un nombre x qui n'est pas copremier avec N alors les seuls pgcd de N et x sont 1,p,q ou N. Donc ce cas très peu probable (de trouver un nombre x qui n'est pas copremier avec N) fait que la factorisation a été résolue.

Cordialement,