PrimeAndPrejudice.frink

View or download PrimeAndPrejudice.frink in plain text format


// Test of adversiarial primality testing of not-really-prime numbers.
// Paper:  Prime and Prejudice: Primality Testing Under Adversarial Conditions
// Martin R. Albrecht and Jake Massimo and Kenneth G. Paterson and
// Juraj Somorovsky
//
// See:  https://eprint.iacr.org/2018/749

// Appendix D
p1 = 2^960 * 0x00000000000000000000000000000000000000000002e394 +
     2^768 * 0x1a2fe4aa9e66358347f63732494d08635ccc9ae0a3c17764 +
     2^576 * 0xa8e266f4d26758ab804a702c235f63b1e109a81fc007f94b +
     2^384 * 0xec5158f231a30b1cbf96a7fc444c09be62f5a809f049cc5d +
     2^192 * 0xe94b84275c38885c9b61a6bdc44111501527722a8ac87ea2 +
             0xa5d4498caa2d9d07b34001a508fa53063991206268c547d7

k2 = 10937
k3 = 11257

p2 = k2(p1-1)+1
p3 = k3(p1-1)+1

n = p1 p2 p3

println["Appendix D: " + (isPrime[n] == true ? "FAIL" : "OK")]


// Appendix F
p1 = 2^1344 * 0x0000000000000000000000000000083dda18eb04a7597ca3 +
     2^1152 * 0xc6bc877df8a08eec6725fa0832cba270c42adc358bc0cf50 +
     2^960 *  0xc82cb10f2733c3fb8875231fc1498a7b14cb675fac1bf3c5 +
     2^768 *  0x127a76fc11e5d20e27940c95ceba671fe1c4232250b74cbd +
     2^576 *  0xf8448c90321513324c0681afb4ba003353b1afb0f1e8b91c +
     2^384 *  0x60af672a5a6f4d06dd0070a4bc74e425f3eae90379e57754 +
     2^192 *  0x82d26e80e247464a4bb817dfcf7572f89f8b9cacd059b584 +
              0x0e4389c8af84f6a6ea15a3ea5d62cb994b082731ba4cde73

k2 = 1013
k3 = 2053

p2 = k2(p1-1)+1
p3 = k3(p1-1)+1

n = p1 p2 p3

println["Appendix F: " + (isPrime[n] == true ? "FAIL" : "OK")]



// Appendix G
p1 = 2^576 * 0x24a027808260908b96d740bef8355ded63f6edb7f70de9a9 +
     2^384 * 0xb99c408f131cef3855b4b0aea6b17a4469ed5a7ec8b2be62 +
     2^192 * 0x66c3a9eae83a6769e175cb2598256da977b9e191b9b847a7 +
             0xe2cf4750d9bc2d64ccd3406f5db662c22c3fc65e3c56eff3

k2 = 641
k3 = 677

p2 = k2(p1-1)+1
p3 = k3(p1-1)+1

n = p1 p2 p3

println["Appendix G: " + (isPrime[n] == true ? "FAIL" : "OK")]


// Appendix H
p1 = 2^2304 * 0x00000000000000000000000000000000000000001e46d6a8 +
     2^2112 * 0x4d42d684ddb3415e871b661303b1c60f0388dfb9e525f8bc +
     2^1920 * 0x51c9de3c9f45627608de2f75dee580d9d4d97cab6fa86dad +
     2^1728 * 0x9e6bbfd721f297472480a9bed9508aa884bda9dc56833752 +
     2^1536 * 0xfac8e89f413a9517d14731277148789987806654a8723593 +
     2^1344 * 0xa452f960facc9b65f6962cb26131b42650c29c8735083c7e +
     2^1152 * 0x6c3a220d77d1cbe7f9628885a7b79465287d4b02ad546007 +
     2^960 *  0x1d43306a8813836de5ccd162fbeca4f117552dba01975451 +
     2^768 *  0x2f7684e32b0377e76f87b96906f8fa276381db612f76c2c7 +
     2^576 *  0xdd97ab4380042c991a4719884377c70065a3614237a41289 +
     2^384 *  0x24a1017fbb529443b0ad43c5424753db5b518cee5a1fcd87 +
     2^192 *  0xea038ffcad33380db1d89cd4e0b15b480cf0c62e8999924d +
              0x0284af806081ea106f35f85a664456166b864650ef034cf3

k2 = 2633
k3 = 5881

p2 = k2(p1-1)+1
p3 = k3(p1-1)+1

n = p1 p2 p3

println["Appendix H: " + (isPrime[n] == true ? "FAIL" : "OK")]


// Appendix I
n = 2^960 * 0x00000000000000000000000000000000ff7d428a8a9f9ffc +
    2^768 * 0x2ea178501115ec855f1154c054f5f67e15967a139a92fe15 +
    2^576 * 0xddf2c49b044820ea8c58551b74f81b45b116da4e1f11b926 +
    2^384 * 0x93e0cdc58006bc2052eb9b2fc32c71dd041d1907225e2814 +
    2^192 * 0xebe18736f626fea57c965b67b296a6461455226b39aba263 +
            0x3faeb483847a715c6a01d8d0e401a4aaf8f3d22121fd142f

println["Appendix I: " + (isPrime[n] == true ? "FAIL" : "OK")]


// Appendix J
q1 = 537242417098003
k2 = 61
k3 = 101

q2 = k2(q1-1)+1
q3 = k3(q1-1)+1

q = q1 q2 q3
println["Appendix J: " + (isPrime[q] == true ? "FAIL" : "OK")]


// Appendix K.5
p1 = 2^192 * 0x000000000000f8ae31e07964373e4997647e75fa186dd5e7 +
             0xe42ada869da0b3a333813f8102b1fb5f20623d6543e78a3b

k2 = 241
k3 = 257

p2 = k2(p1-1)+1
p3 = k3(p1-1)+1

n = p1 p2 p3

println["Appendix K.5: " + (isPrime[n] == true ? "FAIL" : "OK")]



View or download PrimeAndPrejudice.frink in plain text format


This is a program written in the programming language Frink.
For more information, view the Frink Documentation or see More Sample Frink Programs.

Alan Eliasen was born 17958 days, 6 hours, 19 minutes ago.