Algorithme pour nombres premiers.

Antikhippe · 15/09/2004 - 13h00

Bonjour,

Soient deux nombres premiers p et q. Soit r = pq. J’aimerais savoir s’il serait possible de retrouver les deux nombres premiers p et q à partir du nombre r en utilisant un algorithme.

Je donne un exemple au cas où je ne me sois pas fait comprendre : soit p = 17 et q = 23. On a alors r = pq = 391. Ne connaissant pas p et q, puis-je arriver à trouver que p = 17 (ou 23) et q = 23 (ou 17) sachant que pq = 391 et que p et q sont deux nombres premiers à l’aide d’un algorithme ?

Je précise que j’ai le niveau bac (pour ce qui est des maths) et que j’ai un ordinateur de particulier, c’est-à-dire que ce n’est pas un supercalculateur.

Je sais bien que plus p et q sont grands, plus ils seront difficiles (ou plutôt longs) à trouver. Mais je n’ai l’ambition que de trouver deux nombres premiers de deux chiffres (comme dans l’exemple), pas plus…

Ma question est donc de savoir si c’est réalisable et si oui, pourriez –vous m’indiquer une piste ?

En vous remerciant d’avance,
Antikhippe.

yat · 15/09/2004 - 13h21

A mon avis pour des nombres à deux chiffres, le mieux est de prendre tous les nombres premiers entre 2 et la racine de r, et de diviser r par chacun de ces nombres. Quand ça tombe pile, c'est que tu es sur p, et le quotient donne q.

Je sais, c'est la méthode bébète, mais je ne connais pas les méthodes utilisées pour cracker des clés rsa ou ce genre de trucs...

Pour des premiers de deux chiffres, c'est amplement suffisant.

Antikhippe · 15/09/2004 - 13h25

Envoyé par yat

Pour des premiers de deux chiffres, c'est amplement suffisant.

Merci yat !

J'ai pensé exactement à la même méthode que la tienne. Seulement, je voudrais savoir s'il n'y a pas d'algorithme un peu plus élaboré où il y aurait un peu plus de mathématiques.

Quinto · 15/09/2004 - 13h36

Bein a 1e vue si tu voulais un truc avec plus de mathématiques je pense que ton calculateur prendrait plus de temps pour chaque operation...
La tu n'as ainsi pas beaucoup de calculs a faire E(racine de r) calculs pour trouver p et q.

Cela etant si tu commences apres a prendre des nombres a n chiffres avec n qui devient grand, tu risques de passer beaucoup de temps et justement s'il y'avait des algos mathématiques très développé alors la méthode RSA serait cassée...

Antikhippe · 15/09/2004 - 13h43

Envoyé par Quinto

Cela etant si tu commences apres a prendre des nombres a n chiffres avec n qui devient grand, tu risques de passer beaucoup de temps et justement s'il y'avait des algos mathématiques très développé alors la méthode RSA serait cassée...

Je suis d'accord, mais pour des cartes bancaires ou autres, ils utilisent de très grands nombres premiers... moi, des nombres de 2 à 5 chiffres suffiraient amplement ! C'est justement pour prouver que la méthode RSA est très performante aujourd'hui : au départ, je prends deux nombres premiers de 2 chiffres puis après, deux nombres premiers de 3 chiffres et ainsi de suite pour montrer comment il est de plus en plus long de trouver les 2 nombres.

lyapounov · 15/09/2004 - 13h54

Envoyé par Antikhippe

Bonjour,

Soient deux nombres premiers p et q. Soit r = pq. J’aimerais savoir s’il serait possible de retrouver les deux nombres premiers p et q à partir du nombre r en utilisant un algorithme.

cette question est le principe du code à clé révélé en cryptographie.

On transmet un texte codé avec une clé (un nombre non premier très grand).

