File : fz_modex.adb
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 -- --
16 -- See also http://trilema.com/2015/a-new-software-licensing-paradigm . --
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_Divis; use FZ_Divis;
25
26
27 package body FZ_ModEx is
28
29 -- Modular Multiply: Product := X*Y mod Modulus
30 procedure FZ_Mod_Mul(X : in FZ;
31 Y : in FZ;
32 Modulus : in FZ;
33 Product : out FZ) is
34
35 -- The wordness of all three operands is equal:
36 L : constant Indices := X'Length;
37
38 -- Double-width register for multiplication and modulus operations
39 XY : FZ(1 .. L * 2);
40
41 -- To refer to the lower and upper halves of the working register:
42 XY_Lo : FZ renames XY(1 .. L);
43 XY_Hi : FZ renames XY(L + 1 .. XY'Last);
44
45 begin
46
47 -- XY_Lo:XY_Hi := X * Y
48 FZ_Multiply_Buffered(X, Y, XY_Lo, XY_Hi);
49
50 -- Product := XY mod M
51 FZ_Mod(XY, Modulus, Product);
52
53 end FZ_Mod_Mul;
54
55
56 -- Modular Exponent: Result := Base^Exponent mod Modulus
57 procedure FZ_Mod_Exp(Base : in FZ;
58 Exponent : in FZ;
59 Modulus : in FZ;
60 Result : out FZ) is
61
62 -- Working register for the squaring; initially is copy of Base
63 B : FZ(Base'Range) := Base;
64
65 -- Copy of Exponent, for cycling through its bits
66 E : FZ(Exponent'Range) := Exponent;
67
68 -- Register for the Mux operation
69 T : FZ(Result'Range);
70
71 -- Buffer register for the Result
72 R : FZ(Result'Range);
73
74 begin
75 -- Result := 1
76 WBool_To_FZ(1, R);
77
78 -- For each bit of R width:
79 for i in 1 .. FZ_Bitness(R) loop
80
81 -- T := Result * B mod Modulus
82 FZ_Mod_Mul(X => R, Y => B, Modulus => Modulus, Product => T);
83
84 -- Sel is the current low bit of E;
85 -- When Sel=0 -> Result := Result;
86 -- When Sel=1 -> Result := T
87 FZ_Mux(X => R, Y => T, Result => R, Sel => FZ_OddP(E));
88
89 -- Advance to the next bit of E
90 FZ_ShiftRight(E, E, 1);
91
92 -- B := B*B mod Modulus
93 FZ_Mod_Mul(X => B, Y => B, Modulus => Modulus, Product => B);
94
95 end loop;
96
97 -- Output the Result:
98 Result := R;
99
100 end FZ_Mod_Exp;
101
102 end FZ_ModEx;