chiark - git - mdw - catacomb-python/blob - t/t-pgen.py

   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
 226 ###----- That's all, folks --------------------------------------------------
 227
 228 if __name__ == "__main__": U.main()