tree checksum vpatch file split hunks
all signers: asciilifeform bvt diana_coman
antecedents: ffa_ch5_egypt.kv
press order:
patch:
(34 . 11)(34 . 11)-
5 with FZ_Shift; use FZ_Shift;
6 with FZ_Divis; use FZ_Divis;
7 with FZ_Mul; use FZ_Mul;
8 with FZ_ModEx; use FZ_ModEx;
9
10 -- For Output
11 with FFA_IO; use FFA_IO;
12
13
14 procedure FFA_Calc is
15
16 Width : Positive; -- Desired FFA Width
(357 . 13)(357 . 34)
18 -- Multiply, give bottom and top halves
19 when '*' =>
20 Want(2);
21 MustNotZero(Stack(SP));
22 -- Ch5: slow and simple 'Egyptological' method:
23 FZ_Mul_Egyptian(X => Stack(SP - 1),
24 Y => Stack(SP),
25 XY_Lo => Stack(SP - 1),
26 XY_Hi => Stack(SP));
27
28 -- Modular Multiplication
29 when 'M' =>
30 Want(3);
31 MustNotZero(Stack(SP));
32 FZ_Mod_Mul(X => Stack(SP - 2),
33 Y => Stack(SP - 1),
34 Modulus => Stack(SP),
35 Product => Stack(SP - 2));
36 Drop;
37 Drop;
38
39 -- Modular Exponentiation
40 when 'X' =>
41 Want(3);
42 MustNotZero(Stack(SP));
43 FZ_Mod_Exp(Base => Stack(SP - 2),
44 Exponent => Stack(SP - 1),
45 Modulus => Stack(SP),
46 Result => Stack(SP - 2));
47 Drop;
48 Drop;
49
50 -----------------
51 -- Bitwise Ops --
52 -----------------
(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;
-(0 . 0)(1 . 45)
170 ------------------------------------------------------------------------------
171 ------------------------------------------------------------------------------
172 -- This file is part of 'Finite Field Arithmetic', aka 'FFA'. --
173 -- --
174 -- (C) 2017 Stanislav Datskovskiy ( www.loper-os.org ) --
175 -- http://wot.deedbot.org/17215D118B7239507FAFED98B98228A001ABFFC7.html --
176 -- --
177 -- You do not have, nor can you ever acquire the right to use, copy or --
178 -- distribute this software ; Should you use this software for any purpose, --
179 -- or copy and distribute it to anyone or in any manner, you are breaking --
180 -- the laws of whatever soi-disant jurisdiction, and you promise to --
181 -- continue doing so for the indefinite future. In any case, please --
182 -- always : read and understand any software ; verify any PGP signatures --
183 -- that you use - for any purpose. --
184 -- --
185 -- See also http://trilema.com/2015/a-new-software-licensing-paradigm . --
186 ------------------------------------------------------------------------------
187 ------------------------------------------------------------------------------
188
189 with FZ_Type; use FZ_Type;
190
191
192 package FZ_ModEx is
193
194 pragma Pure;
195
196 -- Modular Multiply: Product := X*Y mod Modulus
197 procedure FZ_Mod_Mul(X : in FZ;
198 Y : in FZ;
199 Modulus : in FZ;
200 Product : out FZ);
201 pragma Precondition(X'Length = Y'Length and
202 Modulus'Length = X'Length and
203 Product'Length = Modulus'Length);
204
205 -- Modular Exponent: Result := Base^Exponent mod Modulus
206 procedure FZ_Mod_Exp(Base : in FZ;
207 Exponent : in FZ;
208 Modulus : in FZ;
209 Result : out FZ);
210 pragma Precondition(Base'Length = Exponent'Length and
211 Base'Length = Result'Length and
212 Base'Length = Modulus'Length);
213
214 end FZ_ModEx;