------------------------------------------------------------------------------ ------------------------------------------------------------------------------ -- 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 FZ_Type; use FZ_Type; with W_Pred; with FZ_Lim; with FZ_Basic; with FZ_IO; with FZ_Cmp; with FZ_Pred; with FZ_BitOp; with FZ_Divis; with FZ_ModEx; with FZ_Measr; with FZ_QShft; with FZ_LoMul; with FZ_Prime; -- FFA Exports package FFA is pragma Pure; ---------------------------------------------------------------------------- --- Current 'deg. Kelvin' Version of FFA ---------------------------------------------------------------------------- FFA_K_Version : constant Natural := 200; ---------------------------------------------------------------------------- --- Fundamental Types and Sizes ---------------------------------------------------------------------------- subtype Word is Words.Word; subtype WBool is Words.WBool; subtype Nibble is Words.Nibble; subtype FZ is FZ_Type.FZ; subtype Indices is FZ_Type.Indices; subtype FZBit_Index is FZ_Type.FZBit_Index; subtype Char_Count is FZ_IO.Char_Count; Bitness : Positive renames Words.Bitness; ---------------------------------------------------------------------------- --- Word Predicates ---------------------------------------------------------------------------- -- Return 1 if N is equal to 0; otherwise return 0. function FFA_Word_ZeroP(N : in Word) return WBool renames W_Pred.W_ZeroP; -- Return 1 if N is unequal to 0; otherwise return 0. function FFA_Word_NZeroP(N : in Word) return WBool renames W_Pred.W_NZeroP; -- Return WBool-complement of N. function FFA_Word_Not(N : in WBool) return WBool renames W_Pred.W_Not; -- Return 1 if N is odd; otherwise return 0. function FFA_Word_OddP(N : in Word) return WBool renames W_Pred.W_OddP; -- Return 1 if A is equal to B ; otherwise return 0. function FFA_Word_EqP(A : in Word; B : in Word) return WBool renames W_Pred.W_EqP; ---------------------------------------------------------------------------- --- FZ Limits ---------------------------------------------------------------------------- FFA_Validity_Rule_Doc : String renames FZ_Lim.FZ_Validity_Rule_Doc; -- Determine if a proposed FFA Bitness is valid. function FFA_FZ_Valid_Bitness_P(B : in Positive) return Boolean renames FZ_Lim.FZ_Valid_Bitness_P; ---------------------------------------------------------------------------- --- FZ Basics ---------------------------------------------------------------------------- -- Determine the Bitness of N function FFA_FZ_Bitness(N : in FZ) return Bit_Count renames FZ_Basic.FZ_Bitness; -- N := 0 procedure FFA_FZ_Clear(N : out FZ) renames FZ_Basic.FZ_Clear; -- Set given FZ to a given truth value procedure FFA_WBool_To_FZ(V : in WBool; N : out FZ) renames FZ_Basic.WBool_To_FZ; -- First Word of N := Source procedure FFA_FZ_Set_Head(N : out FZ; Source : in Word) renames FZ_Basic.FZ_Set_Head; -- First Word of N function FFA_FZ_Get_Head(N : in FZ) return Word renames FZ_Basic.FZ_Get_Head; -- Exchange X and Y procedure FFA_FZ_Swap(X : in out FZ; Y : in out FZ) with Pre => X'Length = Y'Length; -- Constant-time MUX: Sel = 0: Result := X; Sel = 1: Result := Y procedure FFA_FZ_Mux(X : in FZ; Y : in FZ; Result : out FZ; Sel : in WBool) with Pre => X'Length = Y'Length and X'Length = Result'Length; ---------------------------------------------------------------------------- --- FZ IO Operations ---------------------------------------------------------------------------- -- Expand FZ N by nibble D, and determine whether this operation overflowed procedure FFA_FZ_Insert_Bottom_Nibble(N : in out FZ; D : in Nibble; Overflow : out WBool) renames FZ_IO.FZ_Insert_Bottom_Nibble; -- Determine the number of ASCII characters required to represent N function FFA_FZ_ASCII_Length(N : in FZ) return Char_Count renames FZ_IO.FZ_ASCII_Length; -- Write an ASCII hex representation of N into existing string buffer S procedure FFA_FZ_To_Hex_String(N : in FZ; S : out String) renames FZ_IO.FZ_To_Hex_String; ---------------------------------------------------------------------------- --- Comparison Predicate Operations on FZ ---------------------------------------------------------------------------- -- 1 iff X == Y (branch-free); else 0 function FFA_FZ_EqP(X : in FZ; Y: in FZ) return WBool renames FZ_Cmp.FZ_EqP; -- 1 iff X < Y (branch-free); else 0 function FFA_FZ_LessThanP(X : in FZ; Y : in FZ) return WBool renames FZ_Cmp.FZ_LessThanP; -- 1 iff X > Y (branch-free); else 0 function FFA_FZ_GreaterThanP(X : in FZ; Y : in FZ) return WBool renames FZ_Cmp.FZ_GreaterThanP; ---------------------------------------------------------------------------- --- Fundamental Predicate Operations on FZ ---------------------------------------------------------------------------- -- 1 iff N == 0 (branch-free); else 0 function FFA_FZ_ZeroP(N : in FZ) return WBool renames FZ_Pred.FZ_ZeroP; -- 1 iff N != 0 (branch-free); else 0 function FFA_FZ_NZeroP(N : in FZ) return WBool renames FZ_Pred.FZ_NZeroP; -- 1 iff N is odd function FFA_FZ_OddP(N : in FZ) return WBool renames FZ_Pred.FZ_OddP; ---------------------------------------------------------------------------- --- Bitwise Operations on FZ ---------------------------------------------------------------------------- -- Result := X & Y procedure FFA_FZ_And(X : in FZ; Y : in FZ; Result : out FZ) with Pre => X'Length = Y'Length and X'Length = Result'Length; -- N := N & W, W is a Word procedure FFA_FZ_And_W(N : in out FZ; W : in Word) renames FZ_BitOp.FZ_And_W; -- Result := X | Y procedure FFA_FZ_Or(X : in FZ; Y : in FZ; Result : out FZ) with Pre => X'Length = Y'Length and X'Length = Result'Length; -- N := N | W, W is a Word procedure FFA_FZ_Or_W(N : in out FZ; W : in Word) renames FZ_BitOp.FZ_Or_W; -- Result := X ^ Y procedure FFA_FZ_Xor(X : in FZ; Y : in FZ; Result : out FZ) with Pre => X'Length = Y'Length and X'Length = Result'Length; -- N := N ^ W, W is a Word procedure FFA_FZ_Xor_W(N : in out FZ; W : in Word) renames FZ_BitOp.FZ_Xor_W; -- NotN := ~N ('ones complement') procedure FFA_FZ_Not(N : in FZ; NotN : out FZ) with Pre => N'Length = NotN'Length; ---------------------------------------------------------------------------- --- Basic Arithmetic on FZ ---------------------------------------------------------------------------- -- Sum := X + Y; Overflow := Carry procedure FFA_FZ_Add(X : in FZ; Y : in FZ; Sum : out FZ; Overflow : out WBool) with Pre => X'Length = Y'Length and X'Length = Sum'Length; -- Difference := X - Y; Underflow := Borrow procedure FFA_FZ_Subtract(X : in FZ; Y : in FZ; Difference : out FZ; Underflow : out WBool) with Pre => X'Length = Y'Length and X'Length = Difference'Length; ---------------------------------------------------------------------------- --- Division on FZ ---------------------------------------------------------------------------- -- Dividend is divided by Divisor, producing Quotient and Remainder. -- WARNING: NO div0 test here! Caller must test. procedure FFA_FZ_IDiv(Dividend : in FZ; Divisor : in FZ; Quotient : out FZ; Remainder : out FZ) renames FZ_Divis.FZ_IDiv; -- Exactly same thing as IDiv, but keep only the Quotient procedure FFA_FZ_Div(Dividend : in FZ; Divisor : in FZ; Quotient : out FZ) renames FZ_Divis.FZ_Div; -- Modulus. procedure FFA_FZ_Mod(Dividend : in FZ; Divisor : in FZ; Remainder : out FZ) renames FZ_Divis.FZ_Mod; ---------------------------------------------------------------------------- --- Multiplication on FZ ---------------------------------------------------------------------------- -- Multiplier. Preserves the inputs. procedure FFA_FZ_Multiply(X : in FZ; Y : in FZ; XY_Lo : out FZ; XY_Hi : out FZ) with Pre => X'Length = Y'Length and XY_Lo'Length = XY_Hi'Length and XY_Lo'Length = ((X'Length + Y'Length) / 2); -- Square. Preserves the inputs. procedure FFA_FZ_Square(X : in FZ; XX_Lo : out FZ; XX_Hi : out FZ) with Pre => XX_Lo'Length = X'Length and XX_Hi'Length = X'Length and X'Length mod 2 = 0; -- Low-Only Multiplier. Preserves the inputs. procedure FFA_FZ_Low_Multiply(X : in FZ; Y : in FZ; XY : out FZ) renames FZ_LoMul.FZ_Low_Multiply_Buffered; ---------------------------------------------------------------------------- --- Modular Operations on FZ ---------------------------------------------------------------------------- -- Modular Multiply: Product := X*Y mod Modulus procedure FFA_FZ_Modular_Multiply(X : in FZ; Y : in FZ; Modulus : in FZ; Product : out FZ) renames FZ_ModEx.FZ_Mod_Mul; -- Modular Squaring: Product := X*X mod Modulus procedure FFA_FZ_Modular_Square(X : in FZ; Modulus : in FZ; Product : out FZ) renames FZ_ModEx.FZ_Mod_Sqr; -- Modular Exponent: Result := Base^Exponent mod Modulus procedure FFA_FZ_Modular_Exponentiate(Base : in FZ; Exponent : in FZ; Modulus : in FZ; Result : out FZ) renames FZ_ModEx.FZ_Mod_Exp; ---------------------------------------------------------------------------- --- Other Operations on FZ ---------------------------------------------------------------------------- -- Find the index of eldest nonzero bit ( 0 if none, or 1 .. FZBitness ) function FFA_FZ_Measure(N : in FZ) return FZBit_Index renames FZ_Measr.FZ_Measure; -- Constant-time arbitrary right-shift. procedure FFA_FZ_Quiet_ShiftRight(N : in FZ; ShiftedN : in out FZ; Count : in FZBit_Index) renames FZ_QShft.FZ_Quiet_ShiftRight; -- Constant-time arbitrary left-shift. procedure FFA_FZ_Quiet_ShiftLeft(N : in FZ; ShiftedN : in out FZ; Count : in FZBit_Index) renames FZ_QShft.FZ_Quiet_ShiftLeft; -- Find Greatest Common Divisor (GCD) of X and Y. procedure FFA_FZ_Greatest_Common_Divisor(X : in FZ; Y : in FZ; Result : out FZ) with Pre => X'Length = Y'Length and X'Length = Result'Length; -- Constant-Time Miller-Rabin Test on N using the given Witness. -- Witness will be used as-is if it conforms to the valid bounds, -- i.e. 2 <= Witness <= N - 2; otherwise will be transformed into a -- valid Witness via modular arithmetic. -- Outputs ONE if N WAS FOUND composite; ZERO if NOT FOUND. -- Handles degenerate cases of N that M-R per se cannot eat: -- N=0, N=1: ALWAYS 'FOUND COMPOSITE'; 2, 3 - ALWAYS 'NOT FOUND'. -- If N is Even and not equal to 2, N is ALWAYS 'FOUND COMPOSITE.' -- For ALL other N, the output is equal to that of the M-R test. function FFA_FZ_MR_Composite_On_Witness(N : in FZ; Witness : in FZ) return WBool renames FZ_Prime.FZ_MR_Composite_On_Witness; end FFA;