Algorithme pour nombres premiers.
Répondre à la discussion
Affichage des résultats 1 à 27 sur 27

Algorithme pour nombres premiers.



  1. #1
    Antikhippe

    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.

    -----

  2. #2
    yat

    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. #3
    Antikhippe

    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. #4
    Quinto

    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. A voir en vidéo sur Futura
  6. #5
    Antikhippe

    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.

  7. #6
    lyapounov

    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é

  8. #7
    invite3f53d719

    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

  9. #8
    invitebd686fd6

    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.

  10. #9
    Antikhippe

    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.

  11. #10
    Quinto

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

  12. #11
    Antikhippe

    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 ?

  13. #12
    invite3f53d719

    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

  14. #13
    leg

    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

  15. #14
    leg

    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.

  16. #15
    Antikhippe

    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 !

  17. #16
    invite3f53d719

    Re : Algorithme pour nombres premiers.

    Citation Envoyé par Antikhippe
    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 !
    Fait gaffe de ne pas viser trop haut non plus, l'arithmétique deviens très vite très compliqué. Pour t'en convaincre, regarde la démo du test de Lucas-Lehmer: http://tpe.crypto.free.fr/index.html...ers/index.html . J'ai mis quelques heures à la comprendre vraiment...

  18. #17
    Antikhippe

    Re : Algorithme pour nombres premiers.

    Citation Envoyé par Eric78
    Fait gaffe de ne pas viser trop haut non plus, l'arithmétique deviens très vite très compliqué. Pour t'en convaincre, regarde la démo du test de Lucas-Lehmer: http://tpe.crypto.free.fr/index.html...ers/index.html . J'ai mis quelques heures à la comprendre vraiment...
    C'est ça qui est bon !!! De la récurrence, du raisonnement par l'absurde, de l'arithmétique... ça m'a l'air très intéressant !

  19. #18
    Quinto

    Re : Algorithme pour nombres premiers.

    T'as pas eu de mal pour un tel TPE?
    Parce que ca nécessite pas mal de connaissances du supérieur quand meme...
    Je n'ai pas trouvé la démonstration du théoreme sinon...

  20. #19
    invite3f53d719

    Re : Algorithme pour nombres premiers.

    Citation Envoyé par Quinto
    T'as pas eu de mal pour un tel TPE?
    Parce que ca nécessite pas mal de connaissances du supérieur quand meme...
    Je n'ai pas trouvé la démonstration du théoreme sinon...
    Heu, je dois t'avouer que certains points m'ont beaucoup pris la tête, mais bon, vu que j'aime bien les maths, ca ne me dérange pas. Et puis vu que j'avais à peu près que ca à faire pendant l'année comme travail à la maison... Au moins j'aurais appris des choses interressantes Sinon, la démonstration en question est dans un rectangle jaune du III] b).

    Eric

  21. #20
    inviteeb72d013

    Re : Algorithme pour nombres premiers.

    Excusez-moi tout le monde !
    Je viens de découvrir cette question. S'il n'est pas trop tard, voici un excellent algorithme qui nécessite des prérequis de 1°S, à savoir la résolution d'équation du 2° degré.
    Cela ne posera de problème personne de ce forum.
    Tout d'abord, ne parle pas de nombres de 'x' chiffres. Tu as plutôt intérêt à donner leur longueur en bits. Par exemple p et q de 6 bits (<64).

    Posons N = pq avec p et q premiers de même longueur (c'est le cas le plus dur ! bien qu'à priori cela nous révèle une information sur eux deux !!)
    Considérons le polynôme :
    (X-p)(X-q) = 0 <==> X^2 - (p+q)X + pq = 0
    <==> X^2 - sX + N = 0 avec s = p+q
    rem : plusieurs chemins de niveau 1°S, T°C mènent à ce polynôme ( => exercice !! )
    Factoriser N revienet donc à résoudre ce polynôme, qui n'a de solution que si son discriminant est strictement positif, soit s^2 > 4N.
    Posons d = s^2 - 4N. Les solutions du polynôme sont donc (s-sqrt(d))/2 et (s+sqrt(d))/2.
    Il faut donc que s et d soit pairs.
    Prends alors s = l'entier pair strictement supérieur à la partie entière de sqrt(4+4N), et c'est gagné (en une seule opération !)

    note : sqrt() signifie racine carré

    Lorsque la longueur de N augmente, des adaptations sont nécessaires, mais cela n'est plus ta question ()...

    Taraua.

  22. #21
    invitec0f3a9cc

    Re : Algorithme pour nombres premiers.

    Désolé, taraua, c'était tentant, mais ça ne fonctionne pas avec le nombre 2627.

    Je planche actuellement sur la définition suivante:

    dans N*+, quelque soit N un nombre composé, il existe N' un nombre composé ayant un facteur commun avec N, tel que:
    N' = ( R(N) + 2n )² + N - R(N)²

    avec R(x) = racine entière de x

    Exemples:

    N=6, n=1, N'=18
    N=21,n=2,N'=69
    N=77,n=3,N'=209
    N=143,n=2,N'=247
    N=2627,n=74,N'=15651
    N=2631463147,n=52634,N'=108017 33699

    Se pose le problème de la progression de n pour parvenir à la factorisation.

    Si quelqu'un a des idées...

  23. #22
    invitedebe236f

    Re : Algorithme pour nombres premiers.

    ca methode marche tres bien sauf si les 2 nombres premier sont tres eloigne voila une amelioration
    Sub a()

    Dim c As Variant
    Dim i As Variant
    Dim f As Variant
    Dim x1 As Long
    Dim x2 As Long
    Dim d As variant

    c = 1124564891 'produit de 2 premiers

    s = Int(Sqr(4 * c)) ' comme lui je calcule la somme minimale
    If Int(s / 2) - s / 2 <> 0 Then s = s + 1 ' on prend un pair

    For i = s To c Step 2 ' on passe tous les pair
    d = i * i - 4 * c ' on calcule son d
    If d > 0 Then
    If Int(Sqr(d)) - Sqr(d) = 0 Then ' on verifie que c est bien un carre
    x1 = (i - Sqr(d)) / 2
    x2 = (i + Sqr(d)) / 2
    If x1 + x2 = i Then
    MsgBox "trouve"
    End If
    End If
    End If

    Next i



    End Sub

  24. #23
    invitedebe236f

    Re : Algorithme pour nombres premiers.

    bon la racine de 1124564891 etant 33534 un algo normal en 16767 test des nombre impair trouve

    ici il faut 393419 iteration avec mon exemple c est catastrophique

  25. #24
    inviteeb72d013

    Re : Algorithme pour nombres premiers.

    C'est bien CriCri !

    Voici alors un complément pour toi qui "voit" certaines choses ...
    Je pose N=pq avec q<q et N de longueur 2n bits
    Je pose D = distance entre p et q: D = q-p
    Je pose S = somme de p et q : S = q + p

    Intéresse-toi à D minimum (noté Dmin), Dmax, Smin et Smax.
    Piste :
    . Bien sûr, Dmin et Smin sont liés entre eux.
    . Bien sûr, Dmax et Smax sont liés entre eux.

    A partir de Dmin et Smin, tu peux calculer p max et q min.
    A partir de Dmax et Smax, tu peux calculer p min et q max.
    Voilà qui te permettra d'améliorer ton algo...

    Aide :
    Dmin = 2 d'où Smin = sqrt(Dmin^2+4N) d'où recalcule Dmin = sqrt(Smin^2-4N).
    Dmax = 2^(n-1)-2 (à priori !) (... mais il y a plus fort encore ! ( ) d'où ...
    Pour être une paire (S,D) valide une condition est nécessaire (test d'arrêt) :
    . 1 seul exactement d'entre les deux doit être divisible par 4, sinon tu incrémente Smin de 2 et recalcule Dmin ou décrémente Smax de 2 et recalcule Dmax.

    Nous ne sommes plus très loin de la limite des acquis de T°C ...

    Prends ton élan !
    Taraua.

  26. #25
    invitedebe236f

    Re : Algorithme pour nombres premiers.

    voila ce que j ai trouve
    http://www-lipn.univ-paris13.fr/~banderier/Facto/

    http://tpe.crypto.free.fr/index.html...ublique/facto/

    mais bon pour se limiter a un entier long 4294967296 les divisions par les nombre impair(32768 division a faire) sont un algo suffisament rapide

  27. #26
    inviteeb72d013

    Re : Algorithme pour nombres premiers.

    Cricri, les sites auxquels tu fais référence dépasse très largement le niveau de lycée et même de maths sup et spé. Là, nous ne jouons vraiment plus dans la même cours ...

    Ma réponse concerne la question de antikhippe sur les "petits nombres premiers", adaptée à son niveau scolaire.
    Prenons N=2336914739
    alors :
    init-min(N) (c'est ma fonction que je lance !)
    Smin = 96684 [1, 0, 1, 1, 1, 1, 0, 0, 1, 1, 0, 1, 0, 1, 1, 0, 0]
    Dmin = 370 [1, 0, 1, 1, 1, 0, 0, 1, 0]
    Pmax = 48157 [1, 0, 1, 1, 1, 1, 0, 0, 0, 0, 0, 1, 1, 1, 0, 1]
    Qmin = 48527 [1, 0, 1, 1, 1, 1, 0, 1, 1, 0, 0, 0, 1, 1, 1, 1]
    et init_max(N) (c'est ma fonction que je lance !)
    Smax = 101194 [1, 1, 0, 0, 0, 1, 0, 1, 1, 0, 1, 0, 0, 1, 0, 1, 0]
    Dmax = 29876 [1, 1, 1, 0, 1, 0, 0, 1, 0, 1, 1, 0, 1, 0, 0]
    Pmin = 35659 [1, 0, 0, 0, 1, 0, 1, 1, 0, 1, 0, 0, 1, 0, 1, 1]
    Qmax = 65535 [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1]

    autre exemple :
    N=2709602099
    init_min(N)
    Xmin = 104110 [1, 1, 0, 0, 1, 0, 1, 1, 0, 1, 0, 1, 0, 1, 1, 1, 0]
    Dmin = 696 [1, 0, 1, 0, 1, 1, 1, 0, 0, 0]
    Pmax = 51707 [1, 1, 0, 0, 1, 0, 0, 1, 1, 1, 1, 1, 1, 0, 1, 1]
    Qmin = 52403 [1, 1, 0, 0, 1, 1, 0, 0, 1, 0, 1, 1, 0, 0, 1, 1]
    init_max(N)
    Xmax = 106880 [1, 1, 0, 1, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 0, 0, 0]
    Dmax = 24186 [1, 0, 1, 1, 1, 1, 0, 0, 1, 1, 1, 1, 0, 1, 0]
    Pmin = 41347 [1, 0, 1, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 0, 1, 1]
    Qmax = 65533 [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1]

    Plutôt que de parcourir les P ou les Q, il est plus court de parcourir S entre Smin et Smax par pas de 2.
    Lorsque sqrt(S^2-4N) est un entier, nous avons D. On en déduit les facteurs P=(S-D)/2 et Q=(S+D)/2.

    C'est là une introduction douce au problème de "résidus quadratiques" ...

    En attendant, essaye de réécrire ton programme en réduisant ton espace de recherche.
    Si tu n'y arrives pas, j'envoie ma version.

    Pour le reste, vise au minimum le DEA de mathématiques pures, et fais ta thèse dans un laboratoire crypto.

    Dernier post ...
    Taraua.

  28. #27
    Antikhippe

    Re : Algorithme pour nombres premiers.

    C'est vrai que les deux documents de cricri sont très complexes pour mon petit niveau de terminale ! lol

    Merci en tout cas pour vos réponses intéressantes. C'est dommage que mes TPE soient déjà passés.

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. Algorithme de génération de polynômes premiers
    Par invitec712cafa dans le forum Mathématiques du supérieur
    Réponses: 3
    Dernier message: 22/07/2005, 10h08