Discussion :

[1pedro1]

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

[droggo]

Jei,

Ce que tu demandes est du niveau arithmétique élémentaire, il suffit d'appliquer à des BigInteger.

[1pedro1]

Merci pour ta réponse svp, mais pourrais tu être un peu plus précis, donner une piste (Euler/Euclide/Gauss un truc quoi )

Merci d'avance