Discussion :

[vierax]

Bonjour, pour un projet de cryptographie, je dois faire l'implémentation de la, trés traditionelle, formule
m^e mod n.

J'ai fait un algorithme d'addition et de multiplication, et je m'attéle maintenant au modulo.
Grâce à un sujet sur ce forum, j'ai pu mettre un nom sur un algortihme que j'avais trouvé à savoir Mephistopheles(je crois) :
a*b mod n = ((a mod n) * (b mod n)) mod n

j'aurai voulu avoir confirmation que j'ai bien le droit de faire:
a^4*4 = ((a^4 mod n)^2) mod n

Sinon pourrais t on me renseigner sur les algorithme de division et de modulo de trés grand nombre, à savoir que dans mon cas :
le message fais 128 octets, mon exponent 8 octets et mon modulus 128 octets.
J'ai déjà crée une classe big int cchargé de transférer mon message et modulus dans des tableau de UInt, pour faire des calculs, et il marche bien pour la multiplication et l'addition (même si je pense je pourrais encore l'optimiser) mais pour la division/mod je ne vois pas comment m'y prendre.

Est-ce faisable? Si oui, quels algorithme permettent de le faire ?
Pour la multiplication j'ai suivit une démarche assez basique, y'a t il des algorithme qui permettent de l'optimiser? (pour l'instant je fais 100000 multiplication en 2s mais je pense que je pourrais faire mieux encore)

[Zavonen]

Grâce à un sujet sur ce forum, j'ai pu mettre un nom sur un algortihme que j'avais trouvé à savoir Mephistopheles(je crois) :
a*b mod n = ((a mod n) * (b mod n)) mod n

Il ne s'agit pas ici d'algo mais d'une identité algébrique (VRAIE).

a^4*4 = ((a^4 mod n)^2) mod n

Non !
a^4*4 (mod n) = ((a^4) mod n)^4) mod n

[vierax]

Au temps pour moi je me suis trompé dans ma formule

j'entendais :

a^(4+4) mod n = (a^4 mod n * a^4 mod n) mod n

Et merci de la précision pour l'identité algébrique/algo

[vierax]

Bon j'ai beau tourner le probleme dans ma tête je n'arrive pas à trouver une solution convenable...

Voilà mon probleme.
J'ai un tableau de UInt pouvant contenir autant d'octets qu'il veux.
Je dois calcul m^e mod n
j'ai pensé à calcul cela de cette maniere :

( (m^2i mod n) * (m^2j mod n) * .. * (m^2l mod n) * m^(e - (2i +2j +.. +2l)) ) mod n
on aurait donc : (e - (2i + 2j +.. +2l)) = 0 ou 1 suivant si e est pair ou impair.
Ensuite on divise chacun des m ^ 2p mod n
en ((m^2q mod n) * (m^2r mod n) ... ) mod n .. ect ect pour avoir des calculs simplifié à la fin.

Déjà est ce que cela est une bonne piste ou non?

Mon vrai problème réside dans le mod n :
Sachant que j'ai un tableau d'UInt je ne vois pas trop comment m'y prendre pour le diviser par n car lui aussi est un tableau d'UInt de 128 octets.
Je pensais le faire de telle manière mais ne suis pas sûr du tout :


calcul M mod N

SI M < N ALORS return M
SINON

JUSQUA M traité entiérement

prendre dans M la taille de N. (en tableaux d'UINT toujours)
SI M' < N alors

M'(last +1) = M(N'Size + 1) &hFF000000 (pour ajouter seulement 1 octets supplémentaire)

FINSI
Val = N
POUR i = 2 A I = 9 PAS 1

Buff = N * i
SI M' > Buff ALORS

Val = Buff

SINON

i = 10 (sortir de la boucle)

FINSI

FIN POUR
Result(Pos) = VAL
Pos += 1

FIN JUSQUA

FINSI



Cet algo est tout brouillon, voir même faux, car je n'arrive pas à me le mettre au clair moi même.
Si quelqu'un aurait une idée j'aimerai bien la recevoir. Merci d'avance.

[Zavonen]

