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 17933 days, 23 hours, 57 minutes ago.