Finite Field Arithmetic

fz_prime.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 with Word_Ops; use Word_Ops;
  20 with W_Pred;   use W_Pred;
  21 with W_Shifts; use W_Shifts;
  22 
  23 with FZ_Basic; use FZ_Basic;
  24 with FZ_QShft; use FZ_QShft;
  25 with FZ_Arith; use FZ_Arith;
  26 with FZ_Divis; use FZ_Divis;
  27 with FZ_Pred;  use FZ_Pred;
  28 with FZ_Cmp;   use FZ_Cmp;
  29 with FZ_Barr;  use FZ_Barr;
  30 with FZ_ModEx; use FZ_ModEx;
  31 
  32 
  33 package body FZ_Prime is
  34    
  35    -- Find the highest power of 2 which divides N. ( or 0 if N is zero. )
  36    function FZ_Count_Bottom_Zeros(N : in FZ) return FZBit_Index is
  37       
  38       -- The result (default : 0, will remain 0 if N is in fact zero)
  39       Index     : Word := 0;
  40       
  41       -- The currently-examined Word, starting from the highest
  42       Ni        : Word;
  43       
  44       -- The most recently-seen nonzero Word, if indeed any exist
  45       W         : Word := 0;
  46       
  47       -- 1 if currently-examined Word is zero, otherwise 0
  48       NiZ       : WBool;
  49       
  50    begin
  51       
  52       -- Find lowest non-zero Word (or simply stop at lowest, if N = 0)
  53       for i in reverse 0 .. Indices(N'Length - 1) loop
  54          Ni    := N(N'First + i);              -- Ni := current Word;
  55          NiZ   := W_ZeroP(Ni);                 -- ... is this Word = 0?
  56          Index := W_Mux(Word(i), Index, NiZ);  -- If NO, save its Index,
  57          W     := W_Mux(Ni,      W,     NiZ);  -- ... and save the Word.
  58       end loop;
  59       
  60       -- Set Index to be the bit-position of the lowest non-zero Word:
  61       Index := Shift_Left(Index, BitnessLog2); -- Index := Index * Bitness
  62       
  63       -- Handle degenerate case: if W is equal to 0, Index is not changed;
  64       -- Otherwise, start by advancing Index by an entire Word Bitness:
  65       Index := Index + ((0 - W_NZeroP(W)) and Word(Bitness));
  66       
  67       -- Now crank back the Index by the number of high bits of W (i.e.
  68       -- starting from its top) that must be discarded for W to become zero:
  69       for b in 1 .. Bitness loop
  70          
  71          -- If W is non-zero at this time, decrement the Index:
  72          Index := Index - W_NZeroP(W);
  73          
  74          -- Advance W left, i.e. discard the top bit of it:
  75          W     := Shift_Left(W, 1);
  76          
  77       end loop;
  78       
  79       -- If N = 0, result will be 0; otherwise: length of bottom zeros in N.
  80       return FZBit_Index(Index);
  81       
  82    end FZ_Count_Bottom_Zeros;
  83    
  84    
  85    -- Constant-Time Miller-Rabin Test on N using the given Witness.
  86    -- Witness will be used as-is if it conforms to the valid bounds,
  87    -- i.e. 2 <= Witness <= N - 2; otherwise will be transformed into a
  88    -- valid Witness via modular arithmetic.
  89    -- Outputs ONE if N WAS FOUND composite; ZERO if NOT FOUND.
  90    -- Handles degenerate cases of N that M-R per se cannot eat:
  91    -- N=0, N=1: ALWAYS 'FOUND COMPOSITE'; 2, 3 - ALWAYS 'NOT FOUND'.
  92    -- If N is Even and not equal to 2, N is ALWAYS 'FOUND COMPOSITE.'
  93    -- For ALL other N, the output is equal to that of the M-R test.
  94    function FZ_MR_Composite_On_Witness(N       : in  FZ;
  95                                        Witness : in  FZ) return WBool is
  96       
  97       -- Widths of N, Witness, and Result are equal :
  98       subtype Width is Word_Index range N'Range;
  99       
 100       -- Whether N is 'small' (i.e. 1 Word) and therefore possibly degenerate :
 101       N_Is_Small       : constant WBool := FZ_OneWordP(N);
 102       
 103       -- Head of N, for detecting (and handling) the degenerate-N case :
 104       N_Head           : constant Word  := FZ_Get_Head(N);
 105       
 106       -- Zero and One are defined as COMPOSITE degenerate cases of N :
 107       N_Is_Zero_Or_One : constant WBool
 108         := N_Is_Small and (W_EqP(N_Head, 0) or W_EqP(N_Head, 1));
 109       
 110       -- Two and Three are PRIME degenerate cases of N :
 111       N_Is_Two         : constant WBool := N_Is_Small and W_EqP(N_Head, 2);
 112       N_Is_Three       : constant WBool := N_Is_Small and W_EqP(N_Head, 3);
 113       
 114       -- The COMPOSITE degenerate case of N where N != 2 and N is Even :
 115       N_Ne_2_Is_Even   : constant WBool :=
 116         (1 - N_Is_Two) and (1 - W_OddP(N_Head));
 117       
 118       -- Degeneracy latch. If N is Zero or One, then set immediately :
 119       Degen_Composite  : constant WBool := N_Is_Zero_Or_One or N_Ne_2_Is_Even;
 120       
 121       -- Possible-primality latch. If N is Two or Three, then set immediately :
 122       Possibly_Prime   : WBool := N_Is_Two or N_Is_Three;
 123       
 124       -- The writable copy of N that we will operate on :
 125       X                : FZ(Width) := N;
 126       
 127       -- Potentially-replaced head of X (if degenerate N) :
 128       X_Head           : Word := N_Head;
 129       
 130       -- Will be Barrettoid(X), for operations modulo X :
 131       XBar             : Barretoid(ZXMLength       => X'Length + 1,
 132                                    BarretoidLength => 2 * X'Length);
 133       
 134       -- The Bound Witness, constrained to valid range 2 <= BW <= X - 2 :
 135       BW               : FZ(Width);
 136       
 137       -- Head of BW, for detecting crossing of the lower bound :
 138       BW_Head          : Word;
 139       
 140       -- X - 1 (for M-R proper, and to constrain BW) :
 141       X_Minus_One      : FZ(Width);
 142       
 143       -- X - 1 = 2^R * K, with K odd :
 144       K                : FZ(Width);
 145       R                : FZBit_Index;
 146       
 147       -- Working register for all M-R modular operations :
 148       T                : FZ(Width);
 149       
 150       -- For subtraction where no underflow can happen, barring cosmic ray:
 151       NoCarry          : WZeroOrDie := 0;
 152       
 153    begin
 154       
 155       -- First: X, which will remain equal to N unless N is degenerate:
 156       
 157       -- If N is one of the two prohibited small primes (2,3) X will become 5:
 158       X_Head := W_Mux(A => X_Head, B => 5, Sel => Possibly_Prime);
 159       
 160       -- If one of the two prohibited small composites (0,1), or even, then 9:
 161       X_Head := W_Mux(A => X_Head, B => 9, Sel => Degen_Composite);
 162       
 163       -- Given as we're stuck carrying out M-R even if N is degenerate case,
 164       -- then let the M-R do The Right Thing, for added cosmic ray resistance.
 165       
 166       -- X gets a new head, if N was a degenerate case; else keeps old head:
 167       FZ_Set_Head(X, X_Head);
 168       
 169       -- Compute X - 1. As now X > 3, underflow is not permitted:
 170       FZ_Sub_W(X => X, W => 1, Difference => X_Minus_One,
 171                Underflow => NoCarry);
 172       
 173       -- Now, compute BW (Bound Witness), which satisfies 2 <= BW <= X - 2:
 174       
 175       -- First, BW := Witness mod (X - 1). After this, 0 <= BW <= X - 2:
 176       FZ_Mod(Dividend => Witness, Divisor => X_Minus_One, Remainder => BW);
 177       
 178       -- Now, adjust BW if it is found to be below Two (the lower bound) :
 179       
 180       -- Get head of BW:
 181       BW_Head := FZ_Get_Head(BW);
 182       
 183       -- If BW is equal to Zero or One, it will be forced to equal Two:
 184       BW_Head := W_Mux(A   => BW_Head,
 185                        B   => 2,
 186                        Sel => FZ_OneWordP(BW) and
 187                          (W_EqP(BW_Head, 0) or W_EqP(BW_Head, 1)));
 188       
 189       -- BW gets the new head, if it must; otherwise keeps its old head:
 190       FZ_Set_Head(BW, BW_Head);
 191       
 192       -- We finished adjusting X and BW for degeneracies, and can now M-R:
 193       
 194       -- Generate Barrettoid(X) to use in all of the modulo-X operations:
 195       FZ_Make_Barrettoid(Modulus => X, Result => XBar);
 196       
 197       -- Find R >= 1, and odd K, where X - 1 = 2^R * K :
 198       
 199       -- ... first, find R, the largest power of two which divides X - 1 :
 200       R := FZ_Count_Bottom_Zeros(X_Minus_One);
 201       
 202       -- ... and now obtain K := X / 2^R, i.e., K := X >> R :
 203       FZ_Quiet_ShiftRight(N => X_Minus_One, ShiftedN => K, Count => R);
 204       
 205       -- T := BW^K mod X
 206       FZ_Mod_Exp_Barrett(Base => BW, Exponent => K, Bar => XBar, Result => T);
 207       
 208       -- if T = 1 or T = X - 1, then X is possibly-prime:
 209       Possibly_Prime := Possibly_Prime or
 210         FZ_EqP_W(T, 1) or FZ_EqP(T, X_Minus_One);
 211       
 212       -- Needs R - 1 times, but perform for max possible count (gated):
 213       for i in 1 .. FZ_Bitness(N) - 1 loop
 214          
 215          -- T := T^2 mod X
 216          FZ_Mod_Sqr_Barrett(X => T, Bar => XBar, Product => T);
 217          
 218          -- if T = X - 1, and i < R, then X is possibly-prime:
 219          Possibly_Prime := Possibly_Prime or 
 220            (FZ_EqP(T, X_Minus_One) and W_LtP(Word(i), Word(R)));
 221          
 222       end loop;
 223       
 224       -- The output, which will be 1 iff X WAS FOUND to be composite via BW,
 225       -- ... or if X was found to equal Zero or One (without regard to BW.)
 226       return (1 - Possibly_Prime) or Degen_Composite;
 227       -- If X was found to equal Two or Three, output will be 0 (under any BW).
 228       
 229    end FZ_MR_Composite_On_Witness;
 230    
 231 end FZ_Prime;