------------------------------------------------------------------------------
------------------------------------------------------------------------------
-- This file is part of 'Finite Field Arithmetic', aka 'FFA'.               --
--                                                                          --
-- (C) 2017 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 FZ_Basic; use FZ_Basic;
with FZ_Pred;  use FZ_Pred;
with FZ_Shift; use FZ_Shift;
with FZ_Mul;   use FZ_Mul;
with FZ_Divis; use FZ_Divis;


package body FZ_ModEx is
   
   -- 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_Mul_Egyptian(X, Y, XY_Lo, XY_Hi);
      
      -- Product := XY mod M
      FZ_Mod(XY, Modulus, Product);
      
   end FZ_Mod_Mul;
   pragma Inline_Always(FZ_Mod_Mul);
   
   
   -- Modular Exponent: Result := Base^Exponent mod Modulus
   procedure FZ_Mod_Exp(Base     : in  FZ;
                        Exponent : in  FZ;
                        Modulus  : in  FZ;
                        Result   : out FZ) is
      
      -- Working register for the squaring
      B : FZ(Base'Range)     := Base;
      
      -- Register for cycling through the bits of E
      E : FZ(Exponent'Range) := Exponent;
      
      -- Register for the Mux operation
      T : FZ(Result'Range);
      
   begin
      -- Result := 1
      WBool_To_FZ(1, Result);
      
      -- For each bit of Result width:
      for i in 1 .. FZ_Bitness(Result) loop
         
         -- T := Result * B mod Modulus
         FZ_Mod_Mul(X => Result, Y => B, Modulus => Modulus,
                    Product => T);
         
         -- Sel is the current low bit of E;
         --    When Sel=0 -> Result := Result;
         --    When Sel=1 -> Result := T
         FZ_Mux(X => Result, Y => T, Result => Result,
                Sel => FZ_OddP(E));
         
         -- Advance to the next bit of E
         FZ_ShiftRight(E, E, 1);
         
         -- B := B*B mod Modulus
         FZ_Mod_Mul(X => B, Y => B, Modulus => Modulus,
                    Product => B);
         
      end loop;
      
   end FZ_Mod_Exp;
   pragma Inline_Always(FZ_Mod_Exp);
   
end FZ_ModEx;