// -*- C++ -*- // Choose modulus of class 'mod' // by uncommenting one line in this file. // ************************************************** // ! IMPLEMENTATION ONLY FOR MODULI WITH <= 63 BITS ! // ************************************************** // Note that FFT-convolutions cannot be done for even moduli. #include "mod/mtypes.h" #define PP static umod_t MF[]={M,0} // saving space with prime moduli #define XX static umod_t MF[] = // saving space with composite moduli #define MM static umod_t M = (umod_t) // more saving space ... // CYCLIC moduli: // i.e. modulus==p^n or ==2*p^n with p odd prime, n>=1 //----- 64 bits: can't yet be used (need <=63bit to multiply) ! // MM 0xffffffffff000001ULL; PP; // 2^64-2^24+1 // MM 0xffffffff00000001ULL; PP; // 2^64-2^32+1 #(8)=64 // MM 0xfffffffc00000001ULL; PP; // 2^64-2^34+1 // MM 0xffffff0000000001ULL; PP; // 2^64-2^40+1 // MM 0xf700000000000001ULL; PP; // 2^56*13*19+1: 63.948 bits = 2^64-9*2^56+1 // MM 0xf600000000000001ULL; PP; // 2^57*3*41+1: 63.942 bits // MM 0xeb00000000000001ULL; PP; // 2^56*5*47+1: 63.876 bits // MM 0xd800000000000001ULL; PP; // 2^59*3^3+1: 63.754 bits // MM 0xbe00000000000001ULL; PP; // 2^57*5*19+1: 63.569 bits // MM 0x9600000000000001ULL; PP; // 2^57*3*5^2+1: 63.228 bits // MM 0x8e00000000000001ULL; PP; // 2^57*71+1: 63.149 bits // MM 0x8000000000800001ULL; PP; // 2^63+2^23+1 63+eps bits //----- 63 bits: // MM 0x7ffffe0000000001ULL; PP; // 2^63-2^41+1: 62.999 bits // MM 0x7fffe40000000001ULL; PP; // 2^63-2^42*7+1: 62.999 bits // MM 0x7fffe00000000001ULL; PP; // 2^63-2^45+1: 62.999 bits // MM 0x7fffcc0000000001ULL; PP; // 2^63-2^42*13+1: 62.999 bits // MM 0x7fff8c0000000001ULL; PP; // 2^63-2^42*29+1: 62.999 bits // MM 0x7ffedc0000000001ULL; PP; // 2^63-2^42*73+1: 62.999 bits // MM 0x7ffe780000000001ULL; PP; // 2^63-2^43*7^2+1: 62.999 bits // MM 0x7ffe0c0000000001ULL; PP; // 2^63-2^42*5^3+1: 62.999 bits // MM 0x7ffdfa0000000001ULL; PP; // 2^63-2^41*7*37+1: 62.999 bits // MM 0x7ffdda0000000001ULL; PP; // 2^41*...+1: 62.999 bits // MM 0x7f47000000000001ULL; PP; // 2^48*...+1: 62.998 bits // MM 0x7fb7000000000001ULL; PP; // 2^48*...+1: 62.996 bits // MM 0x7fb9000000000001ULL; PP; // 2^48*...+1: 62.996 bits // MM 0x7fe1000000000001ULL; PP; // 2^48*...+1: 62.991 bits // MM 0x7f531e0000000001ULL; PP; // 2^41*3^3*5^2*7*883+1 bits=62.9924 // MM 0x7f6bba0000000001ULL; PP; // 2^41*3^2*5^2*7*11*241+1 bits=62.9935 // MM 0x7fc1dc0000000001ULL; PP; // 2^42*3^3*5^2*7*443+1 bits=62.9973 // MM 0x7fbe218200000001ULL; PP; // 2^33*3^4*5^2*11*73*659+1 bits=62.9971 // MM 0x7fd3e24200000001ULL; PP; // 2^33*3^4*5^2*7*11*13*23^2+1 bits=62.9981 // MM 0x7ff9f39200000001ULL; PP; // 2^33*3^8*5^3*7*11*17+1 bits=62.9997 // MM 0x7f66707c00000001ULL; PP; // 2^34*3^4*5^2*7*11*23*149+1 bits=62.9932 // composite: // MM 0x2000000000000001ULL; XX{3,768614336404564651ULL,0}; // 2^61+1 >> 62 bits //----- <= 62 bits: // +++++ start DEFAULTs +++++ (USE ONE OF THESE!): // MM 0x3fffc00000000001ULL; PP; // 2^46*3*5*17*257+1 = 2^62-2^46+1 // MM 0x3fff840000000001ULL; PP; // 2^42*3^5*5*863+1 = 2^62-2^42*31+1 // MM 0x3fff540000000001ULL; PP; // 2^42*3*181*1931+1 = 2^62-2^42*43+1 // MM 0x3ffac00000000001ULL; PP; // 2^46*5*13103+1 = 2^62-2^46*3*7+1 // MM 0x3ff8a00000000001ULL; PP; // 2^45*3^2*14557+1 = 2^62-2^45*59+1 // MM 0x3ff7600000000001ULL; PP; // 2^45*269*487+1 = 2^62-2^45*3*23+1 // MM 0x3a00000000000001ULL; PP; // 2^57*29+1 = 2^62-2^57*3+1 #(2)=2^56 // +++++ end DEFAULTs +++++ // these have also 3^x 5^y and 7^z as factor of max FFT-length: // MM 0x3f40f80000000001ULL; PP; // 2^43*3^2*5^2*7^2*47+1 bits=61.9831 // MM 0x3c0eb50000000001ULL; PP; // 2^40*3^3*5^2*7^3*17+1 bits=61.9083 // MM 0x3d673d0000000001ULL; PP; // 2^40*3^2*5^3*7^2*73+1 bits=61.9402 // MM 0x3fc22b0000000001ULL; PP; // 2^40*3^2*5^2*7^2*379+1 bits=61.9945 // MM 0x3bf6190000000001ULL; PP; // 2^40*3^2*5^3*7*499+1 bits=61.906 // MM 0x3d1d690000000001ULL; PP; // 2^40*3^2*5^2*7*2543+1 bits=61.9335 // MM 0x3d8c270000000001ULL; PP; // 2^40*3^2*5^2*7*13*197+1 bits=61.9436 // MM 0x3e8e8d0000000001ULL; PP; // 2^40*3^2*5^2*7*19*137+1 bits=61.9671 // MM 0x3ee4af0000000001ULL; PP; // 2^40*3^2*5^2*7*2617+1 bits=61.9748 // MM 0x3ed23a0000000001ULL; PP; // 2^41*3^2*5^2*7*1307+1 bits=61.9732 // MM 0x3fafb60000000001ULL; PP; // 2^41*3^2*5^4*7*53+1 bits=61.9929 // MM 0x3c46140000000001ULL; PP; // 2^42*3^3*5^2*7*11*19+1 bits=61.9135 // MM 0x3e32440000000001ULL; PP; // 2^42*3^2*5^2*7*647+1 bits=61.9588 // MM 0x3d23900000000001ULL; PP; // 2^44*3^3*5^2*7*53+1 bits=61.934 // MM 0x1c80000000000001ULL; PP; // 2^55*3*19+1 = 2^61-2^55*7+1 #(2^19)=2^54 // MM 0x2008000000000001ULL; PP; // 2^51*5^2*41+1 = 2^62-2^51*3*11*31+1 // MM 0x3d000000000001ULL; PP; // 2^48*61+1 = 2^53-2^48*3+1 // MM 0x1ec00000000001ULL; PP; // 2^46*3*41+1 = // MM 0xf000000000001ULL; PP; // 2^48*3*5+1 = 2^52-2^48+1 #(8)=2^46 // MM 0x3f00000000001ULL; PP; // 2^44*3^2*7+1 = 2^49-2^44+1 #(8)=2^42 //----- 32 bits: // MM 0xfa000001; PP; // 2^25*5^3+1: 31.965 bits = 4194304001 // MM 0xe8000001; PP; // 2^27*29+1: 31.857 bits // MM 0xd0000001; PP; // 2^28*13+1: 31.700 bits = 3489660929 = 2^31-2^28*3+1 #(2^13)=2^25 // MM 0xc0000001; PP; // 2^30*3+1: 31.584 bits = 3221225473 = 2^32-2^30+1 #(8)=2^28 // MM 0xac000001; PP; // 2^26*43+1: 31.426 bits // MM 0x88000001; PP; // 2^27*17+1: 31.087 bits //----- 31 bits: // MM 0x7f000001; PP; // 2^24*127+1: 30.988 bits (Lipson3)=2130706433 = 2^30-2^24+1 // MM 0x7e000001; PP; // 2^25*3^2*7+1: 30.977 bits (Lipson2)=2113929217 = 2^30-2^25+1 #(2^21)=2^23 // MM 0x7c800001; PP; // 2^23*3*83+1: 30.960 bits // MM 0x78000001; PP; // 2^27*3*5+1: 30.906 bits (Lipson1)=2013265921 = 2^30-2^27+1 #(2^15)=2^26 // MM 0x66000001; PP; // 2^25*51*7+1: 30.672 bits // MM 0x6c000001; PP; // 2^26*3^3+1: 30.754 bits // ------------------------- // MM 7340033; PP; // 2^20*7+1: // MM 1179649; PP; // 2^17*3^2+1: // MM 786433; PP; // 2^18*3+1: // MM 65537; PP; // 2^16+1: // MM 257; PP; // 2^8+1: // MM 17; PP; // 2^4+1: // MM 2130706433*2130706433; XX {2130706433,0}; // 61.977 bits // MM 257*257*257*257*257*257*257; XX {257,0}; // MM 65537*65537; XX {65537,0}; // 32+eps bits // MM 65537*65537*65537; XX {65537,0}; // 48+eps bits // MM 241*241; XX {241,0}; // MM 17*17*17; XX {17,0}; // can't do (length 2**k) FFT convolution with these (2 has no inverse): // MM 2*257*257*257*257*257*257*257; XX {2,257,0}; // MM 2*65537*65537*65537; XX {2,65537,0}; // MM 2*2130706433*2130706433; XX {2,2130706433,0}; // 62.977 bits // MM 2*2013265921*2013265921; XX {2,2013265921,0}; // 62.813 bits // MM 0x7fff800000000002ULL; XX{2,0x3fffc00000000001ULL,0}; // 2*(2^62-2^46+1) 63bit // NONCYCLIC moduli: // MM 16; XX {2,0}; // MM 21; XX {3,7,0}; // MM 2*17*257; XX {2,17,257,0}; // MM 2*17*257*257*257*257*257; XX {2,17,257,0}; // MM 4611686018427387905ULL; XX{5,5581,8681,49477,384773,0}; // 2^62+1: 62+eps bits // MM 65537*65537*65535; XX {3,5,17,257,65537,0}; // 48+eps bits // MM 2305843009213693953ULL; XX{3,768614336404564651ULL,0}; // 2^61+1: 61+eps bits // ... maxorder = 0xaaaaaaaaaaaaaaa == 2*3*5^2*7*11*13*31*41*61*151*331*1321 // MM 0x100000001ULL; XX{641,6700417,0}; // 2^32+1: #(2)=64 // MM 0xffff0001ULL; XX{193,22253377,0}; // 4294901761 = 2^32-2^16+1 #(8)=32 // MM 0x1000000000001ULL; XX{193,65537,22253377,0}; // 2^48+1 #(8)=32 // MM 0xffffff000001ULL; XX{577,487824887233ULL,0}; // 2^48-2^24+1 #(2^9)=16 // MM 0x10000000000001ULL; XX{17,858001,308761441,0}; // 2^52+1 #(2^13)=8 // MM 0x100000000000001ULL; XX{257,5153,54410972897,0}; // 2^56+1 #(2^7)=4 // MM 0x1000000000000001ULL; XX{17,241,61681,4562284561ULL,0}; // 2^60+1 #(2^15)=8 // MM 0x1000100010001ULL; XX{641,65537,6700417,0}; // 2^48+2^32+2^16+1 // #(2)=64 // MM 65537*65536; XX {2,65537,0}; // MM 2013265921ULL*2113929217ULL; XX {2013265921,2113929217,0}; // MM 65536; XX {2,0}; // MM 257*241; XX {257, 241, 0}; // MM 257*17; XX {257, 17, 0}; // MM 65537*257*257; XX {65537,257,0}; // MM 17*5; XX {17,5,0}; // MM 257*241*241; XX {257,241,0}; #undef PP #undef XX #undef MM // cf. pp-primes.gp #endif // !defined HAVE_MODULI_H__