finite_field_tables.cpp

Go to the documentation of this file.

// finitefield_tables.cpp
//
// Anton Betten
//
// started:  October 23, 2002
// moved out of finitefield.cpp:  July 5, 2007
 
 
 
 
#include "foundations.h"
 
using namespace std;
 
 
namespace orbiter {
namespace layer1_foundations {
 
 
static int finitefield_primes[] = {
    2, 3, 4, 5, 7, 8, 9, 11, 13, 16, 
    17, 19, 23, 25, 27, 29, 31, 32, 37, 41, 
    43, 47, 49, 53, 59, 61, 67, 71, 73, 79, 81, 83,
    89, 97, 101, 103, 107, 109, 113, 121, 127, 131, 137,
    139, 149, 151, 157, 163, 167, 169, 173, 179, 181, 191,
    193, 197, 199, 211, 223, 227, 229, 233, 239, 241, 
    251, 257, 263, 269, 271, 277, 281, 283, 289, 293, 307,
    311, 313, 317, 331, 337, 347, 349, 353, 359, 367, 
    373, 379, 383, 389, 397, 401, 409, 419, 421, 431, 
    433, 439, 443, 449, 457, 461, 463, 467, 479, 487, 
    491, 499, /* missing */ 761, 941, 1301
 
 
    };
static int finitefield_nb_primes =
    sizeof(finitefield_primes) / sizeof(finitefield_primes[0]);
 
static int finitefield_largest_degree_irreducible_polynomial[] = {
    60 /*2*/, 
    42 /*3*/, 
    30 /*4*/,
    30 /*5*/,
    20 /*7*/,
    20 /*8*/,
    15 /*9*/,
    15 /*11*/,
    15 /*13*/,
    20 /*16*/,
    10/*17*/, 
    16/*19*/, 
    10/*23*/, 
    16/*25*/, 
    16/*27*/, 
    10/*29*/, 
    12/*31*/, 
    10 /*32*/,
    10/*37*/,
    2/*41*/,
    2/*43*/,
    2/*47*/,
    0 /* 49 */,
    2/*53*/,
    2/*59*/,
    2/*61*/,
    2/*67*/,
    2/*71*/,
    2/*73*/,
    2/*79*/,
    0/*81*/,
    2/*83*/,
    2/*89*/,
    2/*97*/,
    2/*101*/,
    2/*103*/,
    2/*107*/,
    2/*109*/,
    2/*113*/,
    0/*121*/,
    2/*127*/,
    2/*131*/,
    2/*137*/,
    2/*139*/,
    2/*149*/,
    2/*151*/,
    2/*157*/,
    2/*163*/,
    2/*167*/,
    0/*169*/,
    2/*173*/,
    2/*179*/,
    2/*181*/,
    2/*191*/,
    2/*193*/,
    2/*197*/,
    2/*199*/,
    2/*211*/,
    2/*223*/,
    2/*227*/,
    2/*229*/,
    2/*233*/,
    2/*239*/,
    2/*241*/,
    2/*251*/,
    2/*257*/,
    2/*263*/,
    2/*269*/,
    2/*271*/,
    2/*277*/,
    2/*281*/,
    2/*283*/,
    0/*289*/,
    2/*293*/,
    2/*307*/,
    2/*311*/,
    2/*313*/,
    2/*317*/,
    2/*331*/,
    2/*337*/,
    2/*347*/,
    2/*349*/,
    2/*353*/,
    2/*359*/,
    2/*367*/,
    2/*373*/,
    2/*379*/,
    2/*383*/,
    2/*389*/,
    2/*397*/,
    2/*401*/,
    2/*409*/,
    2/*419*/,
    2/*421*/,
    2/*431*/,
    2/*433*/,
    2/*439*/,
    2/*443*/,
    2/*449*/,
    2/*457*/,
    2/*461*/,
    2/*463*/,
    2/*467*/,
    2/*479*/,
    2/*487*/,
    2/*491*/,
    2/*499*/,
    2/*761*/,
    2/*941*/,
    2/*1301*/,
    };
 
 
static const char *finitefield_primitive_polynomial[][100] = {
// over GF(2):
{
    "7", // X^2+X+1
    "13", // X^3 + X^2 + 1
    "25", // X^4 + X^3 + 1
    "37", // X^5 + X^2 + 1
    "97", // X^6 + X^5 + 1
    "193", // X^7 + X^6 + 1
    "285", // X^8 + X^4 + X^3 + X^2 + 1
    "529", // X^9 + X^4 + 1
    "1033", // X^10 + X^3 + 1
    "2053", // X^11 + X^2 + 1
    "4179", // X^12 + X^6 + X^4 + X + 1
    "8219", // X^13 + X^4 + X^3 + X + 1
    "16427", //X^14 + X^5 + X^3 + X + 1
    "49153", // X^15 + X^14 + 1
    "65581", //X^16 + X^5 + X^3 + X^2 + 1
    "131081", //X^17 + X^3 + 1
    "262183", //X^18 + X^5 + X^2 + X + 1
    "524327", //X^19 + X^5 + X^2 + X + 1
    "1048585", //X^20 + X^3 + 1
    "2097157", //x^21 + x^2 + 1
    "6291457", //x^22 + x^21 + 1
    "8388641", //x^23 + x^5 + 1
    "16777243", //x^24 + x^4 + x^3 + x + 1
    "33554441", //x^25 + x^3 + 1
    "67108935", //x^26 + x^6 + x^2 + x + 1
    "134217767", //x^27 + x^5 + x^2 + x + 1
    "268435465", //x^28 + x^3 + 1
    "536870917", //x^29 + x^2 + 1
    "1073741907", //X^30 + X^6 + X^4 + X + 1
    "2147483657", //X^31 + X^3 + 1
    "4294967471", //X^32 + X^7 + X^5 + X^3 + X^2 + X + 1
    "8589934675", //X^33 + X^6 + X^4 + X + 1
    "17179869415", //X^34 + X^7 + X^6 + X^5 + X^2 + X + 1
    "34359738373", //X^35 + X^2 + 1
    "68719476855", //X^36 + X^6 + X^5 + X^4 + X^2 + X + 1
    "137438953535", //X^37 + X^5 + X^4 + X^3 + X^2 + X + 1
    "274877907043", //X^38 + X^6 + X^5 + X + 1
    "549755813905", //X^39 + X^4 + 1
    "1099511627833", //X^40 + X^5 + X^4 + X^3 + 1
    "2199023255561", //X^41 + X^3 + 1
    "4398046511167", //X^42 + X^5 + X^4 + X^3 + X^2 + X + 1
    "8796093022297", //X^43 + X^6 + X^4 + X^3 + 1
    "17592186044517", //X^44 + X^6 + X^5 + X^2 + 1
    "35184372088859", //X^45 + X^4 + X^3 + X + 1
    "70368744177967", //X^46 + X^8 + X^5 + X^3 + X^2 + X + 1
    "140737488355361", //X^47 + X^5 + 1
    "281474976710839", //X^48 + X^7 + X^5 + X^4 + X^2 + X + 1
    "562949953421425", //X^49 + X^6 + X^5 + X^4 + 1
    "1125899906842653", //X^50 + X^4 + X^3 + X^2 + 1
    "2251799813685323", //X^51 + X^6 + X^3 + X + 1
    "4503599627370505", //X^52 + X^3 + 1
    "9007199254741063", //X^53 + X^6 + X^2 + X + 1
    "18014398509482109", //X^54 + X^6 + X^5 + X^4 + X^3 + X^2 + 1
    "36028797018964039", //X^55 + X^6 + X^2 + X + 1
    "72057594037928085", //X^56 + X^7 + X^4 + X^2 + 1
    "144115188075855917", //X^57 + X^5 + X^3 + X^2 + 1
    "288230376151711843", //X^58 + X^6 + X^5 + X + 1
    "576460752303423611", //X^59 + X^6 + X^5 + X^4 + X^3 + X + 1
    "1729382256910270465", //X^60 + X^59 + 1
    "", // 61
    "", // 62
    "13835058055282163713", //X^63 + X^62 + 1
    "18446744073709551643", //X^64 + X^4 + X^3 + X + 1
    "", // 65
    "73786976294838206829", //X^66 + X^8 + X^6 + X^5 + X^3 + X^2 + 1
    "", // 67
    "295147905179352826019", //X^68 + X^7 + X^5 + X + 1
    "", // 69
    "1180591620717411303467", //X^70 + X^5 + X^3 + X + 1
    "", // 71
    "4722366482869645213791", //X^72 + X^6 + X^4 + X^3 + X^2 + X + 1
#if 0
#endif
},
// over GF(3):
{
    "14", // X^2 + X + 2
    "34", // X^3 + 2X + 1
    "110", // X^4 + X^3 + 2
    "250", // X^5 + 2X + 1
    "974", // X^6 + X^5 + 2
    "2203", // X^7 + X^2 + 2X + 1
    "6590", // X^{8} + X^{3} + 2
    "19747", // X^{9} + 2X^{3} + X^{2} + 1
    "59081", // X^{10} + X^{3} + X + 2
    "177163", // X^{11} + X^{2} + 2X + 1
    "531656", // X^{12} + 2X^{4} + X^{3} + 2X^{2} + 2X + 2
    "1594330", // X^{13} + 2X + 1
    "6377294", // X^{14} + X^{13} + 2
    "14348923", // X^{15} + X^{2} + 2X + 1
    "43046837", // X^{16} + X^{4} + X^{3} + 2X + 2
    "129140170", // X^{17} + 2X + 1
    "387420758", // X^{18} + X^{5} + 2X^{2} + 2X + 2
    "1162261483", // X^{19} + X^{2} + 2X + 1
    "3486784649", // X^{20} + X^{5} + X + 2
    "10460353234", // X^{21} + X^{3} + X + 1
    "31381059662", // X^{22} + X^{3} + 2X^{2} + 2X + 2
    "94143178858", // X^{23} + X^{3} + X + 1
    "282429536678", // X^{24} + 2X^{4} + X^{3} + 2X + 2
    "847288609498", // X^{25} + 2X^{3} + 1
    "2541865828361", // X^{26} + X^{3} + X + 2
    "7625597485372", // X^{27} + X^{5} + X^{4} + 2X^{3} + 2X + 1
    "22876792455293", // X^{28} + X^{5} + X^{4} + 2X + 2
    "68630377364974", // X^{29} + X^{4} + X^{2} + 1
    "274521509459534", // X^{30} + X^{29} + 2
    "617673396283978", // X^{31} + X^{3} + X + 1
    "1853020188851957", // X^{32} + X^{4} + X^{3} + 2X + 2
    "5559060566555785", // X^{33} + X^{5} + 2X^{2} + 1
    "16677181699666601", // X^{34} + X^{3} + X + 2
    "50031545098999723", // X^{35} + X^{2} + 2X + 1
    "150094635296999501", // X^{36} + X^{5} + X^{4} + 2X^{3} + 2
    "450283905890997415", // X^{37} + X^{3} + 2X^{2} + 2X + 1
    "1350851717672992133", // X^{38} + X^{3} + X^{2} + 2X + 2
    "4052555153018976583", // X^{39} + X^{5} + 2X^{3} + 2X^{2} + 1
    "16210220612075905070", // X^{40} + X^{39} + 2
    "36472996377170786410", // X^{41} + 2X + 1
    "109418989131512359574", // X^{42} + X^{5} + X^{4} + X^{3} + X^{2} + X + 2
    "", // 43
    "984770902183611232910", // X^{44} + X^{3} + 2
    "2954312706550833698707", // X^{45} + 2X^{3} + X^{2} + 1
    "", // 46
    "", // 47
    "79766443076872509863840", // X^{48} + X^{5} + 2X^{4} + 2X^{3} + 2X^{2} + 2
    "239299329230617529590147", // X^{49} + 2X^{3} + X^{2} + 1
    "717897987691852588770464", // X^{50} + 2X^{4} + X^{3} + 2X^{2} + 2X + 2
    "2153693963075557766310754", // X^{51} + 2X + 1
    "6461081889226673298932654", // X^{52} + X^{5} + 2X^{4} + 2X + 2
},
// over GF(4):
{
        "22", // X^{2} + X + 2
        "86", // X^{3} + X^{2} + X + 2
        "326", // X^{4} + X^{3} + X + 2
        "1282", // X^{5} + X^{4} + 2
        "5126", // X^{6} + X^{5} + X + 2
        "16411", // X^{7} + X^{2} + 2X + 3
        "65606", // X^{8} + X^{3} + X + 2
        "262166", // X^{9} + X^{2} + X + 2
        "1048675", // X^{10} + X^{3} + 2X^{2} + 3
        "5242882", // X^{11} + X^{10} + 2
        "16777554", // X^{12} + X^{4} + X^{3} + X^{2} + 2
        "83886086", // X^{13} + X^{12} + X + 2
        "268435499", // X^{14} + 2X^{2} + 2X + 3
        "1073741959", // X^{15} + 2X^{3} + X + 3
        "5368709126", // X^{16} + X^{15} + X + 2
        "17179869290", // X^{17} + X^{3} + 2X^{2} + 2X + 2
        "68719477018", // X^{18} + X^{4} + X^{2} + 2X + 2
        "274877906971", // X^{19} + X^{2} + 2X + 3
        "1099511627846", // X^{20} + X^{3} + X + 2
        "4398046511126", // X^{21} + X^{2} + X + 2
        "17592186044715", // X^{22} + X^{4} + 2X^{2} + 2X + 3
        "70368744177734", // X^{23} + X^{3} + X + 2
        "281474976711046", // X^{24} + X^{4} + 2X^{3} + X + 2
        "1125899906842966", // X^{25} + X^{4} + X^{3} + X^{2} + X + 2
        "4503599627370539", // X^{26} + 2X^{2} + 2X + 3
        "18014398509482006", // X^{27} + X^{2} + X + 2
        "90071992547409926", // X^{28} + X^{27} + X + 2
        "288230376151711787", // X^{29} + 2X^{2} + 2X + 3
        "1152921504606847314", // X^{30} + X^{4} + X^{3} + X^{2} + 2
},
// over GF(5):
{
        "32", // X^{2} + X + 2
        "152", // X^{3} + X^{2} + 2
        "767", // X^{4} + X^{3} + 3X + 2
        "3147", // X^{5} + 4X + 2
        "18752", // X^{6} + X^{5} + 2
        "93752", // X^{7} + X^{6} + 2
        "390663", // X^{8} + X^{2} + 2X + 3
        "1953163", // X^{9} + X^{2} + 2X + 3
        "11718767", // X^{10} + X^{9} + 3X + 2
        "58593752", // X^{11} + X^{10} + 2
        "244140763", // X^{12} + X^{3} + 2X + 3
        "1464843772", // X^{13} + X^{12} + 4X + 2
        "6103515787", // X^{14} + X^{3} + X^{2} + 2X + 2
        "30517578152", // X^{15} + X^{2} + 2
        "152587890767", // X^{16} + X^{3} + 3X + 2
        "915527343772", // X^{17} + X^{16} + 4X + 2
        "3814697266262", // X^{18} + X^{4} + 2X + 2
        "19073486328262", // X^{19} + X^{3} + 2X + 2
        "95367431640663", // X^{20} + X^{2} + 2X + 3
        "476837158203147", // X^{21} + 4X + 2
        "2861022949218767", // X^{22} + X^{21} + 3X + 2
        "11920928955078173", // X^{23} + X^{2} + 4X + 3
        "59604644775390782", // X^{24} + X^{3} + X^{2} + X + 2
        "357627868652343772", // X^{25} + X^{24} + 4X + 2
        "1490116119384765787", // X^{26} + X^{3} + X^{2} + 2X + 2
        "7450580596923828147", // X^{27} + 4X + 2
        "37252902984619140763", // X^{28} + X^{3} + 2X + 3
        "186264514923095703278", // X^{29} + X^{3} + X^{2} + 3
        "931322574615478516308", // X^{30} + X^{4} + 2X^{2} + X + 3
},
// over GF(7):
{
        "59", // X^{2} + X + 3
        "366", // X^{3} + 3X + 2
        "2754", // X^{4} + X^{3} + X + 3
        "16818", // X^{5} + X + 4
        "134494", // X^{6} + X^{5} + 5X + 3
        "823587", // X^{7} + 6X + 2
        "6588347", // X^{8} + X^{7} + 3
        "40353665", // X^{9} + X^{2} + X + 2
        "322828866", // X^{10} + X^{9} + X + 3
        "1977326754", // X^{11} + X + 4
        "15818613954", // X^{12} + X^{11} + X + 3
        "96889010465", // X^{13} + X^{2} + X + 2
        "775112083287", // X^{14} + X^{13} + 4X + 3
        "4747561510115", // X^{15} + 3X^{2} + 3X + 4
        "37980492079547", // X^{16} + X^{15} + 3
        "232630513987218", // X^{17} + X + 4
        "1628413597910608", // X^{18} + 3X^{2} + X + 5
        "11398895185373259", // X^{19} + 2X^{2} + 2X + 4
        "79792266297612209", // X^{20} + 4X^{2} + X + 5
},
// over GF(8):
{
        "74", // X^{2} + X + 2
        "610", // X^{3} + X^{2} + 4X + 2
        "4650", // X^{4} + X^{3} + 5X + 2
        "32842", // X^{5} + X^{2} + X + 2
        "294914", // X^{6} + X^{5} + 2
        "2359322", // X^{7} + X^{6} + 3X + 2
        "16777754", // X^{8} + X^{3} + 3X + 2
        "150994946", // X^{9} + X^{8} + 2
        "1207959586", // X^{10} + X^{9} + 4X + 2
        "8589935179", // X^{11} + X^{3} + X^{2} + X + 3
        "68719477271", // X^{12} + X^{3} + 2X + 7
        "549755813973", // X^{13} + X^{2} + 2X + 5
        "4947802325034", // X^{14} + X^{13} + 5X + 2
        "35184372088982", // X^{15} + 2X^{2} + 2X + 6
        "281474976711196", // X^{16} + X^{3} + 3X + 4
        "2251799813685335", // X^{17} + X^{2} + 2X + 7
        "20266198323167274", // X^{18} + X^{17} + 5X + 2
        "162129586585337914", // X^{19} + X^{18} + 7X + 2
        "1152921504606847061", // X^{20} + X^{2} + 2X + 5
},
// over GF(9):
{
        "111", // X^{2} + 3X + 3
        "849", // X^{3} + X^{2} + 4X + 3
        "7293", // X^{4} + X^{3} + 3
        "65631", // X^{5} + X^{4} + 2X + 3
        "590511", // X^{6} + X^{5} + 2X + 3
        "5314422", // X^{7} + X^{6} + X + 3
        "43046815", // X^{8} + X^{2} + X + 4
        "387420592", // X^{9} + X^{2} + 2X + 4
        "3874204947", // X^{10} + X^{9} + 6X + 3
        "34867844049", // X^{11} + X^{10} + 4X + 3
        "313810596102", // X^{12} + X^{11} + X + 3
        "2824295364813", // X^{13} + X^{12} + 3
        "25418658283347", // X^{14} + X^{13} + 6X + 3
        "205891132095472", // X^{15} + X^{3} + X^{2} + X + 4
},
// over GF(11):
{
        "167", // X^{2} + 4X + 2
        "1346", // X^{3} + X + 4
        "15985", // X^{4} + X^{3} + X + 2
        "161187", // X^{5} + X^{2} + X + 4
        "1932702", // X^{6} + X^{5} + 8X + 2
        "19487186", // X^{7} + X + 4
        "233846142", // X^{8} + X^{7} + 8X + 2
        "2357947722", // X^{9} + 2X + 9
        "28295372393", // X^{10} + X^{9} + 9X + 2
        "285311670724", // X^{11} + 10X + 3
        "3138428376739", // X^{12} + X + 7
        "34522712143957", // X^{13} + 2X + 4
        "414272545727185", // X^{14} + X^{13} + X + 2
        "4177248169415788", // X^{15} + X^{2} + X + 5
},
// over GF(13):
{
        "184", // X^{2} + X + 2
        "2368", // X^{3} + X^{2} + 2
        "30773", // X^{4} + X^{3} + X + 2
        "371347", // X^{5} + 4X + 2
        "5198169", // X^{6} + X^{5} + 5X + 2
        "62748558", // X^{7} + 3X + 2
        "878479305", // X^{8} + X^{7} + 5X + 2
        "11420230174", // X^{9} + X^{8} + 6X + 2
        "148462991237", // X^{10} + X^{9} + X + 2
        "1930018885901", // X^{11} + X^{10} + X + 2
        "25090245516598", // X^{12} + X^{11} + 6X + 2
        "302875106592411", // X^{13} + 12X + 2
        "4240251492291544", // X^{14} + X^{13} + 2
        "55123269399790178", // X^{15} + X^{14} + 10X + 2
},
// over GF(16):
{
        "274", // X^{2} + X + 2
        "4354", // X^{3} + X^{2} + 2
        "69762", // X^{4} + X^{3} + 8X + 2
        "1114194", // X^{5} + X^{4} + 5X + 2
        "16777516", // X^{6} + X^{2} + 2X + 12
        "285212674", // X^{7} + X^{6} + 2
        "4563402834", // X^{8} + X^{7} + 5X + 2
        "73014444146", // X^{9} + X^{8} + 7X + 2
        "1168231104562", // X^{10} + X^{9} + 3X + 2
        "18691697672402", // X^{11} + X^{10} + 13X + 2
        "299067162755186", // X^{12} + X^{11} + 7X + 2
        "4785074604081154", // X^{13} + X^{12} + 2
        "76561193665298578", // X^{14} + X^{13} + 9X + 2
        "1152921504606847276", // X^{15} + X^{2} + 2X + 12
        "18446744073709555773", // X^{16} + X^{3} + 3X + 13
        "313594649253062377474", // X^{17} + X^{16} + 2
        "5017514388048998039762", // X^{18} + X^{17} + 13X + 2
        "75557863725914323419394", // X^{19} + X^{2} + 2
        "1284483683340543498125410", // X^{20} + X^{19} + 6X + 2
},
// over GF(17):
{
        "309", // X^{2} + X + 3
        "5290", // X^{3} + X^{2} + 5X + 3
        "88556", // X^{4} + X^{3} + 7X + 3
        "1503449", // X^{5} + X^{4} + 4X + 3
        "25557429", // X^{6} + X^{5} + 3
        "434476313", // X^{7} + X^{6} + 4X + 3
        "7386096253", // X^{8} + X^{7} + 8X + 3
        "125563634026", // X^{9} + X^{8} + 5X + 3
        "2134581777034", // X^{10} + X^{9} + 5X + 3
},
// over GF(19):
{
"382", // X^{2} + X + 2
"6882", // X^{3} + X + 4
"137182", // X^{4} + X^{3} + 2
"2476127", // X^{5} + X + 9
"47045903", // X^{6} + X + 3
"893871819", // X^{7} + 4X + 4
"17877435048", // X^{8} + X^{7} + 14X + 2
"322687698165", // X^{9} + X^{2} + X + 6
"6131066258214", // X^{10} + X^{2} + 2X + 14
"116490258898376", // X^{11} + 8X + 5
"2213314919066195", // X^{12} + X + 15
"42052983462257196", // X^{13} + 7X + 4
"841059669245141391", // X^{14} + X^{13} + 11X + 2
"15181127029874798664", // X^{15} + X^{2} + 4
"288441413567621168150", // X^{16} + X^{2} + 5X + 13
},
// over GF(23):
{
"580", // X^{2} + 2X + 5
"12193", // X^{3} + X + 3
"292266", // X^{4} + X^{3} + 11X + 5
"6436369", // X^{5} + X + 3
"154472306", // X^{6} + X^{5} + 3X + 5
"3404825574", // X^{7} + 5X + 12
"78310985861", // X^{8} + X^{2} + 2X + 5
"1801152661489", // X^{9} + X + 3
"43227663875439", // X^{10} + X^{9} + 14X + 5
},
// over GF(25):
{
"655", // X^{2} + X + 5
"16255", // X^{3} + X^{2} + 5
"406305", // X^{4} + X^{3} + 2X + 5
"10156255", // X^{5} + X^{4} + 5
"253906255", // X^{6} + X^{5} + 5
"6347656255", // X^{7} + X^{6} + 5
"158691406280", // X^{8} + X^{7} + X + 5
"3967285156255", // X^{9} + X^{8} + 5
"99182128906255", // X^{10} + X^{9} + 5
"2479553222656255", // X^{11} + X^{10} + 5
"61988830566406255", // X^{12} + X^{11} + 5
"1549720764160156255", // X^{13} + X^{12} + 5
"38743019104003906255", // X^{14} + X^{13} + 5
"968575477600097656255", // X^{15} + X^{14} + 5
"24214386940002441406255", // X^{16} + X^{15} + 5
},
// over GF(27):
{
"867", // X^{2} + 5X + 3
"20523", // X^{3} + X^{2} + 4X + 3
"551289", // X^{4} + X^{3} + 6X + 3
"14880351", // X^{5} + X^{4} + 3
"401769399", // X^{6} + X^{5} + 3
"10847773695", // X^{7} + X^{6} + 3
"292889889687", // X^{8} + X^{7} + 3
"7908027021471", // X^{9} + X^{8} + 3
"213516729579639", // X^{10} + X^{9} + 3
"5764951698650175", // X^{11} + X^{10} + 3
"155653695863554647", // X^{12} + X^{11} + 3
"4202649788315975391", // X^{13} + X^{12} + 3
"113471544284531335479", // X^{14} + X^{13} + 3
"3063731695682346057855", // X^{15} + X^{14} + 3
"82720755783423343562007", // X^{16} + X^{15} + 3
},
// over GF(29):
{
"988", // X^{2} + 5X + 2
"25261", // X^{3} + X^{2} + X + 2
"731672", // X^{4} + X^{3} + 2
"21218432", // X^{5} + X^{4} + 2
"594823353", // X^{6} + X + 3
"17844699632", // X^{7} + X^{6} + 2
"517496289388", // X^{8} + X^{7} + 4X + 2
"15007392388948", // X^{9} + X^{8} + 4X + 2
"435214379276304", // X^{10} + X^{9} + 8X + 2
},
// over GF(31):
{
"1026", // X^{2} + 2X + 3
"29836", // X^{3} + X + 14
"953470", // X^{4} + X^{3} + 5X + 3
"28629200", // X^{5} + X + 18
"916133176", // X^{6} + X^{5} + 11X + 3
"27512614160", // X^{7} + X + 18
"880403652020", // X^{8} + X^{7} + 15X + 3
"26439622160712", // X^{9} + X + 10
"846067909141630", // X^{10} + X^{9} + 5X + 3
"25408476896405057", // X^{11} + 7X + 9
"813071260684955060", // X^{12} + X^{11} + 15X + 3
},
// over GF(32): 
{
        "1250", // X^{2} + 7X + 2
        "33890", // X^{3} + X^{2} + 3X + 2
        "1081474", // X^{4} + X^{3} + 4X + 2
        "33555462", // X^{5} + X^{2} + 6
        "1107296258", // X^{6} + X^{5} + 2
        "35433480354", // X^{7} + X^{6} + 5X + 2
        "1099511660578", // X^{8} + X^{3} + X + 2
        "36283883716834", // X^{9} + X^{8} + 7X + 2
        "1125899906843688", // X^{10} + X^{2} + X + 8
},
// over GF(37):
{
"1519", // X^{2} + 4X + 2
"52061", // X^{3} + X^{2} + X + 2
"1924853", // X^{4} + X^{3} + X + 2
"71218120", // X^{5} + X^{4} + 2
"2635070627", // X^{6} + X^{5} + 7X + 2
"97497603914", // X^{7} + X^{6} + 10X + 2
"3607411331241", // X^{8} + X^{7} + 5X + 2
"133474219249518", // X^{9} + X^{8} + 14X + 2
"4938546112213076", // X^{10} + X^{9} + 4X + 2
},
// over GF(41):
{
"1810", // X^{2} + 3X + 6
},
// over GF(43):
{
"1895", // X^{2} + X + 3
},
// over GF(47):
{
"2308", // X^{2} + 2X + 5
},
// over GF(49):
{
},
// over GF(53):
{
"3023", // X^{2} + 4X + 2
},
// over GF(59):
{
"3542", // X^{2} + X + 2
},
// over GF(61):
{
"3784", // X^{2} + X + 2
},
// over GF(67):
{
"4759", // X^{2} + 4X + 2
},
// over GF(71):
{
"5190", // X^{2} + 2X + 7
},
// over GF(73):
{
"5553", // X^{2} + 3X + 5
},
// over GF(79):
{
"6323", // X^{2} + X + 3
},
// over GF(81):
{
},
// over GF(83):
{
"6974", // X^{2} + X + 2
},
// over GF(89):
{
"8547", // X^{2} + 7X + 3
},
// over GF(97):
{
"9511", // X^{2} + X + 5
},
// over GF(101):
{
"10607", // X^{2} + 4X + 2
},
// over GF(103):
{
"10717", // X^{2} + X + 5
},
// over GF(107):
{
"11879", // X^{2} + 4X + 2
},
// over GF(109):
{
"11996", // X^{2} + X + 6
},
// over GF(113):
{
"14128", // X^{2} + 12X + 3
},
// over GF(121):
{
},
// over GF(127):
{
"16259", // X^{2} + X + 3
},
// over GF(131):
{
"17687", // X^{2} + 4X + 2
},
// over GF(137):
{
"19594", // X^{2} + 6X + 3
},
// over GF(139):
{
"19462", // X^{2} + X + 2
},
// over GF(149):
{
"22799", // X^{2} + 4X + 2
},
// over GF(151):
{
"23109", // X^{2} + 2X + 6
},
// over GF(157):
{
"25439", // X^{2} + 5X + 5
},
// over GF(163):
{
"27223", // X^{2} + 4X + 2
},
// over GF(167):
{
"28061", // X^{2} + X + 5
},
// over GF(169):
{
},
// over GF(173):
{
"30623", // X^{2} + 4X + 2
},
// over GF(179):
{
"33296", // X^{2} + 7X + 2
},
// over GF(181):
{
"33487", // X^{2} + 4X + 2
},
// over GF(191):
{
"36691", // X^{2} + X + 19
},
// over GF(193):
{
"37447", // X^{2} + X + 5
},
// over GF(197):
{
"39796", // X^{2} + 5X + 2
},
// over GF(199):
{
"40798", // X^{2} + 6X + 3
},
// over GF(211):
{
"45367", // X^{2} + 4X + 2
},
// over GF(223):
{
"50178", // X^{2} + 2X + 3
},
// over GF(227):
{
"53120", // X^{2} + 7X + 2
},
// over GF(229):
{
"52676", // X^{2} + X + 6
},
// over GF(233):
{
"54525", // X^{2} + X + 3
},
// over GF(239):
{
"57606", // X^{2} + 2X + 7
},
// over GF(241):
{
"58811", // X^{2} + 3X + 7
},
// over GF(251):
{
"65266", // X^{2} + 9X + 6
},
// over GF(257):
{
"67594", // X^{2} + 6X + 3
},
// over GF(263):
{
"69700", // X^{2} + 2X + 5
},
// over GF(269):
{
"72632", // X^{2} + X + 2
},
// over GF(271):
{
"73989", // X^{2} + 2X + 6
},
// over GF(277):
{
"77565", // X^{2} + 3X + 5
},
// over GF(281):
{
"79245", // X^{2} + X + 3
},
// over GF(283):
{
"80375", // X^{2} + X + 3
},
// over GF(289):
{
},
// over GF(293):
{
"86144", // X^{2} + X + 2
},
// over GF(307):
{
"94561", // X^{2} + X + 5
},
// over GF(311):
{
"97049", // X^{2} + X + 17
},
// over GF(313):
{
"98918", // X^{2} + 3X + 10
},
// over GF(317):
{
"101759", // X^{2} + 4X + 2
},
// over GF(331):
{
"111219", // X^{2} + 5X + 3
},
// over GF(337):
{
"115264", // X^{2} + 5X + 10
},
// over GF(347):
{
"121799", // X^{2} + 4X + 2
},
// over GF(349):
{
"122152", // X^{2} + X + 2
},
// over GF(353):
{
"126377", // X^{2} + 5X + 3
},
// over GF(359):
{
"129247", // X^{2} + X + 7
},
// over GF(367):
{
"135062", // X^{2} + X + 6
},
// over GF(373):
{
"140623", // X^{2} + 4X + 2
},
// over GF(379):
{
"145538", // X^{2} + 5X + 2
},
// over GF(383):
{
"147077", // X^{2} + X + 5
},
// over GF(389):
{
"155213", // X^{2} + 10X + 2
},
// over GF(397):
{
"159599", // X^{2} + 5X + 5
},
// over GF(401):
{
"162809", // X^{2} + 5X + 3
},
// over GF(409):
{
"169347", // X^{2} + 5X + 21
},
// over GF(419):
{
"175982", // X^{2} + X + 2
},
// over GF(421):
{
"178927", // X^{2} + 4X + 2
},
// over GF(431):
{
"186199", // X^{2} + X + 7
},
// over GF(433):
{
"187927", // X^{2} + X + 5
},
// over GF(439):
{
"194053", // X^{2} + 3X + 15
},
// over GF(443):
{
"198909", // X^{2} + 6X + 2
},
// over GF(449):
{
"203849", // X^{2} + 5X + 3
},
// over GF(457):
{
"210233", // X^{2} + 3X + 13
},
// over GF(461):
{
"212984", // X^{2} + X + 2
},
// over GF(463):
{
"215298", // X^{2} + 2X + 3
},
// over GF(476):
{
"219959", // X^{2} + 4X + 2
},
// over GF(479):
{
"231849", // X^{2} + 5X + 13
},
// over GF(487):
{
"238146", // X^{2} + 2X + 3
},
// over GF(491):
{
"243047", // X^{2} + 4X + 2
},
// over GF(499):
{
"252002", // X^{2} + 6X + 7
},
 
// many missing here
 
 
// over GF(761):
{
"581410", // X^{2} + 3X + 6
},
// over GF(941):
{
"886424", // X^{2} + X + 2
},
// over GF(1301):
{
"1700409", // X^{2} + 6X + 2
},
};
 
void knowledge_base::get_primitive_polynomial(std::string &poly,
        int p, int e, int verbose_level)
{
    int f_v = (verbose_level >= 1);
    int idx;
    //char *s;
    data_structures::sorting Sorting;
 
    if (f_v) {
        cout << "knowledge_base::get_primitive_polynomial" << endl;
    }
 
    if (!Sorting.int_vec_search(finitefield_primes, finitefield_nb_primes, p, idx)) {
            cout << "knowledge_base::get_primitive_polynomial "
                    "I don't have prime " << p << " in the tables" << endl;
        exit(1);
 
#if 0
        cout << "searching for a polynomial of degree " << e << endl;
 
        algebra_global AG;
 
        s = AG.search_for_primitive_polynomial_of_given_degree(p, e, verbose_level);
        cout << "the search came up with a polynomial of degree " << e << ", coded as " << s << endl;
        return s;
#endif
 
    }
    if (e > finitefield_largest_degree_irreducible_polynomial[idx]) {
        cout << "knowledge_base::get_primitive_polynomial "
                "I do not have a polynomial" << endl;
        cout << "of that degree over that field" << endl;
        cout << "requested: degree " << e << " polynomial over GF(" << p << ")" << endl;
        exit(1);
    }
    const char *m = finitefield_primitive_polynomial[idx][e - 2];
    if (strlen(m) == 0) {
        cout << "knowledge_base::get_primitive_polynomial "
                "I do not have a polynomial" << endl;
        cout << "of that degree over that field" << endl;
        cout << "requested: degree " << e << " polynomial over GF(" << p << ")" << endl;
        exit(1);
    }
    poly.assign(m);
    if (f_v) {
        cout << "knowledge_base::get_primitive_polynomial done" << endl;
    }
}
 
 
}}