Take the 2-minute tour ×
Software Recommendations Stack Exchange is a question and answer site for people seeking specific software recommendations. It's 100% free, no registration required.

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…

share|improve this question
    
I feel like this is the kinda problem you tinker around in Mathematica to solve. Then if you do it often enough, make a general solution in Mathematica and compile it. –  Oxinabox Feb 8 at 7:29
    
Unless this was example question, with the intent of showign that sometimes the only tool in your toolbox tthat fits is the super high end swiss army knife, its not a great answer. I'll have a tinker and see if it is actually a problem that mathimatica can solve, without pain –  Oxinabox Feb 9 at 0:19
add comment

2 Answers

up vote 2 down vote accepted

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.

share|improve this answer
add comment

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.

share|improve this answer
    
-1, Softwhere Rec is only for Existant Software. Suggestion: Release this on (for example) GitHub, then Link. See: meta.softwarerecs.stackexchange.com/questions/79/… –  Oxinabox Feb 12 at 3:29
    
Such a solution as yours would have been great on almost any other site on the SE network. But not here. –  Oxinabox Feb 12 at 3:32
    
It's nice… but it's brute-forcing. I asked for something quicker. –  e-sushi Feb 12 at 3:55
1  
@Oxinabox I think this perfectly fits the "If you can write a smallish script to do the task, then post it as part of your answer." definition mentioned at Meta. It's merely 70 lines of code, including the comments and blank lines (checked via copy-and-paste). Yet, I won't be accepting it as it doesn't use (what cHiMp calls) "mathematical shortcuts". –  e-sushi Feb 12 at 4:12
1  
You have a fair point, I thought it was a bit longer the 70 lines. -1 retracted. I guess the recommended tool is a C compiler? hmm idk still abit suss –  Oxinabox Feb 12 at 4:50
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.