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       -- A zero-padded double-wide copy of Modulus, to satisfy Ch.5's FZ_Mod
ffa_ch6_simplest_...   46       M     : FZ(XY'Range);
ffa_ch6_simplest_...   47       
ffa_ch6_simplest_...   48    begin
ffa_ch6_simplest_...   49       -- Place the Modulus in a double-width M, as FZ_Mod currently demands
ffa_ch6_simplest_...   50       M(Modulus'Range)   := Modulus;
ffa_ch6_simplest_...   51       M(L + 1 .. M'Last) := (others => 0);
ffa_ch6_simplest_...   52       
ffa_ch6_simplest_...   53       -- XY_Lo:XY_Hi := X * Y
ffa_ch6_simplest_...   54       FZ_Mul_Egyptian(X, Y, XY_Lo, XY_Hi);
ffa_ch6_simplest_...   55       
ffa_ch6_simplest_...   56       -- XY := XY mod M
ffa_ch6_simplest_...   57       FZ_Mod(XY, M, XY);
ffa_ch6_simplest_...   58       
ffa_ch6_simplest_...   59       -- The bottom half of XY is our modular product; top half is always 0
ffa_ch6_simplest_...   60       Product := XY_Lo;
ffa_ch6_simplest_...   61    end FZ_Mod_Mul;
ffa_ch6_simplest_...   62    pragma Inline_Always(FZ_Mod_Mul);
ffa_ch6_simplest_...   63    
ffa_ch6_simplest_...   64    
ffa_ch6_simplest_...   65    -- Modular Exponent: Result := Base^Exponent mod Modulus
ffa_ch6_simplest_...   66    procedure FZ_Mod_Exp(Base     : in  FZ;
ffa_ch6_simplest_...   67                         Exponent : in  FZ;
ffa_ch6_simplest_...   68                         Modulus  : in  FZ;
ffa_ch6_simplest_...   69                         Result   : out FZ) is
ffa_ch6_simplest_...   70       
ffa_ch6_simplest_...   71       -- Working register for the squaring
ffa_ch6_simplest_...   72       B : FZ(Base'Range)     := Base;
ffa_ch6_simplest_...   73       
ffa_ch6_simplest_...   74       -- Register for cycling through the bits of E
ffa_ch6_simplest_...   75       E : FZ(Exponent'Range) := Exponent;
ffa_ch6_simplest_...   76       
ffa_ch6_simplest_...   77       -- Register for the Mux operation
ffa_ch6_simplest_...   78       T : FZ(Result'Range);
ffa_ch6_simplest_...   79       
ffa_ch6_simplest_...   80    begin
ffa_ch6_simplest_...   81       -- Result := 1
ffa_ch6_simplest_...   82       WBool_To_FZ(1, Result);
ffa_ch6_simplest_...   83       
ffa_ch6_simplest_...   84       -- For each bit of Result width:
ffa_ch6_simplest_...   85       for i in 1 .. FZ_Bitness(Result) loop
ffa_ch6_simplest_...   86          
ffa_ch6_simplest_...   87          -- T := Result * B mod Modulus
ffa_ch6_simplest_...   88          FZ_Mod_Mul(X => Result, Y => B, Modulus => Modulus,
ffa_ch6_simplest_...   89                     Product => T);
ffa_ch6_simplest_...   90          
ffa_ch6_simplest_...   91          -- Sel is the current low bit of E;
ffa_ch6_simplest_...   92          --    When Sel=0 -> Result := Result;
ffa_ch6_simplest_...   93          --    When Sel=1 -> Result := T
ffa_ch6_simplest_...   94          FZ_Mux(X => Result, Y => T, Result => Result,
ffa_ch6_simplest_...   95                 Sel => FZ_OddP(E));
ffa_ch6_simplest_...   96          
ffa_ch6_simplest_...   97          -- Advance to the next bit of E
ffa_ch6_simplest_...   98          FZ_ShiftRight(E, E, 1);
ffa_ch6_simplest_...   99          
ffa_ch6_simplest_...  100          -- B := B*B mod Modulus
ffa_ch6_simplest_...  101          FZ_Mod_Mul(X => B, Y => B, Modulus => Modulus,
ffa_ch6_simplest_...  102                     Product => B);
ffa_ch6_simplest_...  103          
ffa_ch6_simplest_...  104       end loop;
ffa_ch6_simplest_...  105       
ffa_ch6_simplest_...  106    end FZ_Mod_Exp;
ffa_ch6_simplest_...  107    pragma Inline_Always(FZ_Mod_Exp);
ffa_ch6_simplest_...  108    
ffa_ch6_simplest_...  109 end FZ_ModEx;