tree checksum vpatch file split hunks

all signers: bvt diana_coman asciilifeform

antecedents: ffa_ch15_gcd.kv

press order:

ffa_ch1_genesis.kvasciilifeform bvt diana_coman
ffa_ch2_logicals.kvasciilifeform bvt diana_coman
ffa_ch3_shifts.kvasciilifeform bvt diana_coman
ffa_ch4_ffacalc.kvasciilifeform bvt diana_coman
ffa_ch5_egypt.kvasciilifeform bvt diana_coman
ffa_ch6_simplest_rsa.kvasciilifeform bvt diana_coman
ffa_ch7_turbo_egyptians.kvasciilifeform diana_coman
ffa_ch8_randomism.kvasciilifeform diana_coman
ffa_ch9_exodus.kvasciilifeform
ffa_ch10_karatsuba.kvasciilifeform
ffa_ch11_tuning_and_api.kvasciilifeform
ffa_ch12_karatsuba_redux.kvasciilifeform
ffa_w_borrow_expr.kvasciilifeform diana_coman
ffa_ch13_measure_and_qshifts.kvasciilifeform
ffa_ch14_barrett.kvasciilifeform
ffa_ch15_gcd.kvasciilifeform
ffa_ch16_miller_rabin.kvasciilifeform

patch:

