X-Git-Url: http://www.chiark.greenend.org.uk/ucgi/~mdw/git/catacomb-python/blobdiff_plain/e91150b266bbd768905258166601fdf333d3d987..553d59fec08fd9102b21fd0dc83ba708862a6090:/t/t-pgen.py diff --git a/t/t-pgen.py b/t/t-pgen.py new file mode 100644 index 0000000..dd66903 --- /dev/null +++ b/t/t-pgen.py @@ -0,0 +1,228 @@ +### -*-python-*- +### +### Testing prime-generation functionality +### +### (c) 2019 Straylight/Edgeware +### + +###----- Licensing notice --------------------------------------------------- +### +### This file is part of the Python interface to Catacomb. +### +### Catacomb/Python is free software: you can redistribute it and/or +### modify it under the terms of the GNU General Public License as +### published by the Free Software Foundation; either version 2 of the +### License, or (at your option) any later version. +### +### Catacomb/Python is distributed in the hope that it will be useful, but +### WITHOUT ANY WARRANTY; without even the implied warranty of +### MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU +### General Public License for more details. +### +### You should have received a copy of the GNU General Public License +### along with Catacomb/Python. If not, write to the Free Software +### Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, +### USA. + +###-------------------------------------------------------------------------- +### Imported modules. + +import catacomb as C +import itertools as I +import unittest as U +import testutils as T + +###-------------------------------------------------------------------------- +class TestPrimeFilter (U.TestCase): + + def test(me): + n0 = 55614384877957400296344428606761687241 + pf = C.PrimeFilter(n0) + me.assertEqual(pf.status, C.PGEN_FAIL) + me.assertFalse(pf) + me.assertEqual(pf.x, n0) + me.assertEqual(int(pf), n0) + while not pf: pf.step(2) + me.assertEqual(pf.status, C.PGEN_TRY) + me.assertEqual(pf.x, n0 + 6) + + n1 = 111228769755914800592688857213523374495 + pf1 = pf.muladd(2, 1) + me.assertEqual(pf1.x, n1) + me.assertEqual(pf1.status, C.PGEN_FAIL) + + step = 2275063338 + pf0 = C.PrimeFilter(step) + me.assertEqual(pf0.status, C.PGEN_FAIL) + while not pf1: pf1.jump(pf0) + me.assertEqual(pf1.x, n1 + 6*step) + +###-------------------------------------------------------------------------- +class TestRabinMiller (U.TestCase): + + def test(me): + ## See `Prime and Prejudice' by Martin R. Albrecht, Jake Massimo, + ## Kenneth G. Paterson, and Juraj Somorovsky. + p1 = C.MP(142445387161415482404826365418175962266689133006163) + p2 = C.MP(5840260873618034778597880982145214452934254453252643) + p3 = C.MP(14386984103302963722887462907235772188935602433622363) + n = p1*p2*p3 + + rm = C.RabinMiller(n) + me.assertEqual(rm.test(2), C.PGEN_PASS) + me.assertEqual(rm.test(41), C.PGEN_FAIL) + me.assertEqual(rm.niters, 6) + + def test_iters(me): + me.assertEqual(C.RabinMiller.iters(50), 27) + me.assertEqual(C.RabinMiller.iters(100), 27) + me.assertEqual(C.RabinMiller.iters(500), 6) + me.assertEqual(C.RabinMiller.iters(1000), 3) + me.assertEqual(C.RabinMiller.iters(2000), 2) + +###-------------------------------------------------------------------------- + +class FailingHandler (object): + def pg_begin(me, ev): return C.PGEN_TRY + def pg_try(me, ev): raise T.Explosion + def pg_done(me, ev): raise ValueError("pg_done") + +class TestPGen (U.TestCase): + + def test_pgen(me): + ev = T.EventRecorder() + p0 = T.detrand("pgen").mp(256, 1) + p = C.pgen(p0, name = "p", event = ev) + me.assertEqual(p, p0 + 54) + me.assertTrue(p.primep()) + me.assertEqual(ev.events, "[p:F4/P11/D]") + + def test_pgen_exc(me): + rng = T.detrand("pgen_exc") + exc = [None] + def hook(why, ty, val, tb): exc[0] = val + C.lostexchook = hook + me.assertRaises(T.Explosion, C.pgen, rng.mp(256, 1), name = "p", + event = T.EventRecorder(explode_after = 19)) + me.assertEqual(exc[0], None) + me.assertRaises(T.Explosion, C.pgen, rng.mp(256, 1), name = "p", + event = FailingHandler(), stepper = FailingHandler()) + me.assertEqual(exc[0].args[0], "pg_done") + exc = [None] + me.assertRaises(T.Explosion, C.limlee, 512, 96, name = "p", rng = rng, + event = T.EventRecorder(explode_after = 8)) + ev = T.EventRecorder(explode_after = 19) + me.assertRaises(T.Explosion, C.limlee, 512, 96, name = "p", rng = rng, + ievent = ev) + me.assertRaises(ValueError, ev.rng.byte) + me.assertEqual(exc[0], None) + C.lostexchook = C.default_lostexchook + + def test_strongprime_setup(me): + ev = T.EventRecorder() + p0, delta = C.strongprime_setup(256, name = "p", event = ev, + rng = T.detrand("strongprime_setup")) + p = C.pgen(p0, name = "p", event = ev, + stepper = C.PrimeGenJumper(delta)) + me.assertTrue(p.primep()) + me.assertEqual((p - p0)%delta, 0) + me.assertEqual(p.nbits, 256) + me.assertEqual(ev.events, + "[p [s]:F3/P26/D]" + "[p [t]:F6/P26/D]" + "[p [r]:F5/P26/D]" + "[p:F7/P11/D]") + + def test_strongprime(me): + ev = T.EventRecorder() + p = C.strongprime(256, name = "p", event = ev, + rng = T.detrand("strongprime")) + me.assertTrue(p.primep()) + me.assertEqual(p.nbits, 256) + me.assertEqual(ev.events, + "[p [s]:F5/P26/D]" + "[p [t]:F13/P26/D]" + "[p [r]:F7/P26/D]" + "[p:F13/P11/D]") + + def test_limlee(me): + ev = T.EventRecorder() + p, qq = C.limlee(512, 96, name = "p", event = ev, ievent = ev, + rng = T.detrand("limlee")) + me.assertTrue(p.primep()) + me.assertEqual(p.nbits, 512) + qbig = qq.pop() + me.assertTrue(qbig.primep()) + me.assertTrue(qbig.nbits >= 96) + for q in qq: + me.assertTrue(q.primep()) + me.assertEqual(q.nbits, 96) + me.assertEqual(p, C.MPMul(qq).factor(qbig).factor(2).done() + 1) + me.assertEqual(ev.events, + "[p:" + "[p_0:P26/D]" + "[p_1:P26/D]" + "[p_2:P26/D]" + "[p_3:F5/P26/D]" + "[p*_4:P26/D]" + "[p_5:F6/P26/D]" + "[p_6:F3/P26/D]" + "[p*_7:P26/D]" + "[p_8:F5/P26/D]" + "[p*_9:F3/P26/D]" + "[p_10:F3/P26/D]" + "[p_11:F1/P26/D]" + "[p_12:F2/P26/D]" + "[p_13:F4/P26/D]" + "[p_14:F15/P26/D]" + "[p_15:P26/D]" + "[p_16:F3/P26/D]" + "[p_17:P26/D]" + "[p_18:F1/P26/D]" + "[p_19:F8/P26/D]" + "[p_20:F12/P26/D]" + "[p_21:F2/P26/D]" + "[p_22:F2/P26/D]" + "[p_23:F2/P26/D]" + "[p_24:F1/P26/D]" + "[p_25:F9/P26/D]" + "[p_26:P26/D]" + "[p_27:F2/P26/D]" + "[p*_28:F8/P26/D]" + "[p*_29:F14/P26/D]" + "[p*_30:F4/P26/D]" + "[p*_31:F6/P26/D]" + "[p*_32:P26/D]" + "[p*_33:F1/P26/D]" + "[p*_34:F6/P26/D]" + "[p*_35:F5/P26/D]" + "[p*_36:F6/P26/D]" + "[p*_37:P26/D]" + "[p*_38:F3/P26/D]" + "[p*_39:P26/D]" + "[p*_40:P26/D]" + "F41/P5/D]") + + def test_sgprime(me): + ev = T.EventRecorder() + q0 = T.detrand("sgprime").mp(255, 1) + q = C.sgprime(q0, event = ev) + me.assertTrue(q.primep()) + p = 2*q + 1 + me.assertEqual(p.nbits, 256) + me.assertTrue(p.primep()) + + def test_kcdsa(me): + ev = T.EventRecorder() + p, q, h = C.kcdsaprime(512, 96, event = ev, rng = T.detrand("kcdsa")) + me.assertTrue(q.primep()) + me.assertEqual(q.nbits, 96) + me.assertTrue(h.primep()) + me.assertEqual(p, 2*q*h + 1) + me.assertTrue(p.primep()) + me.assertEqual(p.nbits, 512) + me.assertEqual(ev.events, "[p [h]:F17/P6/D][p:F60/P26/D]") + +###----- That's all, folks -------------------------------------------------- + +if __name__ == "__main__": U.main()