-
+ 3236467E5470CA5B3B1384473445491EE52C0151D36A450CA1B9E496A9FE53A5AFE490B065FCDDD7A6E7DC6BBBDD902643B7C3BC4CFE5984F84E69AE5D8A7B2Effa/libffa/fz_modex.adb(0 . 0)(1 . 109)
57 ------------------------------------------------------------------------------
58 ------------------------------------------------------------------------------
59 -- This file is part of 'Finite Field Arithmetic', aka 'FFA'. --
60 -- --
61 -- (C) 2017 Stanislav Datskovskiy ( www.loper-os.org ) --
62 -- http://wot.deedbot.org/17215D118B7239507FAFED98B98228A001ABFFC7.html --
63 -- --
64 -- You do not have, nor can you ever acquire the right to use, copy or --
65 -- distribute this software ; Should you use this software for any purpose, --
66 -- or copy and distribute it to anyone or in any manner, you are breaking --
67 -- the laws of whatever soi-disant jurisdiction, and you promise to --
68 -- continue doing so for the indefinite future. In any case, please --
69 -- always : read and understand any software ; verify any PGP signatures --
70 -- that you use - for any purpose. --
71 -- --
72 -- See also http://trilema.com/2015/a-new-software-licensing-paradigm . --
73 ------------------------------------------------------------------------------
74 ------------------------------------------------------------------------------
75
76 with FZ_Basic; use FZ_Basic;
77 with FZ_Pred; use FZ_Pred;
78 with FZ_Shift; use FZ_Shift;
79 with FZ_Mul; use FZ_Mul;
80 with FZ_Divis; use FZ_Divis;
81
82
83 package body FZ_ModEx is
84
85 -- Modular Multiply: Product := X*Y mod Modulus
86 procedure FZ_Mod_Mul(X : in FZ;
87 Y : in FZ;
88 Modulus : in FZ;
89 Product : out FZ) is
90
91 -- The wordness of all three operands is equal:
92 L : constant Indices := X'Length;
93
94 -- Double-width register for multiplication and modulus operations
95 XY : FZ(1 .. L * 2);
96
97 -- To refer to the lower and upper halves of the working register:
98 XY_Lo : FZ renames XY(1 .. L);
99 XY_Hi : FZ renames XY(L + 1 .. XY'Last);
100
101 -- A zero-padded double-wide copy of Modulus, to satisfy Ch.5's FZ_Mod
102 M : FZ(XY'Range);
103
104 begin
105 -- Place the Modulus in a double-width M, as FZ_Mod currently demands
106 M(Modulus'Range) := Modulus;
107 M(L + 1 .. M'Last) := (others => 0);
108
109 -- XY_Lo:XY_Hi := X * Y
110 FZ_Mul_Egyptian(X, Y, XY_Lo, XY_Hi);
111
112 -- XY := XY mod M
113 FZ_Mod(XY, M, XY);
114
115 -- The bottom half of XY is our modular product; top half is always 0
116 Product := XY_Lo;
117 end FZ_Mod_Mul;
118 pragma Inline_Always(FZ_Mod_Mul);
119
120
121 -- Modular Exponent: Result := Base^Exponent mod Modulus
122 procedure FZ_Mod_Exp(Base : in FZ;
123 Exponent : in FZ;
124 Modulus : in FZ;
125 Result : out FZ) is
126
127 -- Working register for the squaring
128 B : FZ(Base'Range) := Base;
129
130 -- Register for cycling through the bits of E
131 E : FZ(Exponent'Range) := Exponent;
132
133 -- Register for the Mux operation
134 T : FZ(Result'Range);
135
136 begin
137 -- Result := 1
138 WBool_To_FZ(1, Result);
139
140 -- For each bit of Result width:
141 for i in 1 .. FZ_Bitness(Result) loop
142
143 -- T := Result * B mod Modulus
144 FZ_Mod_Mul(X => Result, Y => B, Modulus => Modulus,
145 Product => T);
146
147 -- Sel is the current low bit of E;
148 -- When Sel=0 -> Result := Result;
149 -- When Sel=1 -> Result := T
150 FZ_Mux(X => Result, Y => T, Result => Result,
151 Sel => FZ_OddP(E));
152
153 -- Advance to the next bit of E
154 FZ_ShiftRight(E, E, 1);
155
156 -- B := B*B mod Modulus
157 FZ_Mod_Mul(X => B, Y => B, Modulus => Modulus,
158 Product => B);
159
160 end loop;
161
162 end FZ_Mod_Exp;
163 pragma Inline_Always(FZ_Mod_Exp);
164
165 end FZ_ModEx;