Add additional primality tests

Add a long list of 'false' primes from Google's Wycheproof tests:
https://github.com/google/wycheproof/blob/master/java/com/google/security/wycheproof/testcases/BigIntegerTest.java

Split vector file format into Prime and NonPrime sections for easier reading.

2 files changed, 222 insertions, 64 deletions

diff --git a/src/tests/data/bn/isprime.vec b/src/tests/data/bn/isprime.vec
index 9bd5f6583..ec6aca606 100644
--- a/src/tests/data/bn/isprime.vec
+++ b/src/tests/data/bn/isprime.vec
@@ -1,85 +1,242 @@
-[PrimeTest]
-Value = 0x0
-IsPrime = 0
+[Prime]
+X = 2
+X = 3
+X = 5
+X = 7
 
-Value = 0x1
-IsPrime = 0
+X = 0x101
 
-Value = 0x2
-IsPrime = 1
+X = 0xFFF1
 
-Value = 0x3
-IsPrime = 1
+# First prime not in lookup table
+X = 0x10001
 
-Value = 0x4
-IsPrime = 0
+# Misc random primes
+X = 14316557441
 
-Value = 0xFF
-IsPrime = 0
+X = 151601382993659001523
 
-Value = 0x101
-IsPrime = 1
+X = 2199163969452631049452040286673993338197
 
-Value = 0xFFED
-IsPrime = 0
+X = 16507654986299102863
 
-Value = 0xFFF1
-IsPrime = 1
+X = 316362908763458525001406154038726382279
 
-Value = 0x10001
-IsPrime = 1
+X = 0x908EF92E5453DD53
 
-Value = 0x100000001
-IsPrime = 0
+X = 0xC892038CD8BD587BA244C45B
 
-Value = 0x908EF92E5453DD53
-IsPrime = 1
+X = 0x8055A641BA9041BA0D10166579D42F6B
 
-Value = 0xC892038CD8BD587BA244C45B
-IsPrime = 1
+X = 0xFCEEE64D4D40D734058A51944F2B53152FFE7F15
 
-Value = 0x8055A641BA9041BA0D10166579D42F6B
-IsPrime = 1
+X = 0xEE23CE225FDEE2080403C2358C17A72D57C5B7CBE171D6D2BA59FE82DAABA9D3
 
-Value = 0xFCEEE64D4D40D734058A51944F2B53152FFE7F15
-IsPrime = 1
+[NonPrime]
+X = 0
+X = 1
+X = 4
+X = 255
 
-Value = 0xEE23CE225FDEE2080403C2358C17A72D57C5B7CBE171D6D2BA59FE82DAABA9D3
-IsPrime = 1
+X = 0xFFED
 
-Value = 0x1043F9AC97177F7BD0B6876E1747CD0A6CF3B5DBD5306E6D2BA59FE82DAABA9D3
-IsPrime = 0
+X = 0x100000001
 
-Value = 0x24F08CFE94F236901
-IsPrime = 0
+X = 0x1043F9AC97177F7BD0B6876E1747CD0A6CF3B5DBD5306E6D2BA59FE82DAABA9D3
 
-Value = 0x1C443F2F861D29C3B
-IsPrime = 0
+X = 0x24F08CFE94F236901
 
-Value = 0x2BF2F5F313B1784CAC2B5CF9532AA6CFA27DFC0F3
-IsPrime = 0
+X = 0x1C443F2F861D29C3B
 
-Value = 0x95D9E7C08BF3FA230171B6188BBC154FC879D340687A52C6B35424B471E28449091A7D784F9F
-IsPrime = 0
+X = 0x2BF2F5F313B1784CAC2B5CF9532AA6CFA27DFC0F3
 
-Value = 0x886353EE3F610EA9DC507EBC572E2F659D76E1459F175556D93795683BA72A6679491C328076CF
-IsPrime = 0
+X = 0x95D9E7C08BF3FA230171B6188BBC154FC879D340687A52C6B35424B471E28449091A7D784F9F
 
-Value = 0x168E8FA52C7B0274DDC9A7B6BB14FB2437B91638CB25161BD004EF43565B5231FAF88E13AB885AE0E7C20FC96BA3BE15436F03D1603
-IsPrime = 0
+X = 0x886353EE3F610EA9DC507EBC572E2F659D76E1459F175556D93795683BA72A6679491C328076CF
 
