HTTPS SSH

mlpolygen - Maximal Length polynomial generator

MLPolyGen is a command line tool for generating maximal length (ML) polynomials for a linear feedback shift register (LFSR). MLPolyGen can generate ML polynomials of a specified order, or test whether a specified polynomial is maximal length. MLPolyGen can use the GNU Multiple Precision Arithmetic Library (GMP) to work with very large numbers. The larger the numbers, the more time it will take to compute.

Building and Installing

This program is built with CMake, the cross-platform, open-source build system. Typically the program is not built directly inside the source directory. My preference is to build the program in a directory named build, located in the root of the source directory.

To follow this approach:

$ cd mlpolygen-1.x.x # where you put the source code
$ mkdir -p build
$ cd build
$ cmake ..
$ make
$ sudo make install

Normally, MLPolyGen requires GMP to build so that it can support numbers larger than 64 bits. If GMP is present on your system, CMake will automatically detect and use it. If you would like to disable the dependency on GMP, run CMake using the WITHOUT_GMP option as follows:

$ cmake -DWITHOUT_GMP=1 ..

Usage examples

This section contains some examples for some common use cases. All of the options that are built in can shown by requesting help:

$ mlpolygen -?

To generate all of the maximal length polynomials of a particular order (e.g. 16):

$ mlpolygen 16
8016
801c
...
fff5
fff6

These can also be generated using the symmetric pairs method. This is about twice as fast as the linear method (because it only has to search half the space), but it generates an unsorted output:

$ mlpolygen -p 16
8016
b400
...
fdbf
fedf

To generate only few polynomials of a particular order:

$ mlpolygen -n4 16
8016
801c
801f
8029

To generate ML polynomials from a particular starting point:

$ mlpolygen -s 0xff00
ff12
ff18
ff24
ff41
...

To generate a few random ML polynomials of a particular order:

$ mlpolygen -r -n4 16
b354
b5ab
cca0
8299

To test whether specified polynomials are maximal length:

$ mlpolygen -t 0xb354 -t 0xb355
0xb354 is maximal length for order 16
0xb355 is NOT maximal length for order 16

Testing

MLPolyGen includes code for testing its results. The testing is currently implemented using a simple makefile along with the stardard tools provided on a Unix system. To run the test, build according to the above instructions and then:

$ cd mlpolygen-1.x.x # where you put the source code
$ cd test
$ make

Refer to test/Makefile to see the tests performed, or increase the order for which the tests are performed. Note that larger orders could take hours (days, weeks) to complete.

To do

  • add a CLI switch to specify a stop polynomial value (so it could compute subsections in parallel)
  • make sure it works on multiple platforms
  • do some profiling to see if we can speed it up
  • improve PrimeFactorizer to choose better prime candidates
  • increase my CMake knowledge (I'm a noob)
  • use CMake for testing (instead of the current Makefile)

Acknowledgements and Background

  • Thank you to Philip Koopman for providing his page on ML LFSR polynomials: http://www.ece.cmu.edu/~koopman/lfsr/index.html
    • I've used his ML polynomials as reference material for a number of years
    • The mlpolygen tester uses his polynomials for verification
    • His page pointed me to lfsr_s.c
  • Thank you to the author of lfsr_s.c; I believe it was authored by Scott Nelson
    • lfsr_s.c was once located at ftp://helsbreth.org/pub/helsbret/random/lfsr_s.c
    • It contained no license when I downloaded it, and I can no longer find it on the internet
    • I've included an unmodified copy of lfsr_s.c in mlpolygen/src
  • mlpolygen is based on the algorithm described in lfsr_s.c
  • I wrote mlpolygen while examining lfsr_s.c, so portions of mlpolygen may be very loosely based on lfsr_s.c

License

MLPolyGen is released under the GNU General Public License (GPL) version 3. See the file COPYING for the full license.