# Tables of mathematical data

These files are part of the fxt package. For background information see the fxtbook.
all-irredpoly.txt:
#
# Complete list of binary irreducible polynomials
# up to degree 11

#
# Complete list of binary irreducible normal polynomials
# whose roots are a self-dual basis, up to degree 19.
# There are no such polynomials with degree a multiple of 4.
# Primitive polynomials are marked by a P.

#
# Complete list of binary irreducible self-reciprocal polynomials (SRP)
# up to degree 22.  The only SRP of odd degree (1+x) is omitted.
# The number after the percent sign equals (2^(n/2)+1)/r  where
# r is the order of the polynomial with degree n.
#

#
# Complete list of the irreducible polynomials over GF(2)
# of the form  x^d + \sum_{k=0}^{q}{x^q}
#   where q<d  and d<=400
#
# Short form:  a line of the form
#   d:  t1 t2 t3 t4 ...tn
# corresponds to n entries in the usual form:
#   d, tj, tj-1, tj-2, ..., 1, 0  (j \in 1..n)

#
# Complete list of irreducible polynomials over GF(2)
# of the form  x^d + \sum_{k=0}^{q}{x^q}
#   where q<d  and d<=400
# All entries from the second-highest power of
# x to x^0==1 are omitted, i.e. the entry
#   16,5  should be read as
# 16,5,4,3,2,1,0 == x^16+x^5+x^4+x^3+x^2+x+1

#
# Complete list of the primitive polynomials over GF(2)
# of the form  x^d + \sum_{k=0}^{q}{x^q}
#   where q<d  and d<=400
#
# Short form:  a line of the form
#   d:  t1 t2 t3 t4 ...tn
# corresponds to n entries in the usual form:
#   d, tj, tj-1, tj-2, ..., 1, 0  (j \in 1..n)

#
# Complete list of primitive polynomials over GF(2)
# of the form  x^d + \sum_{k=0}^{q}{x^q}
#   where q<d  and d<=400
# All entries from the second-highest power of
# x to x^0==1 are omitted, i.e. the entry
#   16,5  should be read as
# 16,5,4,3,2,1,0 == x^16+x^5+x^4+x^3+x^2+x+1

#
# Primitive polynomials x^k + (1+x)^n over GF(2) for n<=400
#
# An entry n,k,0 means x^k + (1+x)^n is primitive.
# All entries n,*,* correspond to polynomials of degree n, i.e. 0<k<n
# Whenever there is an entry n,k,0 then there is also an entry n,n-k,0
# (for the reciprocal polynomial).
# Also both (1+x)^k + x^n and (1+x)^(n-k) + x^n are irreducible.

#
# Complete list of non-primitive irreducible polynomials over GF(2)
# up to degree 12
# Such polynomials exist only for degrees d where 2^d-1 is composite.

#
# Complete list of binary normal (irreducible) polynomials
#   up to degree 13.
# Non-primitive polynomials are marked with an "X".

#
# Complete list of primitive polynomials over GF(2)
# up to degree 11

#
# Primitive polynomials 1 + (1+x)^k + (1+x)^n over GF(2) for n<=400
#
# An entry n,k,0 means 1 + (1+x)^k + (1+x)^n is primitive.
# All entries n,*,* correspond to polynomials of degree n, i.e. 0<k<n

#
# Complete list of irreducible trinomials over GF(2)
# up to degree 400
# Short form:  a line of the form
#   d:  t1 t2 t3 t4 ...tn
# corresponds to n entries in the usual form:
#   d, tj, 0  (j \in 1..n)

#
# Complete list of irreducible trinomials over GF(2)
# up to degree 400

#
# Complete list of irreducible trinomials over GF(2) that are NOT primitive
# up to degree 400

#
# Complete list of primitive trinomials over GF(2)
# up to degree 400
# Short form:  a line of the form
#   d:  t1 t2 t3 t4 ...tn
# corresponds to n entries in the usual form:
#   d, tj, 0  (j \in 1..n)

#
# Complete list of primitive trinomials over GF(2)
# up to degree 400

#
# Rules for CLHCA with maximal period up to degree 400
#
# An entry n,k,0 means that any length-n CLHCA with a rule of
# weight k has maximal period.
# For example, the entry  5,3,0  gives the rule   r = 00111
# The corresponding primitive polynomial over GF(2) is 1 + x^k*(1+x)^(n-k),
# also the reciprocal polynomial (1+x)^k + x^n is primitive.

