CORNACCHIA ALGORITHM

coucou747 Messages postés 12303 Date d'inscription mardi 10 février 2004 Statut Membre Dernière intervention 30 juillet 2012 - 9 août 2004 à 13:07
ccgousset Messages postés 150 Date d'inscription samedi 1 août 2009 Statut Membre Dernière intervention 4 mars 2023 - 17 déc. 2011 à 22:57

Cette discussion concerne un article du site. Pour la consulter dans son contexte d'origine, cliquez sur le lien ci-dessous.

https://codes-sources.commentcamarche.net/source/25190-cornacchia-algorithm

ccgousset Messages postés 150 Date d'inscription samedi 1 août 2009 Statut Membre Dernière intervention 4 mars 2023
17 déc. 2011 à 22:57

Malik je te pose la meme question qu'au autre user de gmp. As tu utilisé gmp avec le module gmpxx.h(cpp) et vc6++ (ou plus) si oui pourrais tu me faire parvenir le source de gmpxx.h sil te plai. Bonne route.Christophe

malik7934 Messages postés 1154 Date d'inscription mardi 9 septembre 2003 Statut Membre Dernière intervention 15 août 2009 17
22 févr. 2005 à 18:54

J'aurais tendance à dire oui: les unsigned on un bit de moins (le bit de poids fort) donc ils sont plus courts, donc traîtés plus vite!

scelw Messages postés 117 Date d'inscription mercredi 3 septembre 2003 Statut Membre Dernière intervention 17 février 2007
22 févr. 2005 à 17:54

J'ai cherché dans le manuel de GMP si les fonctions unsigned integer (ui) étaient plus rapides que les fonctions signed integer (si) ou que les fonctions "normales" (indéterminées). Sans résultat. Quelqu'un saurait m'informer?

(je ne travaille qu'avec des positifs. vaut-il mieux que j'utilise les fonctions "ui", les fonctions "si" ou les fonctions normales (indéterminées) ?)

scelw Messages postés 117 Date d'inscription mercredi 3 septembre 2003 Statut Membre Dernière intervention 17 février 2007
27 janv. 2005 à 14:34

OK!!! unsigned integer = entier relatif! il suffisait d'avoir un bon traducteur.

Donc, logiquement, on emploie les fonctions qui se terminent par "ui" lorsqu'on veut manipuler des entiers relatifs (négatifs et positifs) et les fonctions de base (sans "ui") lorsqu'on ne manipule que des entiers positifs (ce qui est mon cas)...

Pourquoi le français n'est-il pas la première langue parlée au monde??

ScelW

malik7934 Messages postés 1154 Date d'inscription mardi 9 septembre 2003 Statut Membre Dernière intervention 15 août 2009 17
26 janv. 2005 à 18:29

Il n'y est pas écrit "unsigned integer is...", mais au travers des fonctions on comprends ce que c'est!

Mais si ça suffit pas: http://www.rwc.uc.edu/koehler/comath/13.html

google is your friend ;o)

scelw Messages postés 117 Date d'inscription mercredi 3 septembre 2003 Statut Membre Dernière intervention 17 février 2007
26 janv. 2005 à 17:55

j'ai imprimé toute la doc (en pdf) et j'ai tout lu!!
mais ils n'expliquent pas cette histoire d'ui (unsigned integer)... :(

ou alors j'ai lu trop vite... ?

malik7934 Messages postés 1154 Date d'inscription mardi 9 septembre 2003 Statut Membre Dernière intervention 15 août 2009 17
26 janv. 2005 à 10:14

ui veut dire Unsigned Integer... http://www.swox.com/gmp/#DOC

swox is your friend ;o)

scelw Messages postés 117 Date d'inscription mercredi 3 septembre 2003 Statut Membre Dernière intervention 17 février 2007
26 janv. 2005 à 10:08

Certaines fonctions de GMP ont un nom qui se termine par "ui" et d'autres pas. Que signifie "ui" ?

exemple : mpz_powm_ui, mpz_set_ui, mpz_set

