Tool to calculate polynomial masks with maximal period for LFSRs?

Question

Related to Linear Feedback Shift Registers - does any Windows or Linux tool exist, that helps calculating polynomial masks with maximal periods for different bit-lengths (beyond 64 bits)?

It is pretty simple to find all possible polynomial masks that result in maximal periods when we're talking about LFSRs up to something like 16-bit length by using some C sourcecode to verify-by-brute-forcing all possible masks. But when it comes to LFSRs with a higher bit-length, brute-forcing isn't an option anymore… unless you want to spend several years doing so.

Being pretty sure I'm not the first one who would like to be able to find such "maximal period" polynomial masks for different bit-lengths beyond 64 bits, I'm hoping someone created a nice piece of software that helps by taking a bit-length as input and providing the different polynomial masks as output. Of course, I expect such a tool to take it's time too, but I also expect it to be optimized to find such masks in a way that is quicker than brute-forcing all possible masks to find those producing maximal periods.

Any hints would be greatly appreciated…

Answer 1

Primpoly

I just found binaries (and sourcecode) for a program which generates a primitive polynomial of degree n modulo p. You can also test a given polynomial for primitivity and find all primitive polynomials.

The program is called “Primpoly”, Version 11.0.

A sample run from the command line:

c:\primpoly.exe 2 200

Primpoly Version 11.0 - A Program for Computing Primitive Polynomials.
Copyright (C) 1999-2014 by Sean Erik O'Connor. All Rights Reserved.
Primpoly comes with ABSOLUTELY NO WARRANTY; for details see the
GNU General Public License. This is free software, and you are welcome
to redistribute it under certain conditions; see the GNU General Public
License for details.

Primitive polynomial modulo 2 of degree 200

Self-check passes...

x ^ 200 + x ^ 5 + x ^ 3 + x ^ 2 + 1, 2 

The sourcecode and executables are distributed under the terms of the GNU General Public License.

If you scroll down past the sourcecode on the page linked above, you'll find executables for Mac OS X 10.6, Windows XP (32 bit), and for Windows 7 (32 bit). To be able to run them as expected, you probably will have to rename the files, removing everything after the ….exe part.

I have to admit that I did not download and run the offered executables. Instead, I downloaded the offered sourcecode, tweaked some things to my likings and compiled my own version. Therefore, I can not confirm (nor deny) the offered executables to be functional.

You should also know that I needed to tune some minor nuts-and-bolts to make the sourcecode compile flawlessly on my system. On the other hand, that might just have been the result of my individual system setup and configuration.

Nevertheless, I can confirm that my successfully compiled version of Primpoly does what it should and it's definitely quicker than brute-forcing things one-by-one – which is what I was looking for.

Bonus

What I really like is the fact that the author of the program also took the time to explain the theories he used. See the dedicated website section: “computing primitive polynomials - theory and algorithm”.

_{In case you know about alternatives, or if find anything alike (or better), don't be shy and share it with the Softwarerecs.SE community.}

Answer 2

Since I am not a mathematician, I do not know about any “mathematical shortcuts” to calculate polynomials.

But here's a working commandline program I created a while ago. It should be easy to compile with any C/C++ compiler that fits your platform. To be able to handle “bigger” periods, the sourcecode relies on The GNU Multiple Precision Arithmetic Library, which is a free download. All in all, it should compile well.

// Define period (= range of bits) to calculate LFSRs masks for.

#define MINBITNUM "24"
#define MAXBITNUM "320"

// Of course, the range can be limited to a single LFSR period.
// To do so, enter the same number in both defines.
// Example for a 96-bit period only:
//     #define MINBITNUM "96"
//     #define MAXBITNUM "96"

#include <stdio.h>
#include <iostream>
#include <gmp.h>
using namespace std;

int main(int argc, char *argv[])
{
    mpz_t     i,lfsr, lsb, width, power, mask, maxwidth,
              Eight, Zero,One, Two,Test,Testb;
    mpz_inits(i,lfsr, lsb, width, power, mask, maxwidth,
              Eight,  Zero,One, Two,Test,Testb,NULL);
    mpz_set_str(Zero, "0", 10);
    mpz_set_str(One, "1", 10);
    mpz_set_str(Two, "2", 10);
    mpz_set_str(Eight, "8", 10);

    mpz_set_str(width, MINBITNUM, 10);
    mpz_set_str(maxwidth, MAXBITNUM, 10);

    while(mpz_cmp(width, maxwidth) < 1)
    {
        mpz_mul_2exp(power, One, mpz_get_ui(width));
        mpz_sub(Test,power,One);
        cout<<"Masks with period 0x";
        mpz_out_str(stdout, 16, Test);
        cout<<endl;
        mpz_div_2exp(mask, power, mpz_get_ui(One));
        while(mpz_cmp(mask,power) < 0)
        {
            if(mpz_probab_prime_p(mask,15)==2)
            {
                mpz_set(lfsr,One);
                mpz_set(i, Zero);
                do
                {
                    mpz_and(lsb,lfsr,One);
                    mpz_div_2exp(lfsr,lfsr,mpz_get_ui(One));
                    if(mpz_cmp(lsb,Zero) > 0)
                    {
                        mpz_xor(lfsr, lfsr, mask);
                    }
                    mpz_add(i,i,One);
                }
                while(mpz_cmp(lfsr, One) != 0);
                mpz_sub(Testb,power,One);
                if(mpz_cmp(i, Testb) == 0)
                {
                    cout<<"0x";
                    mpz_out_str(stdout, 16, mask);
                    cout<<endl;
                }
            }
            mpz_add(mask,mask,One);
        }
        cout<<endl;
        mpz_add(width,width,One);
    }
    return 0;
}

Like you said: it takes a while to find masks as periods get bigger. But I doubt there is a quicker way. I do not know about any shortcuts that would make it quicker. In the end, I am sharing this in case you (or anyone else who finds this question and at least wants to see some brute-force code) may find it usable.