Bonjour, cliquez-ici pour vous inscrire et participer au forum.
  • Login:



+ Répondre à la discussion
Page 1 sur 2 1 DernièreDernière
Affichage des résultats 1 à 15 sur 27

Algorithme pour nombres premiers.

  1. Antikhippe

    Date d'inscription
    octobre 2003
    Âge
    30
    Messages
    1 968

    Algorithme pour nombres premiers.

    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.

    -----

     


    • Publicité



  2. yat

    Date d'inscription
    juillet 2004
    Messages
    2 705

    Re : Algorithme pour nombres premiers.

    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.
     

  3. Antikhippe

    Date d'inscription
    octobre 2003
    Âge
    30
    Messages
    1 968

    Re : Algorithme pour nombres premiers.

    Citation 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.
     

  4. Quinto

    Date d'inscription
    septembre 2003
    Localisation
    Québec
    Âge
    34
    Messages
    1 796

    Re : Algorithme pour nombres premiers.

    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...
     

  5. Antikhippe

    Date d'inscription
    octobre 2003
    Âge
    30
    Messages
    1 968

    Re : Algorithme pour nombres premiers.

    Citation 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.
     


    • Publicité



  6. lyapounov

    Date d'inscription
    juillet 2004
    Localisation
    Roanne
    Âge
    63
    Messages
    407

    Re : Algorithme pour nombres premiers.

    Citation 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
    La logique sert à prouver, l'intuition sert à créer. H Poincaré
     

  7. Eric78

    Date d'inscription
    novembre 2003
    Localisation
    Région parisienne
    Âge
    31
    Messages
    570

    Re : Algorithme pour nombres premiers.

    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
    Pour un TPE sur la cryptographie ou les trous noirs, allez voir mon profil.
     

  8. halman

    Date d'inscription
    janvier 2003
    Âge
    56
    Messages
    906

    Talking Re : Algorithme pour nombres premiers.

    Citation 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.
     

  9. Antikhippe

    Date d'inscription
    octobre 2003
    Âge
    30
    Messages
    1 968

    Re : Algorithme pour nombres premiers.

    Merci bien à tous pour vos réponses,

    Citation 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.
     

  10. Quinto

    Date d'inscription
    septembre 2003
    Localisation
    Québec
    Âge
    34
    Messages
    1 796

    Re : Algorithme pour nombres premiers.

    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...
     

  11. Antikhippe

    Date d'inscription
    octobre 2003
    Âge
    30
    Messages
    1 968

    Re : Algorithme pour nombres premiers.

    Citation 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 ?
     

  12. Eric78

    Date d'inscription
    novembre 2003
    Localisation
    Région parisienne
    Âge
    31
    Messages
    570

    Re : Algorithme pour nombres premiers.

    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
    Pour un TPE sur la cryptographie ou les trous noirs, allez voir mon profil.
     

  13. leg

    Date d'inscription
    août 2004
    Localisation
    roquesteron 06910
    Âge
    70
    Messages
    1 240

    Re : Algorithme pour nombres premiers.

    Citation 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
     

  14. leg

    Date d'inscription
    août 2004
    Localisation
    roquesteron 06910
    Âge
    70
    Messages
    1 240

    Re : Algorithme pour nombres premiers.

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

  15. Antikhippe

    Date d'inscription
    octobre 2003
    Âge
    30
    Messages
    1 968

    Re : Algorithme pour nombres premiers.

    Citation 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 !
     


    • Publicité







Sur le même thème :





 

Discussions similaires

  1. Nombres premiers
    Par MS.11 dans le forum Mathématiques du collège et du lycée
    Réponses: 10
    Dernier message: 19/11/2007, 18h08
  2. Nombres premiers (again)
    Par MS.11 dans le forum Mathématiques du collège et du lycée
    Réponses: 8
    Dernier message: 31/10/2007, 11h45
  3. TS- Nombres premiers
    Par MS.11 dans le forum Mathématiques du collège et du lycée
    Réponses: 18
    Dernier message: 20/10/2007, 20h51
  4. Nombres premiers, y aurait-il des nombres premiers jumeaux
    Par RSSBot dans le forum Commentez les actus, dossiers et définitions
    Réponses: 2
    Dernier message: 19/04/2007, 09h45
  5. Algorithme de génération de polynômes premiers
    Par Ahy Goon dans le forum Mathématiques du supérieur
    Réponses: 3
    Dernier message: 22/07/2005, 10h08