Voir le sujet précédent :: Voir le sujet suivant |
Auteur |
Message |
Guimzo
Inscrit le: 02 Juin 2012 Messages: 210
|
Posté le: 11 Oct 2014 15:09 Sujet du message: Factorisation nombre semi-premier RSA v.2 |
|
|
Bonjour ALS,
Et oui encore besoin de votre aide s'il vous plaît lol : )
En fait j'ai une opération telle que :
op := [ sqrt (x^2+4*p)+x) ] * (1/2) ;
sauf que "x" en fait est compris entre tant et tant, plus précisément tous les nombres entiers entre par exemple 1 et 100.
Maple doit donc faire le calcul avec tous ces "x" possibles tant que le résultat de l'opération "op" n'est pas un entier.
Voici un début...??
========================================
restart;
Digits := 155;
p := 77;
length(p);
x := sqrt(p)/sqrt(2);
x1 := round(x);
length(x1);
x2 :=rand (1 .. x1);
do op := (sqrt(x2*x2+4*p)+d1)*(1/2);
length(x);
=========================================
En fait faudrait que l'opération se fasse et s'arrète quand le résultat est un entier.
Sachant que "x2" est un entier entre 1 et x1...?? |
|
Revenir en haut de page |
|
 |
Guimzo
Inscrit le: 02 Juin 2012 Messages: 210
|
Posté le: 11 Oct 2014 20:52 Sujet du message: |
|
|
Bonjour ALS,
Voici ce que j'ai refait :
====================================
Digits := 155;
p := 77;
length(p);
d := sqrt(p)/sqrt(2);
f := round(d);
length(f);
c := 1;
do g := rand(c .. f);
Taille := length(g);
r := (sqrt(g*g+4*p)+g)*(1/2);
m := whattype(r);
if m = integer then `and`(print(" ! LES NOMBRES ONT ETE TROUVES...! "), print("TERMINE")) else 0 end if end do ;
=============================================
Mais il semble avoir un probléme... : ( |
|
Revenir en haut de page |
|
 |
ALS
Inscrit le: 11 Sep 2006 Messages: 647
|
Posté le: 12 Oct 2014 7:01 Sujet du message: |
|
|
Bonjour,
Ca fonctionne à peu près: il suffisait de rajouter des parenthèses à la fin dans g := rand(c .. f)(); et modifier le test en utilisant type à la place de whattype.
Car rand est une fonction qui va calculer un nombre aléatoire.
Sauf qu'il n'y a pas arrêt au premier nombre entier obtenu et que g peut prendre plusieurs fois la même valeur.
Votre code corrigé:
Code: |
> Digits := 155;
> p := 77;
> length(p);
> d := sqrt(p)/sqrt(2);
> f := round(d);
> length(f);
> c := 1;
> do g := rand(c .. f)();
> Taille := length(g);
> r := (sqrt(g*g+4*p)+g)*(1/2);
> if type(r,integer) then `and`(print(" ! LES NOMBRES ONT ETE TROUVES...! "), print("TERMINE")) else 0 end if end do ;
|
Ma proposition de code différent:
Code: |
> Digits := 155;
> p := 77;
> d := sqrt(p)/sqrt(2);
> f := round(d);
> for g from 1 to f do
> r := (sqrt(g*g+4*p)+g)*(1/2);
> if type(r,integer) then break end if
> end do:
> print(" ! PREMIER NOMBRE ENTIER TROUVÉ...! "), print("TERMINÉ r =",r);
Digits := 155
p := 77
1/2 1/2
77 2
d := ----------
2
f := 6
" ! PREMIER NOMBRE ENTIER TROUVÉ...! "
"TERMINE r =", 11
|
break permet de sortir de la boucle for ... do ... end do dès que r est un entier. On affiche alors la valeur de r, 11 ici.
Ce dernier code vous convient-il? |
|
Revenir en haut de page |
|
 |
Guimzo
Inscrit le: 02 Juin 2012 Messages: 210
|
Posté le: 12 Oct 2014 10:38 Sujet du message: |
|
|
Bonjour ALS,
J'ai essayé les 2 séquences, y'à pas photo, votre séquence est instantanée !
C'est vraiment parfait. Le probléme avec ma séquence c'est que les calculs entre autre ne s’arrêtent pas etc etc...
Comme vous avez dû remarquer, c'est une séquence pour factoriser un nombre semi-premier, en partant du principe que la différence entre les 2 facteurs cherchés, est inférieure à sqrt(p)/sqrt(2).
Partant de là, on revient à résoudre une équation du second degré, connaissant la différence de 2 nombres et leur produit.
Alors, ceci dit, peut-être que ça irait encore plus vite, si pour la différence, on ne mettait que les nombres PAIRS, puisque la différence de 2 nombres impairs est toujours PAIR.
Donc pourrait-on faire de sorte que les "g" choisis soient choisis parmi les nombres pairs, au lieu des entiers qui comprennent les pairs comme les impairs....?
En tout cas merci ALS, et quand je trouverais enfin ce que je recherche ( c'est à dire comment factoriser en un temps court, un nombre RSA tel que 21290246318258757547497882016271517497806703963277216278233383215381949984056495911366573853021918316783107387995317230889569230873441936471 ; vous serez le premier informé : )
Bon dimanche et à bientôt. |
|
Revenir en haut de page |
|
 |
Guimzo
Inscrit le: 02 Juin 2012 Messages: 210
|
Posté le: 12 Oct 2014 10:44 Sujet du message: |
|
|
Re-bonjour ALS,
Quand je mets un "p" très "grand" la séquence semble ne pas fonctionner...??
Du genre :
p: = 135066410865995223349603216278805969938881475605667027524485143851526510604859533833940287150571909441798207282164471551373680419703964191743046496589274256239341020864383202110372958725762358509643110564073501508187510676594629205563685529475213500852879416377328533906109750544334999811150056977236890927563 |
|
Revenir en haut de page |
|
 |
ALS
Inscrit le: 11 Sep 2006 Messages: 647
|
Posté le: 13 Oct 2014 6:45 Sujet du message: |
|
|
Bonjour,
Pour n'avoir que des g pairs, remplacer la ligne
> for g from 1 to f do
par la ligne
> for g from 2 to f by 2 do
Sinon, pour des grandes valeurs de p, il faut être patient !
Je ne sais pas si Maple est l'outil le plus performant en vitesse pour que ça fonctionne en temps "raisonnable".
J'ai vu que Maple pouvait utiliser la "GNU Multiple Precision (GMP) Library" que je n'ai jamais eu besoin d'employer.
Taper GMP dans l'aide pour avoir un descriptif des fonctions disponibles. |
|
Revenir en haut de page |
|
 |
Guimzo
Inscrit le: 02 Juin 2012 Messages: 210
|
Posté le: 13 Oct 2014 10:03 Sujet du message: |
|
|
Bonjour ALS,
Merci beaucoup ; je vais voir tout ça.
P.S. : si vous avez des pistes pour faciliter la factorisation des "grands" nombres semi-premiers n'hésitez pas : )
Bonne journée à bientôt |
|
Revenir en haut de page |
|
 |
|