ffa_ch16_miller_r... 1 ------------------------------------------------------------------------------
ffa_ch16_miller_r... 2 ------------------------------------------------------------------------------
ffa_ch16_miller_r... 3 -- This file is part of 'Finite Field Arithmetic', aka 'FFA'. --
ffa_ch16_miller_r... 4 -- --
ffa_ch16_miller_r... 5 -- (C) 2019 Stanislav Datskovskiy ( www.loper-os.org ) --
ffa_ch16_miller_r... 6 -- http://wot.deedbot.org/17215D118B7239507FAFED98B98228A001ABFFC7.html --
ffa_ch16_miller_r... 7 -- --
ffa_ch16_miller_r... 8 -- You do not have, nor can you ever acquire the right to use, copy or --
ffa_ch16_miller_r... 9 -- distribute this software ; Should you use this software for any purpose, --
ffa_ch16_miller_r... 10 -- or copy and distribute it to anyone or in any manner, you are breaking --
ffa_ch16_miller_r... 11 -- the laws of whatever soi-disant jurisdiction, and you promise to --
ffa_ch16_miller_r... 12 -- continue doing so for the indefinite future. In any case, please --
ffa_ch16_miller_r... 13 -- always : read and understand any software ; verify any PGP signatures --
ffa_ch16_miller_r... 14 -- that you use - for any purpose. --
ffa_ch16_miller_r... 15 -- --
ffa_ch16_miller_r... 16 -- See also http://trilema.com/2015/a-new-software-licensing-paradigm . --
ffa_ch16_miller_r... 17 ------------------------------------------------------------------------------
ffa_ch16_miller_r... 18 ------------------------------------------------------------------------------
ffa_ch16_miller_r... 19
ffa_ch16_miller_r... 20 with Words; use Words;
ffa_ch16_miller_r... 21 with FZ_Type; use FZ_Type;
ffa_ch16_miller_r... 22
ffa_ch16_miller_r... 23
ffa_ch16_miller_r... 24 package FZ_Prime is
ffa_ch16_miller_r... 25
ffa_ch16_miller_r... 26 pragma Pure;
ffa_ch16_miller_r... 27
ffa_ch16_miller_r... 28 -- Constant-Time Miller-Rabin Test on N using the given Witness.
ffa_ch16_miller_r... 29 -- Witness will be used as-is if it conforms to the valid bounds,
ffa_ch16_miller_r... 30 -- i.e. 2 <= Witness <= N - 2; otherwise will be transformed into a
ffa_ch16_miller_r... 31 -- valid Witness via modular arithmetic.
ffa_ch16_miller_r... 32 -- Outputs ONE if N WAS FOUND composite; ZERO if NOT FOUND.
ffa_ch16_miller_r... 33 -- Handles degenerate cases of N that M-R per se cannot eat:
ffa_ch16_miller_r... 34 -- N=0, N=1: ALWAYS 'FOUND COMPOSITE'; 2, 3 - ALWAYS 'NOT FOUND'.
ffa_ch16_miller_r... 35 -- If N is Even and not equal to 2, N is ALWAYS 'FOUND COMPOSITE.'
ffa_ch16_miller_r... 36 -- For ALL other N, the output is equal to that of the M-R test.
ffa_ch16_miller_r... 37 function FZ_MR_Composite_On_Witness(N : in FZ;
ffa_ch16_miller_r... 38 Witness : in FZ) return WBool
ffa_ch16_miller_r... 39 with Pre => N'Length = Witness'Length;
ffa_ch16_miller_r... 40
ffa_ch16_miller_r... 41 end FZ_Prime;