raw
ffa_ch6_simplest_...    1 ------------------------------------------------------------------------------
ffa_ch6_simplest_... 2 ------------------------------------------------------------------------------
ffa_ch6_simplest_... 3 -- This file is part of 'Finite Field Arithmetic', aka 'FFA'. --
ffa_ch6_simplest_... 4 -- --
ffa_ch15_gcd.kv 5 -- (C) 2019 Stanislav Datskovskiy ( www.loper-os.org ) --
ffa_ch6_simplest_... 6 -- http://wot.deedbot.org/17215D118B7239507FAFED98B98228A001ABFFC7.html --
ffa_ch6_simplest_... 7 -- --
ffa_ch6_simplest_... 8 -- You do not have, nor can you ever acquire the right to use, copy or --
ffa_ch6_simplest_... 9 -- distribute this software ; Should you use this software for any purpose, --
ffa_ch6_simplest_... 10 -- or copy and distribute it to anyone or in any manner, you are breaking --
ffa_ch6_simplest_... 11 -- the laws of whatever soi-disant jurisdiction, and you promise to --
ffa_ch6_simplest_... 12 -- continue doing so for the indefinite future. In any case, please --
ffa_ch6_simplest_... 13 -- always : read and understand any software ; verify any PGP signatures --
ffa_ch6_simplest_... 14 -- that you use - for any purpose. --
ffa_ch6_simplest_... 15 -- --
ffa_ch6_simplest_... 16 -- See also http://trilema.com/2015/a-new-software-licensing-paradigm . --
ffa_ch6_simplest_... 17 ------------------------------------------------------------------------------
ffa_ch6_simplest_... 18 ------------------------------------------------------------------------------
ffa_ch6_simplest_... 19
ffa_ch14_barrett.kv 20 with Words; use Words;
ffa_ch14_barrett.kv 21 with W_Shifts; use W_Shifts;
ffa_ch6_simplest_... 22 with FZ_Basic; use FZ_Basic;
ffa_ch6_simplest_... 23 with FZ_Mul; use FZ_Mul;
ffa_ch12_karatsub... 24 with FZ_Sqr; use FZ_Sqr;
ffa_ch6_simplest_... 25 with FZ_Divis; use FZ_Divis;
ffa_ch14_barrett.kv 26 with FZ_Barr; use FZ_Barr;
ffa_ch6_simplest_... 27
ffa_ch6_simplest_... 28
ffa_ch6_simplest_... 29 package body FZ_ModEx is
ffa_ch6_simplest_... 30
ffa_ch14_barrett.kv 31 -- (Conventional) Modular Multiply: Product := X*Y mod Modulus
ffa_ch6_simplest_... 32 procedure FZ_Mod_Mul(X : in FZ;
ffa_ch6_simplest_... 33 Y : in FZ;
ffa_ch6_simplest_... 34 Modulus : in FZ;
ffa_ch6_simplest_... 35 Product : out FZ) is
ffa_ch6_simplest_... 36
ffa_ch6_simplest_... 37 -- The wordness of all three operands is equal:
ffa_ch6_simplest_... 38 L : constant Indices := X'Length;
ffa_ch6_simplest_... 39
ffa_ch6_simplest_... 40 -- Double-width register for multiplication and modulus operations
ffa_ch6_simplest_... 41 XY : FZ(1 .. L * 2);
ffa_ch6_simplest_... 42
ffa_ch6_simplest_... 43 -- To refer to the lower and upper halves of the working register:
ffa_ch6_simplest_... 44 XY_Lo : FZ renames XY(1 .. L);
ffa_ch6_simplest_... 45 XY_Hi : FZ renames XY(L + 1 .. XY'Last);
ffa_ch6_simplest_... 46
ffa_ch6_simplest_... 47 begin
ffa_ch6_simplest_... 48
ffa_ch6_simplest_... 49 -- XY_Lo:XY_Hi := X * Y
ffa_ch11_tuning_a... 50 FZ_Multiply_Buffered(X, Y, XY_Lo, XY_Hi);
ffa_ch6_simplest_... 51
ffa_ch7_turbo_egy... 52 -- Product := XY mod M
ffa_ch7_turbo_egy... 53 FZ_Mod(XY, Modulus, Product);
ffa_ch6_simplest_... 54
ffa_ch6_simplest_... 55 end FZ_Mod_Mul;
ffa_ch6_simplest_... 56
ffa_ch6_simplest_... 57
ffa_ch14_barrett.kv 58 -- (Conventional) Modular Squaring: Product := X*X mod Modulus
ffa_ch12_karatsub... 59 procedure FZ_Mod_Sqr(X : in FZ;
ffa_ch12_karatsub... 60 Modulus : in FZ;
ffa_ch12_karatsub... 61 Product : out FZ) is
ffa_ch12_karatsub... 62
ffa_ch12_karatsub... 63 -- The wordness of both operands is equal:
ffa_ch12_karatsub... 64 L : constant Indices := X'Length;
ffa_ch12_karatsub... 65
ffa_ch12_karatsub... 66 -- Double-width register for squaring and modulus operations
ffa_ch12_karatsub... 67 XX : FZ(1 .. L * 2);
ffa_ch12_karatsub... 68
ffa_ch12_karatsub... 69 -- To refer to the lower and upper halves of the working register:
ffa_ch12_karatsub... 70 XX_Lo : FZ renames XX(1 .. L);
ffa_ch12_karatsub... 71 XX_Hi : FZ renames XX(L + 1 .. XX'Last);
ffa_ch12_karatsub... 72
ffa_ch12_karatsub... 73 begin
ffa_ch12_karatsub... 74
ffa_ch12_karatsub... 75 -- XX_Lo:XX_Hi := X^2
ffa_ch12_karatsub... 76 FZ_Square_Buffered(X, XX_Lo, XX_Hi);
ffa_ch12_karatsub... 77
ffa_ch12_karatsub... 78 -- Product := XX mod M
ffa_ch12_karatsub... 79 FZ_Mod(XX, Modulus, Product);
ffa_ch12_karatsub... 80
ffa_ch12_karatsub... 81 end FZ_Mod_Sqr;
ffa_ch12_karatsub... 82
ffa_ch12_karatsub... 83
ffa_ch14_barrett.kv 84 -- (Barrettronic) Modular Exponent: Result := Base^Exponent mod Modulus
ffa_ch6_simplest_... 85 procedure FZ_Mod_Exp(Base : in FZ;
ffa_ch6_simplest_... 86 Exponent : in FZ;
ffa_ch6_simplest_... 87 Modulus : in FZ;
ffa_ch6_simplest_... 88 Result : out FZ) is
ffa_ch6_simplest_... 89
ffa_ch14_barrett.kv 90 -- Double-width scratch buffer for the modular operations
ffa_ch14_barrett.kv 91 D : FZ(1 .. Base'Length * 2);
ffa_ch6_simplest_... 92
ffa_ch14_barrett.kv 93 -- Working register for the squaring; initially is copy of Base
ffa_ch14_barrett.kv 94 B : FZ(Base'Range) := Base;
ffa_ch6_simplest_... 95
ffa_ch6_simplest_... 96 -- Register for the Mux operation
ffa_ch14_barrett.kv 97 T : FZ(Result'Range);
ffa_ch6_simplest_... 98
ffa_ch8_randomism.kv 99 -- Buffer register for the Result
ffa_ch14_barrett.kv 100 R : FZ(Result'Range);
ffa_ch14_barrett.kv 101
ffa_ch14_barrett.kv 102 -- Space for Barrettoid
ffa_ch14_barrett.kv 103 Bar : Barretoid(ZXMLength => Modulus'Length + 1,
ffa_ch14_barrett.kv 104 BarretoidLength => 2 * B'Length);
ffa_ch8_randomism.kv 105
ffa_ch6_simplest_... 106 begin
ffa_ch14_barrett.kv 107
ffa_ch14_barrett.kv 108 -- First, pre-compute the Barretoid for the given Modulus:
ffa_ch14_barrett.kv 109 FZ_Make_Barrettoid(Modulus => Modulus, Result => Bar);
ffa_ch14_barrett.kv 110
ffa_ch6_simplest_... 111 -- Result := 1
ffa_ch8_randomism.kv 112 WBool_To_FZ(1, R);
ffa_ch6_simplest_... 113
ffa_ch14_barrett.kv 114 -- For each Word of the Exponent:
ffa_ch14_barrett.kv 115 for i in Exponent'Range loop
ffa_ch6_simplest_... 116
ffa_ch14_barrett.kv 117 declare
ffa_ch14_barrett.kv 118
ffa_ch14_barrett.kv 119 -- The current Word of the Exponent
ffa_ch14_barrett.kv 120 Wi : Word := Exponent(i);
ffa_ch14_barrett.kv 121
ffa_ch14_barrett.kv 122 begin
ffa_ch14_barrett.kv 123
ffa_ch14_barrett.kv 124 -- For each bit of Wi:
ffa_ch14_barrett.kv 125 for j in 1 .. Bitness loop
ffa_ch14_barrett.kv 126
ffa_ch14_barrett.kv 127 -- T := Result * B mod Modulus
ffa_ch14_barrett.kv 128 FZ_Multiply_Unbuffered(X => R, Y => B, XY => D);
ffa_ch14_barrett.kv 129 FZ_Barrett_Reduce(X => D, Bar => Bar, XReduced => T);
ffa_ch14_barrett.kv 130
ffa_ch14_barrett.kv 131 -- Sel is the current bit of Exponent;
ffa_ch14_barrett.kv 132 -- When Sel=0 -> Result := Result;
ffa_ch14_barrett.kv 133 -- When Sel=1 -> Result := T
ffa_ch14_barrett.kv 134 FZ_Mux(X => R, Y => T, Result => R, Sel => Wi and 1);
ffa_ch14_barrett.kv 135
ffa_ch14_barrett.kv 136 -- Advance to the next bit of Wi (i.e. next bit of Exponent)
ffa_ch14_barrett.kv 137 Wi := Shift_Right(Wi, 1);
ffa_ch14_barrett.kv 138
ffa_ch14_barrett.kv 139 -- B := B^2 mod Modulus
ffa_ch14_barrett.kv 140 FZ_Square_Unbuffered(X => B, XX => D);
ffa_ch14_barrett.kv 141 FZ_Barrett_Reduce(X => D, Bar => Bar, XReduced => B);
ffa_ch14_barrett.kv 142
ffa_ch14_barrett.kv 143 end loop;
ffa_ch6_simplest_... 144
ffa_ch14_barrett.kv 145 end;
ffa_ch6_simplest_... 146
ffa_ch6_simplest_... 147 end loop;
ffa_ch6_simplest_... 148
ffa_ch8_randomism.kv 149 -- Output the Result:
ffa_ch8_randomism.kv 150 Result := R;
ffa_ch8_randomism.kv 151
ffa_ch6_simplest_... 152 end FZ_Mod_Exp;
ffa_ch6_simplest_... 153
ffa_ch6_simplest_... 154 end FZ_ModEx;