# # 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. #
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<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
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<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
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)
# # 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
# # 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. # 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.
# # 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 # 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
# # '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. #