A074744 -id:A074744 - cp's OEIS frontend

A073726 Primitive irreducible trinomials: x^n + x^k + 1 is a primitive irreducible polynomial (mod 2) for some k with 0 < k < n.

2, 3, 4, 5, 6, 7, 9, 10, 11, 15, 17, 18, 20, 21, 22, 23, 25, 28, 29, 31, 33, 35, 36, 39, 41, 47, 49, 52, 55, 57, 58, 60, 63, 65, 68, 71, 73, 79, 81, 84, 87, 89, 93, 94, 95, 97, 98, 100, 103, 105, 106, 108, 111, 113, 118, 119, 121, 123, 124, 127, 129, 130, 132, 134, 135, 137, 140, 142, 145, 148, 150, 151, 153, 159, 161, 167, 169, 170, 172, 174, 175, 177, 178, 183, 185, 191, 193, 194, 198, 199, 201

Offset: 1

Richard P. Brent and Paul Zimmermann, Sep 05 2002

Start is similar to A194125; first terms here but missing there are 140, 212, 236.

S. W. Golomb, "Shift Register Sequences", revised edition, reprinted by Aegean Park Press, 1982. See Tables V-1, V-2.

Joerg Arndt, Complete list of primitive trinomials over GF(2) up to degree 400.
Joerg Arndt, Complete list of primitive trinomials over GF(2) up to degree 400 [Cached copy, with permission]
A. J. Menezes, P. C. van Oorschot and S. A. Vanstone, Handbook of Applied Cryptography, CRC Press, 1996; see Table 4.8.
Index entries for sequences related to trinomials over GF(2)

See A073571 for irreducible trinomials and A001153 for primitive Mersenne trinomials (and references). See A074744 for values of k.

Cf. A194125 (n such that x^n+(1+x)^w over GF(2) is primitive for some w).

A073726 := function(n) for k := 1 to n-1 do if IsPrimitive(x^n+x^k+1) then return true; end if; end for; return false; end function; l := []; for n := 1 to 100 do if A073726(n) then l := Append(l,n); end if; end for; l;

A073726 := proc(n) local k,m: option remember: if(n=1)then return 2: else m:=procname(n-1)+1: while(true)do for k from 1 to m-1 do if Primitive(x^m+x^k+1) mod 2 then return m: fi: od: m:=m+1: od: fi: end:
seq(A073726(n),n=1..20); # Nathaniel Johnston, Apr 26 2011

okQ[n_] := AnyTrue[Range[n-1], PrimitivePolynomialQ[x^n + x^# + 1, 2]&];
Select[Range[201], okQ] (* Jean-François Alcover, Aug 19 2019 *)

a(49)-a(58) from Nathaniel Johnston, Apr 26 2011

A132454 First primitive GF(2)[X] polynomials of degree n and minimal number of terms, expressed as -k for X^n+X^k+1, else with X^n suppressed.

Original entry on oeis.org

1, -1, -1, -1, -2, -1, -1, 29, -4, -3, -2, 83, 27, 43, -1, 45, -3, -7, 39, -3, -2, -1, -5, 27, -3, 71, 39, -3, -2, 83, -3, 197, -13, 281, -2, -11, 83

Offset: 1

Francois R. Grieu, Aug 22 2007

More precisely: when there exists k, 0

			a(10)=-3, representing the GF(2)[X] polynomial X^10+X^3+1, because this degree 10 trinomial is primitive, contrary to X^10+X^1+1, X^10+X^2+1 and X^10+X^2+X^1.

Either of 2^n+2^(-a(n))+1 or 2^n+a(n) belongs to A091250. If there exists m such that n = A073726(m), then a(n) = -A074744(m); otherwise a(n) = A132450(n). A132453(n) gives the primitive polynomial corresponding to a(n). Cf. A132448, similar, with no restriction on number of terms. Cf. A132450, similar, with restriction to at most 5 terms. Cf. A132452, similar, with restriction to exactly 5 terms.

A186440 Number of prime divisors (counted with multiplicity) of n such that the primitive irreducible trinomial x^n + x^k + 1 is a primitive irreducible polynomial (mod 2) for some k with 0 < k < n (A073726).

Original entry on oeis.org

1, 1, 2, 1, 2, 1, 2, 2, 1, 2, 1, 3, 3, 2, 2, 1, 2, 3, 1, 1, 2, 2, 4, 2, 1, 1, 2, 3, 2, 2, 2, 4, 3, 2, 3, 1, 1, 1, 4, 4, 2, 1, 2, 2, 2, 1, 3, 4, 1, 3, 2, 5, 2, 1, 2, 2, 2, 2, 3, 1, 2, 3, 4, 2, 4, 1, 4, 2, 2, 3, 4, 1, 3, 2, 2, 1, 2, 3

Offset: 1

Jonathan Vos Post, Feb 21 2011

			a(48) = 4 because A073726(48) = 100, and Omega(100 = 2^2 * 5^2) = 4.

Alfred J. Menezes, Paul C. van Oorschot and Scott A. Vanstone, Handbook of Applied Cryptography, CRC Press, ISBN: 0-8493-8523-7, October 1996, 816 pages, 5th printing, August 2001.

Cf. A001222, A073726, See A074744 for corresponding values of k.

a(n) = bigomega(A073726(n)) = Omega(A073726(n)) = A001222(A073726(n)).

a(49) - a(78) from Nathaniel Johnston, Apr 26 2011

Showing 1-3 of 3 results.

cp's OEIS Frontend

A073726 Primitive irreducible trinomials: x^n + x^k + 1 is a primitive irreducible polynomial (mod 2) for some k with 0 < k < n.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Magma

Maple

Mathematica

Extensions

A132454 First primitive GF(2)[X] polynomials of degree n and minimal number of terms, expressed as -k for X^n+X^k+1, else with X^n suppressed.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

A186440 Number of prime divisors (counted with multiplicity) of n such that the primitive irreducible trinomial x^n + x^k + 1 is a primitive irreducible polynomial (mod 2) for some k with 0 < k < n (A073726).

Views

Author

Keywords

Examples

Links

Crossrefs

Formula

Extensions