BigInteger classe, quel algorithme utiliser?

Version imprimable

14/05/2009, 13h59
vierax

BigInteger classe, quel algorithme utiliser?

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?
15/05/2009, 15h29
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!
15/05/2009, 23h07
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 :roll:
16/05/2009, 01h23
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.
17/05/2009, 09h05
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^^
17/05/2009, 09h37
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
17/05/2009, 10h01
vierax

C'est exactement ce que je recherche xD !
Merci du lien Wakan ! Vraiment.

Par contre peut on utiliser une classe C# dans une classe vb.net?
Si non, faut que je continue ce que je fais.

Mais a priori il a les même méthodes de multiplication/addition que moi. et mis à part que je tente de faire des tableaux a taille pas fixe et qui change selon les calculs, et bien c'est tout pareil =D !
17/05/2009, 11h35
smyley

Citation:

Envoyé par vierax

Quand aux code je te le met lundi au vu de l'ironie criante que je sens dans le ton du message^^

non non c'était pas ironique, j'aime franchement voir les trucs que les gens trouvent vis à vis des opérations binaires, il y a des fois où on est vraiment surpris par le résultat :roll:

Citation:

Envoyé par vierax

C'est exactement ce que je recherche xD !
Merci du lien Wakan ! Vraiment.

Tient, le pire c'est que je connais cette classe, que j'y ai pensé, mais comme tu as dit savoir qu'il faut réutiliser mais vouloir faire ta propre classe je pensais que tu y étais déjà passé et que tu voulais absolument faire la tienne :aie:

Citation:

Envoyé par vierax

Par contre peut on utiliser une classe C# dans une classe vb.net?

Pas dans le même assembly. Par contre tu peux créer une bibliothèque de classes vb.net, mettre ta classe vb.net dedans, et rajouter cette dll comme référence à ta bibliothèque de classes (ou ton programme) en C#, et l'utiliser.
17/05/2009, 15h05
vierax

Citation:

Envoyé par smyley

non non c'était pas ironique, j'aime franchement voir les trucs que les gens trouvent vis à vis des opérations binaires, il y a des fois où on est vraiment surpris par le résultat

Autant pour moi tes smiley ':roll:' me trouble en fait !

Et mon projet est en vb.net pour moi donc, je n'ai que à fait une dll c'est bien ça?

J'aurai tôt fait d'implanter le mod vu qu'après j'aurai finit ma classe.
On verra!
17/05/2009, 15h10
smyley

Citation:

Envoyé par vierax

Autant pour moi

Au temps pour moi :aie:

Citation:

Envoyé par vierax

Et mon projet est en vb.net pour moi donc, je n'ai que à fait une dll c'est bien ça?

Bah s'il est en vb.net et que tu veux utiliser du C#, oui tu met le C# dans une dll et tu l'utilises en vb.net.
17/05/2009, 16h06
SpiceGuid

Citation:

Envoyé par vierax

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.

Pour ce qui est des algos tu devrais trouver ton bonheur sur dvp dans mon cours sur les grands nombres.
Le code est en Objective-Caml.
Pour les algos c'est avancé mais ça reste accessible (pas d'algèbre modulaire).
Si ça n'est pas assez clair tu as toujours :google: Michel Quercia (pour la division/modulo).

Bon pour calculer la ^65536 : 1journée 5h 59min 11s et 151ms

Donc je pense qu'il va falloir que j'optimise la chose!

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
For i As Integer = len To len - maxsize Step -1
            If longerBI.bigInt(i) <> 0 Then
                carry = 0
                For j As Integer = len To len - minsize Step -1
                    carry = CULng(longerBI.bigInt(i)) * CULng(shorterBI.bigInt(j)) + carry + BIResult.bigInt(j - Pos)
                    BIResult.bigInt(j - Pos) = carry And UInteger.MaxValue
                    carry >>= 32
                Next
            End If
            If carry > 0 Then
                BIResult.bigInt(shorterBI.sizeDefine - Pos) = carry
            End If
            Pos += 1
        Next

C'est le code de ma multiplication.
Les tableau longerBI et shorterBI Sont une classe avec deux choses :

Code:

1
2
Dim BigInt as UInt()
Dim sizeDefine as ULng

BigInt sont mes données recodées en uint
et sizeDefine sert à déterminé la longueur total du tableau définit (donc qui ont des valeurs)

20/05/2009, 01h33
smyley

Au fait, il faudrait peut être chercher un Profile pour tester le code. C'est pas toujours ce que l'on crois qui prend du temps.
20/05/2009, 09h06
vierax

Gnéééééëëëëëêêêê ???

J'avoue que là je ne comprends pas, qu'est ce que tu entends par chercher un Profile ?
20/05/2009, 11h51
nikoko34

Regarde par exemple le profiler ANTS de red gate (+ google et une ch'tite recherche sur ce forum). Y'a une version d'évaluation de 14 jours ce qui suffit à répondre à un besoin ponctuel.

Le but est d'étudier les performances de chaque méthode de ton projet (préalablement compilé en mode Debug) afin de voir ce qui peut être optimisé en terme de code.
20/05/2009, 12h37
smyley

Profiler pas Profile, c'était hier soir, j'étais fatigué, etc etc :aie:
Et en effet ANTS est très puissant mais payant, mais en cherchant ".NET Profiler" sur google on trouve quelques trucs.