Bibm@th

Forum de mathématiques - Bibm@th.net

Bienvenue dans les forums du site BibM@th, des forums où on dit Bonjour (Bonsoir), Merci, S'il vous plaît...

Vous n'êtes pas identifié(e).

#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

Réponse rapide

Veuillez composer votre message et l'envoyer
Nom (obligatoire)

E-mail (obligatoire)

Message (obligatoire)

Programme anti-spam : Afin de lutter contre le spam, nous vous demandons de bien vouloir répondre à la question suivante. Après inscription sur le site, vous n'aurez plus à répondre à ces questions.

Quel est le résultat de l'opération suivante (donner le résultat en chiffres)?
quatre-vingt dix-huit moins seize
Système anti-bot

Faites glisser le curseur de gauche à droite pour activer le bouton de confirmation.

Attention : Vous devez activer Javascript dans votre navigateur pour utiliser le système anti-bot.

Pied de page des forums