//
// program to output recommended basis for F(2^m)
//

#include <iostream>
#include "gf2m.h"

using namespace std;

Miracl precision=100;

BOOL irreducible(int m,int a,int b,int c)
{
    GF2m w4,w5,modulo;
    Big modulus;
    
    get_mip()->M=m;
    get_mip()->AA=a;
    get_mip()->BB=b;
    get_mip()->CC=c;

    if (b==0) modulus=pow((Big)2,m)+pow((Big)2,a)+1;
    else      modulus=pow((Big)2,m)+pow((Big)2,a)+pow((Big)2,b)+pow((Big)2,c)+1;
    copy(modulus.getbig(),get_mip()->modulus);
    copy(modulus.getbig(),getbig(modulo));

    w4=2;
    for (int i=1;i<=m/2;i++)
    {
        w4*=w4;
        w5=w4+2;    
        if (gcd(w5,modulo)!=1) return FALSE;
    }
    return TRUE;
}

int main(int argc,char **argv)
{
    int i,M,A,B,C,pluses,stars;

    argc--; argv++;

    if (argc!=1)
    {
        cout << "Bad Parameters" << endl;
        cout << "findbase <M>" << endl;
        cout << "finds suitable irreducible polynomial for field F(2^M)" << endl;
        exit(0);
    }
    get_mip()->modulus=mirvar(0);
    get_mip()->IOBASE=16;
    M=atoi(argv[0]);

    cout << "Looking for suitable trinomial basis x^M+x^A+1" << endl;
    cout << "- means that basis is not recommended" << endl;
    cout << "* means strongly recommended" << endl;
    cout << "+ means mildly recommended" << endl;

    for (A=M-1;A>=1;A--)
    {
        if (A%2==0) continue;
        if (irreducible(M,A,0,0))
        {
            stars=pluses=0;
            cout << "A= " << A;
            if (M-A < MIRACL) cout << " -";
            else 
            {
                if (((M-A)/MIRACL)+1 == M/MIRACL) stars++;
                if (((M-A)/MIRACL) == M/MIRACL) stars+=2;
                if ((M-A)%MIRACL==0) pluses++;
                for (i=1;i<=stars;i++) cout << "*";
                for (i=1;i<=pluses;i++) cout << "+";
            }
            cout << endl;
        }
    }

    cout << "Looking for suitable pentanomial basis x^M+x^A+x^B+x^C+1" << endl;
    cout << "- means that basis is not recommended" << endl;
    cout << "* means strongly recommended" << endl;
    cout << "+ means mildly recommended" << endl;
 
    for (A=M-1;A>=1;A--)
    {
        if (A%2==0) continue;
        for (B=A-1;B>=1;B--)
        {
            if (B%2==0) continue;
            for (C=B-1;C>=1;C--)
            {
                if (C%2==0) continue;
                if (irreducible(M,A,B,C))
                {
                    pluses=stars=0;
                    cout << "A= " << A << " B= " << B << " C= " << C;
                    if (M-A < MIRACL) cout << " -";
                    else
                    {
                        if ((M-A)/MIRACL == (M-B)/MIRACL) stars++;
                        if ((M-B)/MIRACL == (M-C)/MIRACL) stars++;
                        if (((M-A)/MIRACL)+1 == M/MIRACL) stars++;
                        if (((M-A)/MIRACL) == M/MIRACL) stars+=2;
                        if ((M-A)%MIRACL==0) pluses++;
                        if ((M-B)%MIRACL==0) pluses++;
                        if ((M-C)%MIRACL==0) pluses++;
                        for (i=1;i<=stars;i++) cout << "*";
                        for (i=1;i<=pluses;i++) cout << "+";
                    }
                    cout << endl;
                }
            }
        }
    }

    return 0;
}