#
# Table of weight-5 binary primitive polynomials
# with (roughly) equally spaced coefficients.
#
# The data was taken from:
#   Janusz Rajski, Jerzy Tyszer:
#   "Primitive Polynomials Over GF(2) of Degree up to 660
#   with Uniformly Distributed Coefficients",
#   Journal of Electronic Testing: Theory and Applications,
#   vol.19, pp.645-657, 2003.

#
# Table of weight-7 binary primitive polynomials
# with (roughly) equally spaced coefficients.
#
# The data was taken from:
#   Janusz Rajski, Jerzy Tyszer:
#   "Primitive Polynomials Over GF(2) of Degree up to 660
#   with Uniformly Distributed Coefficients",
#   Journal of Electronic Testing: Theory and Applications,
#   vol.19, pp.645-657, 2003.

#
# Table of weight-9 binary primitive polynomials
# with (roughly) equally spaced coefficients.
#
# The data was taken from:
#   Janusz Rajski, Jerzy Tyszer:
#   "Primitive Polynomials Over GF(2) of Degree up to 660
#   with Uniformly Distributed Coefficients",
#   Journal of Electronic Testing: Theory and Applications,
#   vol.19, pp.645-657, 2003.

#
# Multiplicative identities for the function
# eta(x) = prod( n=1, infinity, 1-x^n )
#
# A line
# r: EXPR
# says that
# prod(j=1,r-1,if ( gcd(j,r)==1, eta(w^j*x), 1)) = EXPR
# where in EXPR eta(x^k) is abbreviated as E(k).

#
# All polynomials over GF(2) corresponding to type-t Gaussian normal bases
# for types 1<=t<=11 and degrees n<=63.
# Line format is
# n,t: list-of-pol-coefficients

#
# List of types of Gaussian normal basis (NB) up to n=1032.
# The smallest 10 types are listed.
# For n divisible by 8 no Gaussian NB exists.
# Bases of type 1 and 2 are optimal normal bases (ONB).
#
# A line of the form
#   n:  t1 t2 t3 t4 ...t10
# says that there is a type-t Gaussian NB for GF(2^n)
#   for t=tj  (j \in 1..10)

#
# Binary primitive polynomials of degree 64
# with lowest non-constant coefficient as high as possible
#
# The polynomials are those given in lowbit64-primpoly.txt but bit-reversed

#
# Normal (irreducible) polynomials over GF(2)
# with lowest non-constant term as high as possible.

#
# Normal primitive polynomials over GF(2)
# with lowest non-constant term as high as possible.

#
# The first four binary primitive polynomials of degree 1000 in counting order.

#
# The first four binary primitive polynomials of degree 1024 in counting order.

#
# Binary primitive polynomials of degree 127 in counting order.
# Table is complete for second-highest term <=15.
# Additionally the first few entries for 16 are listed.

#
# Binary primitive polynomials of degree 128 in counting order.
# Table is complete for second-highest term <=15.
# Additionally the first few entries for 16 are listed.

#
# Binary primitive polynomials of degree 256 in counting order.
# Table is complete for second-highest term <=15.
# Additionally the first few entries for 16 are listed.

#
# Binary primitive polynomials of degree 512 in counting order.
# Table is complete for second-highest term <=15.
# Additionally the first few entries for 16 are listed.

#
# Binary primitive polynomials of degree 521 in counting order.
# Table is complete for second-highest term <=15.
# Additionally the first few entries for 16 are listed.

#
# Binary primitive polynomials of degree 607 in counting order.
# Table is complete for second-highest term <=15.
# Additionally the first few entries for 16 are listed.

#
# Binary primitive polynomials of degree 63 in counting order.
# Table is complete for second-highest term <=15.
# Additionally the first few entries for 16 are listed.

#
# Binary primitive polynomials of degree 64 in counting order.
#
# Table is complete for second-highest term <=15.
# Additionally the first few entries for 16 are listed.
# The polynomials are those given in lowbit64-primpoly.txt

#
# Binary primitive polynomials of degree 64 in counting order.
# Table is complete for second-highest term <=15.
# Additionally the first few entries for 16 are listed.

#
# Binary irreducible polynomials with lowest-most possible set bits.
# These are the minimal numbers with the corresponding
# irreducible polynomial of given degree.
# These are _not_ primitive in general.

#
# Table of low-bit LHCA rules
# corresponding to binary primitive polynomials.
# The rules are those were the highest set bit
# is as low as possible.

#
# Binary normal primitive polynomials with lowest-most possible set bits.
# These are the minimal numbers with the corresponding
# polynomial of given degree primitive.

