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