IdentifiantMot de passe
Loading...
Mot de passe oublié ?Je m'inscris ! (gratuit)
Navigation

Inscrivez-vous gratuitement
pour pouvoir participer, suivre les réponses en temps réel, voter pour les messages, poser vos propres questions et recevoir la newsletter

Mathématiques Discussion :

Factorisation des entiers avec la méthode ECM de Lenstra


Sujet :

Mathématiques

  1. #1
    Rédacteur

    Homme Profil pro
    Administrateur de base de données
    Inscrit en
    août 2013
    Messages
    590
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Oise (Picardie)

    Informations professionnelles :
    Activité : Administrateur de base de données
    Secteur : Finance

    Informations forums :
    Inscription : août 2013
    Messages : 590
    Points : 2 608
    Points
    2 608
    Par défaut Factorisation des entiers avec la méthode ECM de Lenstra
    Bonjour.
    Je vous sollicite pour m’aider à comprendre la méthode factorisation des entiers avec la méthode ECM de Lenstra, car mes faibles notions en mathématiques ne me permettent pas de tout comprendre.

    J’arrive à factoriser de petits nombres, par exemple « 55215650826521 », mais avec des temps de traitements 100 fois plus longs qu’avec la méthode RhoPollard, ce qui n’est pas normal, il doit donc me manquer une pièce dans ce puzzle !

    Voici comment je procède avec N le nombre à factoriser :

    Code C : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    1. Je prends des entiers au hasard pour un point P1(x, y) et un entier a.
     
    2. Je recherche le point suivant, P2(x’,y’) :
    	s = (3x² + a) / 2y
    	s = s modulo N
    	Si s < 0 alors s = N – s
    	x’ = s² - 2x
    	y’ = s(x – x’) – y
     
    3. Je boucle tant qu’une solution n’est pas trouvée pour former d'autres points :
    	P(i) = P1 + P(i-1) avec
    		si x <> x(i-1) alors
    			s = ( y(i-1) – y ) / ( x(i-1) – x ) Modulo N
    			Note : si le numérateur ou le dénominateur de s ont un PGCD commun avec N alors une solution est trouvée.
    		sinon
    			s = ( 3x² + a ) / ( 2y ) Modulo N
    			Note : si le numérateur ou le dénominateur de s ont un PGCD commun avec N alors une solution est trouvée.
    	dans les deux cas
    		si s < 0 alors s = N – s
    		x(i) = s² - x(i-1) – x modulo N
    		si x(i) < 0 alors x(i) = N – s
    		y(i) = s ( x - x(i) ) – y
     
    4. Au bout de trop d’essais je repars en 1

    Je pense que quelque chose m’échappe.
    Peut-être du côté du calcul du modulo. En effet j’ai trouvé une documentation où je ne m’explique pas le résultat du modulo :
    Avec N=3397, x=3, y=-8, a=4
    s = (3x²+a) / (2y) = (3 x 3² - 4) / (2 x -8) = 31 / -16 = 635 modulo 3397
    Comment ce 635 peut-il être trouvé ?
    C'est pour moi un grand mystère.

    Et pourtant la suite du traitement reprend ce 635 indispensable :
    x(i) = s² - x(i-1) – x modulo N
    x(i) = 635² - 3 - 3 = 403219 MOD 3397 = 2373
    y(i) = s ( x - x(i) ) – y = 635 ( 3 - 2373) - (-8) = -1504942 MOD 3397 = -71 soit -71 + 3397 = 3326
    puis dans le calcul du point suivant :
    s = 3334 / 2370 et comme PGCD(2370,3397) = 79 soit la solution.

    Dans l'attente de vos réponses.
    Cordialement.
    Débutants, n'hésitez pas à consulter mon mémento sur la programmation en VBA pour EXCEL tome 1.
    Ou le tome 2 qui aborde la programmation en mode graphique avec un exemple de programmation d'un jeu d'arcade en VBA.
    Pour les curieux, le tome 3 explique le problème du voyageur de commerce.
    Le tome 4 est consacré à la cryptologie en VBA.
    Vous découvrirez dans le tome 5 les fonctions SQL pour gérer les tableaux de données et l'application Sentinelle qui veille sur vos fichiers.
    Le tome 6, dernier de la série, vous apprendra à créer des fonctions pour simplifier la vie des utilisateurs.
    Le Crible Quadratique donne toutes les fonctions pour les opérations sur les grands nombres en VBA.
    En bonus : Programmation en VBA de menus personnalisés pour Excel, Manipuler les données des bases Access depuis Excel et Transférer des fichiers volumineux avec Outlook.

  2. #2
    Expert éminent sénior Avatar de Flodelarab
    Homme Profil pro
    Inscrit en
    septembre 2005
    Messages
    4 704
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Charente (Poitou Charente)

    Informations forums :
    Inscription : septembre 2005
    Messages : 4 704
    Points : 11 799
    Points
    11 799
    Par défaut
    Bonjour

    Je pense que quelque chose m’échappe.
    Le somme des points, non ?

    P est un point de courbe elliptique.
    Q est un point de la courbe elliptique.
    P+Q est point de la courbe elliptique.
    P+P est un point de la courbe elliptique.
    P+P+P+...+P+P+P = nP = 0 aboutit à un groupe cyclique comme Z\nZ.

    L'erreur classique des internautes avec "des faibles notions en mathématiques" est de faire les calculs sur les nombres entiers, alors qu'on parle de points de courbe elliptique.

    Dans ton cas, j'imagine que 3398P = P.
    Cette réponse vous apporte quelque chose ? Cliquez sur en bas à droite du message.

  3. #3
    Rédacteur

    Homme Profil pro
    Administrateur de base de données
    Inscrit en
    août 2013
    Messages
    590
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Oise (Picardie)

    Informations professionnelles :
    Activité : Administrateur de base de données
    Secteur : Finance

    Informations forums :
    Inscription : août 2013
    Messages : 590
    Points : 2 608
    Points
    2 608
    Par défaut
    Citation Envoyé par Flodelarab Voir le message
    Dans ton cas, j'imagine que 3398P = P.
    Bonjour. Et merci d'avoir pris le temps d'apporter une réponse même si, malheureusement, je n'ai rien compris.
    Je ne sais pas qui t'a mis un pouce négatif, mais ce n'est pas moi.
    Si quelqu'un peut apporter une aide plus adaptée à mes faibles notions, je suis preneur.
    Cordialement.
    Débutants, n'hésitez pas à consulter mon mémento sur la programmation en VBA pour EXCEL tome 1.
    Ou le tome 2 qui aborde la programmation en mode graphique avec un exemple de programmation d'un jeu d'arcade en VBA.
    Pour les curieux, le tome 3 explique le problème du voyageur de commerce.
    Le tome 4 est consacré à la cryptologie en VBA.
    Vous découvrirez dans le tome 5 les fonctions SQL pour gérer les tableaux de données et l'application Sentinelle qui veille sur vos fichiers.
    Le tome 6, dernier de la série, vous apprendra à créer des fonctions pour simplifier la vie des utilisateurs.
    Le Crible Quadratique donne toutes les fonctions pour les opérations sur les grands nombres en VBA.
    En bonus : Programmation en VBA de menus personnalisés pour Excel, Manipuler les données des bases Access depuis Excel et Transférer des fichiers volumineux avec Outlook.

  4. #4
    Rédacteur

    Homme Profil pro
    Administrateur de base de données
    Inscrit en
    août 2013
    Messages
    590
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Oise (Picardie)

    Informations professionnelles :
    Activité : Administrateur de base de données
    Secteur : Finance

    Informations forums :
    Inscription : août 2013
    Messages : 590
    Points : 2 608
    Points
    2 608
    Par défaut
    Bonjour.
    J’ai trouvé pourquoi (31/-16) MOD 3397 = 635

    Pour deux raisons :

    La première, c’est qu’il faut retraiter la fraction pour retrouver l’inverse modulo, c’est-à-dire retrouver la valeur de x dans :
    16x MOD 3397 = 1

    Ça peut se faire par la force brute :
    16 x 1 MOD 3397 = 16
    16 x 2 MOD 3397 = 32
    16 x … MOD 3397 = …
    16 x 637 MOD 3397 = 1

    Ou par cet algorithme :
    Code VBA : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    '------------------------------------------------------------------------------------------------
    Function InversMod(ByVal A, ByVal B) 
    '------------------------------------------------------------------------------------------------
    Dim Q, T, X, Y
    X = 1: Y = 0
    While (B <> 0)
        T = B
        Q = Int(A / T)
        B = A - Q * T
        A = T
        T = X
        X = Y - Q * T
        Y = T
    Wend
    InversMod = CDec(Y)
    If Y < 0 Then InversMod = CDec(Y + NbB)
    End Function
    '------------------------------------------------------------------------------------------------

    Donc (31 x 637) MOD 3397 = 2762

    Mais ici, deuxième raison, un des termes est négatif, -16 et non pas 16, donc il faut ôter cette valeur à 3397 :
    3397 – 2762 = 635

    Bon, je continue mes recherches sur la méthode ECM car j’ai encore des zones sombres à éclaircir.
    Si vous le souhaitez, votre aide sera la bienvenue.
    Cordialement.
    Débutants, n'hésitez pas à consulter mon mémento sur la programmation en VBA pour EXCEL tome 1.
    Ou le tome 2 qui aborde la programmation en mode graphique avec un exemple de programmation d'un jeu d'arcade en VBA.
    Pour les curieux, le tome 3 explique le problème du voyageur de commerce.
    Le tome 4 est consacré à la cryptologie en VBA.
    Vous découvrirez dans le tome 5 les fonctions SQL pour gérer les tableaux de données et l'application Sentinelle qui veille sur vos fichiers.
    Le tome 6, dernier de la série, vous apprendra à créer des fonctions pour simplifier la vie des utilisateurs.
    Le Crible Quadratique donne toutes les fonctions pour les opérations sur les grands nombres en VBA.
    En bonus : Programmation en VBA de menus personnalisés pour Excel, Manipuler les données des bases Access depuis Excel et Transférer des fichiers volumineux avec Outlook.

Discussions similaires

  1. Parser des entiers avec JSON
    Par natalie75 dans le forum Android
    Réponses: 0
    Dernier message: 25/04/2015, 17h43
  2. concaténation des entiers avec C++
    Par etudiante11 dans le forum C++
    Réponses: 3
    Dernier message: 09/06/2014, 09h51
  3. gprolog : manipuler des entiers avec beaucoup de chiffres
    Par DavidleVrai dans le forum Prolog
    Réponses: 2
    Dernier message: 15/11/2012, 09h01
  4. manipuler des entier avec la virgule
    Par sky88 dans le forum Débuter
    Réponses: 6
    Dernier message: 16/01/2009, 13h47
  5. Réponses: 1
    Dernier message: 15/05/2006, 18h05

Partager

Partager
  • Envoyer la discussion sur Viadeo
  • Envoyer la discussion sur Twitter
  • Envoyer la discussion sur Google
  • Envoyer la discussion sur Facebook
  • Envoyer la discussion sur Digg
  • Envoyer la discussion sur Delicious
  • Envoyer la discussion sur MySpace
  • Envoyer la discussion sur Yahoo