File : fz_modex.adb
1 ------------------------------------------------------------------------------
2 ------------------------------------------------------------------------------
3 -- This file is part of 'Finite Field Arithmetic', aka 'FFA'. --
4 -- --
5 -- (C) 2019 Stanislav Datskovskiy ( www.loper-os.org ) --
6 -- http://wot.deedbot.org/17215D118B7239507FAFED98B98228A001ABFFC7.html --
7 -- --
8 -- You do not have, nor can you ever acquire the right to use, copy or --
9 -- distribute this software ; Should you use this software for any purpose, --
10 -- or copy and distribute it to anyone or in any manner, you are breaking --
11 -- the laws of whatever soi-disant jurisdiction, and you promise to --
12 -- continue doing so for the indefinite future. In any case, please --
13 -- always : read and understand any software ; verify any PGP signatures --
14 -- that you use - for any purpose. --
15 -- --
16 -- See also http://trilema.com/2015/a-new-software-licensing-paradigm . --
17 ------------------------------------------------------------------------------
18 ------------------------------------------------------------------------------
19
20 with Words; use Words;
21 with W_Shifts; use W_Shifts;
22 with FZ_Basic; use FZ_Basic;
23 with FZ_Mul; use FZ_Mul;
24 with FZ_Sqr; use FZ_Sqr;
25 with FZ_Divis; use FZ_Divis;
26
27
28 package body FZ_ModEx is
29
30 -- (Conventional) Modular Multiply: Product := X*Y mod Modulus
31 procedure FZ_Mod_Mul(X : in FZ;
32 Y : in FZ;
33 Modulus : in FZ;
34 Product : out FZ) is
35
36 -- The wordness of all three operands is equal:
37 L : constant Indices := X'Length;
38
39 -- Double-width register for multiplication and modulus operations
40 XY : FZ(1 .. L * 2);
41
42 -- To refer to the lower and upper halves of the working register:
43 XY_Lo : FZ renames XY(1 .. L);
44 XY_Hi : FZ renames XY(L + 1 .. XY'Last);
45
46 begin
47
48 -- XY_Lo:XY_Hi := X * Y
49 FZ_Multiply_Buffered(X, Y, XY_Lo, XY_Hi);
50
51 -- Product := XY mod M
52 FZ_Mod(XY, Modulus, Product);
53
54 end FZ_Mod_Mul;
55
56
57 -- (Conventional) Modular Squaring: Product := X*X mod Modulus
58 procedure FZ_Mod_Sqr(X : in FZ;
59 Modulus : in FZ;
60 Product : out FZ) is
61
62 -- The wordness of both operands is equal:
63 L : constant Indices := X'Length;
64
65 -- Double-width register for squaring and modulus operations
66 XX : FZ(1 .. L * 2);
67
68 -- To refer to the lower and upper halves of the working register:
69 XX_Lo : FZ renames XX(1 .. L);
70 XX_Hi : FZ renames XX(L + 1 .. XX'Last);
71
72 begin
73
74 -- XX_Lo:XX_Hi := X^2
75 FZ_Square_Buffered(X, XX_Lo, XX_Hi);
76
77 -- Product := XX mod M
78 FZ_Mod(XX, Modulus, Product);
79
80 end FZ_Mod_Sqr;
81
82
83 -- (Barrettronic) Modular Squaring, using given Barrettoid
84 procedure FZ_Mod_Sqr_Barrett(X : in FZ;
85 Bar : in Barretoid;
86 Product : out FZ) is
87
88 -- The wordness of both operands is equal:
89 L : constant Indices := X'Length;
90
91 -- Double-width register for squaring and modulus operations
92 XX : FZ(1 .. L * 2);
93
94 -- To refer to the lower and upper halves of the working register:
95 XX_Lo : FZ renames XX(1 .. L);
96 XX_Hi : FZ renames XX(L + 1 .. XX'Last);
97
98 begin
99
100 -- XX_Lo:XX_Hi := X^2
101 FZ_Square_Buffered(X, XX_Lo, XX_Hi);
102
103 -- Product := XX mod M
104 FZ_Barrett_Reduce(X => XX, Bar => Bar, XReduced => Product);
105
106 end FZ_Mod_Sqr_Barrett;
107
108
109 -- Barrettronic Modular Exponent, using given Barrettoid
110 procedure FZ_Mod_Exp_Barrett(Base : in FZ;
111 Exponent : in FZ;
112 Bar : in Barretoid;
113 Result : out FZ) is
114
115 -- Double-width scratch buffer for the modular operations
116 D : FZ(1 .. Base'Length * 2);
117
118 -- Working register for the squaring; initially is copy of Base
119 B : FZ(Base'Range) := Base;
120
121 -- Register for the Mux operation
122 T : FZ(Result'Range);
123
124 -- Buffer register for the Result
125 R : FZ(Result'Range);
126
127 begin
128
129 -- Result := 1
130 WBool_To_FZ(1, R);
131
132 -- For each Word of the Exponent:
133 for i in Exponent'Range loop
134
135 declare
136
137 -- The current Word of the Exponent
138 Wi : Word := Exponent(i);
139
140 begin
141
142 -- For each bit of Wi:
143 for j in 1 .. Bitness loop
144
145 -- T := Result * B mod Modulus
146 FZ_Multiply_Unbuffered(X => R, Y => B, XY => D);
147 FZ_Barrett_Reduce(X => D, Bar => Bar, XReduced => T);
148
149 -- Sel is the current bit of Exponent;
150 -- When Sel=0 -> Result := Result;
151 -- When Sel=1 -> Result := T
152 FZ_Mux(X => R, Y => T, Result => R, Sel => Wi and 1);
153
154 -- Advance to the next bit of Wi (i.e. next bit of Exponent)
155 Wi := Shift_Right(Wi, 1);
156
157 -- B := B^2 mod Modulus
158 FZ_Square_Unbuffered(X => B, XX => D);
159 FZ_Barrett_Reduce(X => D, Bar => Bar, XReduced => B);
160
161 end loop;
162
163 end;
164
165 end loop;
166
167 -- Output the Result:
168 Result := R;
169
170 end FZ_Mod_Exp_Barrett;
171
172
173 -- (Barrettronic) Modular Exponent: Result := Base^Exponent mod Modulus
174 procedure FZ_Mod_Exp(Base : in FZ;
175 Exponent : in FZ;
176 Modulus : in FZ;
177 Result : out FZ) is
178
179 -- Space for Barrettoid
180 Bar : Barretoid(ZXMLength => Modulus'Length + 1,
181 BarretoidLength => 2 * Base'Length);
182
183 begin
184
185 -- First, pre-compute the Barretoid for the given Modulus:
186 FZ_Make_Barrettoid(Modulus => Modulus, Result => Bar);
187
188 -- Compute the modular exponentiation using the above Barrettoid:
189 FZ_Mod_Exp_Barrett(Base => Base,
190 Exponent => Exponent,
191 Bar => Bar,
192 Result => Result);
193
194 end FZ_Mod_Exp;
195
196 end FZ_ModEx;