Voici l'algo.
Tu peux élever des nmbres de l'ordre de 1000000000 à la pussance 1000000000
modulo .... sans utiliser aucun tableau en une fraction de seconde.

Code Python :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
# calcul de N**M  modulo p
 
def modpower(N,M,p):
    r=1 # puissance initialisee a 1
    for i in range(0,M): #pour i allant de 0 à M-1
        x=N%p  #prendre le modulo de N
        r=(r*x)%p #le multiplier par la puissance precedente et prendre le reste
    return r #retourner la puissance modulo
 
print modpower(2009,1000000,5)

[vierax]

Je sais déjà cela, mais cela ne marche pas dans mon cas:
Mes valeurs sont codés sur 128OCTETS, donc pas géré par l'OS !!!

J'ai donc crée une classe BigInt qui prends nimporte quelle tableau d'octets qu'on lui donne et la recode pour s'adapter ce qui donne un tableau de UInt de taille dépendant de ce qu'on lui as donné.
Ex : je lui donne un tableau de 128 octets, il me resort un tableau de 32 UInt.
Je lui envoit dans un tableau { FF, BC, 32, 29, 29, BE, BE }
il va l'interpréter et créer un tableau de 2 UInt :
{ FFBC32, 2929BEBE } donc { 16759858, 690601662 } et faire ses opérations dessus. La multiplication et l'addition marche déjà, si vous le souhaitez je peux poster mes fonctions afin que vous vous fassiez une idée de leur fonctionnement, et me dire si je peux encore les optimisez ou non.

Mais pour le modPow (puissance modulo) je ne vois pas trop comment faire. J'ai un algorithme sur papier mais il est trés brouillon, je peux également tenté de le retranscrire pour que vous vous fassiez uen idée de ma démarche.

[pseudocode]

La multiplication et l'addition marche déjà, si vous le souhaitez je peux poster mes fonctions afin que vous vous fassiez une idée de leur fonctionnement, et me dire si je peux encore les optimisez ou non.

Mais pour le modPow (puissance modulo) je ne vois pas trop comment faire. J'ai un algorithme sur papier mais il est trés brouillon, je peux également tenté de le retranscrire pour que vous vous fassiez uen idée de ma démarche.

Tu devrais ecrire l'algo de division entiere (quotient + reste). Ca te permettra de coder la fonction modulo et ainsi tu pourras appliquer l'algo de Zavonen

[vierax]

Voici ou j'en suis arrivé avec mes algo :
Pour le mod Pow :

SI BIExpo = 0 then return 1
SI BIExpo = 1 then return BIValue

Sinon

BIValue, BIExpo, BIMod As BigInt
pow, powTmp as ULong = 1
BIResult As BigInt = 1
BITmp As BigInt

BITmp = BIValue * BIValue
powTmp = 2

TANT QUE BIExpo - pow > 1 FAIRE

TANT QUE pow + 2*powTmp <= BIExpo FAIRE

BITmp = BITmp * BITmp
BITmp = BITmp mod BIMod
powTmp = powTmp *2

FIN TANT QUE
BIResult = BIResult * BITmp
BIResult = BIResult mod BIMod
pow = pow + powTmp
BITmp = BIValue
powTmp = 1

FIN TANT QUE
SI BIExpo - pow = 1 FAIRE
BIResult = BIResult * BIValue
BIResult = BIResult mod BIMod

Return BIResult[/INDENT]


Voila ce que donne mon algo pour le modPow, cela a un nom?

Sinon pour la divison entiére, c'est là que j'ai mon problème, je ne vois pas du tout comment faire, mis à part le fait de prendre des valeurs consécutifs dans mon Dividende
faire une itération de 1 a 9 pour teste Diviseur * it < Dividende.
Et ainsi calculer le résultat.
Mais ceci est, je pense, beaucoup trop lourd niveau machine. Et je n'arrive pas à trouver quelques choses de correct.

[Zavonen]

Le sujet de la division des 'bignums' a été abordé sur ce forum:
http://www.developpez.net/forums/d55...grands+entiers

[vierax]

