```   1 ------------------------------------------------------------------------------
2 ------------------------------------------------------------------------------
3 -- This file is part of 'Finite Field Arithmetic', aka 'FFA'.               --
4 --                                                                          --
5 -- (C) 2017 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 FZ_Basic; use FZ_Basic;
21 with FZ_Pred;  use FZ_Pred;
22 with FZ_Shift; use FZ_Shift;
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    -- 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    -- 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    -- Modular Exponent: Result := Base^Exponent mod Modulus
84    procedure FZ_Mod_Exp(Base     : in  FZ;
85                         Exponent : in  FZ;
86                         Modulus  : in  FZ;
87                         Result   : out FZ) is
88
89       -- Working register for the squaring; initially is copy of Base
90       B : FZ(Base'Range)     := Base;
91
92       -- Copy of Exponent, for cycling through its bits
93       E : FZ(Exponent'Range) := Exponent;
94
95       -- Register for the Mux operation
96       T : FZ(Result'Range);
97
98       -- Buffer register for the Result
99       R : FZ(Result'Range);
100
101    begin
102       -- Result := 1
103       WBool_To_FZ(1, R);
104
105       -- For each bit of R width:
106       for i in 1 .. FZ_Bitness(R) loop
107
108          -- T := Result * B mod Modulus
109          FZ_Mod_Mul(X => R, Y => B, Modulus => Modulus, Product => T);
110
111          -- Sel is the current low bit of E;
112          --    When Sel=0 -> Result := Result;
113          --    When Sel=1 -> Result := T
114          FZ_Mux(X => R, Y => T, Result => R, Sel => FZ_OddP(E));
115
116          -- Advance to the next bit of E
117          FZ_ShiftRight(E, E, 1);
118
119          -- B := B^2 mod Modulus
120          FZ_Mod_Sqr(X => B, Modulus => Modulus, Product => B);
121
122       end loop;
123
124       -- Output the Result:
125       Result := R;
126
127    end FZ_Mod_Exp;
128
129 end FZ_ModEx;
```