------------------------------------------------------------------------------
------------------------------------------------------------------------------
-- This file is part of 'Finite Field Arithmetic', aka 'FFA'.               --
--                                                                          --
-- (C) 2019 Stanislav Datskovskiy ( www.loper-os.org )                      --
-- http://wot.deedbot.org/17215D118B7239507FAFED98B98228A001ABFFC7.html     --
--                                                                          --
-- You do not have, nor can you ever acquire the right to use, copy or      --
-- distribute this software ; Should you use this software for any purpose, --
-- or copy and distribute it to anyone or in any manner, you are breaking   --
-- the laws of whatever soi-disant jurisdiction, and you promise to         --
-- continue doing so for the indefinite future. In any case, please         --
-- always : read and understand any software ; verify any PGP signatures    --
-- that you use - for any purpose.                                          --
--                                                                          --
-- See also http://trilema.com/2015/a-new-software-licensing-paradigm .     --
------------------------------------------------------------------------------
------------------------------------------------------------------------------

with Words;    use Words;
with W_Shifts; use W_Shifts;
with FZ_Basic; use FZ_Basic;
with FZ_Mul;   use FZ_Mul;
with FZ_Sqr;   use FZ_Sqr;
with FZ_Divis; use FZ_Divis;


package body FZ_ModEx is
   
   -- (Conventional) Modular Multiply: Product := X*Y mod Modulus
   procedure FZ_Mod_Mul(X        : in  FZ;
                        Y        : in  FZ;
                        Modulus  : in  FZ;
                        Product  : out FZ) is
      
      -- The wordness of all three operands is equal:
      L     : constant Indices := X'Length;
      
      -- Double-width register for multiplication and modulus operations
      XY    : FZ(1 .. L * 2);
      
      -- To refer to the lower and upper halves of the working register:
      XY_Lo : FZ renames XY(1     .. L);
      XY_Hi : FZ renames XY(L + 1 .. XY'Last);
      
   begin
      
      -- XY_Lo:XY_Hi := X * Y
      FZ_Multiply_Buffered(X, Y, XY_Lo, XY_Hi);
      
      -- Product := XY mod M
      FZ_Mod(XY, Modulus, Product);
      
   end FZ_Mod_Mul;
   
   
   -- (Conventional) Modular Squaring: Product := X*X mod Modulus
   procedure FZ_Mod_Sqr(X        : in  FZ;
                        Modulus  : in  FZ;
                        Product  : out FZ) is
      
      -- The wordness of both operands is equal:
      L     : constant Indices := X'Length;
      
      -- Double-width register for squaring and modulus operations
      XX    : FZ(1 .. L * 2);
      
      -- To refer to the lower and upper halves of the working register:
      XX_Lo : FZ renames XX(1     .. L);
      XX_Hi : FZ renames XX(L + 1 .. XX'Last);
   
   begin
      
      -- XX_Lo:XX_Hi := X^2
      FZ_Square_Buffered(X, XX_Lo, XX_Hi);
      
      -- Product := XX mod M
      FZ_Mod(XX, Modulus, Product);
      
   end FZ_Mod_Sqr;
   
   
   -- (Barrettronic) Modular Squaring, using given Barrettoid
   procedure FZ_Mod_Sqr_Barrett(X        : in  FZ;
                                Bar      : in  Barretoid;
                                Product  : out FZ) is
      
      -- The wordness of both operands is equal:
      L     : constant Indices := X'Length;
      
      -- Double-width register for squaring and modulus operations
      XX    : FZ(1 .. L * 2);
      
      -- To refer to the lower and upper halves of the working register:
      XX_Lo : FZ renames XX(1     .. L);
      XX_Hi : FZ renames XX(L + 1 .. XX'Last);
   
   begin
      
      -- XX_Lo:XX_Hi := X^2
      FZ_Square_Buffered(X, XX_Lo, XX_Hi);
      
      -- Product := XX mod M
      FZ_Barrett_Reduce(X => XX, Bar => Bar, XReduced => Product);
      
   end FZ_Mod_Sqr_Barrett;
   
   
   -- Barrettronic Modular Exponent, using given Barrettoid
   procedure FZ_Mod_Exp_Barrett(Base     : in  FZ;
                                Exponent : in  FZ;
                                Bar      : in  Barretoid;
                                Result   : out FZ) is
      
      -- Double-width scratch buffer for the modular operations
      D   : FZ(1 .. Base'Length * 2);
      
      -- Working register for the squaring; initially is copy of Base
      B   : FZ(Base'Range) := Base;
      
      -- Register for the Mux operation
      T   : FZ(Result'Range);
      
      -- Buffer register for the Result
      R   : FZ(Result'Range);
      
   begin
      
      -- Result := 1
      WBool_To_FZ(1, R);
      
      -- For each Word of the Exponent:
      for i in Exponent'Range loop
         
         declare
            
            -- The current Word of the Exponent
            Wi : Word := Exponent(i);
            
         begin
            
            -- For each bit of Wi:
            for j in 1 .. Bitness loop
               
               -- T := Result * B mod Modulus
               FZ_Multiply_Unbuffered(X => R, Y => B, XY => D);
               FZ_Barrett_Reduce(X => D, Bar => Bar, XReduced => T);
               
               -- Sel is the current bit of Exponent;
               --    When Sel=0 -> Result := Result;
               --    When Sel=1 -> Result := T
               FZ_Mux(X => R, Y => T, Result => R, Sel => Wi and 1);
               
               -- Advance to the next bit of Wi (i.e. next bit of Exponent)
               Wi := Shift_Right(Wi, 1);
               
               -- B := B^2 mod Modulus
               FZ_Square_Unbuffered(X => B, XX => D);
               FZ_Barrett_Reduce(X => D, Bar => Bar, XReduced => B);
               
            end loop;
         
         end;
         
      end loop;
      
      -- Output the Result:
      Result := R;
      
   end FZ_Mod_Exp_Barrett;
   
   
   -- (Barrettronic) Modular Exponent: Result := Base^Exponent mod Modulus
   procedure FZ_Mod_Exp(Base     : in  FZ;
                        Exponent : in  FZ;
                        Modulus  : in  FZ;
                        Result   : out FZ) is
      
      -- Space for Barrettoid
      Bar : Barretoid(ZXMLength       => Modulus'Length + 1,
                      BarretoidLength => 2 * Base'Length);
      
   begin
      
      -- First, pre-compute the Barretoid for the given Modulus:
      FZ_Make_Barrettoid(Modulus => Modulus, Result => Bar);
      
      -- Compute the modular exponentiation using the above Barrettoid:
      FZ_Mod_Exp_Barrett(Base     => Base,
                         Exponent => Exponent,
                         Bar      => Bar,
                         Result   => Result);
      
   end FZ_Mod_Exp;
   
end FZ_ModEx;