Apprendre Maple Index du Forum Apprendre Maple
Site dédié au logiciel de calcul formel Maple
 
  Page d'accueilPage d'accueil   FAQFAQ    RechercherRechercher    Liste des MembresListe des Membres    Groupes d'utilisateursGroupes d'utilisateurs 
S'enregistrerS'enregistrer    ProfilProfil   Se connecter pour vérifier ses messages privésSe connecter pour vérifier ses messages privés   ConnexionConnexion 

Factorisation nombre semi-premier RSA v.2

 
Poster un nouveau sujet   Répondre au sujet    Apprendre Maple Index du Forum -> Programmation
Voir le sujet précédent :: Voir le sujet suivant  
Auteur Message
Guimzo



Inscrit le: 02 Juin 2012
Messages: 209

MessagePosté le: 11 Oct 2014 15:09    Sujet du message: Factorisation nombre semi-premier RSA v.2 Répondre en citant

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
Voir le profil de l'utilisateur Envoyer un message privé
Guimzo



Inscrit le: 02 Juin 2012
Messages: 209

MessagePosté le: 11 Oct 2014 20:52    Sujet du message: Répondre en citant

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
Voir le profil de l'utilisateur Envoyer un message privé
ALS



Inscrit le: 11 Sep 2006
Messages: 647

MessagePosté le: 12 Oct 2014 7:01    Sujet du message: Répondre en citant

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
Voir le profil de l'utilisateur Envoyer un message privé
Guimzo



Inscrit le: 02 Juin 2012
Messages: 209

MessagePosté le: 12 Oct 2014 10:38    Sujet du message: Répondre en citant

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
Voir le profil de l'utilisateur Envoyer un message privé
Guimzo



Inscrit le: 02 Juin 2012
Messages: 209

MessagePosté le: 12 Oct 2014 10:44    Sujet du message: Répondre en citant

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
Voir le profil de l'utilisateur Envoyer un message privé
ALS



Inscrit le: 11 Sep 2006
Messages: 647

MessagePosté le: 13 Oct 2014 6:45    Sujet du message: Répondre en citant

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
Voir le profil de l'utilisateur Envoyer un message privé
Guimzo



Inscrit le: 02 Juin 2012
Messages: 209

MessagePosté le: 13 Oct 2014 10:03    Sujet du message: Répondre en citant

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
Voir le profil de l'utilisateur Envoyer un message privé
Montrer les messages depuis:   
Poster un nouveau sujet   Répondre au sujet    Apprendre Maple Index du Forum -> Programmation Toutes les heures sont au format GMT + 2 Heures
Page 1 sur 1

 
Sauter vers:  
Vous ne pouvez pas poster de nouveaux sujets dans ce forum
Vous ne pouvez pas répondre aux sujets dans ce forum
Vous ne pouvez pas éditer vos messages dans ce forum
Vous ne pouvez pas supprimer vos messages dans ce forum
Vous ne pouvez pas voter dans les sondages de ce forum


phpBB

Développé par phpBB © 2001, 2006 phpBB Group
Traduction par : phpBB-fr.com


Apprendre Maple - ©  - Alain Le Stang - Navigation optimisée pour une résolution 1024 x 768.