Le destinataire possede une clé (un nombre premier d'environ 8 à 10 chiffres) qui lui permettra de décoder le message grace aux deux cles réunies : Les deux nombres r et p permettent d'obtenir le troisieme nombre q (nombre premier de huit à 10 chiffres) qui lui est la clé du code.

Un super CRAY ou un de ses confreres mettrait quelque chose comme 10^9 ans à tester tous les couples de nombre premiers

Eric78 · 15/09/2004 - 15h40

Lu,

Il existe un très grand nombre de méthodes pour factoriser les entiers, et la plupart sont assez complexes (d'un point de vue mathématique). J'ai fait un TPE sur la cryptographie, et j'ai donc du traiter un minimum la factorisation des clefs RSA. Sur cette page: http://tpe.crypto.free.fr/contenu/cl...cto/index.html , je développe la méthode du crible quadratique, qui permet de factoriser de très grands nombres. Les algorithmes modernes utilisent une version amélioré de cette méthode, mais le principe reste le même.

Eric

halman · 15/09/2004 - 18h10

Envoyé par Antikhippe

Bonjour,

Soient deux nombres premiers p et q. Soit r = pq. J’aimerais savoir s’il serait possible de retrouver les deux nombres premiers p et q à partir du nombre r en utilisant un algorithme.

Je donne un exemple au cas où je ne me sois pas fait comprendre : soit p = 17 et q = 23. On a alors r = pq = 391. Ne connaissant pas p et q, puis-je arriver à trouver que p = 17 (ou 23) et q = 23 (ou 17) sachant que pq = 391 et que p et q sont deux nombres premiers à l’aide d’un algorithme ?

Je précise que j’ai le niveau bac (pour ce qui est des maths) et que j’ai un ordinateur de particulier, c’est-à-dire que ce n’est pas un supercalculateur.

Je sais bien que plus p et q sont grands, plus ils seront difficiles (ou plutôt longs) à trouver. Mais je n’ai l’ambition que de trouver deux nombres premiers de deux chiffres (comme dans l’exemple), pas plus…

Ma question est donc de savoir si c’est réalisable et si oui, pourriez –vous m’indiquer une piste ?

En vous remerciant d’avance,
Antikhippe.

Pas un super calculateur ?

C'est trop drole ça !

Mais l'Eniac, il était 5000 foix moins puissant qu'un p4 et un de ses premiers programmes était sur les nombres premiers.

Alors si un Eniac le faisait, ton pc le fait des plus à l'aise.

Antikhippe · 15/09/2004 - 21h39

Merci bien à tous pour vos réponses,

Envoyé par Eric78

Lu,

Il existe un très grand nombre de méthodes pour factoriser les entiers, et la plupart sont assez complexes (d'un point de vue mathématique). J'ai fait un TPE sur la cryptographie, et j'ai donc du traiter un minimum la factorisation des clefs RSA. Sur cette page: http://tpe.crypto.free.fr/contenu/cl...cto/index.html , je développe la méthode du crible quadratique, qui permet de factoriser de très grands nombres. Les algorithmes modernes utilisent une version amélioré de cette méthode, mais le principe reste le même.

Eric

J'avais déjà vu ton site et je ne te cacherai pas que c'est lui qui m'a donné l'idée pour mes TPE... mais je ne m'étais pas plongé dans tes calculs. Ca a l'air assez dur mais je pense qu'en travaillant un peu, ça devrait marcher, sinon, je poserai des questions !

Maintenant, je pense que je vais essayer d'utiliser différentes méthodes pour factoriser les nombres premiers et de les comparer. Ca pourrait être assez intéressant, je pense.

Quinto · 15/09/2004 - 22h41

Salut,
si tu veux montrer que c'est long de trouver la factorisation, tu peux peut etre le montrer mathématiquement aussi, ca se fait bien je pense...

Antikhippe · 16/09/2004 - 07h37

Envoyé par Quinto

Salut,
si tu veux montrer que c'est long de trouver la factorisation, tu peux peut etre le montrer mathématiquement aussi, ca se fait bien je pense...

Salut Quinto,

Je vois ce que tu veux dire... mais je compare les méthodes avec le nombre de symboles, le nombres de paramètres ?

Eric78 · 16/09/2004 - 13h29

Effectivement, c'est interressant de comparer le temps mit par les différentes méthodes pour factoriser tel nombre. Par exemple, tu peux tracer un graphe représentant en abscisse la taille du nombre, et en ordonné le temps mit pour le factoriser. Ensuite, il faut essayer de modéliser cette courbe par une fonction (par exemple exp pour la division triviale). Tu peux t'amuser aussi à démontrer ce modèle (ce qui est très complexe pour les méthodes évolués) à partir de l'algorithme utilisé. Sinon, pour le crible quadratique, il va te falloir des connaissances en arithmétique qui viendront avec le cours de spé (en esperant que tu sois spé maths). Bon courage pour ton tpe!

Eric

leg · 16/09/2004 - 19h08

Envoyé par Antikhippe

Merci yat !

J'ai pensé exactement à la même méthode que la tienne. Seulement, je voudrais savoir s'il n'y a pas d'algorithme un peu plus élaboré où il y aurait un peu plus de mathématiques.

bonjour si tu cherches un algo un peu plus mathe, il y a l'algorithme P(30) il s'agit de 8 familles disjointes donc 8 séries avec a la tête de ces 8 séries un nombre premier P < 31 où 1 sera remplacé par 31 dans ton ex,17 * 23 = 391 = r ; r est congrue 1(30) r se trouve donc dans la série 1, a : 390/30 = 13 cellules de la cellule 0 = 1 par conséquent cette cellule se factorise par 17 et 23 ; ensuite tu compte a partir de la cellule = r, soit 17 cellules ou 23 cellules et tu obtient r1 ou r2; r1= 17*53 et r2= 23 *37 ce qui t'indique , que 17 va parcourir l'ensemble des P (30) ,c'est a dire la série 23 (30) et inversement 23 va parcourir la série 17(30). Pour information cet Ensemble des nombres P modulo 30 représente 26.6666.....666..des entiers naturels > 0 àl'exclsusion des 3 premiers: 2, 3 et 5 ainsi que leurs multiples! et rassure toi dans cet enssemble il y a tous les P sans exception avec leurs composés = r! le cycle de cet ensemble en partant de 1 est le suivant: 6.4.2.4.2.4.6.2 cest à dire la différence entre les nombre de cet E.p(30)
1 7 11 13 17 19 23 29
31 37 41 43 47 49 53 59.
je pense que tu as assez d'information pour tes travaux
pour positionner les bases de chaque série tu pars toujours de la céllule 0 dans cette cellule se trouve le premier P , 1 à 29 dans ton ex , la base 17 et 23 se positionne dans la treizième cellule , la base 7 et 13 dans la troisième cellule : 0,1,2,et 3 . Chaque cellule vaut 30 sauf la première qui est la cellule zéro = 1, ou 7, ou 11...ou 29 en fonction de la série que tu choisiras! dernière indication pour les séries 1 et 19 il y a 6 bases au lieu de 4 pour les autres!car tous nombres P au carré est congrue 1 ou 19 (30) donc dans la série 1, tu auras les bases 11*11, 19*19, 29*29,et 31*31
alors que pour l

leg · 16/09/2004 - 19h12

pour la série 13 modulo 30 les 4 bases sont:7 et19, 17 et 29, 13 et 31 , 11et 23 .
bon courrage amicalement.

Antikhippe · 16/09/2004 - 21h36

Envoyé par Eric78

Sinon, pour le crible quadratique, il va te falloir des connaissances en arithmétique qui viendront avec le cours de spé (en esperant que tu sois spé maths). Bon courage pour ton tpe!

Eric

Merci Eric pour ton investissement, je vais aller chercher dans tout ce que tu m'indiques. Sinon, je suis en spé maths, mais la prof de maths nous a dit qu'il faudrait viser plus haut... donc ça peut être compliqué que ça ne me dérrangera pas !

Et merci à toi, leg pour ta contribution... Je n'ai pas encore vu les modulos ou la congruence mais je vais aller regarder sur mon bouquin de maths de TS.

Merci encore à tous !