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_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;