N'étant pas du tout familiarisé avec le langage CAML, je ne comprends rien du programme mis en place. :s !
Sinon auriez vous d'autre piste, cela m'aiderait grandement. Je suis en train d'implémenter une division scolaire, c'est à dire que j'ai mon dividende et diviseur et je cherche les valeurs une par une pour trouver la valeur final du quotien, plutot long :s

[FR119492]

Salut!
Une solution différente pourrait être envisagée si tu ne cherches pas une grande vitesse d'exécution: tu écris tes nombres non pas comme des nombres, mais comme des chaînes de caractères et tu programmes les opérations arithmétiques exactement comme tu as appris à les effectuer avec un crayon et du papier lorsque tu étais à l'école primaire.
Jean-Marc Blanc

[vierax]

Le problème est qu'il me faudrait quand même une vitesse d'éxécution correct. La méthode que tu m'indique correspond a la premiere que j'ai fait avec une chaine d'octet (si l'on suppose qu'un char est codé sur deux octets !) or celle ci était beaucoup trop lente pour les même algos avec ma nouvelle méthode :
pour 100 000 multiplication de deux nombre de 128 octets :
avec la nouvelle méthode : 2s
avec l'ancienne (celle que tu dit) : +20s

Donc, pas du tout interessant.
Également, je suis en train déjà en train d'essayer de faire la méthode de la division que l'on apprend en primaire avec ma classe ! Mais cela ne parait pas évident, même pas du tout :s

[Zavonen]

Je suppose que tu disposes déjà de 4 méthodes:

• l'addition
• la soustraction
• la multiplication par les puissances de la base (cela suffit)
• la comparaison <=

Avec tout cela tu peux faire une division assez vite.
Tu travailles dans une certaine base b (2 ou 10 ou autre).
Les puissances successives de cette base ne nécessitent aucun calcul.
Divisons m par n.
si m<n terminé.
Sinon:
initialiser q avec 0
'calculer' b^p tant que b^p*n <= m (aucun calcul réel)
On trouve une valeur maximale de p
faire m=m-b^p*n et q=q+b^p
et recommencer jusqu'à ce que m<n.
Peut-on faire plus simple ?

[vierax]

J'ai un bout d'algo que voici :

Ma base : UInt donc : 4294967295
Deux tableaux X et Y, X est divisé par Y

X = x0, x1, .., xn
Y = y0, y1, .., ym

SI x<y ALORS quotient = 0, reste = 1
SINONSI x=y ALORS quotient = 1, rest = 0
SINON

TANT QUE traitement pas finit FAIRE

tmp = 0 || x(n-lenTraité-m .. n-lenTraité) + tmp
SI tmp = y ALORS quotient(i) = 1, tmp = 0
SINONSI tmp<y alors tmp(0) = x(n - lenTraité - m - 1)
FINSI
/!\RECHERCHE DICHOTOMIQUE/!\
On Trouve quotientTmp tel que Y > tmp - (quotientTmp * Y) > 0
/!\FIN RECHERCHE DICHOTOMIQUE/!\
tmp = tmp - (quotientTmp * Y)
Quotient(i) = quotientTmp

FINTANTQUE

FINSI

On a donc à la fin le reste et le quotient correspondant.
La méthode est la méthode par potence, appris en primaire. L'algo n'est pas forcément juste ici mais il permet de se donner une idée de ce que je fais.
Explication :
Si X > Y
Alors on prends dans X la taille de Y (en commençant par le début)
puis on trouve un quotient qui multiplié par Y est supérieur à cette valeur.
on la soustrait et on obtient un reste.
A ce reste on ajoute la valeur suivante dans X donc la taille de Y + 1
Et ainsi de suite.

Ainsi j'obtient un quotient et un reste correcte, logiquement...



@Zagoven :
Je ne comprends pas trés bien l'algo que tu m'as mis.

'calculer' b^p tant que b^p*n <= m (aucun calcul réel)

Ici tu fais l'équivalent de ma recherche Dichotomique c'est ça ?

[Zavonen]

SI x<y ALORS quotient = 0, reste = 1

non, reste=x

Ici tu fais l'équivalent de ma recherche Dichotomique c'est ça ?