- 9B65BB45012CDBE66D613823F63E75E1A8A63AB64B11B2235549FE62BDA45D09ADE27AEAFC8DF47C32D905D4400A82F80AEE488A6AE7D7795CB91E6408057EAB
+ 590DA100178588E299522D64788D4C3C2732B7645D5A967DB505EA91F3B08D5933C3E0642423A7E1E889B3F10A8BE3275922CDE27D63B1C0E6F25C9F11C4D2F1
ffa/MANIFEST.TXT
(14 . 3)(14 . 4)
5 551516 ffa_ch13_measure_and_qshifts "Measure and Quiet Shifts."
6 555788 ffa_ch14_barrett "Barrett's Modular Reduction."
7 557938 ffa_ch15_gcd "Greatest Common Divisor."
8 560516 ffa_ch16_miller_rabin "Miller-Rabin Method."
- 0DC7983700B4D2EEC0CD0FE41D7BE166568CAF3BEE53D635CAB6685A0FBFC4057AB6B5836A3CD74AC152973A4A6CBBCFE4C8A514942E03F3591DCD811C8D1AA2
+ 772AAAF953790FBB7D7FE6AFD0BF2DEAF77988B1376A7C169FBD21F47F5AAFF6DF87B2C333B90E8CD373C11379BA4830CEDC3A48B36C26767AC7303889EF6A69
ffa/ffacalc/ffa_calc.adb
(513 . 6)(513 . 29)
13 FFA_FZ_Clear(Stack(SP));
14 FFA_FZ_Set_Head(Stack(SP), Word(FFA_K_Version));
15
16 -- Constant-Time Miller-Rabin Test on N using the given Witness.
17 -- Witness will be used as-is if it conforms to the valid range,
18 -- i.e. 2 <= Witness <= N - 2; else will be transformed into a
19 -- valid Witness via modular arithmetic.
20 -- Outputs ONE if N WAS FOUND composite; ZERO if NOT FOUND.
21 -- Handles degenerate cases of N that M-R per se cannot eat:
22 -- N=0, N=1: ALWAYS 'FOUND COMPOS.'; 2, 3 - ALWAYS 'NOT FOUND'.
23 -- If N is Even and not equal to 2, N is ALWAYS 'FOUND COMPOS.'
24 -- For ALL other N, the output is equal to that of the M-R test.
25 -- At most 1/4 of all possible Witnesses will be 'liars' for
26 -- a particular composite N , i.e. fail to attest to its
27 -- compositivity.
28 when 'P' =>
29 Want(2);
30 declare
31 MR_Result : WBool :=
32 FFA_FZ_MR_Composite_On_Witness(N => Stack(SP - 1),
33 Witness => Stack(SP));
34 begin
35 FFA_WBool_To_FZ(MR_Result, Stack(SP - 1));
36 end;
37 Drop;
38
39 --------------
40 -- Prefixes --
41 --------------
(534 . 7)(557 . 7)
43 ---------------------------------------------------------
44 when '!' | '@' | '$' | ':' | ';' | ',' |
45 'H' | 'I' | 'J' | 'K' | 'N' |
46 'P' | 'T' | 'X' | 'Y' =>
47 'T' | 'X' | 'Y' =>
48
49 E("This Operator is not defined yet: " & C);
50 ---------------------------------------------------------
- DE74B71AD764A1253CA500C7EF1E4F285356B2A9F4CCD056F05DEB9FB99F7477488C6C03FE1CAEE82D8FF153461EE81C9E046D74DC880281C43C5AC565706A07
+ 7863511153DAAF0B1940927701245ECC7EC8AFF31C79B80CC6D8D90852F88FEDE9458D678B0AE8BC6C09A5D57465CA9CE4C699B3212EBD863BB41D9170E2C08F
ffa/ffacalc/version.ads
(24 . 7)(24 . 7)
55 ----------------------------------------------
56 -- Current 'deg. Kelvin' Version of FFACalc --
57 ----------------------------------------------
58 FFACalc_K_Version : constant Natural := 254;
59 FFACalc_K_Version : constant Natural := 253;
60 ----------------------------------------------
61
62 end Version;
- BA6B8ED841FF5C8CBADD59934821B311F6F74200C23BCBDA0B3A430C43A151B8242296D255C97C44788C6A5C97AFBE7DAC8339FD369AAFF3B509A70E9BA620F8
+ D6E1B802991B5A601E4253D419E72B22ADD215ACE76B8CDD8449C7587D7C6BBDB3A90074D67DDD33C5B7FA9A2584CAEC81DB4A658B817B7659CD3F92AF3491D7
ffa/libffa/ffa.ads
(33 . 6)(33 . 7)
67 with FZ_Measr;
68 with FZ_QShft;
69 with FZ_LoMul;
70 with FZ_Prime;
71
72
73 -- FFA Exports
(44 . 7)(45 . 7)
75 --- Current 'deg. Kelvin' Version of FFA
76 ----------------------------------------------------------------------------
77
78 FFA_K_Version : constant Natural := 254;
79 FFA_K_Version : constant Natural := 253;
80
81 ----------------------------------------------------------------------------
82 --- Fundamental Types and Sizes
(330 . 4)(331 . 17)
84 Result : out FZ)
85 with Pre => X'Length = Y'Length and X'Length = Result'Length;
86
87 -- Constant-Time Miller-Rabin Test on N using the given Witness.
88 -- Witness will be used as-is if it conforms to the valid bounds,
89 -- i.e. 2 <= Witness <= N - 2; otherwise will be transformed into a
90 -- valid Witness via modular arithmetic.
91 -- Outputs ONE if N WAS FOUND composite; ZERO if NOT FOUND.
92 -- Handles degenerate cases of N that M-R per se cannot eat:
93 -- N=0, N=1: ALWAYS 'FOUND COMPOSITE'; 2, 3 - ALWAYS 'NOT FOUND'.
94 -- If N is Even and not equal to 2, N is ALWAYS 'FOUND COMPOSITE.'
95 -- For ALL other N, the output is equal to that of the M-R test.
96 function FFA_FZ_MR_Composite_On_Witness(N : in FZ;
97 Witness : in FZ) return WBool
98 renames FZ_Prime.FZ_MR_Composite_On_Witness;
99
100 end FFA;
- A6774EA126B6431E912686B5269349926976A8685A61817E99FE468B61056842A0881B0569D5EC0DE27B904B456BD13350FC4F939286A5633C08A7888DD23C4B
+ BE7752AC12AD772033C57E4E844A62A2451B9E398A6B5F3CA4CD8873B0ADAF6CCEBE8093C3D4F4D9A4A40CDE4FC48282E5E04579D9F284D0170A32B4DDB06777
ffa/libffa/fz_arith.adb
(161 . 6)(161 . 26)
105 end FZ_Sub;
106
107
108 -- Difference := X - W; Underflow := Borrow
109 procedure FZ_Sub_W(X : in FZ;
110 W : in Word;
111 Difference : out FZ;
112 Underflow : out WBool) is
113 Borrow : Word := W;
114 begin
115 for i in 0 .. Word_Index(X'Length - 1) loop
116 declare
117 A : constant Word := X(X'First + i);
118 S : constant Word := A - Borrow;
119 begin
120 Difference(Difference'First + i) := S;
121 Borrow := W_Borrow(A, 0, S);
122 end;
123 end loop;
124 Underflow := Borrow;
125 end FZ_Sub_W;
126
127
128 -- Destructive: If Cond is 1, NotN := ~N; otherwise NotN := N.
129 procedure FZ_Not_Cond_D(N : in out FZ;
130 Cond : in WBool)is
- 5AD89E1C806E453F5F1A37C024F28B0A37D535395C301DE29AC3488A29F4670BF7517FE870EEA5B17033EC718B35A02A21CB6127B3A26B95D1F3631B83495F63
+ 922B4A0CACE3230D1CEE982C66C0D1237E0510F74D05E5B612947F5998FED01A655960731C392FB4F868AF2B8260ACBE0CA51E6C8A40E334C9698BDCE8F0A54E
ffa/libffa/fz_arith.ads
(33 . 7)(33 . 7)
135 OF_In : in WBool := 0);
136 pragma Inline_Always(FZ_Add_D);
137
138 -- Destructive Add: X := X + W; Overflow := Carry
139 -- Destructive Add: X := X + W; Overflow := Carry
140 procedure FZ_Add_D_W(X : in out FZ;
141 W : in Word;
142 Overflow : out WBool);
(62 . 12)(62 . 19)
144 Sum : out FZ);
145 pragma Inline_Always(FZ_Add_Gated);
146
147 -- Destructive Sub: X := X - Y; Underflow := Borrow
148 -- Destructive Subtract: X := X - Y; Underflow := Borrow
149 procedure FZ_Sub_D(X : in out FZ;
150 Y : in FZ;
151 Underflow : out WBool);
152 pragma Inline_Always(FZ_Sub_D);
153
154 -- Difference := X - W; Underflow := Borrow
155 procedure FZ_Sub_W(X : in FZ;
156 W : in Word;
157 Difference : out FZ;
158 Underflow : out WBool);
159 pragma Inline_Always(FZ_Sub_W);
160
161 -- Difference := X - Y; Underflow := Borrow
162 procedure FZ_Sub(X : in FZ;
163 Y : in FZ;
- 83D6EB138AF7DBBE49A29FBD4AF186EA79F8D4441FD84814316E84C20DE20614F7B9D69B3BD8E160BA37FC6C30B83AEC2CCC26600E289D87225C677686C6072B
+ BAEFDDB79033F5D5657EC6C1685BBD6EC468F41535215B0D88CACC9089BBBD0CE073352C8EBC287C81EAD2BE8A33972A0CE6BB4F3DFC19B0CD8A048121173ACE
ffa/libffa/fz_barr.adb
(51 . 8)(51 . 8)
168 -- `Md///////+mMMMMys////////sh/- -yy/////////////////////////dM` --
169 -- -ssssssssymssssssssssssssssso- .+ossssssssssssssssssssssssssss- --
170 -- --
171 --Ch. 14A: Barrett’s Modular Reduction: http://www.loper-os.org/?p=2842 --
172 --Ch. 14A-Bis: Barrett’s Physical Bounds: http://www.loper-os.org/?p=2875 --
173 --Ch. 14A: Barrett's Modular Reduction: http://www.loper-os.org/?p=2842 --
174 --Ch. 14A-Bis: Barrett's Physical Bounds: http://www.loper-os.org/?p=2875 --
175 -- --
176 -----------------------------------------------------------------------------
177
- 45E9005159D1D31DB9308676B44C7E70CCC98F1E2C01039510E17F332E24CAE7C0B95854E043FFB4B245340B2277B8A99FFE92BD7CA1CDDBAD38BD1B7EE0A7AA
+ F868F341DE78088C46182617DFE0C6D4ECBE52560FA457AD9C1B2F592566CD292890E8E0345F9799C98A5514192D765D2877F1A16C47A341AF7D31099084007C
ffa/libffa/fz_cmp.adb
(19 . 6)(19 . 7)
182
183 with W_Pred; use W_Pred;
184 with FZ_Arith; use FZ_Arith;
185 with FZ_Pred; use FZ_Pred;
186
187
188 package body FZ_Cmp is
(38 . 6)(39 . 13)
190 end FZ_EqP;
191
192
193 -- 1 iff X == W (branch-free); else 0
194 function FZ_EqP_W(X : in FZ; W : in Word) return WBool is
195 begin
196 return FZ_OneWordP(X) and W_EqP(X(X'First), W);
197 end FZ_EqP_W;
198
199
200 -- 1 iff X < Y (branch-free); else 0
201 function FZ_LessThanP(X : in FZ; Y : in FZ) return WBool is
202 Scratch : FZ(X'Range);
- 81851EEDEADDE7D3E5CDDB55027C3D65224C3600EE45FC378AC509D8578B458F823F93227BD7010000C890BA9574D57D3BC3FFF86A795D5A45E614CAE0B0AA2B
+ 0B578E5293749B2EDDE1FD1C4E538CDAD8C9E806E44471E331230DD9CDE52E216D9F318DFA8171EA820E367F55C9071787A952DE8E389B50735E622671706E6B
ffa/libffa/fz_cmp.ads
(33 . 6)(33 . 10)
207 function FZ_EqP(X : in FZ; Y: in FZ) return WBool
208 with Pre => X'Length = Y'Length;
209
210 -- 1 iff X == W (branch-free); else 0
211 function FZ_EqP_W(X : in FZ; W : in Word) return WBool;
212 pragma Inline_Always(FZ_EqP_W);
213
214 -- 1 iff X < Y (branch-free); else 0
215 function FZ_LessThanP(X : in FZ; Y : in FZ) return WBool
216 with Pre => X'Length = Y'Length;
- D1F331872729DE629191F57371544DA4AC672DCE61B7CD9829912EAA07DAD4628A297AFD91AB2A923B39BF640AB3787F4BA6662119B2A4FD9C7C79B82B11E097
+ 5D7FFD960A5F49E0FCB3CD30EDBD2BE5E6D111A820293DAB68638966B6B2DC264A97EF05039FBECF0AB7C72E57EFB53D8BB665BC2B80D302CB31C1177E10CDB8
ffa/libffa/fz_modex.adb
(23 . 7)(23 . 6)
221 with FZ_Mul; use FZ_Mul;
222 with FZ_Sqr; use FZ_Sqr;
223 with FZ_Divis; use FZ_Divis;
224 with FZ_Barr; use FZ_Barr;
225
226
227 package body FZ_ModEx is
(81 . 11)(80 . 37)
229 end FZ_Mod_Sqr;
230
231
232 -- (Barrettronic) Modular Exponent: Result := Base^Exponent mod Modulus
233 procedure FZ_Mod_Exp(Base : in FZ;
234 Exponent : in FZ;
235 Modulus : in FZ;
236 Result : out FZ) is
237 -- (Barrettronic) Modular Squaring, using given Barrettoid
238 procedure FZ_Mod_Sqr_Barrett(X : in FZ;
239 Bar : in Barretoid;
240 Product : out FZ) is
241
242 -- The wordness of both operands is equal:
243 L : constant Indices := X'Length;
244
245 -- Double-width register for squaring and modulus operations
246 XX : FZ(1 .. L * 2);
247
248 -- To refer to the lower and upper halves of the working register:
249 XX_Lo : FZ renames XX(1 .. L);
250 XX_Hi : FZ renames XX(L + 1 .. XX'Last);
251
252 begin
253
254 -- XX_Lo:XX_Hi := X^2
255 FZ_Square_Buffered(X, XX_Lo, XX_Hi);
256
257 -- Product := XX mod M
258 FZ_Barrett_Reduce(X => XX, Bar => Bar, XReduced => Product);
259
260 end FZ_Mod_Sqr_Barrett;
261
262
263 -- Barrettronic Modular Exponent, using given Barrettoid
264 procedure FZ_Mod_Exp_Barrett(Base : in FZ;
265 Exponent : in FZ;
266 Bar : in Barretoid;
267 Result : out FZ) is
268
269 -- Double-width scratch buffer for the modular operations
270 D : FZ(1 .. Base'Length * 2);
(99 . 15)(124 . 8)
272 -- Buffer register for the Result
273 R : FZ(Result'Range);
274
275 -- Space for Barrettoid
276 Bar : Barretoid(ZXMLength => Modulus'Length + 1,
277 BarretoidLength => 2 * B'Length);
278
279 begin
280
281 -- First, pre-compute the Barretoid for the given Modulus:
282 FZ_Make_Barrettoid(Modulus => Modulus, Result => Bar);
283
284 -- Result := 1
285 WBool_To_FZ(1, R);
286
(149 . 6)(167 . 30)
288 -- Output the Result:
289 Result := R;
290
291 end FZ_Mod_Exp_Barrett;
292
293
294 -- (Barrettronic) Modular Exponent: Result := Base^Exponent mod Modulus
295 procedure FZ_Mod_Exp(Base : in FZ;
296 Exponent : in FZ;
297 Modulus : in FZ;
298 Result : out FZ) is
299
300 -- Space for Barrettoid
301 Bar : Barretoid(ZXMLength => Modulus'Length + 1,
302 BarretoidLength => 2 * Base'Length);
303
304 begin
305
306 -- First, pre-compute the Barretoid for the given Modulus:
307 FZ_Make_Barrettoid(Modulus => Modulus, Result => Bar);
308
309 -- Compute the modular exponentiation using the above Barrettoid:
310 FZ_Mod_Exp_Barrett(Base => Base,
311 Exponent => Exponent,
312 Bar => Bar,
313 Result => Result);
314
315 end FZ_Mod_Exp;
316
317 end FZ_ModEx;
- 674B3C93EA1DB47AA9944896EF8A3D4B47B10176D2E76BE0F76DE8AB5058B84EAF59CD34E16594F914414CF407EE4D656DDDDE996A7E078DFA1E4C354A9CBB30
+ 106C1EAF0DE722A10436B1A84AA1A6B0F49D74723D62769C8A1B50B5DDDFE9BB6A96EC3448C918A97786058AA8B3F64467CD7324D777FB0AB7711F30FF6F233A
ffa/libffa/fz_modex.ads
(18 . 6)(18 . 7)
322 ------------------------------------------------------------------------------
323
324 with FZ_Type; use FZ_Type;
325 with FZ_Barr; use FZ_Barr;
326
327
328 package FZ_ModEx is
(40 . 6)(41 . 19)
330 with Pre => Modulus'Length = X'Length and
331 Product'Length = Modulus'Length;
332
333 -- (Barrettronic) Modular Squaring, using given Barrettoid
334 procedure FZ_Mod_Sqr_Barrett(X : in FZ;
335 Bar : in Barretoid;
336 Product : out FZ);
337 pragma Inline_Always(FZ_Mod_Sqr_Barrett);
338
339 -- Barrettronic Modular Exponent, using given Barrettoid
340 procedure FZ_Mod_Exp_Barrett(Base : in FZ;
341 Exponent : in FZ;
342 Bar : in Barretoid;
343 Result : out FZ);
344 pragma Inline_Always(FZ_Mod_Exp_Barrett);
345
346 -- (Barrettronic) Modular Exponent: Result := Base^Exponent mod Modulus
347 procedure FZ_Mod_Exp(Base : in FZ;
348 Exponent : in FZ;
- DCE7717443C377E450E327CA0F5681883AEA87C0EA32C3434A079D0175EA9530355D7E031DC5FCD29DF3CB22F1E8DA2EC1D57D2CB42E09180ABAA1E0D21B84C0
+ 3D4BBF3635F035298A307C1E245B67B5B47CBD9233BE5A26DBEAC74F6B65D78D1A53C966E4C58A0A81BD0CF0D1685BD871ABC02E32C4570CCDEE0997DEFDD3A3
ffa/libffa/fz_pred.adb
(50 . 4)(50 . 11)
353 return W_OddP(N(N'First));
354 end FZ_OddP;
355
356
357 -- 1 iff N fits inside one Word
358 function FZ_OneWordP(N : in FZ) return WBool is
359 begin
360 return FZ_ZeroP(N(N'First + 1 .. N'Last));
361 end FZ_OneWordP;
362
363 end FZ_Pred;
- 299605F7227834B125629ADE2FFF78CB7C8C3C4137F393A79B8C089432DA4A74F14FD0BDB97809FE972B6605BACD5D8D40D519708A8926B19B668A637A4021C0
+ 97C4D64EC6D344DC21475E68B1536006D257568E65FD142080CB9332B603A6717E0F8BB1F3116AACAFC59970227AD86ED83655237C53FE179102E4092DDE5459
ffa/libffa/fz_pred.ads
(41 . 4)(41 . 8)
368 function FZ_OddP(N : in FZ) return WBool;
369 pragma Inline_Always(FZ_OddP);
370
371 -- 1 iff N fits inside one Word
372 function FZ_OneWordP(N : in FZ) return WBool;
373 pragma Inline_Always(FZ_OneWordP);
374
375 end FZ_Pred;
-
+ 78D4C49FFCA81897F9E4832F272A46DF2DD8258BCD4502FFF7C716E4D8B7E67F5C96AEA13E193D44374FFADC7BF3487AE14C512257875D95C3414FD37C69F03A
ffa/libffa/fz_prime.adb
(0 . 0)(1 . 231)
380 ------------------------------------------------------------------------------
381 ------------------------------------------------------------------------------
382 -- This file is part of 'Finite Field Arithmetic', aka 'FFA'. --
383 -- --
384 -- (C) 2019 Stanislav Datskovskiy ( www.loper-os.org ) --
385 -- http://wot.deedbot.org/17215D118B7239507FAFED98B98228A001ABFFC7.html --
386 -- --
387 -- You do not have, nor can you ever acquire the right to use, copy or --
388 -- distribute this software ; Should you use this software for any purpose, --
389 -- or copy and distribute it to anyone or in any manner, you are breaking --
390 -- the laws of whatever soi-disant jurisdiction, and you promise to --
391 -- continue doing so for the indefinite future. In any case, please --
392 -- always : read and understand any software ; verify any PGP signatures --
393 -- that you use - for any purpose. --
394 -- --
395 -- See also http://trilema.com/2015/a-new-software-licensing-paradigm . --
396 ------------------------------------------------------------------------------
397
398 with Word_Ops; use Word_Ops;
399 with W_Pred; use W_Pred;
400 with W_Shifts; use W_Shifts;
401
402 with FZ_Basic; use FZ_Basic;
403 with FZ_QShft; use FZ_QShft;
404 with FZ_Arith; use FZ_Arith;
405 with FZ_Divis; use FZ_Divis;
406 with FZ_Pred; use FZ_Pred;
407 with FZ_Cmp; use FZ_Cmp;
408 with FZ_Barr; use FZ_Barr;
409 with FZ_ModEx; use FZ_ModEx;
410
411
412 package body FZ_Prime is
413
414 -- Find the highest power of 2 which divides N. ( or 0 if N is zero. )
415 function FZ_Count_Bottom_Zeros(N : in FZ) return FZBit_Index is
416
417 -- The result (default : 0, will remain 0 if N is in fact zero)
418 Index : Word := 0;
419
420 -- The currently-examined Word, starting from the highest
421 Ni : Word;
422
423 -- The most recently-seen nonzero Word, if indeed any exist
424 W : Word := 0;
425
426 -- 1 if currently-examined Word is zero, otherwise 0
427 NiZ : WBool;
428
429 begin
430
431 -- Find lowest non-zero Word (or simply stop at lowest, if N = 0)
432 for i in reverse 0 .. Indices(N'Length - 1) loop
433 Ni := N(N'First + i); -- Ni := current Word;
434 NiZ := W_ZeroP(Ni); -- ... is this Word = 0?
435 Index := W_Mux(Word(i), Index, NiZ); -- If NO, save its Index,
436 W := W_Mux(Ni, W, NiZ); -- ... and save the Word.
437 end loop;
438
439 -- Set Index to be the bit-position of the lowest non-zero Word:
440 Index := Shift_Left(Index, BitnessLog2); -- Index := Index * Bitness
441
442 -- Handle degenerate case: if W is equal to 0, Index is not changed;
443 -- Otherwise, start by advancing Index by an entire Word Bitness:
444 Index := Index + ((0 - W_NZeroP(W)) and Word(Bitness));
445
446 -- Now crank back the Index by the number of high bits of W (i.e.
447 -- starting from its top) that must be discarded for W to become zero:
448 for b in 1 .. Bitness loop
449
450 -- If W is non-zero at this time, decrement the Index:
451 Index := Index - W_NZeroP(W);
452
453 -- Advance W left, i.e. discard the top bit of it:
454 W := Shift_Left(W, 1);
455
456 end loop;
457
458 -- If N = 0, result will be 0; otherwise: length of bottom zeros in N.
459 return FZBit_Index(Index);
460
461 end FZ_Count_Bottom_Zeros;
462
463
464 -- Constant-Time Miller-Rabin Test on N using the given Witness.
465 -- Witness will be used as-is if it conforms to the valid bounds,
466 -- i.e. 2 <= Witness <= N - 2; otherwise will be transformed into a
467 -- valid Witness via modular arithmetic.
468 -- Outputs ONE if N WAS FOUND composite; ZERO if NOT FOUND.
469 -- Handles degenerate cases of N that M-R per se cannot eat:
470 -- N=0, N=1: ALWAYS 'FOUND COMPOSITE'; 2, 3 - ALWAYS 'NOT FOUND'.
471 -- If N is Even and not equal to 2, N is ALWAYS 'FOUND COMPOSITE.'
472 -- For ALL other N, the output is equal to that of the M-R test.
473 function FZ_MR_Composite_On_Witness(N : in FZ;
474 Witness : in FZ) return WBool is
475
476 -- Widths of N, Witness, and Result are equal :
477 subtype Width is Word_Index range N'Range;
478
479 -- Whether N is 'small' (i.e. 1 Word) and therefore possibly degenerate :
480 N_Is_Small : constant WBool := FZ_OneWordP(N);
481
482 -- Head of N, for detecting (and handling) the degenerate-N case :
483 N_Head : constant Word := FZ_Get_Head(N);
484
485 -- Zero and One are defined as COMPOSITE degenerate cases of N :
486 N_Is_Zero_Or_One : constant WBool
487 := N_Is_Small and (W_EqP(N_Head, 0) or W_EqP(N_Head, 1));
488
489 -- Two and Three are PRIME degenerate cases of N :
490 N_Is_Two : constant WBool := N_Is_Small and W_EqP(N_Head, 2);
491 N_Is_Three : constant WBool := N_Is_Small and W_EqP(N_Head, 3);
492
493 -- The COMPOSITE degenerate case of N where N != 2 and N is Even :
494 N_Ne_2_Is_Even : constant WBool :=
495 (1 - N_Is_Two) and (1 - W_OddP(N_Head));
496
497 -- Degeneracy latch. If N is Zero or One, then set immediately :
498 Degen_Composite : constant WBool := N_Is_Zero_Or_One or N_Ne_2_Is_Even;
499
500 -- Possible-primality latch. If N is Two or Three, then set immediately :
501 Possibly_Prime : WBool := N_Is_Two or N_Is_Three;
502
503 -- The writable copy of N that we will operate on :
504 X : FZ(Width) := N;
505
506 -- Potentially-replaced head of X (if degenerate N) :
507 X_Head : Word := N_Head;
508
509 -- Will be Barrettoid(X), for operations modulo X :
510 XBar : Barretoid(ZXMLength => X'Length + 1,
511 BarretoidLength => 2 * X'Length);
512
513 -- The Bound Witness, constrained to valid range 2 <= BW <= X - 2 :
514 BW : FZ(Width);
515
516 -- Head of BW, for detecting crossing of the lower bound :
517 BW_Head : Word;
518
519 -- X - 1 (for M-R proper, and to constrain BW) :
520 X_Minus_One : FZ(Width);
521
522 -- X - 1 = 2^R * K, with K odd :
523 K : FZ(Width);
524 R : FZBit_Index;
525
526 -- Working register for all M-R modular operations :
527 T : FZ(Width);
528
529 -- For subtraction where no underflow can happen, barring cosmic ray:
530 NoCarry : WZeroOrDie := 0;
531
532 begin
533
534 -- First: X, which will remain equal to N unless N is degenerate:
535
536 -- If N is one of the two prohibited small primes (2,3) X will become 5:
537 X_Head := W_Mux(A => X_Head, B => 5, Sel => Possibly_Prime);
538
539 -- If one of the two prohibited small composites (0,1), or even, then 9:
540 X_Head := W_Mux(A => X_Head, B => 9, Sel => Degen_Composite);
541
542 -- Given as we're stuck carrying out M-R even if N is degenerate case,
543 -- then let the M-R do The Right Thing, for added cosmic ray resistance.
544
545 -- X gets a new head, if N was a degenerate case; else keeps old head:
546 FZ_Set_Head(X, X_Head);
547
548 -- Compute X - 1. As now X > 3, underflow is not permitted:
549 FZ_Sub_W(X => X, W => 1, Difference => X_Minus_One,
550 Underflow => NoCarry);
551
552 -- Now, compute BW (Bound Witness), which satisfies 2 <= BW <= X - 2:
553
554 -- First, BW := Witness mod (X - 1). After this, 0 <= BW <= X - 2:
555 FZ_Mod(Dividend => Witness, Divisor => X_Minus_One, Remainder => BW);
556
557 -- Now, adjust BW if it is found to be below Two (the lower bound) :
558
559 -- Get head of BW:
560 BW_Head := FZ_Get_Head(BW);
561
562 -- If BW is equal to Zero or One, it will be forced to equal Two:
563 BW_Head := W_Mux(A => BW_Head,
564 B => 2,
565 Sel => FZ_OneWordP(BW) and
566 (W_EqP(BW_Head, 0) or W_EqP(BW_Head, 1)));
567
568 -- BW gets the new head, if it must; otherwise keeps its old head:
569 FZ_Set_Head(BW, BW_Head);
570
571 -- We finished adjusting X and BW for degeneracies, and can now M-R:
572
573 -- Generate Barrettoid(X) to use in all of the modulo-X operations:
574 FZ_Make_Barrettoid(Modulus => X, Result => XBar);
575
576 -- Find R >= 1, and odd K, where X − 1 = 2^R * K :
577
578 -- ... first, find R, the largest power of two which divides X - 1 :
579 R := FZ_Count_Bottom_Zeros(X_Minus_One);
580
581 -- ... and now obtain K := X / 2^R, i.e., K := X >> R :
582 FZ_Quiet_ShiftRight(N => X_Minus_One, ShiftedN => K, Count => R);
583
584 -- T := BW^K mod X
585 FZ_Mod_Exp_Barrett(Base => BW, Exponent => K, Bar => XBar, Result => T);
586
587 -- if T = 1 or T = X - 1, then X is possibly-prime:
588 Possibly_Prime := Possibly_Prime or
589 FZ_EqP_W(T, 1) or FZ_EqP(T, X_Minus_One);
590
591 -- Needs R - 1 times, but perform for max possible count (gated):
592 for i in 1 .. FZ_Bitness(N) - 1 loop
593
594 -- T := T^2 mod X
595 FZ_Mod_Sqr_Barrett(X => T, Bar => XBar, Product => T);
596
597 -- if T = X - 1, and i < R, then X is possibly-prime:
598 Possibly_Prime := Possibly_Prime or
599 (FZ_EqP(T, X_Minus_One) and W_LtP(Word(i), Word(R)));
600
601 end loop;
602
603 -- The output, which will be 1 iff X WAS FOUND to be composite via BW,
604 -- ... or if X was found to equal Zero or One (without regard to BW.)
605 return (1 - Possibly_Prime) or Degen_Composite;
606 -- If X was found to equal Two or Three, output will be 0 (under any BW).
607
608 end FZ_MR_Composite_On_Witness;
609
610 end FZ_Prime;
-
+ DC79CACA9A6A286AEC3B4484F21E55F8A61AE1B991CE17909CB3DAFE0EF2F761ECA6043CF6A86F10EE7E8582DD95F233E271978210DD8778F4140D51DDC8E040
ffa/libffa/fz_prime.ads
(0 . 0)(1 . 41)
615 ------------------------------------------------------------------------------
616 ------------------------------------------------------------------------------
617 -- This file is part of 'Finite Field Arithmetic', aka 'FFA'. --
618 -- --
619 -- (C) 2019 Stanislav Datskovskiy ( www.loper-os.org ) --
620 -- http://wot.deedbot.org/17215D118B7239507FAFED98B98228A001ABFFC7.html --
621 -- --
622 -- You do not have, nor can you ever acquire the right to use, copy or --
623 -- distribute this software ; Should you use this software for any purpose, --
624 -- or copy and distribute it to anyone or in any manner, you are breaking --
625 -- the laws of whatever soi-disant jurisdiction, and you promise to --
626 -- continue doing so for the indefinite future. In any case, please --
627 -- always : read and understand any software ; verify any PGP signatures --
628 -- that you use - for any purpose. --
629 -- --
630 -- See also http://trilema.com/2015/a-new-software-licensing-paradigm . --
631 ------------------------------------------------------------------------------
632 ------------------------------------------------------------------------------
633
634 with Words; use Words;
635 with FZ_Type; use FZ_Type;
636
637
638 package FZ_Prime is
639
640 pragma Pure;
641
642 -- Constant-Time Miller-Rabin Test on N using the given Witness.
643 -- Witness will be used as-is if it conforms to the valid bounds,
644 -- i.e. 2 <= Witness <= N - 2; otherwise will be transformed into a
645 -- valid Witness via modular arithmetic.
646 -- Outputs ONE if N WAS FOUND composite; ZERO if NOT FOUND.
647 -- Handles degenerate cases of N that M-R per se cannot eat:
648 -- N=0, N=1: ALWAYS 'FOUND COMPOSITE'; 2, 3 - ALWAYS 'NOT FOUND'.
649 -- If N is Even and not equal to 2, N is ALWAYS 'FOUND COMPOSITE.'
650 -- For ALL other N, the output is equal to that of the M-R test.
651 function FZ_MR_Composite_On_Witness(N : in FZ;
652 Witness : in FZ) return WBool
653 with Pre => N'Length = Witness'Length;
654
655 end FZ_Prime;
- 7EC39EE4A3AD6422DC9A47CB6C2B2F54C617F935817F8ABB8ED43608921A6A401673BCB2444A1AAFFE937792073F9B339EDABA117F709D280FFC98FDA9D70D6F
+ 674EF3017128D99C18659B510929DC1CA0A242E3E05873E356A377552ABA62728A24F0A0D8836B0F014FB33F85E95B7A3BEEB9B9A0A4F728D43C9BEE23379D99
ffa/libffa/w_pred.adb
(19 . 6)(19 . 7)
660
661 with Word_Ops; use Word_Ops;
662
663
664 -- Elementary Predicates on Words:
665 package body W_Pred is
666
(56 . 4)(57 . 11)
668 return W_ZeroP(A xor B);
669 end W_EqP;
670
671
672 -- Return 1 if A is less than B ; otherwise return 0.
673 function W_LtP(A : in Word; B : in Word) return WBool is
674 begin
675 return W_Borrow(A, B, A - B);
676 end W_LtP;
677
678 end W_Pred;
- 030953EDA47712590600CF57F24DF3B0A828EF877446545F47B35B151B82FA94CD1F20D5E0EB96AFC8F971182112CA955407F54DAFB5C6B4A66B8FC1FE0A1023
+ 58712EB4C343CD4D5980A895DC2F092E847398F4E70F64EDAAA644B20A3964FC919BCC3CA8A047FB6CF3B89E1DED009BEF35DAB19E223316EDBAFE6CE306D157
ffa/libffa/w_pred.ads
(44 . 4)(44 . 8)
683 function W_EqP(A : in Word; B : in Word) return WBool;
684 pragma Inline_Always(W_EqP);
685
686 -- Return 1 if A is less than B ; otherwise return 0.
687 function W_LtP(A : in Word; B : in Word) return WBool;
688 pragma Inline_Always(W_LtP);
689
690 end W_Pred;