-
Notifications
You must be signed in to change notification settings - Fork 2
/
CorpsModulaire.wdc
312 lines (276 loc) · 9.78 KB
/
CorpsModulaire.wdc
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
#To edit and compare internal_properties, use WINDEV integrated tools.
#Internal properties refer to the properties of controls in windows, reports, etc.
info :
name : CorpsModulaire
major_version : 26
minor_version : 0
type : 4
description : ""
subtype : 0
class :
identifier : 0x1b3a8e5132bf57e3
internal_properties : BgAAAAYAAAB2/vstTMCJbS/hlxjFxirSqKvCUuv8YxgpWyl7S3iA
code_elements :
type_code : 10
p_codes :
-
code : |1+
// gestion des opérateur dans le corps des entiers (256 bits) modulo P avec P premier
CorpsModulaire est une Classe
// modulo principal utilisé pour Z/PZ. doit doit être premier
// ex : "0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEFFFFFC2F"
P est Entier256
// c = 2n −p : pour L’algorithme basé sur la retenue sortante d’Omura
DeuxPuissance256MoinsP est entier256
// P - 2 : pour inverse modulaire par algorithme d'Euleur
PMoins2 est Entier256
FIN
type : 131072
procedures :
-
name : Constructeur
procedure_id : 1962037067068233699
type_code : 27
code : |1+
PROCEDURE Constructeur( valeurHexa chaine )
// Init P, modulo principal
p.affecteAvecChaineHexa( valeurHexa )
// Init constantes en fonction de P
MaxInt256 est entier256("0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF")
// 2^256-P-1 :
:DeuxPuissance256MoinsP = soustraction (MaxInt256, P )
:DeuxPuissance256MoinsP = additionAvecUn( :DeuxPuissance256MoinsP )
// P-2 :
deux est Entier256(2)
:PMoins2 = soustraction (P, deux )
type : 589824
-
name : Destructeur
procedure_id : 1962037067068299235
type_code : 28
code : |1+
PROCEDURE Destructeur()
type : 655360
-
name : additionModulo
procedure_id : 1962037479385255214
type_code : 12
group : 1
code : |1+
// renvoie A + B ( mod P )
Procédure additionModulo( nombreA entier256, nombreB entier256) : Entier256
// S = A + B
retenue est un booléen
resultat est Entier256 = addition(nombreA,nombreB, retenue)
SI retenue ALORS
// ajout le résultat du modulo pour 2^256
resultat = addition( resultat,DeuxPuissance256MoinsP)
FIN
si resultat.estSupérieurOuEgalA(P) ALORS
renvoyer soustraction(resultat, P)
FIN
renvoyer resultat
type : 458752
-
name : négationModulo
procedure_id : 1962039966171440705
type_code : 12
code : |1+
// renvoie B = -A (mod P), cad tel que A +B = 0 (mod P)
PROCÉDURE négationModulo( nombre entier256 ) : entier256
dbgAssertion(P.estSupérieurOuEgalA(nombre))
RENVOYER soustraction ( P, nombre )
//RENVOYER additionModulo ( P, negation(nombre))
type : 458752
-
name : soustractionModulo
procedure_id : 1964419115212207273
type_code : 12
code : |1+
// renvoie A - B ( mod P )
Procédure soustractionModulo( nombreA Entier256, nombreB Entier256) : Entier256
si nombreA.estSupérieurOuEgalA( nombreB ) ALORS
renvoyer soustraction(nombreA,nombreB)
sinon
moinsR est Entier256 = soustraction ( nombreB, nombreA )
renvoyer négationModulo( moinsR )
fin
type : 458752
-
name : multiplicationModulo_DEBUG
procedure_id : 1962047327745723262
type_code : 12
group : 1
code : |1-
// renvoie A * B ( mod P )
// version lente pour test en debug
procédure multiplicationModulo_DEBUG( nombreA entier256, nombreB entier256) : Entier256
resultat est un entier256
zero est un entier256 //TEST
pour i = 255 a 0 pas -1
// r = r * 2
si pas resultat.estEgalAZero() alors
resultat = multiplicationPar2Modulo(resultat)
fin
// r = r + A
si nombreB.bit( i ) alors
resultat = additionModulo(resultat, nombreA )
sinon
resultat = additionModulo(resultat, zero )
FIN
FIN
renvoyer resultat
type : 458752
-
name : multiplicationModulo
procedure_id : 1962192921991122669
type_code : 12
group : 1
code : |1+
// renvoie A * B ( mod P )
procédure abstraite multiplicationModulo( nombreA entier256, nombreB entier256) : Entier256
type : 458752
-
name : carréModulo
procedure_id : 1964406591087343535
type_code : 12
group : 1
code : |1+
procédure carréModulo( nombre est Entier256 ) : entier256
renvoyer multiplicationModulo(nombre,nombre)
type : 458752
-
name : cubeModulo
procedure_id : 1964412170249914761
type_code : 12
code : |1+
Procédure cubeModulo( nombre est Entier256 ) : entier256
RENVOYER multiplicationModulo( multiplicationModulo(nombre,nombre), nombre)
type : 458752
-
name : multiplicationPar2Modulo
procedure_id : 1962194124583490858
type_code : 12
code : |1+
// renvoie A * 2 ( mod P )
// =>décalage de bits
procédure multiplicationPar2Modulo( nombreA entier256) : Entier256
// OPTIM: version ASM
resultat2 est un entier256 = nombreA
API(arithmetique.addrprocAddition256p256_256c, &resultat2, &resultat2 )
//dépassement est un booléen = (nombreA.val3 & 0x8000000000000000) <> 0
SI (nombreA.val3 & 0x8000000000000000) ALORS
// ajout le résultat du modulo pour 2^256
resultat2 = additionModulo( resultat2,DeuxPuissance256MoinsP)
FIN
SI resultat2.estSupérieurOuEgalA( P ) ALORS
resultat2 = soustraction(resultat2, P )
FIN
renvoyer resultat2
type : 458752
-
name : MultiplicationPar3Modulo
procedure_id : 1964419553298908132
type_code : 12
code : |1+
Procédure MultiplicationPar3Modulo( nombre Entier256 ) : entier256
renvoyer additionModulo( multiplicationPar2Modulo(nombre), nombre)
type : 458752
-
name : multiplicationPar4Modulo
procedure_id : 2166246092384922583
type_code : 12
code : |1+
procédure multiplicationPar4Modulo( nombre Entier256 ) : entier256
//@A optimiser
RENVOYER multiplicationPar2Modulo( multiplicationPar2Modulo(nombre) )
type : 458752
-
name : multiplicationPar8Modulo
procedure_id : 2166340036236684091
type_code : 12
code : |1-
PROCÉDURE multiplicationPar8Modulo( nombre Entier256 ) : Entier256
//@A optimiser
RENVOYER multiplicationPar2Modulo( multiplicationPar4Modulo( nombre) )
type : 458752
-
name : puissanceModulo
procedure_id : 1964422602725873770
type_code : 12
code : |1+
// envoie A^B (mod p)
procédure puissanceModulo( nombreA entier256, nombreB entier256) : Entier256
pow2 est Entier256 = nombreA
résultat est Entier256(1)
pour i = 0 a 255
si nombreB.bit(i) alors
résultat = multiplicationModulo( résultat, pow2 )
FIN
pow2 = carréModulo(pow2)
FIN
renvoyer résultat
type : 458752
-
name : inverseModulo
procedure_id : 1964420450947150377
type_code : 12
code : |1+
// renvoie l'inverse modulaire d'un nombre A.
// cas un nombre I tel que A * I = 1 (mod P)
Procédure virtuelle inverseModulo( nombre entier256 ) : entier256
inverseMod est Entier256
// test division par 0
si nombre.estEgalAZero() ALORS
dbgAssertion(faux)
renvoyer inverseMod
FIN
// calcul "rapide" par une version optimisée de l'algorithme d'Eurclide étendu.
inverseMod = inverseModulaire_HGCD256( P, nombre )
// si echec
si inverseMod.estEgalAZero() ALORS
// calcul par le théorème d’Euler :
// inverse(A) = A ^ (P-2)
inverseMod = puissanceModulo( nombre, PMoins2 )
sinon
//gère le cas ou l'on obtient P-X au lieu de X
_valTest est Entier256 = multiplicationModulo( nombre, inverseMod )
SI pas _valTest.estEgalA1() ALORS
inverseMod = négationModulo( inverseMod ) // soustraction( inverseDex, gCorps.P )
_valTest = multiplicationModulo( nombre, inverseMod )
SI pas _valTest.estEgalA1() ALORS
// Pb
dbgAssertion(faux,"nombre*inverseMod <>1."+rc+"nombre = "+nombre.VersChaineHexa()+rc+inverseMod.VersChaineHexa() )
// calcul par le théorème d’Euler :
// inverse(A) = A ^ (P-2)
inverseMod = puissanceModulo( nombre, PMoins2 )
FIN
FIN
fin
//@TEST en debug on vérifie qu'on a bien trouvé l'inverse modulaire
si pas gbModeBench _et_ EnModeTest()
DBG_1 est Entier256 = multiplicationModulo( inverseMod, nombre )
dbgAssertion( DBG_1.estEgalA1(), nombre.VersChaineHexa() + rc + inverseMod.VersChaineHexa() + rc + DBG_1.VersChaineHexa() )
fin
renvoyer inverseMod
type : 458752
-
name : divisionModulo
procedure_id : 1964420506781804621
type_code : 12
code : |1+
// renvoie A / B (mod P), cas un nombre C tel que C*B = A (mod P)
Procédure divisionModulo( nombreA entier256, nombreB entier256 ) : Entier256
renvoyer multiplicationModulo( nombreA, inverseModulo(nombreB))
type : 458752
procedure_templates : []
property_templates : []
code_parameters :
internal_properties : BgAAAAYAAAA6ih3UbgNXHwTtiPSFUEj+2fi/m7v4QV2rqidAupM=
original_name : Classe1
resources :
string_res :
identifier : 0x1b3a8e2532bcacde
internal_properties : BgAAAAYAAAAnMYFQ1bL/vz9ehh7L22SNNSlIzGTOI8h5F/WtgDNP
custom_note :
internal_properties : BgAAAAYAAABtB9HWVzrXO2+4NDRVK0vmzaNKrCKqH1DBX30lMmGZ