```   1 ------------------------------------------------------------------------------
2 ------------------------------------------------------------------------------
3 -- This file is part of 'Finite Field Arithmetic', aka 'FFA'.               --
4 --                                                                          --
5 -- (C) 2018 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 with FZ_Barr;  use FZ_Barr;
27
28
29 package body FZ_ModEx is
30
31    -- (Conventional) Modular Multiply: Product := X*Y mod Modulus
32    procedure FZ_Mod_Mul(X        : in  FZ;
33                         Y        : in  FZ;
34                         Modulus  : in  FZ;
35                         Product  : out FZ) is
36
37       -- The wordness of all three operands is equal:
38       L     : constant Indices := X'Length;
39
40       -- Double-width register for multiplication and modulus operations
41       XY    : FZ(1 .. L * 2);
42
43       -- To refer to the lower and upper halves of the working register:
44       XY_Lo : FZ renames XY(1     .. L);
45       XY_Hi : FZ renames XY(L + 1 .. XY'Last);
46
47    begin
48
49       -- XY_Lo:XY_Hi := X * Y
50       FZ_Multiply_Buffered(X, Y, XY_Lo, XY_Hi);
51
52       -- Product := XY mod M
53       FZ_Mod(XY, Modulus, Product);
54
55    end FZ_Mod_Mul;
56
57
58    -- (Conventional) Modular Squaring: Product := X*X mod Modulus
59    procedure FZ_Mod_Sqr(X        : in  FZ;
60                         Modulus  : in  FZ;
61                         Product  : out FZ) is
62
63       -- The wordness of both operands is equal:
64       L     : constant Indices := X'Length;
65
66       -- Double-width register for squaring and modulus operations
67       XX    : FZ(1 .. L * 2);
68
69       -- To refer to the lower and upper halves of the working register:
70       XX_Lo : FZ renames XX(1     .. L);
71       XX_Hi : FZ renames XX(L + 1 .. XX'Last);
72
73    begin
74
75       -- XX_Lo:XX_Hi := X^2
76       FZ_Square_Buffered(X, XX_Lo, XX_Hi);
77
78       -- Product := XX mod M
79       FZ_Mod(XX, Modulus, Product);
80
81    end FZ_Mod_Sqr;
82
83
84    -- (Barrettronic) Modular Exponent: Result := Base^Exponent mod Modulus
85    procedure FZ_Mod_Exp(Base     : in  FZ;
86                         Exponent : in  FZ;
87                         Modulus  : in  FZ;
88                         Result   : out FZ) is
89
90       -- Double-width scratch buffer for the modular operations
91       D   : FZ(1 .. Base'Length * 2);
92
93       -- Working register for the squaring; initially is copy of Base
94       B   : FZ(Base'Range) := Base;
95
96       -- Register for the Mux operation
97       T   : FZ(Result'Range);
98
99       -- Buffer register for the Result
100       R   : FZ(Result'Range);
101
102       -- Space for Barrettoid
103       Bar : Barretoid(ZXMLength       => Modulus'Length + 1,
104                       BarretoidLength => 2 * B'Length);
105
106    begin
107
108       -- First, pre-compute the Barretoid for the given Modulus:
109       FZ_Make_Barrettoid(Modulus => Modulus, Result => Bar);
110
111       -- Result := 1
112       WBool_To_FZ(1, R);
113
114       -- For each Word of the Exponent:
115       for i in Exponent'Range loop
116
117          declare
118
119             -- The current Word of the Exponent
120             Wi : Word := Exponent(i);
121
122          begin
123
124             -- For each bit of Wi:
125             for j in 1 .. Bitness loop
126
127                -- T := Result * B mod Modulus
128                FZ_Multiply_Unbuffered(X => R, Y => B, XY => D);
129                FZ_Barrett_Reduce(X => D, Bar => Bar, XReduced => T);
130
131                -- Sel is the current bit of Exponent;
132                --    When Sel=0 -> Result := Result;
133                --    When Sel=1 -> Result := T
134                FZ_Mux(X => R, Y => T, Result => R, Sel => Wi and 1);
135
136                -- Advance to the next bit of Wi (i.e. next bit of Exponent)
137                Wi := Shift_Right(Wi, 1);
138
139                -- B := B^2 mod Modulus
140                FZ_Square_Unbuffered(X => B, XX => D);
141                FZ_Barrett_Reduce(X => D, Bar => Bar, XReduced => B);
142
143             end loop;
144
145          end;
146
147       end loop;
148
149       -- Output the Result:
150       Result := R;
151
152    end FZ_Mod_Exp;
153
154 end FZ_ModEx;
```