File : 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 with FZ_Barr;  use FZ_Barr;
  27 
  28 
  29 package body FZ_ModEx is
  30    
  31    -- (Conventional) Modular Multiply: Product := X*Y mod Modulus
  32    procedure FZ_Mod_Mul(X        : in  FZ;
  33                         Y        : in  FZ;
  34                         Modulus  : in  FZ;
  35                         Product  : out FZ) is
  36       
  37       -- The wordness of all three operands is equal:
  38       L     : constant Indices := X'Length;
  39       
  40       -- Double-width register for multiplication and modulus operations
  41       XY    : FZ(1 .. L * 2);
  42       
  43       -- To refer to the lower and upper halves of the working register:
  44       XY_Lo : FZ renames XY(1     .. L);
  45       XY_Hi : FZ renames XY(L + 1 .. XY'Last);
  46       
  47    begin
  48       
  49       -- XY_Lo:XY_Hi := X * Y
  50       FZ_Multiply_Buffered(X, Y, XY_Lo, XY_Hi);
  51       
  52       -- Product := XY mod M
  53       FZ_Mod(XY, Modulus, Product);
  54       
  55    end FZ_Mod_Mul;
  56    
  57    
  58    -- (Conventional) Modular Squaring: Product := X*X mod Modulus
  59    procedure FZ_Mod_Sqr(X        : in  FZ;
  60                         Modulus  : in  FZ;
  61                         Product  : out FZ) is
  62       
  63       -- The wordness of both operands is equal:
  64       L     : constant Indices := X'Length;
  65       
  66       -- Double-width register for squaring and modulus operations
  67       XX    : FZ(1 .. L * 2);
  68       
  69       -- To refer to the lower and upper halves of the working register:
  70       XX_Lo : FZ renames XX(1     .. L);
  71       XX_Hi : FZ renames XX(L + 1 .. XX'Last);
  72    
  73    begin
  74       
  75       -- XX_Lo:XX_Hi := X^2
  76       FZ_Square_Buffered(X, XX_Lo, XX_Hi);
  77       
  78       -- Product := XX mod M
  79       FZ_Mod(XX, Modulus, Product);
  80       
  81    end FZ_Mod_Sqr;
  82    
  83    
  84    -- (Barrettronic) Modular Exponent: Result := Base^Exponent mod Modulus
  85    procedure FZ_Mod_Exp(Base     : in  FZ;
  86                         Exponent : in  FZ;
  87                         Modulus  : in  FZ;
  88                         Result   : out FZ) is
  89       
  90       -- Double-width scratch buffer for the modular operations
  91       D   : FZ(1 .. Base'Length * 2);
  92       
  93       -- Working register for the squaring; initially is copy of Base
  94       B   : FZ(Base'Range) := Base;
  95       
  96       -- Register for the Mux operation
  97       T   : FZ(Result'Range);
  98       
  99       -- Buffer register for the Result
 100       R   : FZ(Result'Range);
 101       
 102       -- Space for Barrettoid
 103       Bar : Barretoid(ZXMLength       => Modulus'Length + 1,
 104                       BarretoidLength => 2 * B'Length);
 105       
 106    begin
 107       
 108       -- First, pre-compute the Barretoid for the given Modulus:
 109       FZ_Make_Barrettoid(Modulus => Modulus, Result => Bar);
 110       
 111       -- Result := 1
 112       WBool_To_FZ(1, R);
 113       
 114       -- For each Word of the Exponent:
 115       for i in Exponent'Range loop
 116          
 117          declare
 118             
 119             -- The current Word of the Exponent
 120             Wi : Word := Exponent(i);
 121             
 122          begin
 123             
 124             -- For each bit of Wi:
 125             for j in 1 .. Bitness loop
 126                
 127                -- T := Result * B mod Modulus
 128                FZ_Multiply_Unbuffered(X => R, Y => B, XY => D);
 129                FZ_Barrett_Reduce(X => D, Bar => Bar, XReduced => T);
 130                
 131                -- Sel is the current bit of Exponent;
 132                --    When Sel=0 -> Result := Result;
 133                --    When Sel=1 -> Result := T
 134                FZ_Mux(X => R, Y => T, Result => R, Sel => Wi and 1);
 135                
 136                -- Advance to the next bit of Wi (i.e. next bit of Exponent)
 137                Wi := Shift_Right(Wi, 1);
 138                
 139                -- B := B^2 mod Modulus
 140                FZ_Square_Unbuffered(X => B, XX => D);
 141                FZ_Barrett_Reduce(X => D, Bar => Bar, XReduced => B);
 142                
 143             end loop;
 144          
 145          end;
 146          
 147       end loop;
 148       
 149       -- Output the Result:
 150       Result := R;
 151       
 152    end FZ_Mod_Exp;
 153    
 154 end FZ_ModEx;