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 20 with Words; use Words; 21 with FZ_Type; use FZ_Type; 22 23 24 package FZ_Prime is 25 26 pragma Pure; 27 28 -- Constant-Time Miller-Rabin Test on N using the given Witness. 29 -- Witness will be used as-is if it conforms to the valid bounds, 30 -- i.e. 2 <= Witness <= N - 2; otherwise will be transformed into a 31 -- valid Witness via modular arithmetic. 32 -- Outputs ONE if N WAS FOUND composite; ZERO if NOT FOUND. 33 -- Handles degenerate cases of N that M-R per se cannot eat: 34 -- N=0, N=1: ALWAYS 'FOUND COMPOSITE'; 2, 3 - ALWAYS 'NOT FOUND'. 35 -- If N is Even and not equal to 2, N is ALWAYS 'FOUND COMPOSITE.' 36 -- For ALL other N, the output is equal to that of the M-R test. 37 function FZ_MR_Composite_On_Witness(N : in FZ; 38 Witness : in FZ) return WBool 39 with Pre => N'Length = Witness'Length; 40 41 end FZ_Prime;