From bdb332623b6c0e0b9b5e27bfe47b863b86b6a6bf Mon Sep 17 00:00:00 2001 From: Mark Wooding Date: Tue, 3 Sep 2019 02:41:21 +0100 Subject: [PATCH] @@@ utils/: Add Pocklington proofs for important prime numbers. This is work in progress. I need to complete the (intensive) computations for some of the larger primes. --- utils/catacomb-ll-128-512.pock | 56 +++++++++++++ utils/catacomb-ll-160-1024.pock | 83 +++++++++++++++++++ utils/catacomb-ll-192-1536.pock | 105 ++++++++++++++++++++++++ utils/catacomb-ll-224-2048.pock | 124 +++++++++++++++++++++++++++++ utils/catacomb-ll-256-3072.pock | 172 ++++++++++++++++++++++++++++++++++++++++ utils/curve25519.pock | 68 ++++++++++++++++ utils/ed448.pock | 21 +++++ utils/findpock.mk | 23 ++++++ utils/findpock.sage | 81 +++++++++++++++++++ utils/g224.mk | 13 +++ utils/g384.mk | 24 ++++++ utils/poly1305.pock | 16 ++++ 12 files changed, 786 insertions(+) create mode 100644 utils/catacomb-ll-128-512.pock create mode 100644 utils/catacomb-ll-160-1024.pock create mode 100644 utils/catacomb-ll-192-1536.pock create mode 100644 utils/catacomb-ll-224-2048.pock create mode 100644 utils/catacomb-ll-256-3072.pock create mode 100644 utils/curve25519.pock create mode 100644 utils/ed448.pock create mode 100644 utils/findpock.mk create mode 100755 utils/findpock.sage create mode 100644 utils/g224.mk create mode 100644 utils/g384.mk create mode 100644 utils/poly1305.pock diff --git a/utils/catacomb-ll-128-512.pock b/utils/catacomb-ll-128-512.pock new file mode 100644 index 00000000..058b66a9 --- /dev/null +++ b/utils/catacomb-ll-128-512.pock @@ -0,0 +1,56 @@ +;;; -*-conf-windows-*- + +sievebits 32 + +small 5 = 5 +small 11 = 11 +small 17 = 17 +small 73 = 73 +small 919 = 919 +small 971 = 971 +small 3463 = 3463 +small 313163 = 313163 +small 3595409 = 3595409 +small 4484167 = 4484167 +small 5518543 = 5518543 +small 6879893 = 6879893 + +;;;-------------------------------------------------------------------------- +;;; First factor. + +pock $q0.0 = 2, 60730, [6879893] +pock q0 = 2, 3002666150370648941, [17, 919, 3463, $q0.0] +check q0, 128, 271499434142083095503643289076442321059 + +;;;-------------------------------------------------------------------------- +;;; Second factor. + +pock $q1.0 = 2, 158753, [11, 73, 971] +pock $q1.1 = 2, 357445, [$q1.0] +pock $q1.2 = 2, 15, [$q1.1] +pock $q1.3 = 2, 45, [$q1.2] +pock q1 = 2, 262818328748417486, [$q1.3] +check q1, 128, 251174382438405784142034780246853570853 + +;;;-------------------------------------------------------------------------- +;;; Third factor. + +pock $q2.0 = 2, 396, [5518543] +pock $q2.1 = 2, 2, [$q2.0] +pock $q2.2 = 2, 1268335209, [$q2.1] +pock q2 = 2, 2927510370377493347, [$q2.2] +check q2, 128, 259658226261043076610234546745792177763 + +;;;-------------------------------------------------------------------------- +;;; Fourth factor. + +pock q3 = 2, 5452482166508126949, [5, 313163, 3595409, 4484167] +check q3, 128, 275292752516630714214627215608643381611 + +;;;-------------------------------------------------------------------------- +;;; Put them all together. + +pock p = 2, 1, [q0, q1, q2, q3] +check p, 512, 9749248307666198278625282069621029423614285873414870747628872221551255623823205551438908261067675576856742534707535779666498916029617598868013496631088223 + +;;;----- That's all, folks -------------------------------------------------- diff --git a/utils/catacomb-ll-160-1024.pock b/utils/catacomb-ll-160-1024.pock new file mode 100644 index 00000000..e24e9e74 --- /dev/null +++ b/utils/catacomb-ll-160-1024.pock @@ -0,0 +1,83 @@ +;;; -*-conf-windows-*- + +sievebits 32 + +small 2 = 2 +small 3 = 3 +small 5 = 5 +small 11 = 11 +small 13 = 13 +small 17 = 17 +small 47 = 47 +small 71 = 71 +small 401 = 401 +small 1409 = 1409 +small 23581 = 23581 +small 156833 = 156833 +small 394123 = 394123 +small 871649 = 871649 +small 5876687 = 5876687 +small 18875107 = 18875107 +small 63190123 = 63190123 +small 83108387 = 83108387 + +;;;-------------------------------------------------------------------------- +;;; First factor. + +pock $q0.0 = 2, 19483749, [47, 71, 23581] +pock $q0.1 = 2, 103005859808795823, [2, 3, 13, $q0.0] +pock q0 = 2, 7527498979719, [$q0.1] +check q0, 160, 741802303617786660769426556982216255271020758647 + +;;;-------------------------------------------------------------------------- +;;; Second factor. + +pock $q1.0 = 2, 1102545, [63190123] +pock $q1.1 = 2, 6791537660, [$q1.0] +pock $q1.2 = 2, 880359, [$q1.1] +pock $q1.3 = 2, 107739483877920611, [$q1.2] +pock q1 = 2, 1, [$q1.3] +check q1, 160, 1436145082693042410533997633791272917636904431479 + +;;;-------------------------------------------------------------------------- +;;; Third factor. + +pock $q2.0 = 2, 51810, [83108387] +pock $q2.1 = 2, 275, [$q2.0] +pock q2 = 7, 392753319979291851337545, [3, 5, 18875107, $q2.1] +check q2, 160, 1053371763883815722032496338163704236230178616951 + +;;;-------------------------------------------------------------------------- +;;; Fourth factor. + +pock $q3.0 = 2, 42115, [871649] +pock $q3.1 = 3, 3546095728807, [11, 17, $q3.0] +pock q3 = 2, 6244124526426951914047, [$q3.1] +check q3, 160, 1215995718665420681503927009463070333378310191827 + +;;;-------------------------------------------------------------------------- +;;; Fifth factor. + +pock $q4.0 = 2, 3194856718821, [401, 394123, 5876687] +pock $q4.1 = 2, 88023387, [$q4.0] +pock q4 = 2, 693071580690, [$q4.1] +check q4, 160, 1448192360714741582009673893725822727433041298541 + +;;;-------------------------------------------------------------------------- +;;; Sixth (large) factor. + +pock $q5.0 = 2, 483753262, [17, 1409, 156833] +pock $q5.1 = 2, 4, [$q5.0] +pock $q5.2 = 2, 18, [$q5.1] +pock $q5.3 = 2, 37886, [$q5.2] +pock $q5.4 = 2, 4776601169474131886106058, [$q5.3] +pock q5 = 2, 11649782787072175, [$q5.4] +check q5, 224, 17654251325616983743094122151298023764308424678047987263690296014551 + +;;;-------------------------------------------------------------------------- +;;; Put them all together. + +pock p = 2, 1, [q0, q1, q2, q3, q4, q5] +check p, 1023, 69775951038073580217048751187698556149910661999359201823421066000439190288124938297116840422332973903349265313226189724474672148172906743149961449018143681316055777549225333684417216672046201528908637006946721694566251047975893301628540057123962444434130461052652526277961662241061299058137499738575071867183 + +;;;----- That's all, folks -------------------------------------------------- diff --git a/utils/catacomb-ll-192-1536.pock b/utils/catacomb-ll-192-1536.pock new file mode 100644 index 00000000..13b7986d --- /dev/null +++ b/utils/catacomb-ll-192-1536.pock @@ -0,0 +1,105 @@ +;;; -*-conf-windows-*- + +sievebits 32 + +small 2 = 2 +small 3 = 3 +small 5 = 5 +small 7 = 7 +small 19 = 19 +small 61 = 61 +small 113 = 113 +small 397 = 397 +small 523 = 523 +small 1361 = 1361 +small 58403 = 58403 +small 127291 = 127291 +small 149027 = 149027 +small 445339 = 445339 +small 964679 = 964679 +small 1915619 = 1915619 +small 7495531 = 7495531 +small 41700697 = 41700697 +small 85904549 = 85904549 +small 89406461 = 89406461 + +;;;-------------------------------------------------------------------------- +;;; First factor. + +pock $q0.0 = 2, 599673, [3, 445339] +pock $q0.1 = 2, 6, [$q0.0] +pock $q0.2 = 2, 37216238751500, [523, $q0.1] +pock q0 = 2, 2181607886944713854570678098, [$q0.2] +check q0, 192, 3265942811645946563242629602041107481841853511350443184197 + +;;;-------------------------------------------------------------------------- +;;; Second factor. + +pock $q1.0 = 2, 10091300, [41700697] +pock $q1.1 = 2, 7266992134776439, [19, $q1.0] +pock q1 = 2, 9042734768136800077225363, [$q1.1] +check q1, 192, 4203281750074745560664516895168522022509720946720609480259 + +;;;-------------------------------------------------------------------------- +;;; Third factor. + +pock $q2.0 = 2, 9900, [85904549] +pock $q2.1 = 2, 272940, [$q2.0] +pock $q2.2 = 2, 90407177525, [$q2.1] +pock $q2.3 = 2, 185793279988736350, [$q2.2] +pock q2 = 2, 40144676658, [$q2.3] +check q2, 192, 5008750505930402098755083797499946811957880698185704286517 + +;;;-------------------------------------------------------------------------- +;;; Fourth factor. + +pock $q3.0 = 2, 293749, [5, 113, 1361] +pock $q3.1 = 2, 4, [$q3.0] +pock $q3.2 = 2, 185056946153757, [2, 61, $q3.1] +pock $q3.3 = 2, 74168236934813703, [$q3.2] +pock q3 = 2, 112317748991, [$q3.3] +check q3, 192, 5437815993255342021982036827752826453901545498474314278259 + +;;;-------------------------------------------------------------------------- +;;; Fifth factor. + +pock $q4.0 = 6, 2844543891759, [2, 3, 397, 58403, 127291] +pock $q4.1 = 2, 6244865664613736594, [$q4.0] +pock $q4.2 = 2, 21894839271, [$q4.1] +pock q4 = 2, 35, [$q4.2] +check q4, 192, 3856915640937851719940744630159301063173277801391043813291 + +;;;-------------------------------------------------------------------------- +;;; Sixth factor. + +pock $q5.0 = 2, 252277691602972, [3, 1915619, 89406461] +pock $q5.1 = 2, 86808465789509869145375, [$q5.0] +pock q5 = 2, 67254, [$q5.1] +check q5, 192, 6054082443893470116716978196535076127652382149483455623509 + +;;;-------------------------------------------------------------------------- +;;; Seventh factor. + +pock $q6.0 = 5, 40962985, [3, 5, 7, 964679] +pock $q6.1 = 2, 55194680320049063319715, [2, 7495531, $q6.0] +pock $q6.2 = 2, 82423836319, [$q6.1] +pock q6 = 2, 1, [$q6.2] +check q6, 192, 4527580176039500642864307604310793340910014541817043735439 + +;;;-------------------------------------------------------------------------- +;;; Eighth factor. + +pock $q7.0 = 3, 38990, [2, 149027] +pock $q7.1 = 2, 2964985671, [$q7.0] +pock $q7.2 = 2, 1238052, [$q7.1] +pock $q7.3 = 2, 200918482739479179978, [$q7.2] +pock q7 = 2, 12505948575, [$q7.3] +check q7, 192, 3430016280837410693307976287901159907499384818919106315351 + +;;;-------------------------------------------------------------------------- +;;; Put them all together. + +pock p = 2, 1, [q0, q1, q2, q3, q4, q5, q6, q7] +check p, 1533, 271163844483056215974969265313967454661676256266511940924304321373021958106999031565631233996938091358447023677706317722695337026864685384345663120704730255257202847527192911265950638087504732115876440997750045081880863038141607482083211725689822517898206821836185159703555104632867971994304356879518337226475272092974597967943366038800089283400183985773753490774687966167193456249452974119129018696293050595073100284829925638444204379135326678813960293114732959 + +;;;----- That's all, folks -------------------------------------------------- diff --git a/utils/catacomb-ll-224-2048.pock b/utils/catacomb-ll-224-2048.pock new file mode 100644 index 00000000..e96863e3 --- /dev/null +++ b/utils/catacomb-ll-224-2048.pock @@ -0,0 +1,124 @@ +;;; -*-conf-windows-*- + +sievebits 32 + +small 2 = 2 +small 3 = 3 +small 5 = 5 +small 11 = 11 +small 17 = 17 +small 23 = 23 +small 43 = 43 +small 53 = 53 +small 73 = 73 +small 103 = 103 +small 229 = 229 +small 787 = 787 +small 1019 = 1019 +small 1031 = 1031 +small 2371 = 2371 +small 3259 = 3259 +small 3343 = 3343 +small 6823 = 6823 +small 14009 = 14009 +small 16763 = 16763 +small 31271 = 31271 +small 32911 = 32911 +small 44711 = 44711 +small 65629 = 65629 +small 548749 = 548749 +small 685493 = 685493 +small 922729 = 922729 +small 2416067 = 2416067 +small 2724367 = 2724367 +small 20455543 = 20455543 +small 283040143 = 283040143 + +;;;-------------------------------------------------------------------------- +;;; First factor. + +pock $q0.0 = 2, 77557244, [32911, 65629] +pock $q0.1 = 2, 1314023863943291657101441, [103, 548749, $q0.0] +pock q0 = 2, 188376034169635741, [$q0.1] +check q0, 224, 18749474022970964965792505501868745784157349746475161167020805104727 + +;;;-------------------------------------------------------------------------- +;;; Second factor. + +pock $q1.0 = 13, 9773254, [2, 3, 1019, 3259] +pock $q1.1 = 2, 93311355, [3343, 2724367] +pock q1 = 2, 1816846807414613664743331831208744, [11, $q1.0, $q1.1] +check q1, 224, 26459793266106143518700371316953986751950547842631163615799385478033 + +;;;-------------------------------------------------------------------------- +;;; Third factor. + +pock $q2.0 = 2, 139291, [685493] +pock $q2.1 = 2, 4167310526515483, [1031, 16763, $q2.0] +pock q2 = 2, 425068431593487259907781956594238, [$q2.1] +check q2, 224, 23385205652191135191327958583020476187937251160152256504448581299573 + +;;;-------------------------------------------------------------------------- +;;; Fourth factor. + +pock $q3.0 = 2, 22932, [2416067] +pock $q3.1 = 2, 6063239, [$q3.0] +pock $q3.2 = 2, 124379961, [$q3.1] +pock $q3.3 = 2, 70999304, [$q3.2] +pock q3 = 2, 182104245730305170970108862655863, [$q3.3] +check q3, 224, 17287418736358368314036906794523064561326146990020019216549187737103 + +;;;-------------------------------------------------------------------------- +;;; Fifth factor. + +pock $q4.0 = 2, 9984, [922729] +pock $q4.1 = 2, 965786944, [53, $q4.0] +pock $q4.2 = 2, 417, [$q4.1] +pock q4 = 3, 1166927186146195925203643655841975, [3, 5, 6823, 44711, $q4.2] +check q4, 224, 16800288948485454351848726052252844830400274721321174607061304165751 + +;;;-------------------------------------------------------------------------- +;;; Sixth factor. + +pock $q5.0 = 2, 2588625, [283040143] +pock $q5.1 = 2, 69033, [2, 43, 2371] +pock $q5.2 = 2, 4754043, [$q5.1] +pock $q5.3 = 2, 15, [$q5.2] +pock q5 = 2, 629586845267554567042966724914193, [$q5.0, $q5.3] +check q5, 224, 14817124042645057452868896146782513905071983176482538876644503596827 + +;;;-------------------------------------------------------------------------- +;;; Seventh factor. + +pock $q6.0 = 2, 67125, [53, 14009] +pock $q6.1 = 2, 95117540, [$q6.0] +pock $q6.2 = 2, 10551, [$q6.1] +pock $q6.3 = 3, 22632791408615889282525061, [3, 229, $q6.2] +pock q6 = 2, 967965417275960, [$q6.3] +check q6, 224, 24089412810223523640445605527780074479098235298741910558499656689361 + +;;;-------------------------------------------------------------------------- +;;; Eighth factor. + +pock $q7.0 = 2, 7134269, [3, 20455543] +pock $q7.1 = 2, 12201211278023578452, [73, 787, $q7.0] +pock q7 = 2, 7706102558810683184709001911, [$q7.1] +check q7, 224, 18919386933765812741111621380736732547216460099506859126765656541087 + +;;;-------------------------------------------------------------------------- +;;; Ninth (large) factor. + +pock $q8.0 = 2, 4774038, [17, 23, 31271] +pock $q8.1 = 2, 587, [$q8.0] +pock $q8.2 = 2, 2301482227, [$q8.1] +pock $q8.3 = 2, 8617612182191973, [$q8.2] +pock q8 = 2, 3146437495502300328833645023384575, [$q8.3] +check q8, 256, 68423637472150676252123752731403397187923476268634988015857219241126016100451 + +;;;-------------------------------------------------------------------------- +;;; Put them all together. + +pock p = 2, 1, [q0, q1, q2, q3, q4, q5, q6, q7, q8] +check p, 2045, 3113844893182469436423817481922802329154474934213986369565700235348098440269001480103560846535113493144522446351379349356211385191632945710341444495577638160076546999114567117877732507854868463110804063964212132228977417231690350182211790515961798314443291574015832300281633156990779527484905381392680532643288437519954295652416759988107781937077836044809781096660654460207183523575424301901443740349094152501352983589721328225459512044516684078781305909247963063040562914192132284695886353707336911126238203292592145886841905764429235683487108646920559740458905874135798982283901137307047131586817745416509850061963 + +;;;----- That's all, folks -------------------------------------------------- diff --git a/utils/catacomb-ll-256-3072.pock b/utils/catacomb-ll-256-3072.pock new file mode 100644 index 00000000..1dc2d290 --- /dev/null +++ b/utils/catacomb-ll-256-3072.pock @@ -0,0 +1,172 @@ +;;; -*-conf-windows-*- + +sievebits 32 + +small 2 = 2 +small 3 = 3 +small 5 = 5 +small 7 = 7 +small 11 = 11 +small 13 = 13 +small 17 = 17 +small 67 = 67 +small 73 = 73 +small 89 = 89 +small 103 = 103 +small 107 = 107 +small 151 = 151 +small 307 = 307 +small 479 = 479 +small 911 = 911 +small 1549 = 1549 +small 2819 = 2819 +small 5333 = 5333 +small 11813 = 11813 +small 19037 = 19037 +small 33811 = 33811 +small 37987 = 37987 +small 65579 = 65579 +small 101149 = 101149 +small 148663 = 148663 +small 1065937 = 1065937 +small 1611773 = 1611773 +small 2703341 = 2703341 +small 23298673 = 23298673 +small 41105063 = 41105063 +small 46402949 = 46402949 +small 50464027 = 50464027 +small 63180751 = 63180751 +small 104583559 = 104583559 +small 121012807 = 121012807 +small 223299767 = 223299767 +small 651836959 = 651836959 +small 755741237 = 755741237 +small 989213989 = 989213989 +small 1123562633 = 1123562633 +small 1939589783 = 1939589783 + +;;;-------------------------------------------------------------------------- +;;; First factor. + +pock $q0.0 = 2, 221, [63180751] +pock $q0.1 = 2, 287985, [$q0.0] +pock $q0.2 = 2, 6, [$q0.1] +pock $q0.3 = 2, 799592, [$q0.2] +pock $q0.4 = 2, 140121481233820837, [$q0.3] +pock q0 = 2, 516012789589567525245228517748639317, [$q0.4] +check q0, 256, 89271282791461757245617785540129155142212959423277129581512553253419075634703 + +;;;-------------------------------------------------------------------------- +;;; Second factor. + +pock $q1.0 = 3, 26655, [5, 73, 307] +pock $q1.1 = 2, 113566177, [89, $q1.0] +pock $q1.2 = 2, 2313, [$q1.1] +pock q1 = 3, 110885609577740909340347456997460959441, [11, 2703341, 23298673, $q1.2] +check q1, 256, 85831054040144766435760746678768685031101307134949905606966042252247846736739 + +;;;-------------------------------------------------------------------------- +;;; Third factor. + +pock $q2.0 = 2, 967, [46402949] +pock $q2.1 = 2, 10150, [$q2.0] +pock $q2.2 = 2, 577531808038551323, [2, 5, 7, 11, $q2.1] +pock $q2.3 = 2, 1909, [$q2.2] +pock $q2.4 = 2, 4, [$q2.3] +pock $q2.5 = 2, 161492771766, [$q2.4] +pock q2 = 2, 3346150790641406755842632, [$q2.5] +check q2, 256, 106974241938861083915762659525277908624697359844432666343676471334975764276049 + +;;;-------------------------------------------------------------------------- +;;; Fourth factor. + +pock $q3.0 = 2, 3986961, [2819, 19037] +pock $q3.1 = 2, 717472194, [$q3.0] +pock $q3.2 = 7, 296079454464816888738186, [2, $q3.1] +pock $q3.3 = 2, 38351856539861991076107006, [$q3.2] +pock q3 = 2, 665, [$q3.3] +check q3, 256, 74188558205228235051388929541366735789893711666871143431413381703129034070571 + +;;;-------------------------------------------------------------------------- +;;; Fifth factor. + +pock $q4.0 = 2, 9100134, [50464027] +pock q4 = 3, 123286331671468380322893919539199160018, [3, 7, 1065937, 104583559, 121012807, $q4.0] +check q4, 256, 64157908398727096384500697645883202842334928055247546726538359334678953374533 + +;;;-------------------------------------------------------------------------- +;;; Sixth factor. + +pock $q5.0 = 2, 15902537, [5, 151, 65579] +pock $q5.1 = 2, 15, [$q5.0] +pock $q5.2 = 2, 205994, [$q5.1] +pock $q5.3 = 2, 4508442663943453928415, [$q5.2] +pock $q5.4 = 2, 78, [$q5.3] +pock q5 = 2, 1678161634428932615998239726693, [$q5.4] +check q5, 256, 91888021786522811643506031866522514605588426773858897142365239694153824388723 + +;;;-------------------------------------------------------------------------- +;;; Seventh factor. + +pock $q6.0 = 2, 94880014, [223299767] +pock $q6.1 = 2, 2611430923, [103, 479, 148663] +pock q6 = 2, 132103609398873302338919658147561406741, [3, 67, $q6.0, $q6.1] +check q6, 256, 86202112980065410413258705060295663522206392211838714986438313175672540034679 + +;;;-------------------------------------------------------------------------- +;;; Eighth factor. + +pock $q7.0 = 2, 5983906, [41105063] +pock $q7.1 = 2, 13, [$q7.0] +pock $q7.2 = 2, 2, [989213989] +pock $q7.3 = 2, 4, [$q7.2] +pock $q7.4 = 3, 41726813637741, [3, 911, $q7.3] +pock q7 = 2, 550759989015563177538248996460639, [$q7.1, $q7.4] +check q7, 256, 101718718485667336124248700072690338405530751717394437871691123315096947983183 + +;;;-------------------------------------------------------------------------- +;;; Ninth factor. + +pock $q8.0 = 2, 544, [755741237] +pock $q8.1 = 2, 37923639, [651836959] +pock $q8.2 = 2, 2737547132248882314854590682374331, [1939589783, $q8.0, $q8.1] +pock q8 = 2, 100378, [$q8.2] +check q8, 256, 86666452227843804499517643692692014159268339780015078349842908985056208435853 + +;;;-------------------------------------------------------------------------- +;;; Tenth factor. + +pock $q9.0 = 2, 18810, [1123562633] +pock $q9.1 = 2, 1260, [$q9.0] +pock $q9.2 = 2, 4519227, [13, 107, 11813] +pock $q9.3 = 2, 751612091072, [$q9.2] +pock q9 = 2, 2265614871095316418059393297451933, [$q9.1, $q9.3] +check q9, 256, 107755126504421076829573915729759110231793946298489260169446357640494497518059 + +;;;-------------------------------------------------------------------------- +;;; Eleventh factor. + +pock $q10.0 = 2, 52944235, [3, 5, 17, 307, 1549] +pock $q10.1 = 2, 29043, [$q10.0] +pock $q10.2 = 2, 7481661599, [$q10.1] +pock $q10.3 = 2, 7, [$q10.2] +pock q10 = 2, 105231020596360331675725034221656645151, [2, 1611773, $q10.3] +check q10, 256, 106001951238340530179427922980522671485637210826387486585015951056665476348869 + +;;;-------------------------------------------------------------------------- +;;; Twelfth factor. + +pock $q11.0 = 2, 21040824, [5333, 101149] +pock $q11.1 = 2, 507442, [3, 11, 33811] +pock $q11.2 = 2, 378, [$q11.1] +pock $q11.3 = 2, 1716, [$q11.2] +pock q11 = 2, 20166606578680090414315933249796640869, [37987, $q11.0, $q11.3] +check q11, 256, 102183593360154313236939029184315018977616435836107396944951781361526011480879 + +;;;-------------------------------------------------------------------------- +;;; Put them all together. + +pock p = 2, 1, [q0, q1, q2, q3, q4, q5, q6, q7, q8, q9, q10, q11] +check p, 3069, 635937223373484887991140560420669529960468634418212194527199243018802509220923645480563049852948379631872315326364181219863391536284352632127476573990043945919830000350264391397346335414535975554209931971547284463207275833747975949070870172306582775948778222246682185331862354083029804303222690541851195763223409045953191584611635790362191424339883737168342809190665629632289528654983812904611647818546832860081714363504512892885600580448186423533085059295328609139522690627823102925150246378111221377628009667319528150747320084312110336288028683700603719073769314245952464113622780032073817850603131463761017417455806035107984621889773217138911836476354442521466189648565925624512100087534918369360007697883847802211797655614684090408428715299537509886614640500137409891381649298835563011151796284848165977247286439820050405175697064122759870661294968492275655767983096727976056361878300352234381528837008128941375285251387 + +;;;----- That's all, folks -------------------------------------------------- diff --git a/utils/curve25519.pock b/utils/curve25519.pock new file mode 100644 index 00000000..7ebf4321 --- /dev/null +++ b/utils/curve25519.pock @@ -0,0 +1,68 @@ +;;; -*-conf-windows-*- +;;; +;;; Primality proofs for Curve25519. + +sievebits 32 + +small 127 = 127 +small 2281 = 2281 +small 3911 = 3911 +small 4153 = 4153 +small 8053 = 8053 +small 28859 = 28859 +small 430751 = 430751 +small 531581 = 531581 +small 1224481 = 1224481 +small 8574133 = 8574133 +small 2773320623 = 2773320623 + +;;;-------------------------------------------------------------------------- +;;; Check the coordinate field order, 2^255 - 19, using Pocklington. + +pock $p.0 = 2, 13, [2773320623] +pock $p.1 = 2, 881391, [127, 8574133] +pock $p.2 = 2, 272545200, [$p.0, $p.1] +pock $p.3 = 2, 8876292, [4153, 430751] +pock $p.4 = 2, 15454641059763671901, [$p.2, $p.3] +pock 2p255m19 = 2, 390882, [$p.4] +check 2p255m19, 255, 57896044618658097711785492504343953926634992332820282019728792003956564819949 + +;;;-------------------------------------------------------------------------- +;;; Check the large prime dividing the primary curve order. +;;; +;;; If this is l, then the curve order is 8 l. + +pock $l.0 = 2, 966, [531581, 1224481] +pock $l.1 = 2, 1763, [$l.0] +pock $l.2 = 2, 19401055, [$l.1] +pock $l.3 = 2, 57415875541459, [$l.2] +pock $l.4 = 2, 7, [$l.3] +pock l25519 = 2, 13081953933241429764863578700404002, [$l.4] +check l25519, 253, 7237005577332262213973186563042994240857116359379907606001950938285454250989 + +;;;-------------------------------------------------------------------------- +;;; Check the large prime dividing the quadratic twist curve order. +;;; +;;; If this is l', then the twist's order is 4 l'. + +pock $ll.0 = 2, 39277, [2281, 28859] +pock $ll.1 = 2, 2181507, [$ll.0] +pock $ll.2 = 2, 16086, [3911, 8053] +pock $ll.3 = 2, 4458627402, [$ll.1, $ll.2] +pock $ll.4 = 2, 256850, [$ll.3] +pock $ll.5 = 2, 130890, [$ll.4] +pock ll25519 = 2, 263995577955218862480758, [$ll.5] +check ll25519, 253, 14474011154664524427946373126085988481603263447650325797860494125407373907997 + +;;;-------------------------------------------------------------------------- +;;; Prove primality of the coordinate field again, using ECPP. +;;; +;;; Two proofs, for the primary curve and its twist. + +ecpp 2p255m19.1 = 57896044618658097711785492504343953926634992332820282019728792003956564819949, -102314837768112, 398341948620716521344, 5840268, 8547346653146300712246123037639701684230346772043151331330916737595562181421, [l25519] +check 2p255m19.1, 255, 57896044618658097711785492504343953926634992332820282019728792003956564819949 + +ecpp 2p255m19.2 = 57896044618658097711785492504343953926634992332820282019728792003956564819949, -6548149617159168, -203951077693806858928128, 8, 27383066511106528251246245619606060380838675100485973882307388960169781073998, [ll25519] +check 2p255m19.2, 255, 57896044618658097711785492504343953926634992332820282019728792003956564819949 + +;;;----- That's all, folks -------------------------------------------------- diff --git a/utils/ed448.pock b/utils/ed448.pock new file mode 100644 index 00000000..fc2bc066 --- /dev/null +++ b/utils/ed448.pock @@ -0,0 +1,21 @@ +;;; -*-conf-windows-*- + +sievebits 32 + +small 271 = 271 +small 2531 = 2531 +small 379979 = 379979 +small 1255525949 = 1255525949 +small 1335912079 = 1335912079 +small 1764234391 = 1764234391 + +pock $p.0 = 2, 475164, [271, 379979] +pock $p.1 = 3, 338688, [2531, $p.0] +pock $p.2 = 2, 9846158, [1764234391] +pock $p.3 = 2, 520, [$p.2] +pock $p.4 = 3, 8251, [$p.3] +pock $p.5 = 2, 12, [1335912079] +pock $p.6 = 2, 392, [$p.5] +pock $p.7 = 3, 592753238784, [1255525949, $p.6] +pock 2p448m2p224m1 = 2, 97101489617462949088673466836125803538803873344385433, [$p.1, $p.4, $p.7] +check 2p448m2p224m1, 448, 726838724295606890549323807888004534353641360687318060281490199180612328166730772686396383698676545930088884461843637361053498018365439 diff --git a/utils/findpock.mk b/utils/findpock.mk new file mode 100644 index 00000000..002a2def --- /dev/null +++ b/utils/findpock.mk @@ -0,0 +1,23 @@ +### -*-makefile-*- + +FACTORS := $(shell seq -f"q%g" 0 $$(expr $(NFACTORS) - 1)) + +all: $(addprefix $(GROUP).d/,$(FACTORS)) $(GROUP).d/final + { echo ";;; -*-conf-windows-*-" && \ + echo && \ + echo "sievebits 32" && \ + echo && \ + grep -h '^small' $+ | sort -k4n -u && \ + for q in $(FACTORS); do echo; grep '^[^s]' $(GROUP).d/$$q; done && \ + echo && \ + grep '^[^s]' $(GROUP).d/final; } + +$(addprefix $(GROUP).d/,$(FACTORS)): $(GROUP).d/%: + @mkdir -p $(GROUP).d/ + ./findpock.sage $* $($*) >$@.new && mv $@.new $@ + +$(GROUP).d/final: + @mkdir -p $(GROUP).d/ + ./findpock.sage p 0 $(foreach q,$(FACTORS),$($q)) >$@.new && mv $@.new $@ + +show:; : $x diff --git a/utils/findpock.sage b/utils/findpock.sage new file mode 100755 index 00000000..02e87755 --- /dev/null +++ b/utils/findpock.sage @@ -0,0 +1,81 @@ +#! /usr/local/bin/sage + +from sys import argv +from itertools import combinations + +sievebits = 32 + +SEQ = 0 +LABEL = {} + +def label(p): + global SEQ + try: lab = LABEL[p] + except KeyError: + if p.nbits() < sievebits: lab = LABEL[p] = '%d' % p + else: + lab = LABEL[p] = '$%s.%d' % (name, SEQ) + SEQ += 1 + return lab + +SMALL = set() +POCK = [] +DONE = {} + +def pock(p, rr): + r = prod(rr) + ll = map(recurse, rr) + lab = DONE[p] = label(p) + a = 2 + while True: + if pow(a, p - 1, p) != 1: + raise ValueError('%d not prime (%d is Fermat witness)' % (p, a)) + win = True + for q in rr: + g = gcd(pow(a, (p - 1)/q, p) - 1, p) + if 1 < g < p: raise ValueError('%d not prime (%d divides)' % (p, g)) + if g != 1: win = False + if win: break + a += 1 + POCK.append('pock %s = %d, %d, [%s]' % + (lab, a, (p - 1)/(2*r), ', '.join(ll))) + return lab + +def recurse(p): + try: return DONE[p] + except KeyError: pass + + if p.nbits() < sievebits: + lab = DONE[p] = str(p) + SMALL.add(p) + return lab + + best, score = None, p + qq = [q for (q, e) in factor((p - 1)/2)] + for n in xrange(1, len(qq) + 1): + for rr in combinations(qq, n): + r = prod(rr) + if r^2 <= p: continue + if r < score: best, score = rr, r + + best = list(best); best.sort() + return pock(p, best) + +name, p = argv[1], Integer(argv[2]) +if len(argv) == 3: + LABEL[p] = name + recurse(p) + for q in sorted(SMALL): print 'small %d = %d' % (q, q) + print +else: + qq = map(Integer, argv[3:]) + for i in xrange(len(qq)): LABEL[qq[i]] = DONE[qq[i]] = 'q%d' % i + q = prod(qq) + if not p: p = 2*q + 1 + elif p%(2*q) != 1: raise ValueError('incorrect factorization') + if q^2 <= p: raise ValueError('factorization insufficient') + LABEL[p] = name + pock(p, qq) + +for line in POCK: print line +print 'check %s, %d, %d' % (name, p.nbits(), p) diff --git a/utils/g224.mk b/utils/g224.mk new file mode 100644 index 00000000..2485e1c8 --- /dev/null +++ b/utils/g224.mk @@ -0,0 +1,13 @@ +GROUP = catacomb-ll-224-2048 +NFACTORS = 9 +q0 = 18749474022970964965792505501868745784157349746475161167020805104727 +q1 = 26459793266106143518700371316953986751950547842631163615799385478033 +q2 = 23385205652191135191327958583020476187937251160152256504448581299573 +q3 = 17287418736358368314036906794523064561326146990020019216549187737103 +q4 = 16800288948485454351848726052252844830400274721321174607061304165751 +q5 = 14817124042645057452868896146782513905071983176482538876644503596827 +q6 = 24089412810223523640445605527780074479098235298741910558499656689361 +q7 = 18919386933765812741111621380736732547216460099506859126765656541087 +q8 = 68423637472150676252123752731403397187923476268634988015857219241126016100451 + +include findpock.mk diff --git a/utils/g384.mk b/utils/g384.mk new file mode 100644 index 00000000..89b83dc7 --- /dev/null +++ b/utils/g384.mk @@ -0,0 +1,24 @@ +GROUP = catacomb-ll-384-7680 +NFACTORS = 20 +q0 = 33126499307317576797871833023217004335728314922050873541842362900543256622519036793987373377351818708943025119171013 +q1 = 39355538213779465581327905402419970362362827155309917911796788256581129259700838386618633466328785307910060598484089 +q2 = 24990988056514685939227489925894893740599480412356885556635114159485308445876939770393364881549529860169928180358751 +q3 = 29710393998736802825004025579677917729092552502321819764111039726208854433428942095508492913578932136133436765710137 +q4 = 30739990822741028562742164007270587796692423847729505877569973917995737943042778723217469119645159801429991709987411 +q5 = 38467104071408925475553899301420008676544897864238119086844380566779548268491996551153519861871328607592273248640063 +q6 = 26249202441547885968346939762119297860863007366370739789532392353072352597721946778221716140197625626869457398407943 +q7 = 35113510884533077462576668870689443131037411172656549819745724383911555364605887073198680214468558440325573744139273 +q8 = 22799521027155572453510717469170377645186972219918245680012037643676230864376926993221681405925996643835629140041553 +q9 = 35237903572957790995889936270089932531166269466107290813994448142778414605138387309936585467385466822473088271031989 +q10 = 27428052831286394078655137717030752972732374814011687175621160166365055343004612251793080304507732432129056200291727 +q11 = 20653805003557030567582482355924457431196786739428479408853799555350943953733271029133593962324338862058432369521581 +q12 = 20826184829221859923080357759745090302065026449606341016497732724141145977802307612276509411486570418197846062995143 +q13 = 26186565771074398017481590713676896769947111595943534554546789381717976098676902111563130714755073678247235508588839 +q14 = 25062273677906610062620640227124848504281876654137470308684277968100792708156285085199790540571827305085913619650939 +q15 = 28620246516918127020366359691491908359742867622666550018522929993024502416569436771205673472786682579926850748107811 +q16 = 37856943506407240881326721106883344091018942980536189030625919515240362253893275735656123073145875668656864714642553 +q17 = 22067087486134964177557541373312161142485654981859077450341811542291069526079170766664489890765256439946132722899891 +q18 = 23098926790257626751285008739153477597734517594763012574497649607286859624287080618144594023194033634778511868647877 +q19 = 29874082012645596638985309976826212131328113612069017684649166404247820505933961130580996098120522635385267888074961 + +include findpock.mk diff --git a/utils/poly1305.pock b/utils/poly1305.pock new file mode 100644 index 00000000..ce75e491 --- /dev/null +++ b/utils/poly1305.pock @@ -0,0 +1,16 @@ +;;; -*-conf-windows-*- +;;; +;;; Primality proof for Poly1305. +;;; +;;; This is exactly the proof of Theorem 3.1 from Daniel J. Bernstein, `The +;;; Poly1305-AES message-authentication code'. + +sievebits 32 + +small a = 37003 +small b = 221101 + +pock p2 = 2, 245965590, [a, b] +pock p1 = 2, 111445310351, [p2] +pock 2p130m5 = 2, 758657323, [p1] +check 2p130m5, 130, 1361129467683753853853498429727072845819 -- 2.11.0