#
# Binary primitive polynomials with lowest-most possible set bits.
# These are the minimal numbers with the corresponding
# polynomial of given degree primitive.

#
# Primitive polynomials over GF(2)
# with smallest possible block of set bits.
# All entries from the second-highest power of
# x to x^0==1 are omitted, i.e. the entry
#   16,5  should be read as
# 16,5,4,3,2,1,0 == x^16+x^5+x^4+x^3+x^2+x+1

#
# Factorizations of Mersenne numbers 2**n-1 for n<=1200
#
# format:  an entry
#    n: a.b.c.d
# means that 2**n-1 == a*b*c*d
#
# Repeated factors occur according to their multiplicity.
# Composite factors have the letter C prepended.
# The first such entry appears with n=787
#
# Extracted from:
#   J.Brillhart, D.H.Lehmer, J.L.Selfridge, B.Tuckerman, S.S.Wagstaff Jr.:
#   {Factorizations of $b^n +-1 b=2,3,5,6,10,11$ up to high powers},
#   Contemporary Mathematics, Volume~22, Second Edition,
#   American Mathematical Society, 1988
#   (online version of June-2006)

#
# Factorizations of Mersenne numbers 2**n-1 for prime n<=1103
# where the complete factorization is known
#
# format:  an entry
#    n: a.b.c.d
# means that 2**n-1 == a*b*c*d
#
# Repeated factors occur according to their multiplicity.
#
# The (prime) exponents not in the list are:
# 787 821 823 827 853 857 859 863 877 887 919 929 937 941 947 953 977
# 991 1009 1013 1019 1031 1039 1051 1061 1069 1087 1093

#
# Minimal weight irreducible polynomials over GF(2)
# In addition the coefficients/bits (apart from the
# constant and the leading term) are as close to
# the low end as possible.
# These are _not_ primitive in general.

#
# Table of minimun-weight LHCA rules
# corresponding to binary primitive polynomials.
#
# The data was taken from:
#   Kevin Cattel, Shujian Zhang:
#   "Minimal Cost One-Dimensional Linear Hybrid Cellular Automata
#   of Degree Through 500",
#   Journal of Electronic Testing: Theory and Applications,
#   vol.6, pp.255-258, 1995

#
# Minimal weight primitive polynomials over GF(2)
# with leading term between 10000 and 30000.
# These are the values of n, between 10000 and 30000,
# for which the factorization of 2^n-1 is known to me.
# In addition the coefficients/bits (apart from the
# constant and the leading term) are as small as possible.

#
# Minimal weight primitive polynomials over GF(2)
# taken from the paper
#    K. Cattell, J. Muzio:
#   "Tables of linear cellular automata for minimal weight
#    primitive polynomials of degrees up to 300"
#
# Note that the minweight polynomials given here are do not have the
# additional lowbit property (highest non-zero entry as far right as
# possible, given in minweight-primpoly.txt).
# e.g. for degree==30 (weight=5):
#  0x40018003UL == 30,16,15,1,0 // minweight entry (this file)
#  0x40000053UL == 30,6,4,1,0   // minweight-lowbit entry

#
# Minimal weight primitive polynomials over GF(2)
# In addition the coefficients/bits (apart from the
# constant and the leading term) are as close to
# the low end as possible.

#
# Number of irreducible normal degree-n polynomials over GF(2):
# A line
# n:  N  p1^e1.p2^e2. ...
# says there are N normal polynomials of degree n,
# the third column gives the factorization of N.

#
# Pentanomial primitive polynomials over GF(2)
# The coefficients/bits (apart from the constant and the leading term)
# are as close to the low end as possible.

#
# Structure of the factorization of x^n-1 over GF(2):
# A line
# n: [e] [m1*d1 + m2*d2 + ... ]
# says that (x^n-1) = P(x)^e and P(x) factors into
# m1 different irreducible polynomials of degree d1
# m2 different irreducible polynomials of degree d2 etc.
#
# (x^(2*n)+1) = (x^n+1)^2 ==>
#   e is the largest power of two that divides n
#
# Examples:
# n=6:  [x^6+1] = ( [x+1]*[x^2+x+1] )^2
# n=15: [x^15+1] = ( [x+1]*[x^2+x+1][x^4+x+1]*[x^4+x^3+1]*[x^4+x^3+x^2+x+1] )^1

# Composites n<2^32 of the form 24k+13 for which
# H_{(n-1)/4}==0 (where H_0=1, H_1=2, H_{k}=4*H_{k-1}-H_{k-2})
# together with up to five bases a<1000 they are strong pseudoprimes to.

