Commit | Line | Data |
---|---|---|
ffad1322 MW |
1 | ### -*-python-*- |
2 | ### | |
3 | ### Testing prime-generation functionality | |
4 | ### | |
5 | ### (c) 2019 Straylight/Edgeware | |
6 | ### | |
7 | ||
8 | ###----- Licensing notice --------------------------------------------------- | |
9 | ### | |
10 | ### This file is part of the Python interface to Catacomb. | |
11 | ### | |
12 | ### Catacomb/Python is free software: you can redistribute it and/or | |
13 | ### modify it under the terms of the GNU General Public License as | |
14 | ### published by the Free Software Foundation; either version 2 of the | |
15 | ### License, or (at your option) any later version. | |
16 | ### | |
17 | ### Catacomb/Python is distributed in the hope that it will be useful, but | |
18 | ### WITHOUT ANY WARRANTY; without even the implied warranty of | |
19 | ### MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU | |
20 | ### General Public License for more details. | |
21 | ### | |
22 | ### You should have received a copy of the GNU General Public License | |
23 | ### along with Catacomb/Python. If not, write to the Free Software | |
24 | ### Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, | |
25 | ### USA. | |
26 | ||
27 | ###-------------------------------------------------------------------------- | |
28 | ### Imported modules. | |
29 | ||
30 | import catacomb as C | |
31 | import itertools as I | |
32 | import unittest as U | |
33 | import testutils as T | |
34 | ||
35 | ###-------------------------------------------------------------------------- | |
36 | class TestPrimeFilter (U.TestCase): | |
37 | ||
38 | def test(me): | |
39 | n0 = 55614384877957400296344428606761687241 | |
40 | pf = C.PrimeFilter(n0) | |
41 | me.assertEqual(pf.status, C.PGEN_FAIL) | |
42 | me.assertFalse(pf) | |
43 | me.assertEqual(pf.x, n0) | |
44 | me.assertEqual(int(pf), n0) | |
45 | while not pf: pf.step(2) | |
46 | me.assertEqual(pf.status, C.PGEN_TRY) | |
47 | me.assertEqual(pf.x, n0 + 6) | |
48 | ||
49 | n1 = 111228769755914800592688857213523374495 | |
50 | pf1 = pf.muladd(2, 1) | |
51 | me.assertEqual(pf1.x, n1) | |
52 | me.assertEqual(pf1.status, C.PGEN_FAIL) | |
53 | ||
54 | step = 2275063338 | |
55 | pf0 = C.PrimeFilter(step) | |
56 | me.assertEqual(pf0.status, C.PGEN_FAIL) | |
57 | while not pf1: pf1.jump(pf0) | |
58 | me.assertEqual(pf1.x, n1 + 6*step) | |
59 | ||
60 | ###-------------------------------------------------------------------------- | |
61 | class TestRabinMiller (U.TestCase): | |
62 | ||
63 | def test(me): | |
64 | ## See `Prime and Prejudice' by Martin R. Albrecht, Jake Massimo, | |
65 | ## Kenneth G. Paterson, and Juraj Somorovsky. | |
66 | p1 = C.MP(142445387161415482404826365418175962266689133006163) | |
67 | p2 = C.MP(5840260873618034778597880982145214452934254453252643) | |
68 | p3 = C.MP(14386984103302963722887462907235772188935602433622363) | |
69 | n = p1*p2*p3 | |
70 | ||
71 | rm = C.RabinMiller(n) | |
72 | me.assertEqual(rm.test(2), C.PGEN_PASS) | |
73 | me.assertEqual(rm.test(41), C.PGEN_FAIL) | |
74 | me.assertEqual(rm.niters, 6) | |
75 | ||
76 | def test_iters(me): | |
77 | me.assertEqual(C.RabinMiller.iters(50), 27) | |
78 | me.assertEqual(C.RabinMiller.iters(100), 27) | |
79 | me.assertEqual(C.RabinMiller.iters(500), 6) | |
80 | me.assertEqual(C.RabinMiller.iters(1000), 3) | |
81 | me.assertEqual(C.RabinMiller.iters(2000), 2) | |
82 | ||
83 | ###-------------------------------------------------------------------------- | |
84 | ||
85 | class FailingHandler (object): | |
86 | def pg_begin(me, ev): return C.PGEN_TRY | |
87 | def pg_try(me, ev): raise T.Explosion | |
88 | def pg_done(me, ev): raise ValueError("pg_done") | |
89 | ||
90 | class TestPGen (U.TestCase): | |
91 | ||
92 | def test_pgen(me): | |
93 | ev = T.EventRecorder() | |
94 | p0 = T.detrand("pgen").mp(256, 1) | |
95 | p = C.pgen(p0, name = "p", event = ev) | |
96 | me.assertEqual(p, p0 + 54) | |
97 | me.assertTrue(p.primep()) | |
98 | me.assertEqual(ev.events, "[p:F4/P11/D]") | |
99 | ||
100 | def test_pgen_exc(me): | |
101 | rng = T.detrand("pgen_exc") | |
102 | exc = [None] | |
103 | def hook(why, ty, val, tb): exc[0] = val | |
104 | C.lostexchook = hook | |
105 | me.assertRaises(T.Explosion, C.pgen, rng.mp(256, 1), name = "p", | |
106 | event = T.EventRecorder(explode_after = 19)) | |
107 | me.assertEqual(exc[0], None) | |
108 | me.assertRaises(T.Explosion, C.pgen, rng.mp(256, 1), name = "p", | |
109 | event = FailingHandler(), stepper = FailingHandler()) | |
110 | me.assertEqual(exc[0].args[0], "pg_done") | |
111 | exc = [None] | |
112 | me.assertRaises(T.Explosion, C.limlee, 512, 96, name = "p", rng = rng, | |
113 | event = T.EventRecorder(explode_after = 8)) | |
114 | ev = T.EventRecorder(explode_after = 19) | |
115 | me.assertRaises(T.Explosion, C.limlee, 512, 96, name = "p", rng = rng, | |
116 | ievent = ev) | |
117 | me.assertRaises(ValueError, ev.rng.byte) | |
118 | me.assertEqual(exc[0], None) | |
119 | C.lostexchook = C.default_lostexchook | |
120 | ||
121 | def test_strongprime_setup(me): | |
122 | ev = T.EventRecorder() | |
123 | p0, delta = C.strongprime_setup(256, name = "p", event = ev, | |
124 | rng = T.detrand("strongprime_setup")) | |
125 | p = C.pgen(p0, name = "p", event = ev, | |
126 | stepper = C.PrimeGenJumper(delta)) | |
127 | me.assertTrue(p.primep()) | |
128 | me.assertEqual((p - p0)%delta, 0) | |
129 | me.assertEqual(p.nbits, 256) | |
130 | me.assertEqual(ev.events, | |
131 | "[p [s]:F3/P26/D]" | |
132 | "[p [t]:F6/P26/D]" | |
133 | "[p [r]:F5/P26/D]" | |
134 | "[p:F7/P11/D]") | |
135 | ||
136 | def test_strongprime(me): | |
137 | ev = T.EventRecorder() | |
138 | p = C.strongprime(256, name = "p", event = ev, | |
139 | rng = T.detrand("strongprime")) | |
140 | me.assertTrue(p.primep()) | |
141 | me.assertEqual(p.nbits, 256) | |
142 | me.assertEqual(ev.events, | |
143 | "[p [s]:F5/P26/D]" | |
144 | "[p [t]:F13/P26/D]" | |
145 | "[p [r]:F7/P26/D]" | |
146 | "[p:F13/P11/D]") | |
147 | ||
148 | def test_limlee(me): | |
149 | ev = T.EventRecorder() | |
150 | p, qq = C.limlee(512, 96, name = "p", event = ev, ievent = ev, | |
151 | rng = T.detrand("limlee")) | |
152 | me.assertTrue(p.primep()) | |
153 | me.assertEqual(p.nbits, 512) | |
154 | qbig = qq.pop() | |
155 | me.assertTrue(qbig.primep()) | |
156 | me.assertTrue(qbig.nbits >= 96) | |
157 | for q in qq: | |
158 | me.assertTrue(q.primep()) | |
159 | me.assertEqual(q.nbits, 96) | |
160 | me.assertEqual(p, C.MPMul(qq).factor(qbig).factor(2).done() + 1) | |
161 | me.assertEqual(ev.events, | |
162 | "[p:" | |
163 | "[p_0:P26/D]" | |
164 | "[p_1:P26/D]" | |
165 | "[p_2:P26/D]" | |
166 | "[p_3:F5/P26/D]" | |
167 | "[p*_4:P26/D]" | |
168 | "[p_5:F6/P26/D]" | |
169 | "[p_6:F3/P26/D]" | |
170 | "[p*_7:P26/D]" | |
171 | "[p_8:F5/P26/D]" | |
172 | "[p*_9:F3/P26/D]" | |
173 | "[p_10:F3/P26/D]" | |
174 | "[p_11:F1/P26/D]" | |
175 | "[p_12:F2/P26/D]" | |
176 | "[p_13:F4/P26/D]" | |
177 | "[p_14:F15/P26/D]" | |
178 | "[p_15:P26/D]" | |
179 | "[p_16:F3/P26/D]" | |
180 | "[p_17:P26/D]" | |
181 | "[p_18:F1/P26/D]" | |
182 | "[p_19:F8/P26/D]" | |
183 | "[p_20:F12/P26/D]" | |
184 | "[p_21:F2/P26/D]" | |
185 | "[p_22:F2/P26/D]" | |
186 | "[p_23:F2/P26/D]" | |
187 | "[p_24:F1/P26/D]" | |
188 | "[p_25:F9/P26/D]" | |
189 | "[p_26:P26/D]" | |
190 | "[p_27:F2/P26/D]" | |
191 | "[p*_28:F8/P26/D]" | |
192 | "[p*_29:F14/P26/D]" | |
193 | "[p*_30:F4/P26/D]" | |
194 | "[p*_31:F6/P26/D]" | |
195 | "[p*_32:P26/D]" | |
196 | "[p*_33:F1/P26/D]" | |
197 | "[p*_34:F6/P26/D]" | |
198 | "[p*_35:F5/P26/D]" | |
199 | "[p*_36:F6/P26/D]" | |
200 | "[p*_37:P26/D]" | |
201 | "[p*_38:F3/P26/D]" | |
202 | "[p*_39:P26/D]" | |
203 | "[p*_40:P26/D]" | |
204 | "F41/P5/D]") | |
205 | ||
206 | def test_sgprime(me): | |
207 | ev = T.EventRecorder() | |
208 | q0 = T.detrand("sgprime").mp(255, 1) | |
209 | q = C.sgprime(q0, event = ev) | |
210 | me.assertTrue(q.primep()) | |
211 | p = 2*q + 1 | |
212 | me.assertEqual(p.nbits, 256) | |
213 | me.assertTrue(p.primep()) | |
214 | ||
215 | def test_kcdsa(me): | |
216 | ev = T.EventRecorder() | |
217 | p, q, h = C.kcdsaprime(512, 96, event = ev, rng = T.detrand("kcdsa")) | |
218 | me.assertTrue(q.primep()) | |
219 | me.assertEqual(q.nbits, 96) | |
220 | me.assertTrue(h.primep()) | |
221 | me.assertEqual(p, 2*q*h + 1) | |
222 | me.assertTrue(p.primep()) | |
223 | me.assertEqual(p.nbits, 512) | |
224 | me.assertEqual(ev.events, "[p [h]:F17/P6/D][p:F60/P26/D]") | |
225 | ||
54ccbb3b MW |
226 | ###-------------------------------------------------------------------------- |
227 | class TestPrimeIter (U.TestCase): | |
228 | ||
229 | def test(me): | |
230 | me.assertEqual(list(I.islice(C.PrimeIter(0), 5)), [2, 3, 5, 7, 11]) | |
231 | me.assertEqual(list(I.islice(C.PrimeIter(1000), 5)), | |
232 | [1009, 1013, 1019, 1021, 1031]) | |
233 | me.assertEqual(list(I.islice(C.PrimeIter(1000000), 5)), | |
234 | [1000003, 1000033, 1000037, 1000039, 1000081]) | |
235 | me.assertEqual(list(I.islice(C.PrimeIter(1000000000000000000000000000000000000), 5)), | |
236 | [1000000000000000000000000000000000067, | |
237 | 1000000000000000000000000000000000123, | |
238 | 1000000000000000000000000000000000141, | |
239 | 1000000000000000000000000000000000159, | |
240 | 1000000000000000000000000000000000163]) | |
241 | ||
ffad1322 MW |
242 | ###----- That's all, folks -------------------------------------------------- |
243 | ||
244 | if __name__ == "__main__": U.main() |