Finite Field Arithmetic

fz_modex.adb


   1 ------------------------------------------------------------------------------
   2 ------------------------------------------------------------------------------
   3 -- This file is part of 'Finite Field Arithmetic', aka 'FFA'.               --
   4 --                                                                          --
   5 -- (C) 2019 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 Words;    use Words;
  21 with W_Shifts; use W_Shifts;
  22 with FZ_Basic; use FZ_Basic;
  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    -- (Conventional) 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    -- (Conventional) 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    -- (Barrettronic) Modular Squaring, using given Barrettoid
  84    procedure FZ_Mod_Sqr_Barrett(X        : in  FZ;
  85                                 Bar      : in  Barretoid;
  86                                 Product  : out FZ) is
  87       
  88       -- The wordness of both operands is equal:
  89       L     : constant Indices := X'Length;
  90       
  91       -- Double-width register for squaring and modulus operations
  92       XX    : FZ(1 .. L * 2);
  93       
  94       -- To refer to the lower and upper halves of the working register:
  95       XX_Lo : FZ renames XX(1     .. L);
  96       XX_Hi : FZ renames XX(L + 1 .. XX'Last);
  97    
  98    begin
  99       
 100       -- XX_Lo:XX_Hi := X^2
 101       FZ_Square_Buffered(X, XX_Lo, XX_Hi);
 102       
 103       -- Product := XX mod M
 104       FZ_Barrett_Reduce(X => XX, Bar => Bar, XReduced => Product);
 105       
 106    end FZ_Mod_Sqr_Barrett;
 107    
 108    
 109    -- Barrettronic Modular Exponent, using given Barrettoid
 110    procedure FZ_Mod_Exp_Barrett(Base     : in  FZ;
 111                                 Exponent : in  FZ;
 112                                 Bar      : in  Barretoid;
 113                                 Result   : out FZ) is
 114       
 115       -- Double-width scratch buffer for the modular operations
 116       D   : FZ(1 .. Base'Length * 2);
 117       
 118       -- Working register for the squaring; initially is copy of Base
 119       B   : FZ(Base'Range) := Base;
 120       
 121       -- Register for the Mux operation
 122       T   : FZ(Result'Range);
 123       
 124       -- Buffer register for the Result
 125       R   : FZ(Result'Range);
 126       
 127    begin
 128       
 129       -- Result := 1
 130       WBool_To_FZ(1, R);
 131       
 132       -- For each Word of the Exponent:
 133       for i in Exponent'Range loop
 134          
 135          declare
 136             
 137             -- The current Word of the Exponent
 138             Wi : Word := Exponent(i);
 139             
 140          begin
 141             
 142             -- For each bit of Wi:
 143             for j in 1 .. Bitness loop
 144                
 145                -- T := Result * B mod Modulus
 146                FZ_Multiply_Unbuffered(X => R, Y => B, XY => D);
 147                FZ_Barrett_Reduce(X => D, Bar => Bar, XReduced => T);
 148                
 149                -- Sel is the current bit of Exponent;
 150                --    When Sel=0 -> Result := Result;
 151                --    When Sel=1 -> Result := T
 152                FZ_Mux(X => R, Y => T, Result => R, Sel => Wi and 1);
 153                
 154                -- Advance to the next bit of Wi (i.e. next bit of Exponent)
 155                Wi := Shift_Right(Wi, 1);
 156                
 157                -- B := B^2 mod Modulus
 158                FZ_Square_Unbuffered(X => B, XX => D);
 159                FZ_Barrett_Reduce(X => D, Bar => Bar, XReduced => B);
 160                
 161             end loop;
 162          
 163          end;
 164          
 165       end loop;
 166       
 167       -- Output the Result:
 168       Result := R;
 169       
 170    end FZ_Mod_Exp_Barrett;
 171    
 172    
 173    -- (Barrettronic) Modular Exponent: Result := Base^Exponent mod Modulus
 174    procedure FZ_Mod_Exp(Base     : in  FZ;
 175                         Exponent : in  FZ;
 176                         Modulus  : in  FZ;
 177                         Result   : out FZ) is
 178       
 179       -- Space for Barrettoid
 180       Bar : Barretoid(ZXMLength       => Modulus'Length + 1,
 181                       BarretoidLength => 2 * Base'Length);
 182       
 183    begin
 184       
 185       -- First, pre-compute the Barretoid for the given Modulus:
 186       FZ_Make_Barrettoid(Modulus => Modulus, Result => Bar);
 187       
 188       -- Compute the modular exponentiation using the above Barrettoid:
 189       FZ_Mod_Exp_Barrett(Base     => Base,
 190                          Exponent => Exponent,
 191                          Bar      => Bar,
 192                          Result   => Result);
 193       
 194    end FZ_Mod_Exp;
 195    
 196 end FZ_ModEx;