Discussion :

[vierax]

Bonjour, aprés avoir trop cherché des information/tutos/classe pour le RSA avec 1024 bits, je fais ma propre classe big integer, je suis d'accords qu'il faut réutilisez ce qui as déjà était fait, c'est un principe. Mais j'aime bien plancher sur ce genre de problème en réalité.

Donc : pour l'instant je gére mes big integer en gros tableau de bits, je pense pas que ce soit le meilleur moyen mais ça marche pour le moment.
J'arrive à additionner et multiplier.
A l'aide de multiple multiplication j'arrive à calculer une puissance 32000 en /!\ 1min11s ! /!\ et une puissance 64000 en /!\ 4 min 48s /!\ (bon certes je ne peux guère vérifier le résultat car cela met plus de temps à l'écrire qu'a le calculer mais je pense que l'algorithme est bon).
J'obtient des tableaux de 21000 et quelques octets pour ^32000 et 42861 pour ^64000 (les chiffres viennent de tomber).
Bon certes les résultats ne sont pas trés malin car la valeur de départ est 0x29 donc pas trés gros.

Je vais lancer entre midi et deux une génération ^16000 avec un tableau de 128octets, nous verrons bien, je vous ferais suivre les résultats.

Néanmoins j'ai une question, je vais devoir me mettre sur le module, néanmoins je n'ai aucune idée de l'algo qu'il faudrait utiliser.
A part des tonnes de soustraction successive, je ne vois pas trop.
Si quelqu'un a une idée, ou une piste je suis preneur.

Merci d'avance.


Edit : Il apparait clairement que tout n'est pas du tout optimiser, a mon retour a 14h, il n'avait pas finit le traitement de mon tableau de byte ^16000, je pense que cela vient du fait que j'utilise justement un tableau de byte.
De votre avis, serait il possible d'utiliser un tableau d'entier non signé, de partir d'un tableau de byte, de convertir ce tableau de byte en tableau d'entier non signé UINT donc, de faire les opérations dessus et enfint de remettre le tableau correctement?

[vierax]

Bon alors trés net progression, voici les résultats tout frais.

Alors ma première démarche comme je l'ai expliqué ci dessus fut de partir de tableau de Byte et de faire les calculs qui m'intéressait (à savoir : addition, multiplication, mod). J'ai réussit à le faire mais je trouvais les temps trop long.

Je suis donc passé sur des tableau de UInt, qui eux gére 4Byte d'un coup. J'ai recoder les algos pour les adapter à cette classe en optimisant la chose, tout en faisant les optimisation sur les tableaux de Byte pour pouvoir uen comparaison. Et il n'y a pas photo, les résultats sont flagrants.

Pour des opérations sur des données de 128Bytes :

pour 100.000 additions :
En UInt : 45ms
En Byte : 5s 43ms

pour 100.000 multiplications :
En UInt : 2s 51ms
En Byte : 22s 12ms

Néanmoins il apparait clairement que plus la taille du tableau augmente, plus les temps de calcul sont long, explication :
Les test ci dessus ont été fait pour des taille de tableau de UInt de 70, les mêmes tests avec cette fois une table de tableau de 10000000 montre un temps de 2min 55s 25ms. La différence est donc énorme. Cependant je suis obligé d'avoir cette valeur pour faire a^e pour mon cryptage.

Je lance un puissance 65535 ce week end, on verra ça lundi pour le résultat!

[smyley]

Tu sais, il y a un forum Algorithmes. Ils ne vont surement pas t'aider pour le C#, mais en général ils aiment bien tout ce qui est calcul et algo ...

Sinon je serai curieux de voir ton code pour le fun

[tomlev]

Avec des ulong (64 bits) ce serait mieux qu'avec des uint (32 bits)... d'autant plus que la plupart des processeurs actuels ont une archi 64 bits

Et comme dit smyley, c'est plutôt une question d'algorithmique que de C#, donc tu aurais plus de réponses utiles sur le forum algo.

[vierax]

J'explique mon choix des uint :
lors des opérations on a souvent une retenue.
Donc quand je fais une opération je stock les variables dans un Ulong.
Pour la valeur que je suis en train de calculer je lui apose un masque &hFFFFFFFF
et pour la retenue je la décale de 32bit

Je ne savais pas qu'il y avais un forum algorithme.
Quand aux code je te le met lundi au vu de l'ironie criante que je sens dans le ton du message^^

[wakan]

Bonjour,
Du point de vue algorithmique le fait de refaire cette classe est un excellent exercice.
Cependant, je penses que tu devrais utiliser ce qui est déjà fait.
Meme si tu le fais toi va jeter un coup d'oeil ca te permttra de partir du bon pied.
http://www.codeproject.com/KB/cs/biginteger.aspx
J'espère que ca aura pu d'aider.
A bientôt