File : fz_modex.adb
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 -- --
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 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;