¿Herramienta para calcular máscaras polinómicas con período máximo para LFSR?

Primpolio

Acabo de encontrar binarios (y código fuente) para un programa que genera un polinomio primitivo de grado n módulo p . También puede probar la primitividad de un polinomio dado y encontrar todos los polinomios primitivos.

El programa se llama “Primpoly”, Versión 11.0.

Una muestra ejecutada desde la línea de comando:

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 

El código fuente y los ejecutables se distribuyen bajo los términos de la Licencia Pública General GNU.

Si se desplaza hacia abajo más allá del código fuente en la página vinculada anteriormente, encontrará ejecutables para Mac OS X 10.6, Windows XP (32 bits) y para Windows 7 (32 bits). Para poder ejecutarlos como se esperaba, probablemente tendrá que cambiar el nombre de los archivos, eliminando todo después de la ….exeparte.

Debo admitir que no descargué ni ejecuté los ejecutables ofrecidos. En cambio, descargué el código fuente ofrecido, modifiqué algunas cosas a mi gusto y compilé mi propia versión. Por lo tanto, no puedo confirmar (ni negar) que los ejecutables ofrecidos sean funcionales.

También debe saber que necesitaba ajustar algunas tuercas y tornillos menores para que el código fuente se compilara sin problemas en mi sistema. Por otro lado, eso podría haber sido el resultado de la instalación y configuración de mi sistema individual.

Sin embargo, puedo confirmar que mi versión compilada con éxito de Primpoly hace lo que debería y definitivamente es más rápido que forzar las cosas una por una, que es lo que estaba buscando.

Prima

Lo que realmente me gusta es el hecho de que el autor del programa también se tomó el tiempo de explicar las teorías que usó. Consulte la sección dedicada del sitio web: " Cálculo de polinomios primitivos: teoría y algoritmo ".

_{En caso de que conozcas alternativas, o si encuentras algo parecido (o mejor), no seas tímido y compártelo con la comunidad Softwarerecs.SE.}

Como no soy matemático, no conozco ningún "atajo matemático" para calcular polinomios.

Pero aquí hay un programa de línea de comandos que funciona y que creé hace un tiempo. Debería ser fácil de compilar con cualquier compilador C/C++ que se ajuste a su plataforma. Para poder manejar períodos "más grandes", el código fuente se basa en la biblioteca aritmética de precisión múltiple de GNU , que es una descarga gratuita. Con todo, debería compilar bien.

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

Como dijiste: lleva un tiempo encontrar máscaras a medida que aumentan los períodos. Pero dudo que haya una manera más rápida. No conozco ningún atajo que lo haga más rápido. Al final, estoy compartiendo esto en caso de que usted (o cualquier otra persona que encuentre esta pregunta y al menos quiera ver algún código de fuerza bruta) pueda encontrarlo útil.