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

  1. #1
    Expert éminent sénior Avatar de Artemus24
    Homme Profil pro
    Agent secret au service du président Ulysses S. Grant !
    Inscrit en
    février 2011
    Messages
    4 817
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Paris (Île de France)

    Informations professionnelles :
    Activité : Agent secret au service du président Ulysses S. Grant !
    Secteur : Finance

    Informations forums :
    Inscription : février 2011
    Messages : 4 817
    Points : 13 819
    Points
    13 819
    Par défaut [mingw32]Décomposition inverse d'une multiplication !
    Salut à tous.

    Le but est de partir d'un nombre très très grand qui est le résultat d'une multiplication de deux nombres premiers (N = a * b).
    Bien sûr, essayer de retrouver ces deux nombres premiers le plus rapidement.

    Je me suis penché sur cette question, et la première idée consiste à décomposer ce nombre N sous la forme : x * ( x + y ).
    Ce qui revient à dire que x est la racine carré du nombre N et ce x est en fait a.
    Je dois retrouver b qui est en fait le reste de : N - x*x où x est initialisé à la racine carré de N puis varie par décrémentation.

    Le mieux est de donner mon petit programme en 'C' :
    Code : 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
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    /**********************************************/
    /*                                            */
    /*     Décomposition de la multiplication     */
    /*                                            */
    /**********************************************/
     
    #include <stdio.h>
    #include <stdlib.h>
    #include <limits.h>
    #include <math.h>
     
    /********************************/
    /*                              */
    /*     Procédure Principale     */
    /*                              */
    /********************************/
     
    int main(void)
    {
    	unsigned long long int		a,b,i,n;
     
    	/*==========================*/
    	/*     Saisie du nombre     */
    	/*==========================*/
     
    	printf("Maximum : %llu\n", ULLONG_MAX);
    	printf( "Veuillez saisir le nombre à décomposer : " );
    	scanf( "%llu", &n );
     
    	/*=====================*/
    	/*     Préparation     */
    	/*=====================*/
     
    	a = (long long int)sqrt(n);
    	b = n - a*a;
    	i = 2 * a + 1;
     
    	/*================*/
    	/*     Calcul     */
    	/*================*/
     
    	while ((b%a) != 0)
    	{
    		b += (i -= 2);
    		a--;
    	}
     
    	printf("\nA = %8.0llu   B = %8.0llu   Res = %llu\n", a, (a + (b/a)), (a*a + b));
    }
    Et voici quelques résultats :
    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    Maximum : 18446744073709551615
    Veuillez saisir le nombre à décomposer : 1234567890987654321
     
    A = 1111011111   B = 1111211111   Res = 1234567890987654321
    Appuyez sur une touche pour continuer...
    Ou encore :
    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    Maximum : 18446744073709551615
    Veuillez saisir le nombre à décomposer : 987654313456789
     
    A =   203423   B = 4855175243   Res = 987654313456789
    Appuyez sur une touche pour continuer...
    Le résultat est assez rapide quand la multiplication est proche de son carré.

    Question : peut-on améliorer cet algorithme ?

    @+
    Si vous êtes de mon aide, vous pouvez cliquer sur .
    Mon site : http://www.jcz.fr

  2. #2
    Membre éprouvé

    Homme Profil pro
    Directeur de projet
    Inscrit en
    mai 2013
    Messages
    342
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Yvelines (Île de France)

    Informations professionnelles :
    Activité : Directeur de projet
    Secteur : Service public

    Informations forums :
    Inscription : mai 2013
    Messages : 342
    Points : 1 206
    Points
    1 206
    Par défaut Espoir vs espérance
    Bonjour,

    En cryptologie, un critère de choix des premiers qui vont participer à un grand nombre est la relation d'ordre de grandeur entre eux qui doit être importante. Les facteurs ne sont donc jamais proche de la racine carré. Cet algorithme apparaît donc assez vite hors course. Il y a quelques améliorations qui s'appuient sur la structure du N à décomposé mais elles n'en changent pas fondamentalement l'efficacité.

    Il y a beaucoup de littérature (voir wikipedia pour commencer) sur ce problème difficile mais pas NP complet (il y a pire c'est rassurant ).

    Salutations
    Ever tried. Ever failed. No matter. Try Again. Fail again. Fail better. (Samuel Beckett)

  3. #3
    Expert éminent sénior
    Avatar de Sve@r
    Homme Profil pro
    Ingénieur développement logiciels
    Inscrit en
    février 2006
    Messages
    8 780
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Oise (Picardie)

    Informations professionnelles :
    Activité : Ingénieur développement logiciels
    Secteur : Aéronautique - Marine - Espace - Armement

    Informations forums :
    Inscription : février 2006
    Messages : 8 780
    Points : 24 102
    Points
    24 102
    Billets dans le blog
    1
    Par défaut
    Citation Envoyé par Artemus24 Voir le message
    Salut à tous.
    Bonjour

    Citation Envoyé par Artemus24 Voir le message
    Le but est de partir d'un nombre très très grand qui est le résultat d'une multiplication de deux nombres premiers (N = a * b).
    Bien sûr, essayer de retrouver ces deux nombres premiers le plus rapidement.
    Ah ? Parti pour casser RSA ? Bonne chance

    Citation Envoyé par Artemus24 Voir le message
    Je me suis penché sur cette question, et la première idée consiste à décomposer ce nombre N sous la forme : x * ( x + y ).
    Ce qui revient à dire que x est la racine carré du nombre N et ce x est en fait a.
    Tu as conscience, j'espère, que ton algorithme n'est en réalité qu'un "brute force" inversé. Parce que entre partir de 2 et tester tous les nombres (2, 3, 4, 5, ...) jusqu'à (au pire) racine(N) ou bien partir de racine(N) et tester -1, -2, -3, ... jusqu'à (au pire) 2 c'est quelque part un peu la même chose. Avec toutefois une petite préférence pour le brute force classique car à moins d'être teubé et avoir choisi a=2, on peut présumer que a et b sont impairs donc partir de 3 et monter de 2 en 2.
    Donc en fait, ta question c'est "peut-on optimiser le brute force". Voià quoi.
    Mon Tutoriel sur la programmation «Shell»
    Sinon il y en a pleins d'autres. N'oubliez pas non plus les différentes faq disponibles sur ce site

  4. #4
    Expert éminent sénior Avatar de Artemus24
    Homme Profil pro
    Agent secret au service du président Ulysses S. Grant !
    Inscrit en
    février 2011
    Messages
    4 817
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Paris (Île de France)

    Informations professionnelles :
    Activité : Agent secret au service du président Ulysses S. Grant !
    Secteur : Finance

    Informations forums :
    Inscription : février 2011
    Messages : 4 817
    Points : 13 819
    Points
    13 819
    Par défaut
    Salut à tous.

    Citation Envoyé par Guesset
    Les facteurs ne sont donc jamais proche de la racine carré.
    C'est une autre approche, que l'approche triviale qui consiste à utiliser les nombres premiers inférieurs à la racine carré de la multiplication.
    Je reste conscient que mon algorithme est juste une ébauche de la fonction inverse de la multiplication.

    L'idée est la même que celle de l'algorithme de Shor.
    Cette approche reste très simpliste, mais bien que meilleur que l'approche triviale.

    Citation Envoyé par Guesset
    Cet algorithme apparaît donc assez vite hors course.
    Pourquoi est-ce si difficile de trouve cette fonction inverse ?

    Citation Envoyé par Guesset
    Il y a quelques améliorations qui s'appuient sur la structure du N à décomposé mais elles n'en changent pas fondamentalement l'efficacité.
    Quelle amélioration peut-on apporter ?

    Citation Envoyé par Sve@r
    Ah ? Parti pour casser RSA ? Bonne chance
    Je ne cherche pas à casser le RSA. A moins de me tromper, la longueur conseillé par le RSA est de 2048, voire 4096 bits, non ?
    Les 4096 bits représente un nombre de 1234 chiffres. Mon petit ordinateur ne pourrait pas supporter le choc.

    Citation Envoyé par Sve@r
    Tu as conscience, j'espère, que ton algorithme n'est en réalité qu'un "brute force" inversé.
    Oui, c'est bien cela. Peut-on l'améliorer ?

    Citation Envoyé par Sve@r
    Donc en fait, ta question c'est "peut-on optimiser le brute force". Voilà quoi.
    Ou mieux, expliquer pourquoi cette approche ne mène à rien.

    J'ai vu le prix et les records.
    Incroyable ! Le RSA-250 a été cassé le 28 février 2020, soit 829 bits.

    @+
    Si vous êtes de mon aide, vous pouvez cliquer sur .
    Mon site : http://www.jcz.fr

  5. #5
    Membre éprouvé

    Homme Profil pro
    Directeur de projet
    Inscrit en
    mai 2013
    Messages
    342
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Yvelines (Île de France)

    Informations professionnelles :
    Activité : Directeur de projet
    Secteur : Service public

    Informations forums :
    Inscription : mai 2013
    Messages : 342
    Points : 1 206
    Points
    1 206
    Par défaut Les difficultés se multiplient
    Bonsoir,

    Le problème de l'algorithme proposé est qu'il parcourt linéairement l'intervalle entre a et b. Or les 2 sont en général très distants l'un de l'autre. Prenons une exemple supposons que a soit de l'ordre de N1/3 et donc b de l'ordre de N2/3. La distance entre les deux est donc de l'ordre de N1/3*(N1/3-1) soit environ (N1/3-1/2)². Avec 1024 bits cela représenterait de l'ordre de 2680 étapes soit au moins 10204. C'est beaucoup. Beaucoup trop.

    On cherche des algorithmes dont la complexité soit un polynôme de log(N) et non une puissance (même fractionnaire) de N.

    La structure à laquelle on peut s'intéresser est le début de N = n*2p + r, r permet d'interdire a priori des valeurs de a et b et donc de diminuer le nombre de valeurs à tester mais cela ne change pas fondamentalement l'algorithme.

    C'est désolant mais c'est ainsi.

    Salutations
    Ever tried. Ever failed. No matter. Try Again. Fail again. Fail better. (Samuel Beckett)

  6. #6
    Expert éminent sénior
    Avatar de Sve@r
    Homme Profil pro
    Ingénieur développement logiciels
    Inscrit en
    février 2006
    Messages
    8 780
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Oise (Picardie)

    Informations professionnelles :
    Activité : Ingénieur développement logiciels
    Secteur : Aéronautique - Marine - Espace - Armement

    Informations forums :
    Inscription : février 2006
    Messages : 8 780
    Points : 24 102
    Points
    24 102
    Billets dans le blog
    1
    Par défaut
    J'ai tenté un truc en partant de l'hypothèse d'Artemus24 disant N=x * ( x + y ). En développant, on obtient x²+xy-N=0. Equation du second degré. On calcule delta=y²+4N. Il existe donc deux solutions qui sont (-y+sqrt(delta))/2 et (-y-sqrt(delta))/2.
    La seconde qui se factorisera en -(y+sqrt(delta))/2 et qui est donc clairement négative sera à oublier et on se concentre sur (sqrt(delta)-y)/2. Ne reste qu'à trouver"y" tel que y²+4N soit un carré parfait (sinon sqrt(delta) donne un nombre irrationnel qui ne convient pas).
    Ca me paraissait une bonne idée sur le papier. Mais quand je l'ai appliquée, elle a foirée. Parce que pour par exemple 13*97, là où le brute force fera 6 tests (on ne teste que les impairs), il m'a fallu monter jusqu'à 84 pour trouver y²+4N carré parfait. Et 84 tests au lieu de 6...
    C'est dommage car ça fonctionne. Quand y=84 on a bien delta=12100 et sqrt(delta)=110 ce qui donne au final x=13 (et x=-97 pour la seconde solution). Mais reste 84 tests au lieu de 6...
    Mon Tutoriel sur la programmation «Shell»
    Sinon il y en a pleins d'autres. N'oubliez pas non plus les différentes faq disponibles sur ce site

  7. #7
    Membre éprouvé

    Homme Profil pro
    Directeur de projet
    Inscrit en
    mai 2013
    Messages
    342
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Yvelines (Île de France)

    Informations professionnelles :
    Activité : Directeur de projet
    Secteur : Service public

    Informations forums :
    Inscription : mai 2013
    Messages : 342
    Points : 1 206
    Points
    1 206
    Par défaut Produit comme différence de carrés
    Bonjour Sve

    Citation Envoyé par Sve@r Voir le message
    Ne reste qu'à trouver"y" tel que y²+4N soit un carré parfait...
    En fait, c'est toujours la force brute sous une autre forme.

    La valeur de y est paire sinon x+y serait pair puisque x est impair (on suppose que N est impair bien sûr). Écrivons y = 2a. Nous avons donc 4a² + 4N = B² ce qui implique B pair = 2b d'où a²+N=b² soit N = (b-a)(b+a) = x(x+y) = ((x+y/2)-y/2)((x+y/2)+y/2).

    Ça tourne en rond

    Salut
    Ever tried. Ever failed. No matter. Try Again. Fail again. Fail better. (Samuel Beckett)

  8. #8
    Expert éminent sénior Avatar de Artemus24
    Homme Profil pro
    Agent secret au service du président Ulysses S. Grant !
    Inscrit en
    février 2011
    Messages
    4 817
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Paris (Île de France)

    Informations professionnelles :
    Activité : Agent secret au service du président Ulysses S. Grant !
    Secteur : Finance

    Informations forums :
    Inscription : février 2011
    Messages : 4 817
    Points : 13 819
    Points
    13 819
    Par défaut
    Salut à tous.

    Merci de votre collaboration.

    Citation Envoyé par Guesset
    Or les 2 facteurs" sont en général très distants l'un de l'autre.
    Pour éviter de cracker trop rapidement le RSA, l'astuce est de trouver ces deux facteurs dans un schéma non prédictible.
    C'est pourquoi, comme tu le dis, ils sont très distants l'un de l'autre.
    C'est un écueil difficile à résoudre car ce schéma est en dehors de toute logique basique.

    Citation Envoyé par Guesset
    C'est beaucoup, beaucoup trop.
    Plus le nombre à décomposer est grand, plus cela va prendre du temps.
    Donc impossible à cracker le RSA dans un temps raisonnable.
    Sauf si ce nombre N a une particularité.

    1) Pour revenir sur ma démarche, j'ai commencé par raisonner sur la multiplication elle-même.
    J'ai cherché à décomposer la multiplication, de la même façon qu'on l'apprend dans les petites classes.
    Nous avons alors un système d'équations avec comme contrainte, la propagation de la partie entière à l'unité supérieure.
    A chaque étape, je suis obligé de calculer le modulo 10 ainsi que la division euclidienne de 10.
    C'est complexe à mettre en œuvre puisqu'il y a des retours en arrière. Au final, c'est très très long.

    2) Ma démarche suivante a été la classique division par la liste des nombres premiers.
    Le problème de cette approche est de posséder la liste des nombres premiers.

    3) Au lieu de débuter par les petits nombres premiers, j'ai pensé à commencer par la racine carré.
    Mais cette approche est tout aussi longue.

    Citation Envoyé par Guesset
    On cherche des algorithmes dont la complexité soit un polynôme de log(N) et non une puissance (même fractionnaire) de N.
    C'est un autre problème, celui de ma résolution NP = P

    Citation Envoyé par Guesset
    La structure à laquelle on peut s'intéresser est le début de N = n*2p + r,
    Au lieu d'avoir la base 10, ici la base est 2p.
    Il est vrai que trouver la partie entière n et le reste r est bien plus facile avec une représentation binaire.

    Citation Envoyé par Guesset
    r permet d'interdire a priori des valeurs de a et b et donc de diminuer le nombre de valeurs à tester mais cela ne change pas fondamentalement l'algorithme.
    Je ne comprends pas trop cette affirmation.

    Citation Envoyé par Sve@r
    J'ai tenté un truc en partant de l'hypothèse d'Artemus24 disant N=x * ( x + y ).
    J'avais déjà tenté cette solution, sans succès.

    Citation Envoyé par Sve@r
    Mais reste 84 tests au lieu de 6...
    Tu arrives à la même solution que moi, à savoir trop de calcul pour arriver au résultat.

    Je persiste à dire que si je sais calculer xi qui est la racine carré entière de N, mon problème est de trouver la divisibilité euclidienne de yi/xi.
    Par division euclidienne, j'entends l'obtention d'un reste nul.

    Dans mon algorithme yi augmente tandis que xi diminue.
    N'y-a-t-il pas un moyen de trouver la convergence où plusieurs i de yi serait divisible par le xi ?

    Ce que je remarque, c'est que la variation yi est toujours un nombre impair dont on décrémente de 2.
    Par exemple 17, 15, 13, 11, 9, 7, 5, 3, 1. Si l'on fait la somme de cette variation, c'est toujours un carré.

    Prenons un exemple. N=91 la racine carré est 9.

    --> a0 = 9.
    --> b0 = 91 - (a0)2 = 91 - 92 = 91 - 81 = 10.
    --> i0 = 2 * a0 + 1 = 2 * 9 + 1 = 19.

    test : 19 / 9 ? non

    --> i1 = i0 - 2 = 19 - 2 = 17.
    --> b1 = b0 + i1 = 10 + 17 = 27
    --> a1 = a0 - 1 = 9 - 1 = 8.

    test : 27 / 8 ? non

    --> i2 = i1 - 2 = 17 - 2 = 15.
    --> b2 = b1 + i1 = 27 + 15 = 42.
    --> a2 = a1 - 1 = 8 - 1 = 7.

    test : 42 / 7 ? oui = 6

    Résultat :
    --> a = a2 = 7.
    --> b = a2 + b2 / a2 = 7 + 6 = 13.

    Vérification : 7 * 13 = 91. Ok !

    Pour l'indice 2, nous obtenons la solution.

    b2 = 42.
    N vaut 91.
    Donc 91 - 42 = 49 qui est un carré.
    C'est aussi le carré de 7, qui est la valeur de a que nous trouvons pour l'indice 2.

    Je ne sais pas trop si l'on peut exploiter quoi que ce soit avec cette constatation.
    Cela revient à dire que : N - a2 est divisible par a.

    Citation Envoyé par Guesset
    Ça tourne en rond
    Qu'est-ce que tu sous-entends ? La récursivité ?

    @+
    Si vous êtes de mon aide, vous pouvez cliquer sur .
    Mon site : http://www.jcz.fr

  9. #9
    Membre éprouvé

    Homme Profil pro
    Directeur de projet
    Inscrit en
    mai 2013
    Messages
    342
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Yvelines (Île de France)

    Informations professionnelles :
    Activité : Directeur de projet
    Secteur : Service public

    Informations forums :
    Inscription : mai 2013
    Messages : 342
    Points : 1 206
    Points
    1 206
    Par défaut NP complet
    Bonjour,

    Ça tourne en rond signifie juste que l'approche revient à son point de départ sans donner de piste exploitable.

    Toutes les formes d'algorithmes en O(np) sont inexploitables pour les grand nombres c'est pourquoi on cherche des algorithmes en O(ln(N)q) fussent ils heuristiques. La démonstration N=NP ou N!=NP n'a rien à voir car même s'il existe un algorithme déterministe pour la factorisation en O(ln(N)q), il ne prouvera pas l'assertion N=NP car ce problème n'est pas NP complet.

    Salutations
    Ever tried. Ever failed. No matter. Try Again. Fail again. Fail better. (Samuel Beckett)

Discussions similaires

  1. Inversion d'une liste chaînée
    Par sossomj dans le forum Pascal
    Réponses: 10
    Dernier message: 25/06/2006, 16h51
  2. Réponses: 8
    Dernier message: 31/05/2006, 12h10
  3. Améliorer le calcul d'une multiplication (32*32)bits ?
    Par progfou dans le forum Algorithmes et structures de données
    Réponses: 36
    Dernier message: 23/03/2006, 12h34
  4. [LG] Inversion avec une boucle tant que
    Par erickson dans le forum Langage
    Réponses: 2
    Dernier message: 09/12/2005, 16h15
  5. Utilité d'une multiplication rapide ?
    Par Jo'CaML dans le forum Algorithmes et structures de données
    Réponses: 9
    Dernier message: 08/06/2005, 10h49

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