Forum de mathématiques - Bibm@th.net
Vous n'êtes pas identifié(e).
- Contributions : Récentes | Sans réponse
Pages : 1
#1 10-01-2009 16:39:17
- 1pedro1
- Invité
Trouver un facteur d'un BigInteger
Bonjour a tous,
Mon binome et moi avons un problème en ce qui concerne le procédé de signature numerique de Pointcheval-Vaudenay.
Nous devons trouvé un nombre premier p appartenant à ]2^511,2^512[ et un nombre premier q appartenant à ]2^159,2^160[ qui est facteur de p-1.
Grâce à la classe BigInteger de l'API Java nous avons trouvé un nombre p premier ( grâce à la méthode ProbablePrime ), ainsi que p-1.
Par contre on a aucune idée de comment trouver le q. En effet si on génère un nombre premier q avec ProbablePrime comment s'assurer qu'il est bien le facteur de p-1.
La méthode divide( p-1/q) nous retourne toujours un BigInteger pourtant nous ne sommes jamais sur que q est bien facteur de p-1 car divide cast le résultat en BigInteger.
Nous avons crée une boucle avec la fonction remainder pour vérifier que le reste est nulle, si ce n'est pas le cas la boucle est relancée.
BigInteger q = BigInteger.probablePrime(160, new Random());
while((p.subtract(BigInteger.ONE)).remainder(q) != BigInteger.ZERO) {
q = BigInteger.probablePrime(160, new Random());
}
Cependant cela tourne, tourne, tourne et ne trouve jamais.
Ma question est donc comment (quelle méthode utilisé) s'assurer que le nombre q est bien facteur de p-1.
Votre aide serait très souhaitable.
Merci d'avoir pris le temps de me lire.
ps: p.substract(BigInteger.ONE) est fait pour trouver p-1
Merci d'avance
#2 10-01-2009 22:35:08
- pascal
- Membre
- Inscription : 27-01-2007
- Messages : 56
Re : Trouver un facteur d'un BigInteger
je ne sais pas si votre méthode est la bonne. Par contre, je pense que pour une recherche exhaustive, utiliser JAVA ne me semble pas très indiqué à cause de la lenteur du langage. Je pense que vous devriez tenter le coup avec du C/C++ en utilisant par exemple l'excellente bibliothèque MIRACL (elle travaille sur les BigNums). Utilisez les fonctions "nxprime" et "divisible"...
Hors ligne
Pages : 1