malik7934 Messages postés 1154 Date d'inscription mardi 9 septembre 2003 Statut Membre Dernière intervention 15 août 2009 17
20 janv. 2005 à 14:36

Sincèrement, je ne sais pas répondre à tes questions, je ne connais pas NTL. Tout ce que je peux me dire, c'est que c'est un doctorant en cryptographie et sécurité qui m'a vanté les mérites de GMP.

Par contre tu trouveras un tas de réponses en t'inscrivant à http://swox.com/mailman/listinfo/gmp-discuss. Il s'agit du groupe de discussion de GMP et les réponses sont rapides et souvent bonnes ;o)

scelw Messages postés 117 Date d'inscription mercredi 3 septembre 2003 Statut Membre Dernière intervention 17 février 2007
20 janv. 2005 à 13:17

Salut,

Je fais une étude sur les nombres premiers et le test de primalité de Miller-Rabin.

Pour mes calculs sur ordinateur, j'utilise NTL (www.shoup.net/ntl/) mais il paraît que GMP donne de meilleurs résultats en terme de rapidité. J'ai lu votre article http://www-lmc.imag.fr/lmc-mosaic/Jean-Guillaume.Dumas/Enseignements/2003_ProjetCrypto_ENSIMAG/primalite-test/primalite-test.htm. Peut-être savez-vous si GMP est vraiment une meilleure librairie que NTL... Sauriez-vous également me dire combien de secondes prend la fonction mpz_probab_prime_p de GMP, si on lui passe, comme arguments, reps = 10 et n, un nombre premier d'un millier de chiffres ? Ceci me permettrait de comparer avec NTL (qui prend 48 secondes, sur un Athlon 1.8 Ghz, pour effectuer 10 itérations du test de Miller-Rabin, avec un nombre effectivement premier d'un millier de chiffres). Est-ce que 48 secondes vous semble être une performance satisfaisante?

Merci d'avance pour votre aide,

Cordialement,

ScelW

malik7934 Messages postés 1154 Date d'inscription mardi 9 septembre 2003 Statut Membre Dernière intervention 15 août 2009 17
22 sept. 2004 à 15:06

Ben si ça t'intéresse etque t'as du temps à perdre, vas voir http://www.cacr.math.uwaterloo.ca/hac/ ... c'est bourré d'infos et c'est gratuit!

coucou747 Messages postés 12303 Date d'inscription mardi 10 février 2004 Statut Membre Dernière intervention 30 juillet 2012 44
22 sept. 2004 à 14:58

je sais que c'ets pas le suel, masi c'ets le seul parmi les performatn dont je connaisse le fonctionnement, j'ai essayé les symétriques, mais j'ai pas réussi a comprendre...

malik7934 Messages postés 1154 Date d'inscription mardi 9 septembre 2003 Statut Membre Dernière intervention 15 août 2009 17
22 sept. 2004 à 07:31

Je sais plus si je t'avais répondu? Il sert à avoir des entiers gaussiens (des complexes donc) dont la norme est un nombre premier. Le but est de rendre difficile la décomposition en facteur premier. Imagine: n = p*q très grand (genre 1024 bits)... le casseur doit trouver la décomposition de n. Seule chance: trouver p ou q, il y a donc 2^1023 possibilités!

Encore un truc: RSA est très loin d'être le seul algo de crypto! Pour ma part, j'utilise Cornacchia pour des signatures indéniables...

coucou747 Messages postés 12303 Date d'inscription mardi 10 février 2004 Statut Membre Dernière intervention 30 juillet 2012 44
9 août 2004 à 13:07

crypto ? En RSA ? c'est le seul algorythme que je connaisse qui utilise des nombres premiers et je ne vois pas ce que cette équation peut faire dedans...
expliques vraiment a quoi sert ton code stp

Discussions similaires

Trouver le plus grand carré

algorithme d'hypercube

Algorithme de statistique

Algorithme PERT

Algorithme génétique

Votre réponse

Discussions similaires