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_ch15_gcd.kv         5 -- (C) 2019 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_ch14_barrett.kv    20 with Words;    use Words;
ffa_ch14_barrett.kv    21 with W_Shifts; use W_Shifts;
ffa_ch6_simplest_...   22 with FZ_Basic; use FZ_Basic;
ffa_ch6_simplest_...   23 with FZ_Mul;   use FZ_Mul;
ffa_ch12_karatsub...   24 with FZ_Sqr;   use FZ_Sqr;
ffa_ch6_simplest_...   25 with FZ_Divis; use FZ_Divis;
ffa_ch6_simplest_...   26 
ffa_ch6_simplest_...   27 
ffa_ch6_simplest_...   28 package body FZ_ModEx is
ffa_ch6_simplest_...   29    
ffa_ch14_barrett.kv    30    -- (Conventional) Modular Multiply: Product := X*Y mod Modulus
ffa_ch6_simplest_...   31    procedure FZ_Mod_Mul(X        : in  FZ;
ffa_ch6_simplest_...   32                         Y        : in  FZ;
ffa_ch6_simplest_...   33                         Modulus  : in  FZ;
ffa_ch6_simplest_...   34                         Product  : out FZ) is
ffa_ch6_simplest_...   35       
ffa_ch6_simplest_...   36       -- The wordness of all three operands is equal:
ffa_ch6_simplest_...   37       L     : constant Indices := X'Length;
ffa_ch6_simplest_...   38       
ffa_ch6_simplest_...   39       -- Double-width register for multiplication and modulus operations
ffa_ch6_simplest_...   40       XY    : FZ(1 .. L * 2);
ffa_ch6_simplest_...   41       
ffa_ch6_simplest_...   42       -- To refer to the lower and upper halves of the working register:
ffa_ch6_simplest_...   43       XY_Lo : FZ renames XY(1     .. L);
ffa_ch6_simplest_...   44       XY_Hi : FZ renames XY(L + 1 .. XY'Last);
ffa_ch6_simplest_...   45       
ffa_ch6_simplest_...   46    begin
ffa_ch6_simplest_...   47       
ffa_ch6_simplest_...   48       -- XY_Lo:XY_Hi := X * Y
ffa_ch11_tuning_a...   49       FZ_Multiply_Buffered(X, Y, XY_Lo, XY_Hi);
ffa_ch6_simplest_...   50       
ffa_ch7_turbo_egy...   51       -- Product := XY mod M
ffa_ch7_turbo_egy...   52       FZ_Mod(XY, Modulus, Product);
ffa_ch6_simplest_...   53       
ffa_ch6_simplest_...   54    end FZ_Mod_Mul;
ffa_ch6_simplest_...   55    
ffa_ch6_simplest_...   56    
ffa_ch14_barrett.kv    57    -- (Conventional) Modular Squaring: Product := X*X mod Modulus
ffa_ch12_karatsub...   58    procedure FZ_Mod_Sqr(X        : in  FZ;
ffa_ch12_karatsub...   59                         Modulus  : in  FZ;
ffa_ch12_karatsub...   60                         Product  : out FZ) is
ffa_ch12_karatsub...   61       
ffa_ch12_karatsub...   62       -- The wordness of both operands is equal:
ffa_ch12_karatsub...   63       L     : constant Indices := X'Length;
ffa_ch12_karatsub...   64       
ffa_ch12_karatsub...   65       -- Double-width register for squaring and modulus operations
ffa_ch12_karatsub...   66       XX    : FZ(1 .. L * 2);
ffa_ch12_karatsub...   67       
ffa_ch12_karatsub...   68       -- To refer to the lower and upper halves of the working register:
ffa_ch12_karatsub...   69       XX_Lo : FZ renames XX(1     .. L);
ffa_ch12_karatsub...   70       XX_Hi : FZ renames XX(L + 1 .. XX'Last);
ffa_ch12_karatsub...   71    
ffa_ch12_karatsub...   72    begin
ffa_ch12_karatsub...   73       
ffa_ch12_karatsub...   74       -- XX_Lo:XX_Hi := X^2
ffa_ch12_karatsub...   75       FZ_Square_Buffered(X, XX_Lo, XX_Hi);
ffa_ch12_karatsub...   76       
ffa_ch12_karatsub...   77       -- Product := XX mod M
ffa_ch12_karatsub...   78       FZ_Mod(XX, Modulus, Product);
ffa_ch12_karatsub...   79       
ffa_ch12_karatsub...   80    end FZ_Mod_Sqr;
ffa_ch12_karatsub...   81    
ffa_ch12_karatsub...   82    
ffa_ch16_miller_r...   83    -- (Barrettronic) Modular Squaring, using given Barrettoid
ffa_ch16_miller_r...   84    procedure FZ_Mod_Sqr_Barrett(X        : in  FZ;
ffa_ch16_miller_r...   85                                 Bar      : in  Barretoid;
ffa_ch16_miller_r...   86                                 Product  : out FZ) is
ffa_ch16_miller_r...   87       
ffa_ch16_miller_r...   88       -- The wordness of both operands is equal:
ffa_ch16_miller_r...   89       L     : constant Indices := X'Length;
ffa_ch16_miller_r...   90       
ffa_ch16_miller_r...   91       -- Double-width register for squaring and modulus operations
ffa_ch16_miller_r...   92       XX    : FZ(1 .. L * 2);
ffa_ch16_miller_r...   93       
ffa_ch16_miller_r...   94       -- To refer to the lower and upper halves of the working register:
ffa_ch16_miller_r...   95       XX_Lo : FZ renames XX(1     .. L);
ffa_ch16_miller_r...   96       XX_Hi : FZ renames XX(L + 1 .. XX'Last);
ffa_ch16_miller_r...   97    
ffa_ch16_miller_r...   98    begin
ffa_ch16_miller_r...   99       
ffa_ch16_miller_r...  100       -- XX_Lo:XX_Hi := X^2
ffa_ch16_miller_r...  101       FZ_Square_Buffered(X, XX_Lo, XX_Hi);
ffa_ch16_miller_r...  102       
ffa_ch16_miller_r...  103       -- Product := XX mod M
ffa_ch16_miller_r...  104       FZ_Barrett_Reduce(X => XX, Bar => Bar, XReduced => Product);
ffa_ch16_miller_r...  105       
ffa_ch16_miller_r...  106    end FZ_Mod_Sqr_Barrett;
ffa_ch16_miller_r...  107    
ffa_ch16_miller_r...  108    
ffa_ch16_miller_r...  109    -- Barrettronic Modular Exponent, using given Barrettoid
ffa_ch16_miller_r...  110    procedure FZ_Mod_Exp_Barrett(Base     : in  FZ;
ffa_ch16_miller_r...  111                                 Exponent : in  FZ;
ffa_ch16_miller_r...  112                                 Bar      : in  Barretoid;
ffa_ch16_miller_r...  113                                 Result   : out FZ) is
ffa_ch6_simplest_...  114       
ffa_ch14_barrett.kv   115       -- Double-width scratch buffer for the modular operations
ffa_ch14_barrett.kv   116       D   : FZ(1 .. Base'Length * 2);
ffa_ch6_simplest_...  117       
ffa_ch14_barrett.kv   118       -- Working register for the squaring; initially is copy of Base
ffa_ch14_barrett.kv   119       B   : FZ(Base'Range) := Base;
ffa_ch6_simplest_...  120       
ffa_ch6_simplest_...  121       -- Register for the Mux operation
ffa_ch14_barrett.kv   122       T   : FZ(Result'Range);
ffa_ch6_simplest_...  123       
ffa_ch8_randomism.kv  124       -- Buffer register for the Result
ffa_ch14_barrett.kv   125       R   : FZ(Result'Range);
ffa_ch14_barrett.kv   126       
ffa_ch6_simplest_...  127    begin
ffa_ch14_barrett.kv   128       
ffa_ch6_simplest_...  129       -- Result := 1
ffa_ch8_randomism.kv  130       WBool_To_FZ(1, R);
ffa_ch6_simplest_...  131       
ffa_ch14_barrett.kv   132       -- For each Word of the Exponent:
ffa_ch14_barrett.kv   133       for i in Exponent'Range loop
ffa_ch6_simplest_...  134          
ffa_ch14_barrett.kv   135          declare
ffa_ch14_barrett.kv   136             
ffa_ch14_barrett.kv   137             -- The current Word of the Exponent
ffa_ch14_barrett.kv   138             Wi : Word := Exponent(i);
ffa_ch14_barrett.kv   139             
ffa_ch14_barrett.kv   140          begin
ffa_ch14_barrett.kv   141             
ffa_ch14_barrett.kv   142             -- For each bit of Wi:
ffa_ch14_barrett.kv   143             for j in 1 .. Bitness loop
ffa_ch14_barrett.kv   144                
ffa_ch14_barrett.kv   145                -- T := Result * B mod Modulus
ffa_ch14_barrett.kv   146                FZ_Multiply_Unbuffered(X => R, Y => B, XY => D);
ffa_ch14_barrett.kv   147                FZ_Barrett_Reduce(X => D, Bar => Bar, XReduced => T);
ffa_ch14_barrett.kv   148                
ffa_ch14_barrett.kv   149                -- Sel is the current bit of Exponent;
ffa_ch14_barrett.kv   150                --    When Sel=0 -> Result := Result;
ffa_ch14_barrett.kv   151                --    When Sel=1 -> Result := T
ffa_ch14_barrett.kv   152                FZ_Mux(X => R, Y => T, Result => R, Sel => Wi and 1);
ffa_ch14_barrett.kv   153                
ffa_ch14_barrett.kv   154                -- Advance to the next bit of Wi (i.e. next bit of Exponent)
ffa_ch14_barrett.kv   155                Wi := Shift_Right(Wi, 1);
ffa_ch14_barrett.kv   156                
ffa_ch14_barrett.kv   157                -- B := B^2 mod Modulus
ffa_ch14_barrett.kv   158                FZ_Square_Unbuffered(X => B, XX => D);
ffa_ch14_barrett.kv   159                FZ_Barrett_Reduce(X => D, Bar => Bar, XReduced => B);
ffa_ch14_barrett.kv   160                
ffa_ch14_barrett.kv   161             end loop;
ffa_ch6_simplest_...  162          
ffa_ch14_barrett.kv   163          end;
ffa_ch6_simplest_...  164          
ffa_ch6_simplest_...  165       end loop;
ffa_ch6_simplest_...  166       
ffa_ch8_randomism.kv  167       -- Output the Result:
ffa_ch8_randomism.kv  168       Result := R;
ffa_ch8_randomism.kv  169       
ffa_ch16_miller_r...  170    end FZ_Mod_Exp_Barrett;
ffa_ch16_miller_r...  171    
ffa_ch16_miller_r...  172    
ffa_ch16_miller_r...  173    -- (Barrettronic) Modular Exponent: Result := Base^Exponent mod Modulus
ffa_ch16_miller_r...  174    procedure FZ_Mod_Exp(Base     : in  FZ;
ffa_ch16_miller_r...  175                         Exponent : in  FZ;
ffa_ch16_miller_r...  176                         Modulus  : in  FZ;
ffa_ch16_miller_r...  177                         Result   : out FZ) is
ffa_ch16_miller_r...  178       
ffa_ch16_miller_r...  179       -- Space for Barrettoid
ffa_ch16_miller_r...  180       Bar : Barretoid(ZXMLength       => Modulus'Length + 1,
ffa_ch16_miller_r...  181                       BarretoidLength => 2 * Base'Length);
ffa_ch16_miller_r...  182       
ffa_ch16_miller_r...  183    begin
ffa_ch16_miller_r...  184       
ffa_ch16_miller_r...  185       -- First, pre-compute the Barretoid for the given Modulus:
ffa_ch16_miller_r...  186       FZ_Make_Barrettoid(Modulus => Modulus, Result => Bar);
ffa_ch16_miller_r...  187       
ffa_ch16_miller_r...  188       -- Compute the modular exponentiation using the above Barrettoid:
ffa_ch16_miller_r...  189       FZ_Mod_Exp_Barrett(Base     => Base,
ffa_ch16_miller_r...  190                          Exponent => Exponent,
ffa_ch16_miller_r...  191                          Bar      => Bar,
ffa_ch16_miller_r...  192                          Result   => Result);
ffa_ch16_miller_r...  193       
ffa_ch6_simplest_...  194    end FZ_Mod_Exp;
ffa_ch6_simplest_...  195    
ffa_ch6_simplest_...  196 end FZ_ModEx;