Tool zur Berechnung von Polynommasken mit maximaler Periode für LFSRs?

Primpoly

Ich habe gerade Binärdateien (und Quellcode) für ein Programm gefunden, das ein primitives Polynom des Grades n modulo p generiert . Sie können auch ein bestimmtes Polynom auf Primitivität testen und alle primitiven Polynome finden.

Das Programm heißt „Primpoly“, Version 11.0.

Ein Beispiellauf von der Befehlszeile:

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 

Der Quellcode und die ausführbaren Dateien werden unter den Bedingungen der GNU General Public License vertrieben.

Wenn Sie auf der oben verlinkten Seite am Quellcode vorbei nach unten scrollen, finden Sie ausführbare Dateien für Mac OS X 10.6, Windows XP (32 Bit) und für Windows 7 (32 Bit). Um sie wie erwartet ausführen zu können, müssen Sie die Dateien wahrscheinlich umbenennen und alles nach dem ….exeTeil entfernen.

Ich muss zugeben, dass ich die angebotenen ausführbaren Dateien nicht heruntergeladen und ausgeführt habe. Stattdessen habe ich den angebotenen Quellcode heruntergeladen, einige Dinge nach meinen Wünschen angepasst und meine eigene Version kompiliert. Daher kann ich die Funktionsfähigkeit der angebotenen ausführbaren Dateien nicht bestätigen (noch dementieren).

Sie sollten auch wissen, dass ich einige kleinere Schrauben und Muttern optimieren musste, damit der Quellcode auf meinem System fehlerfrei kompiliert wird. Auf der anderen Seite könnte das auch nur das Ergebnis meiner individuellen Systemeinrichtung und -konfiguration gewesen sein.

Nichtsdestotrotz kann ich bestätigen, dass meine erfolgreich kompilierte Version von Primpoly tut, was sie sollte, und dass sie definitiv schneller ist, als Dinge einzeln zu erzwingen – was ich gesucht habe.

Bonus

Was mir sehr gut gefällt, ist die Tatsache, dass sich der Autor der Sendung auch die Zeit genommen hat, die von ihm verwendeten Theorien zu erklären. Siehe den entsprechenden Abschnitt der Website: „ Berechnung primitiver Polynome – Theorie und Algorithmus “.

_{Falls Sie Alternativen kennen oder etwas Ähnliches (oder Besseres) finden, seien Sie nicht schüchtern und teilen Sie es mit der Softwarerecs.SE-Community.}

Da ich kein Mathematiker bin, kenne ich keine „mathematischen Abkürzungen“ zur Berechnung von Polynomen.

Aber hier ist ein funktionierendes Befehlszeilenprogramm, das ich vor einiger Zeit erstellt habe. Es sollte einfach mit jedem C/C++-Compiler zu kompilieren sein, der zu Ihrer Plattform passt. Um mit „größeren“ Perioden umgehen zu können, stützt sich der Quellcode auf The GNU Multiple Precision Arithmetic Library , die kostenlos heruntergeladen werden kann. Alles in allem sollte es gut kompilieren.

// 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;
}

Wie Sie sagten: Es dauert eine Weile, Masken zu finden, wenn die Periode größer wird. Aber ich bezweifle, dass es einen schnelleren Weg gibt. Ich kenne keine Abkürzungen, die es schneller machen würden. Am Ende teile ich dies für den Fall, dass Sie (oder jeder andere, der diese Frage findet und zumindest etwas Brute-Force-Code sehen möchte) es brauchbar finden.