-Value = 0x1DA20BCB5DE084D2DDA31B118D671342B828052EF5D39AEB65904E9F6027000D3A00F88658EA1EC52A10CF32D8892ED16F2BB9E110F6C9555ABB069BA7A069C6F1FE46873E957
-IsPrime = 0
+X = 0x168E8FA52C7B0274DDC9A7B6BB14FB2437B91638CB25161BD004EF43565B5231FAF88E13AB885AE0E7C20FC96BA3BE15436F03D1603
 
-Value = 0x7215D1519157B349829486479DCA81AF352EFE7B516C0079D4213F1554FEA6FE81A5E099B528536361EB5B5ECEC96CC3183CB21B3E4A045F50A5D18BAF5CA154E856D88A2D6082E93BA5AF650E20C3C2873A98AFD9D54843C02547157
-IsPrime = 0
+X = 0x1DA20BCB5DE084D2DDA31B118D671342B828052EF5D39AEB65904E9F6027000D3A00F88658EA1EC52A10CF32D8892ED16F2BB9E110F6C9555ABB069BA7A069C6F1FE46873E957
 
-Value = 0x36133736D1
-IsPrime = 0
+X = 0x7215D1519157B349829486479DCA81AF352EFE7B516C0079D4213F1554FEA6FE81A5E099B528536361EB5B5ECEC96CC3183CB21B3E4A045F50A5D18BAF5CA154E856D88A2D6082E93BA5AF650E20C3C2873A98AFD9D54843C02547157
 
-Value = 0x8DD3F98C901
-IsPrime = 0
+X = 0x36133736D1
 
-Value = 0x53251
-IsPrime = 0
+X = 0x8DD3F98C901
 