# Composites n<2^32 of the form 24k+19 for which
# U_{(n+1)/4}==0 (where U_0=0, U_1=1, U_{k}=4*U_{k-1}-U_{k-2})
# together with bases a<10^5 they are strong pseudoprimes to.
# Maximal 5 bases are listed with each number.

# Composites n<2^32 of the form 24k+1 for which
# U_{(n-1)/4}==0 (where U_0=0, U_1=1, U_{k}=4*U_{k-1}-U_{k-2})
# together with bases a<100 they are strong pseudoprimes to.
# Maximal 5 bases are listed with each number.

# Composites n<2^32 of the form 6k+5 for which
# U_{(n+s)/2}==0 (where U_0=0, U_1=1, U_{k}=4*U_{k-1}-U_{k-2}
#  and s=1 if n%4=1, s=-1 if n%4=3).
# n followed by the smallest bases a<1000 they are strong pseudoprimes to
# (up to six bases are given).

# Composites n<2^32 of the form 24k+7 for which
# H_{(n+1)/4}==0 (where H_0=1, H_1=2, H_{k}=4*H_{k-1}-H_{k-2})
# together with bases a<10^5 they are SPPs to.
# Maximal 5 SPP bases are listed with each number.

# Odd composite n<2^32 which are strong pseudoprimes to both bases 2, and 3.
# There are 104 entries in the list.
# Modulo 12 the distribution is:
#    n%12  num
#     1     75
#     5      9
#     7     18
#    11      2

#
# 100 'random' degree-32 binary primitive polynomials
#
# The polynomials are those given in rand32-primpoly.txt

#
# 100 'random' degree-32 binary primitive polynomials

#
# 100 'random' degree-64 binary primitive polynomials
#
# The polynomials are those given in rand64-primpoly.txt

#
# 100 'random' degree-64 binary primitive polynomials

#
# 'random' binary primitive polynomials

# Aperiodic sums of roots of unity that are zero.
# Format:
# k: [bit-string] n [subset]
# k is the rank of the necklace in lex order
# (starting with k=1 for the all-zero word),
# n is the length of the necklace.
#
# For example, the line
#   6:  ...11..1..11  12    0 1 4 7 8
# says that Z:=w^0+w^1+w^4+w^7+w^8==0  where  w := exp(2*Pi*I/12)
#
# Such sums Z exist for the following n:
# n:       1, 12, 18, 20,  24, 28,  30,   36,    40,    42,    44,   45,
# numof(Z) 1,  2, 24,  6, 236, 18, 3768, 20384, 7188, 227784, 186, 481732448,
# The list is complete for 1<n<28,
# and contains the first and last few Z for n=30 and n=36.
#

# The 4*42=168 zero-divisors of the sedenions
# that are sums or differences of two units.
#
# In an entry (A + B) A and B
# are to the indices of the units (starting with index zero).
# Only 42 zero-divisors are given:
# for each entry (A + B) there are also
# the zero-divisors (A - B), (-A + B), and (-A -B).

# The 4*42=168 products of zero-divisors of the sedenions
# that are sums or differences of two units.
#
# In an entry (A + B)*(C +- D) A, B, C, and D
# are to the indices of the units (starting with index zero).
# Only 2*42=84 products are given:
# for each entry (A + B)*(C + D) there is another
# zero-product (A - B)*(C - D),
# and for each entry (A + B)*(C - D)
# there is also (A - B)*(C + D).

#
# Small prime factors of composite Fermat numbers F_n=2^t+1 where t=2^n.
# The factors are of the form p=1+k*2^(n+2).
# The order of two modulo a factor p (of F_n) equals 2^(n+1).
# For each n the search included candidates <=1+(10^5)*2^(n+2)
#   but was stopped when one factor was found.
#  5 <= n <= 300

# Primes p<2^2048 of the form x^k-x^j+1 where x=2^8.
# These primes allow for easy modular reduction.

# Structure of zero-divisors of the 64-ions
# that are sums or differences of two units.
#
# In the 64 x 64 matrix below
# a one corresponds to a pair of indices A and B
# such that (A+B) is a zero-divisor.
# For each such pair all of (+-A +-B) are zero divisors.
# If (A + B) is a zero-divisor then trivially also
# (B + A) is a zero-divisor, hence the symmetry.
# The upper left 32 x 32 square gives the structure for
# the 32-ions, the upper left 16 x 16 square for the sedenions.
# The upper left 8x8 square contains no ones:
# there are no zero-divisors for the octonions,
# quaternions, complex, and real numbers.
#