Factorisation d'un nb composé en 2 premiers (par attack en force brute)

Soyez le premier à donner votre avis sur cette source.

Snippet vu 3 355 fois - Téléchargée 36 fois

Commenter

Contenu du snippet

Slt,
un ptit prog ki permet de trouver les 2 facteurs premiers d'un nombre composé...
Nb = nombre à factoriser et a et b les 2 facteur premiers (avec a <= (inf ou egal) b)
on test (Nb/i=entier)? avec i decrivant l'ensemble des premiers de 2 à sqrt(Nb) (enfin o nb premier inferier et le plus "proche" de sqrt(Nb))
si le test est verifié alors i=a et Nb/i =b
pour l'instant c limiter au int (ou au long) ...

Source / Exemple : 


#include <iostream.h>
#include <math.h>

bool EstPremier ( long  N)
//d'autre algo st dispo sur le site mé celui ci (enpreinté ossi sur le site) fonctionne  
// trés bien sur les petits nbs (ca commence à ramer vers 10000000)
{
   long i;
   if (N<2) return false;
   if (N==2) return true;
   if (N % 2 == 0) return false;
   i = 3;
   while (i<N)
   {
     
     if (N % i == 0) return false;
     i += 2;
   }
   return true;
}

bool EstDiviseur (long UnNb, long UnI)
//si le rest e de la div euclidienne d'un nb composé par un premier est nul alors le resultat 
//de la division (normal ;-)) est lui ossi un premier!!
{
	if (UnNb%UnI==0)   
	     return true;
	else return false;
}

void main ()
{
    long Nb;
    long i=2;
    bool Trouver=false;
	
    cout<<"Nb a factoriser? (ne pas depasser 2 147 483 647 car g po implementer la classe sur les grand nb) "<<endl;
    cin>> Nb;

    while (i<=sqrt(Nb) && !Trouver) 
    //Nb=a*b
    //soit a le facteur premier le plus petit 
    //<=> 2<a<b   (c des inf ou egal)
    //=> a*a<a*b  (a²<a*b et a*b==Nb)
    //<=>a<sqrt(Nb)  (sqrt(Nb) c la racine carré de Nb)
          {
	if (EstPremier(i))
	{ 
	                if (EstDiviseur(Nb,i))
		{
			Trouver=true;
			cout<<i;
			cout<<" et ";
			cout<< Nb/i;
			cout<<" sont les facteurs premiers de ";
			cout<<Nb>>endl;
			}
		};
		i++;
	}
}

Conclusion :


je me suis inspiré d'un source du site pour la fonction EstPremier (jme souviens plus ki est l'auteur mais il se reconnaitra et je l'en remercie)

il y a un warning à la sortie de la fonction EstDiviseur si kukun c pourkoi??

A voir également

Ajouter un commentaire

Commentaires

Signaler
Orkblutt
Messages postés
17
Date d'inscription
samedi 20 avril 2002
Statut
Membre
Dernière intervention
7 septembre 2004
 -
precision:
"tout nb premier superieur ou égal à 5 est de la forme 6*n-1 ou 6*n+1 avec n entier naturel"

On ne génére pas que des premiers avec une fonction du type f(x)= { 6x-1 , 6x+1} mais cela n'as aucune importance si l'on veut "attaquer" en force un nb (plus couteux de faire des test de primalité, meme très très basique, que de tester ts les nb générés par f(x)...)
Signaler
Orkblutt
Messages postés
17
Date d'inscription
samedi 20 avril 2002
Statut
Membre
Dernière intervention
7 septembre 2004
 -
oula... trop vieux ca :) et pas super performant...
on test tous les nombres impaires supèrieurs à 2...

pour générer tous les premiers dans un intervalle donné, il est beaucoup moins couteux d'utiliser l'axiom "tout nb premier superieur ou égal à 5 est de la forme 6*n-1 ou 6*n+1 avec n entier naturel"...

Pour factoriser un entier la brute force est la mèthode la moins performante. Pour des nombres spéciaux ECM ou SNFS sont parfait (ECM pour des nombres a environ 100 digits et jusquà 180 digits pour SNFS). Pour des nombres dont les 2 facteurs premiers sont du meme ordre de grandeure que N (clef RSA...) GNFS est l'algo le plus rapide à ce jour (factorisation d'une 576bits en decembre 2003). Les variantes des cribles quadratiques
marchent très bien sur des nb inférieurs à ~100digits...
Signaler
Super_Mat
Messages postés
37
Date d'inscription
jeudi 2 septembre 2004
Statut
Membre
Dernière intervention
31 août 2005
 -
Tu pourrais retrouver le source dont tu t'es inspiré car ca m'intéresse peut-être. Merci
Signaler
cs_LordBob
Messages postés
2865
Date d'inscription
samedi 2 novembre 2002
Statut
Membre
Dernière intervention
11 mai 2009
 8 -
merci je chercher un code dans ce style
S'inscrire maintenant

Vous n'êtes pas encore membre ?

inscrivez-vous, c'est gratuit et ça prend moins d'une minute !

Les membres obtiennent plus de réponses que les utilisateurs anonymes.

Le fait d'être membre vous permet d'avoir un suivi détaillé de vos demandes et codes sources.

Le fait d'être membre vous permet d'avoir des options supplémentaires.

Du même auteur (Orkblutt)