oui, la recherche dichotomique est mieux

[vierax]

D'ac ! Et bien je vais voir à implémenter ça alors même si la partie :
"calculer' b^p tant que b^p*n <= m (aucun calcul réel) "

reste obscure pour moi.

[Zavonen]

"calculer' b^p tant que b^p*n <= m (aucun calcul réel) "

Tu ne fais rien que rajouter des zéros derrière n.
Un puis deux,etc .... jusqu'à dépasser m, on s'arrête juste avant.

[vierax]

Tu ne fais rien que rajouter des zéros derrière n.

Rectification : En base 10 tu ne rajoute que des 0 ^^


Si j'ai bien compris voilà ce que donne ta méthode :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
 
//division de m par n dans une base b
//condition m > n
//sinon si m = n : rest = 0, quot = 1
//sinon si m < n : rest = m, quot = 0
 
rest = m
TANTQUE rest > n FAIRE
    puisTmp = 0
    TANTQUE ((b^puisTmp) * n) < rest FAIRE
        puis = puisTmp
        puisTmp ++
    FIN TANTQUE
    rest = rest - ((b^puis) * n)
    quot = quot + b^puis
FIN TANTQUE

C'est bien cela?
Je viens de la coder là, et je pense avoir fait une erreur quelques part car le calcul est beaucoup trop long.

Merci de ta précieuse aide qui m'a permit de voir la division autrement !
Cet algorithme a t il un nom que je pourrais mettre dans mon rapport ? (j'avais l'algorithme de potence, qui est celui que l'on apprend en primaire, mais beaucoup trop long a mettre en place et pas du tout optimisé je pense, le tien est niquel). Cependant avec lui la recherche dichotomique ne marche pas, car celle ci ne peux fonctionner que lorsque l'ont a une valeur comprise entre deux valeur définit.

[Zavonen]

Rectification : En base 10 tu ne rajoute que des 0 ^^

Non, quelle que soit la base.
En base 2 quand tu multiplies par 2 tu ajoutes un zéro, par 4 tu en ajoutes 2, etc...

C'est bien cela?

Parfaitement !

Cependant avec lui la recherche dichotomique ne marche pas, car celle ci ne peux fonctionner que lorsque l'ont a une valeur comprise entre deux valeur définit.

Exact! mais tu peux avoir une borne supérieure en comparant les longueurs du dividande et du diviseur.

Cet algorithme a t il un nom que je pourrais mettre dans mon rapport ?

Pas que je sache mais si tu y regardes de plus près tu verras qu'il s'agit d'une variante de la division 'scolaire'. Simplement à l'école tu cherches combien de fois il va 2120 dans 5748, tu trouves 2. Là tu trouves 1 puis tu retranches 2120 et tu trouves une fois encore 1.
En fait tu ne fais jamais de divisions (même modestes), et pour ce qui est des multiplications tu ne fais que des décalages (donc pas des 'vraies' multiplication. Ton algo est donc une suite de décalages, comparaisons, soustractions.

Je viens de la coder là, et je pense avoir fait une erreur quelques part car le calcul est beaucoup trop long.

Encore un petit effort tu es au bout du chemin.

[vierax]

Bon je pense avoir trouvé d'ou vient l'erreur :

Lorsqu'il arrive au moment ou
b*n (donc b^1 * n) < rest
il boucle sur rest - n et si rest = 1000 * n alors il va le faire 100 fois.
Donc j'ai changé et désormais je vais faire comme cela :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
 
TANTQUE rest > m FAIRE
   SI b*n >= rest ALORS
Faire l'algo présenté au dessus
    SINON
        min = 0, max = Uint.MaxValue
        TANTQUE tmp <> n ou max > min FAIRE
            cur = min + ((max - min) \ 2)
            tmp = n * cur
            SI tmp > n ALORS
                max = cur
            SINONSI tmp < n ALORS
                min = cur
            FINSI
        FIN TANTQUE
        tmp = n*cur
        rest = rest - tmp
        quot = quot + cur
    FINSI
FINFAIRE

j'espère que cette fosi ça va marcher !!! Je croise les doigts