GOPRIMPOLY

GOPRIMPOLY is an application for efficiently finding binary primitive polynomials from order 16 to 53

Description

Robust error detection techniques are vital for reliable and efficient digital communication. Commonly occurring digital communication errors and changes are often a result of factors such as noise and interference. Cyclic redundancy check (CRC) is an error detection method for finding burst errors up to the length of the CRC used. CRC generator polynomials using the factor (x+1) times the primitive polynomial can detect up to 3 errors for messages up to a length of approximately 2d bits where d is the degree of the polynomial. Using larger generator polynomials creates very low probability of undetected errors for short message lengths. The factoring of polynomials has been a well-known and researched problem, particularly for degree m greater than or equal to 16.

Sandia researchers have developed the GOPRIMPOLY application and primitive polynomial search algorithm to efficiently determine primitive binary polynomials from order 16 to 53. Using GOPRIMPOLY, the user can select the number of non-zero coefficients of the primitive polynomial in order to find binary primitive polynomials with the desired characteristic. GOPRIMPOLY is a self-contained Matlab executable and requires the Matlab Compile Runtime (MCR) to execute in a target machine without the need for the full Matlab application. If the user has the full Matlab application, the application can run from the command line. In addition, if the user has the application with the parallel toolbox enabled, the application can exploit multi-core processors. With this tool, many different generator polynomials can be examined and various output options are possible, including results similar to those from Matlab’s “primpoly” function.

Benefits

• Efficiently determines primitive polynomials up to order 53 or larger if a separate method is available
• Billions of candidate polynomials for high degrees can be treated using subsets of the polynomials and limit memory requirements
• Speed/efficiency- Nearly eightfold increase using an 8-core processor
• Ease of use. Includes GUI interface and user manual

Applications and Industries

• Cyclic Redundancy Check (CRC)
• Random number generators using linear feedback shift registers (LFSR)
• Digital communications companies
• Digital content generation
• Mathematical toolboxes