```   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 --                                                                          --
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;
```