# # 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 binary irreducible polynomials # up to degree 11
all-lowblock-irredpoly-short.txt:
#
# Complete list of the irreducible polynomials over GF(2)
# of the form x^d + \sum_{k=0}^{q}{x^q}
# where q
#
# Complete list of irreducible polynomials over GF(2)
# of the form x^d + \sum_{k=0}^{q}{x^q}
# where q
all-lowblock-primpoly-short.txt:
#
# Complete list of the primitive polynomials over GF(2)
# of the form x^d + \sum_{k=0}^{q}{x^q}
# where q
#
# Complete list of primitive polynomials over GF(2)
# of the form x^d + \sum_{k=0}^{q}{x^q}
# where q
#
# 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
#
# 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
all-trinomial-irredpoly-short.txt:
#
# 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
all-trinomial-nonprimpoly.txt:
#
# Complete list of irreducible trinomials over GF(2) that are NOT primitive
# up to degree 400
all-trinomial-primpoly-short.txt:
#
# 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)
#
# 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.
#
# Binary primitive polynomials of degree 64
# with lowest non-constant coefficient as high as possible
# as hexadecimal numbers with leading coefficient omitted (!)
#
# The polynomials are those given in lowbit64-primpoly.txt but bit-reversed
#
# 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.
#
# 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.
# Printed as hexadecimal numbers with leading coefficient omitted (!)
#
# 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.
#
# 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)
# 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
#
# 'random' binary primitive polynomials
#
# 100 'random' degree-32 binary primitive polynomials
# as hexadecimal numbers with leading coefficient omitted (!)
#
# The polynomials are those given in rand32-primpoly.txt
#
# 100 'random' degree-32 binary primitive polynomials
#
# 100 'random' degree-64 binary primitive polynomials
# as hexadecimal numbers with leading coefficient omitted (!)
#
# The polynomials are those given in rand64-primpoly.txt
#
# 100 'random' degree-64 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
# 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 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 the 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.
#
Your
feedback
is appreciated.
Jörg Arndt
Last modified
2010-June-15 (15:17)
Goto
Jörg's ugly Homepage