+X = 0x53251
+
+# The following non-prime values (and commentary) are from Google's Wycheproof tests
+
+# If p is prime then the Mersenne number 2^p-1 is pseudoprime for base 2.
+X = 147573952589676412927
+X = 2361183241434822606847
+
+# pseudoprime squares derived from Wiefrich primes
+X = 1194649
+X = 12327121
+
+# G. Jaeschke: "On strong pseudoprimes to several bases", Math o. comp. v.61, p 915-926
+X = 2152302898747
+X = 3474749660383
+X = 341550071728321
+X = 41234316135705689041
+X = 1553360566073143205541002401
+X = 56897193526942024370326972321
+
+# A list of strong pseudoprimes to 12 or more bases from
+# https://arxiv.org/pdf/1509.00864v1.pdf
+X = 164280218643672633986221
+X = 2995741773170734841812261
+X = 3110269097300703345712981
+X = 318665857834031151167461
+X = 3317044064679887385961981
+X = 3404730287403079539471001
+X = 360681321802296925566181
+X = 552727880697763694556181
+X = 667636712015520329618581
+X = 7395010240794120709381
+
+# Richarg G.E. Pinch, "Some primality testing algorithms"
+# Some composites that passed Maple V's primality test.
+X = 10710604680091
+X = 4498414682539051
+X = 6830509209595831
+
+# Composites that passed the primality test of Mathematica 2.0
+X = 38200901201
+X = 6646915915638769
+
+# Composites that passed Axioms primality tests
+X = 168790877523676911809192454171451
+X = 68528663395046912244223605902738356719751082784386681071
+
+# A composite q that was acceptied by Gnu Crypto. p = 2*q + 1 is prime and could have been
+# used to break the SRP with that library.
+# http://www.iacr.org/archive/pkc2005/33860010/33860010.pdf
+
+X = 233827489457314527331467907356100405232549379971733249650087398191542695662679115657626701477211734957066864835979560428632968558985491020031718032728786934761830612407539788738389834804112831048493371292441426451179971550359625305463829009730525437856060434572821557303838067028455480173152174543909940520352338084540532209678251
+
+# The following pseudoprimes are 1024 to 1280 bits long and pass the MR test for
+# about 1/4 of all bases.
+
+X = 173062611414399390658232917862739135524848544363998436303084727513085426673093684058028234312597183385536670796001184814581807178685660312964257923307841168376622412972295432300191118906455596063609936643031721065109822926173698786848786582094520943139138009108180649097618810676094425505547347369635059151651
+
+X = 136099885892399458477080305673739378689483245066221584061455921570784014696997016196935523316168750387027856624173915737138040384334162971247398689854706029275431407028615888533012918610480990022386148796379692392850397246576121436088869385931427080895536740913457414488449790876563256100025424908640036566991
+
+X = 316688375608386437421379757779276540412122545033442874913608227262770470335539825484056485495303653581675917765425776336382516484708794514891794859629545011811469601460428778510574606216627610930594654525686171019765270172220260057282202615710851069446603121873496655525294839125742517721479483987924741221051
+
+X = 186785694002678642132801225656186719643704247017683123340863572840120481332740690296425537870889503100273775347189620291247182266051117402306961193255486702389001315623336948708913938663766675822604289835221988612387022254700737033287973420727356494651195431833673259400609717994958747847898007198993092012403
+
+X = 179639066126300967799401671841610886660929207919727738745232300602750546404186962234806423243160992149524026517310832658546103698224730515713772933976457906751697355710699183284927973990745341231158578954614781007101406949906000339898234046606680082274669864309065127941774208780103317444828873858305613764441
+
+X = 197194524085561523935938577984854327845985252162946770376109467281189594776245829996960570423566272168211942090903965989665312046718418693934025583647341695134065566474352554207810854787929284015042099758637116781199978266343468760679551811591367813147177875984898571603525952885934025286780854976730638309011
+
+X = 315000813248346168693407625056991248935216183936964838573658781159971838226732674288265941973610843971773212814194827628754750849549588421903702315436565970387119142993552663715551586581960248038598579837710301034898247047182667956083431512960522212612279266245495948831504762364224662571600318327270033084451
+
+X = 170894610236614232071564956494126711146504551032906128147621274032573410076795759093464783793540456868246805453794432693438608747656833753674500442989626468892341565281803639470271121897646438029795161418432797979461569692919748848065959091755776480614225664177795195470929762281195447906351417368682849843661
+
+X = 344000370199347416505163474679365912312228588642939088787442579805396287970863997000504005120780533350535874773754291779072767657299212000552180980839328379536622696237474649639004862671352175928935249466938367953074872370682165966418566130395323376736516767872755699135674189217223109386132423577475778316621
+
+X = 138448909343722671880314351740830916278120326372935587281862834944695264415850785820375793931599456884131330850309445163053132348118439725196722488178936032989162127096990828542718648126854836321501499457100367916779232817286863221952600626787469684939436451238457213158274397103569820623680840515654121967511
+
+X = 316439386823206871346636164448924890050652125877864816263874447019119652991341471892512767356833013036596313520681688846037642422058303711027020977731971469313828021385806157441077657252831199515126729145408040958578380505446806576341163588698094381212906912979884469786023782783106107762632814558326808787771
+
+X = 342961098100864161486224083444064996530615333608713481168433421427817847848808231587480736204728509866407803683577588064876248986627917970721407574366482474956464008840562218539437088991213443686581244468670230768746624924083761284969471148856846083279368375653516879275492605255161494494045951397742913942521
+
+X = 145262597146950198402983317029784468866625742919846744533002367696562782381925075139139930520346726630860925038417520841048478748173408690100803386628315407260460724324957380860416531476612359390675514955532124090127597883627039869878570938907641350999452942901485886289548101644664410043634050840333618736241
+
+X = 103875970392676952824793549226382893918770722897777186300203751664479562050977123972289929315717558677706616837050252404201111892868394359927108413461144788316226799790655169187714036057483534137944994036412984530284019391161346173629541003286304852813525704436628490382188950208123780350213139500089456366841
+
+X = 209262684834708760781378828826012883216045622771588748049592833781430908796364015367633518238497257347693398354563483221744331332528919261931329808331753456631473557050588173643619875493912344262122927629778826442021480388121726709494897667644505493953841122580436721054077839958796624587867034849970594728503
+
+X = 259961974092249031010227603062857594431439837198127643068846961266772005421073175255160571859806585623933076083354026720150711464375869967746325500371685760342898099183114419807958654613613854399259408657437156780223269043081096609877199006862511248990329589067604336669355585402887916288037943709029191674911
+
+X = 148494412403103322617790447472967208041427708128812693048671309929515715881545523410764344130359406227126016497399642347726034074857469854866669198948655053082186111410005989963123962723450119664228552171284801593222656654683510273370663211536463220415691464644614536183219912321808854090915103775109695786903
+
+X = 198951823787361124930411813610219829991074975106392146571215767501609838087179827135862554836592949340043265497052033837199003071263871954417468537542759843054899935687365194283002403584007149487837111761068191757630773706541137817805185812103245128290071673542006653340382017735899123084476453857081318545991
+
+X = 100151654947252996043048304163211754746777587142702306692434166984038755330098831955228744694322537016096512607358351287591352995655554893223580483857764100115214746205606713424344869011314868310794273156514093861279449413522759799967523399898069268728739367463341929936509718884001903262839905032784262429503
+
+X = 95231206592596470170500609905849442045564547265058783767596160210162649328723702952067039028722189901551617226203049071432575686912108071032771616159536783552831568339753661508472308255156836457399521849955736774530191276074724269639715623883903007852200496655144350028488056721467755918814393298596327869403
+
+X = 113269289613139045987221838168670476157836730159022951727133866871803517984548824974383829544258356211263936613672131433712832720317909560575328664237540188143415517690966913820407105917871661636540517137224670577811216377174354694586862330746730799787557140869529264839386342569691698111927128704157615097153
+
+X = 146847844534363588585309790039628824975112779508886863375458304099023620010134739900409422108297615491941343243438794419278070814832779046634885071582835688508933384516245429006116427382617949079713164417750742186233232850990403187128712092976902908607450338866991708762791875618755240139448209180903665732503
+
+X = 358412810221928846165188109606360323720655048142248089956469337069891988161925279182207899372236993040751183199049811064730560746022073963857677172123650694187762839204698560127083582857191356761960185713492812536976691258036712784053125734439393862988510716841734490107828355376447675347185589367615046902903
+
+X = 136413254073020125119434184465514800285073635295381931240903345105818069560349289617656965328836783198111535348238932718954415951560405730847235775035340408484490592989244418679611824558459897397010340558814522802854982012583742552368228166904908748136802133702260393866732616878693744975284760231993354960641
+
+X = 120121309077413673757973584538895340053078707116007436412672855151473033018568172415152125730799408413400442697832948048164313838284868252529547559069691488487393115675459439240223181642866729342993196497371101511116354455141429907183234984597199837581257543510797169400923829329952407436122292964382266031253
+
+X = 274961162498721700837795876571850161951923504987707945218130565747245640262722421808114353386438668769035914966494393198895709050358277453956447636555409300854018401232502616530331143658908539168226609336701796936963304692734694998233898508239810354573599326268702707614772584950389057955691219494031838859791
+
+X = 247298211474214536023668493148879183399132978885752967092151982122755890641856724943270179044946868108401503142712501669997689725488277075239138647902134463451436706674384070937644414378922408397424080253817427253472696804180199677968577101924609860357709848139330190576017582503777009836399771498662905893541
+
+X = 186534718886580998173370111544816079042584670455810850117180327746163633753014575413454959923578288266455109198977784465376154230882378024111971510810465276396395657415178370245114122816237302328393303099711090670061109774495422227139479023758278081750794950528224900273599212004329531461848157373189908642761
+
+X = 285222066304318808807440348756959206512109737156133765320791968958061255441639532142589633195949710293792634007355153699552500134028759770788754166339078427645792536001991144766729628117371050306527654454337958520732309306981263990241529867679171677372308601834079961869281917489638496882679996929360595283091
+
+X = 181226694573701424780809995604208189403454412466009020384060212389337953064906112451523821277506877740852536185141584946755187420904863344271961110077635791220319963938065397633608138595169161436595273219128460849681615673231703413005405286329650440795248270402413500178325587999299003705988651612697260381081
+
+X = 346147802084908988163605730186745996807051687260298732207255261061226967176670988511272076506359607314799699361510659216049566069966154794154897232197433347544538725616640069913605417680979153794166392029635163055246391693210977409542760131833241323790056533380330505490643091283956267491266793755039018149751
+
+X = 291997980097006865890553981103897105153148223341834443462048822970699554781915153514961936955543911140074002652746536457498993361682279972987736655018586409178146143048864596533190807270958265838634581161605509776918985909639375293439321397861730276448559427971296399182413971389773786687947710326691137231821
+
+X = 4145154657949019520090421067892641813006171355169512965016842717965605608345677070047674053932189113793437189588504071861413206876596422868599328943199463347247109139279156232354244036749607133015105499354740364264523832014989327244648027567866644179973588685140041000602876709543832749014374100484229987854182496484982493504634095371261651820866750919282103255096749335753834321723611
+
+X = 7263570684005586918409651676342477962666063384721447164820162267363790003137994944696141214510462612778986577033412479555865362502656930339533617799427179849708811066678403560574528663579436770299187611159071848712668510417692823114550446719084221850233353544862258108486420641329524797224084595903392576175926450327110287113582813113256500835397705152529000369324993100375959770969653
+
+X = 3266663369261434628530741133725226939380890029427130078147736465299657609609866300289037551044842755296645715455685385229229753037488770815042188048059347290440541953284413920836228770883378333839361634881282676119589334709165541036798092721269225600972531571877021083483173456889586533434762148051173834392034092081944586022679255357901358842147871934591187835506106526312170065069453
+
+X = 2714275054823322283846947242758076394288969833351667671546539844865164304081725719193278199274587859302964845933174264046206721616978898415824746652517284154696057825266292769391590992419682314563946417035619325266947257091436696492494177352417584114484475661078574695869675993807128667478899686975153304356423463804980259495149174741764929495016696034025325328362453468725905824967341
+
+X = 9266983839147571189339684823228253420616685503762301572754412275112784329325896460070245239752617832925926748469508691163897231549619954919002517181056246469211229002569927844376004535572738353861591882136393291951512396743267427648075154617935904316277726449386507253882066728735163630819726247327318549654310222647082566628770190476835111363804804130289258330689970347505178654499153
+
+X = 6943685859962113005380005918916483733270787990846044283782171250109685123273631832530232093515797678613166669636433353226818439586659507237191626629561100778400131847260203138804429806291455932383952066228056762115442513166346145910224582828425403465971492726015022712635093903343807744925561923150283620959189103749396693669637302516191876159629263102871218404211406214291913457837031
+
+X = 8697498751458522624235585703214358189002281420472600166267178848980987666586924803733439542008165386809605610353749313146537722602615273804265594080404564052198483620234454011455111149365063946240472545398288332411818055040869427951279027405975059749360297586866737986343943071199029523215312890080825621259691281966944084616331478525965853482434855661783331701815854319557311791089421
+
+X = 4252141813347264797276096871298065242070358505647997888003056375005314524854352079310528912951451072362402998902953098969590411710408837750141172009165548416886410221360178681572909258112397873664014299809018676076741787758620956387796785085878200748397774100098277829187755707448924352539796147791636919657848349116938620050178856948159776951152904039928184566420276462662063200768003
+
+X = 3356647398302910967427184201762737607743709740247537918189248572175533954283802689062525081851852734889897477334086780084079147031820727070324920070840437155763226320158001284899218149321246112300036417841991332124497348096579076242448857352000771247540736125494932479963810579612138848322530062021159961102867820239356780956355417516589837048328595783663185309228059280538060703599461
+
+X = 3687125575229624930459923973437509789116885700012081850445193578448642376842508935093284643740184187161367381099111236064332065202257820899866692588032081832786591527415524508016853418430485681125008729650000322084879372381541270180139663134377177885154388955828150837227279419346006939707087576369145528995973353007018603605253425313893549623322294320271794700959979551805023755301753
+
+X = 6088560764944279853795552546797623009536823218028533977947580608201502351499239562431906098700162556623464821186830052418230647270268723857805333260836829600476446747589889271361495026265577182561494515318563339483672950711193945073071458843901227339418284308418249346164255537263904716264107533715262289286225173170023166725474264485741673708045592422332077910805474866320141535282581
+
+X = 6081766267938901970682791123502557184373300073506187731779846380408319328847515288256342223013061371721646953608064927698171220288957077247001074713915746730873934116374154451501318344435872804243131225731630921851260690656608624225797294197741881140769183047423036591415554315572834216165818564674211730699205101430138380407908411653089682561429233629882257193405738361710224809601753
+
+X = 5000879164859908887599881582814678322611278734193303790540199067694680487630949138029561981059040676622704805199759505344261591426777024652195253427903233383141727974223807795260167091026502016058553529785304239405043134061167377896985489252957729348463979606693348302035145499408189528388311420653920801330868717079628682687526955257367318056584393982273703259039286649949183439159753
+
+X = 5033660524073962747735388920230339629907033897027296197974576730565442285770625764556644742555355351632593596423437331609301931491253476638422358536021269897373786970147536124316480116188329213881347704723060451053853932258315572365588301231482715348124261924429243350354700249690669153072088296895527429954890479118171541902174533835033869855676849020277072477676533264422475881350311
+
+X = 7656692474335471169217545128846872228367812415627865759181393395824161882582837117325964824736330503446252358450994304908935138254338790534753258273308644071243551595575749198649556319567571199044097578241324151657090338112756973390540016908863938814598847539682462098038069550359839730605084928463925913734287506607573840601410310907532071167877913851021343288086388023500885078468451
+
+X = 6916552449605114038869281931877716049700938960849845402874660241341657411577096773695551899347519493283572406534713868735362052083315244085748653192655726562280996506756099290098242247672536575459382651810818256784829505942965567114371502731619372511210627161036252027448018534647854500781285005795085102984883071052178783569323746170765354579006834683132794491034727000125687008493191
+
+# F. Arnault, "Rabin-Miller primality test: composite numbers which pass it", Math. comp.
+# v.64, n.209, p 355-361.
+#
+# A strong pseudoprime for the first 46 primes
+
+X = 8038374574536394912570796143419421081388376882875581458374889175222974273765333652186502336163960045457915042023603208766569966760987284043965408232928738791850869166857328267761771029389697739470167082304286871099974399765441448453411558724506334092790222752962294149842306881685404326457534018329786111298960644845216191652872597534901
+
+# Richard G.E. Pinch, Absolute quadratic pseudorprimes
+# http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.210.6783&rep=rep1&type=pdf
+# Lucas-Charmichael-(-) numbers
+X = 28295303263921
+X = 443372888629441
+X = 582920080863121
+X = 894221105778001
+X = 2013745337604001
+
+# Lucas-Charmichael-(+) numbers
+X = 6479
+X = 84419
+X = 1930499
+X = 7110179
+X = 15857855
+X = 63278892599
+X = 79397009999
diff --git a/src/tests/test_bigint.cpp b/src/tests/test_bigint.cpp
index e73bbd08d..29f0203b8 100644
--- a/src/tests/test_bigint.cpp
+++ b/src/tests/test_bigint.cpp
@@ -445,17 +445,18 @@ BOTAN_REGISTER_TEST("bn_powmod", BigInt_Powmod_Test);
 class BigInt_IsPrime_Test : public Text_Based_Test
    {
    public:
-      BigInt_IsPrime_Test() : Text_Based_Test("bn/isprime.vec", "Value,IsPrime") {}
+      BigInt_IsPrime_Test() : Text_Based_Test("bn/isprime.vec", "X") {}
 
-      Test::Result run_one_test(const std::string&, const VarMap& vars) override
+      Test::Result run_one_test(const std::string& header, const VarMap& vars) override
          {
-         Test::Result result("BigInt IsPrime");
-
-         const BigInt value = get_req_bn(vars, "Value");
-         const bool v_is_prime = get_req_sz(vars, "IsPrime") > 0;
+         if(header != "Prime" && header != "NonPrime")
+            throw Test_Error("Bad header for prime test " + header);
 
-         result.test_eq("is_prime", Botan::is_prime(value, Test::rng()), v_is_prime);
+         const BigInt value = get_req_bn(vars, "X");
+         const bool is_prime = (header == "Prime");
 
+         Test::Result result("BigInt Test " + header);
+         result.test_eq("is_prime", Botan::is_prime(value, Test::rng()), is_prime);
          return result;
          }
    };