[math-fun] Redundant trinomials --- are they really necessary?
I need an existence proof --- it's the missing link in a theorem establishing full-plane integer zero-free number walls over finite characteristic ( |F_2 excepted). CONJECTURE: Given any r > 1 , there exists over |F_2 a trinomial f(X) = X^s + X^t + 1 = g(X) h(X) , where g(X) is irreducible of degree r . This topic turns out to have been studied previously, since it is of interest in elliptic curve public-key cryptography. Such "redundant trinomials" are used to do arithmetic in binary finite fields |F^(2^r) lacking a trinomial generating polynomial: the idea is to calculate instead in a larger ring using trinomial f(X) with factor some field generator g(X) , afterwards reducing the result to the field. Of course, engineers don't care greatly about proving that such a trinomial exists for every field degree: they're just content that some have been found for every degree up to 10,000, comfortably exceeding anything currently required. I haven't uncovered a great deal about this in the literature: Christophe Doche (2005) <doche@ics.mq.edu.au> "Redundant Trinomials for Finite Fields of Characteristic 2 " http://web.science.mq.edu.au/~doche/redundant.pdf is cited by most of the rest; Ryul Kim, Wolfram Koepf <koepf@mathematik.uni-kassel.de> "Divisibility of Trinomials by Irreducible Polynomials over |F_2 " https://arxiv.org/pdf/1311.1366.pdf includes results about cofactor h(X) , along with baffling typos. If required I can post lists of sample trinomials and cofactors, currently for prime r < 4096 (in 3 hrs), also all r < 1024 (in 12 mins). Fred Lunnon
The answer may well be found somewhere in the bible: Rudolf Lidl, Harald Niederreiter: {Finite fields}, Cambridge University Press, second edition, (1997). The kid's version may be sufficient in this case: Rudolf Lidl, Harald Niederreiter: {Introduction to finite fields and their applications}, Cambridge University Press, revised edition, (1994). %%%% THIS ONE %%%% may be pertinent: Solomon W.\ Golomb, Pey-Feng Lee: {Irreducible Polynomials Which Divide Trinomials over $\GF(2)$}, %IEEE Transactions on Information Theory, vol.~53, no.~2, pp.~768-774, \bdate{February-2007}.} %% Theorem 7 (Welch s Criterion): For any odd integer t, the irreducible polynomials %% of primitivity t divide trinomials iff gcd( 1 + x^n, 1 + (1+x)^n ) has degree greater than 1. %% Cf. A261524 Some papers about trinomials (raw copy from my bib-file): {Ian F.\ Blake, Shuhong Gao, Robert J.\ Lambert: {Construction and Distribution Problems for Irreducible Trinomials over Finite Fields}, In: D.\ Gollmann, (ed.): {Applications of finite fields}, pp.~19-32, \bdate{1996}. Richard P.\ Brent: {Primitive and Almost Primitive Trinomials}, %\bdate{3-May-2002}.} Richard P.\ Brent: {All You Wanted to Know about Irreducible and Primitive Trinomials}, %Oxford Supercomputer Centre Mini-Conference, \bdate{1-July-2003}. Richard P.\ Brent, Paul Zimmermann: {Algorithms for finding almost irreducible and almost primitive trinomials}, in: Primes and Misdemeanours: Lectures in Honour of the Sixtieth Birthday of Hugh Cowie Williams, Fields Institute Communication FIC/41, The Fields Institute, Toronto, pp.~91-102, \bdate{2004}. Mathieu Ciet, Jean-Jacques Quisquater, Francesco Sica: {A Short Note on Irreducible Trinomials in Binary Fields}, in: {23rd Symposium on Information Theory in the BENELUX}, Louvain-la-Neuve, Belgium, Macq, B., Quisquater, J.-J. (eds.), pp.~233-234, \bdate{May-2002}. URL: \url{http://www.uclouvain.be/crypto/publications/year/2002}.}% OK Harold M.\ Fredricksen, R.\ Wisniewski: {On trinomials $x^n+x^2+1$ and $x^{8l\pm{}3}+x^k+1$ irreducible over $\GF(2)$}, %Information and Control, vol.~50, no,1, pp.~58-63, \bdate{July-1981}.} Ryul Kim, Wolfram Koepf: {Divisibility of Trinomials by Irreducible Polynomials over $\FF_2$}, %arXiv:1311.1366 [math.RA], \bdate{6-November-2013}. %% Extends Welch's criterion (Welch is the special case a=b=1): %% Let f be an irreducible polynomial of order e and degree n over GF(2) and %% a and b be positive integers. Then f divides trinomials x^{am} + x^{bs} + 1 %% if and only if gcd(1 + x^{e1}, 1 + (1 + x)^{e2}) has degree greater than 1, %% where e1 = e / gcd(a,e) and e2 = e / gcd(b,e). Ernst S.\ Selmer: {On the irreducibility of certain trinomials}, %Mathematica Scandinavica, vol.~4, pp.~ \bdate{1956}. %URL: \url{http://www.mscand.dk/issue.php?year=1956&volume=4&issue=}.} %% http://www.mscand.dk/article.php?id=1472 Uzi Vishne: {Factorization of Trinomials over Galois Fields of Characteristic 2}, %Finite Fields and Their Applications, vol.~3, no.~4, pp.~370-377, \bdate{1997}. %URL: \url{http://www.math.biu.ac.il/~vishne/publications.html}.} %% extension of Swan's theorems And there is always Solomon W.\ Golomb: {Shift Register Sequences}, %Holden-Day, \bdate{1967}.} Trinomially yours, jj P.S.: I can send electronic versions of most (or all) of the above. * Fred Lunnon <fred.lunnon@gmail.com> [Jun 10. 2018 07:51]:
I need an existence proof --- it's the missing link in a theorem establishing full-plane integer zero-free number walls over finite characteristic ( |F_2 excepted).
CONJECTURE: Given any r > 1 , there exists over |F_2 a trinomial f(X) = X^s + X^t + 1 = g(X) h(X) , where g(X) is irreducible of degree r .
This topic turns out to have been studied previously, since it is of interest in elliptic curve public-key cryptography. Such "redundant trinomials" are used to do arithmetic in binary finite fields |F^(2^r) lacking a trinomial generating polynomial: the idea is to calculate instead in a larger ring using trinomial f(X) with factor some field generator g(X) , afterwards reducing the result to the field.
Of course, engineers don't care greatly about proving that such a trinomial exists for every field degree: they're just content that some have been found for every degree up to 10,000, comfortably exceeding anything currently required.
I haven't uncovered a great deal about this in the literature:
Christophe Doche (2005) <doche@ics.mq.edu.au> "Redundant Trinomials for Finite Fields of Characteristic 2 " http://web.science.mq.edu.au/~doche/redundant.pdf is cited by most of the rest;
Ryul Kim, Wolfram Koepf <koepf@mathematik.uni-kassel.de> "Divisibility of Trinomials by Irreducible Polynomials over |F_2 " https://arxiv.org/pdf/1311.1366.pdf includes results about cofactor h(X) , along with baffling typos.
If required I can post lists of sample trinomials and cofactors, currently for prime r < 4096 (in 3 hrs), also all r < 1024 (in 12 mins).
Fred Lunnon
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
Dear Joerg, Thanks for comprehensive list of references! As it happens, Richard Schroeppel already had come up with a one-liner, which I had to program before I understood it: Consider set { (z^s, z^s + 1) } where z generates F* and s in |N ; some coincidence z^s = z^t + 1 occurs since both columns permute F* . Fred // Rich Schroeppel's proof of redundant trinomial existence! (Magma) q := 2^8; FF<z> := FiniteField(q); FF2 := FiniteField(2); PR<X> := PolynomialRing(FF2); trip := [ < s, z^s, z^s + 1 > : s in [1..#FF-2] ]; //trip; exists(s, t){ <s, t> : s in [1..#FF-2], t in [1..#FF-2] | trip[s][2] eq trip[t][3] }; X^s + X^t + 1; // X^25 + X + 1 ; On 7/8/18, Joerg Arndt <arndt@jjj.de> wrote:
The answer may well be found somewhere in the bible: Rudolf Lidl, Harald Niederreiter: {Finite fields}, Cambridge University Press, second edition, (1997).
The kid's version may be sufficient in this case: Rudolf Lidl, Harald Niederreiter: {Introduction to finite fields and their applications}, Cambridge University Press, revised edition, (1994).
%%%% THIS ONE %%%% may be pertinent: Solomon W.\ Golomb, Pey-Feng Lee: {Irreducible Polynomials Which Divide Trinomials over $\GF(2)$}, %IEEE Transactions on Information Theory, vol.~53, no.~2, pp.~768-774, \bdate{February-2007}.} %% Theorem 7 (Welch s Criterion): For any odd integer t, the irreducible polynomials %% of primitivity t divide trinomials iff gcd( 1 + x^n, 1 + (1+x)^n ) has degree greater than 1. %% Cf. A261524
Some papers about trinomials (raw copy from my bib-file):
{Ian F.\ Blake, Shuhong Gao, Robert J.\ Lambert: {Construction and Distribution Problems for Irreducible Trinomials over Finite Fields}, In: D.\ Gollmann, (ed.): {Applications of finite fields}, pp.~19-32, \bdate{1996}.
Richard P.\ Brent: {Primitive and Almost Primitive Trinomials}, %\bdate{3-May-2002}.}
Richard P.\ Brent: {All You Wanted to Know about Irreducible and Primitive Trinomials}, %Oxford Supercomputer Centre Mini-Conference, \bdate{1-July-2003}.
Richard P.\ Brent, Paul Zimmermann: {Algorithms for finding almost irreducible and almost primitive trinomials}, in: Primes and Misdemeanours: Lectures in Honour of the Sixtieth Birthday of Hugh Cowie Williams, Fields Institute Communication FIC/41, The Fields Institute, Toronto, pp.~91-102, \bdate{2004}.
Mathieu Ciet, Jean-Jacques Quisquater, Francesco Sica: {A Short Note on Irreducible Trinomials in Binary Fields}, in: {23rd Symposium on Information Theory in the BENELUX}, Louvain-la-Neuve, Belgium, Macq, B., Quisquater, J.-J. (eds.), pp.~233-234, \bdate{May-2002}. URL: \url{http://www.uclouvain.be/crypto/publications/year/2002}.}% OK
Harold M.\ Fredricksen, R.\ Wisniewski: {On trinomials $x^n+x^2+1$ and $x^{8l\pm{}3}+x^k+1$ irreducible over $\GF(2)$}, %Information and Control, vol.~50, no,1, pp.~58-63, \bdate{July-1981}.}
Ryul Kim, Wolfram Koepf: {Divisibility of Trinomials by Irreducible Polynomials over $\FF_2$}, %arXiv:1311.1366 [math.RA], \bdate{6-November-2013}. %% Extends Welch's criterion (Welch is the special case a=b=1): %% Let f be an irreducible polynomial of order e and degree n over GF(2) and %% a and b be positive integers. Then f divides trinomials x^{am} + x^{bs} + 1 %% if and only if gcd(1 + x^{e1}, 1 + (1 + x)^{e2}) has degree greater than 1, %% where e1 = e / gcd(a,e) and e2 = e / gcd(b,e).
Ernst S.\ Selmer: {On the irreducibility of certain trinomials}, %Mathematica Scandinavica, vol.~4, pp.~ \bdate{1956}. %URL: \url{http://www.mscand.dk/issue.php?year=1956&volume=4&issue=}.} %% http://www.mscand.dk/article.php?id=1472
Uzi Vishne: {Factorization of Trinomials over Galois Fields of Characteristic 2}, %Finite Fields and Their Applications, vol.~3, no.~4, pp.~370-377, \bdate{1997}. %URL: \url{http://www.math.biu.ac.il/~vishne/publications.html}.} %% extension of Swan's theorems
And there is always Solomon W.\ Golomb: {Shift Register Sequences}, %Holden-Day, \bdate{1967}.}
Trinomially yours, jj
P.S.: I can send electronic versions of most (or all) of the above.
* Fred Lunnon <fred.lunnon@gmail.com> [Jun 10. 2018 07:51]:
I need an existence proof --- it's the missing link in a theorem establishing full-plane integer zero-free number walls over finite characteristic ( |F_2 excepted).
CONJECTURE: Given any r > 1 , there exists over |F_2 a trinomial f(X) = X^s + X^t + 1 = g(X) h(X) , where g(X) is irreducible of degree r .
This topic turns out to have been studied previously, since it is of interest in elliptic curve public-key cryptography. Such "redundant trinomials" are used to do arithmetic in binary finite fields |F^(2^r) lacking a trinomial generating polynomial: the idea is to calculate instead in a larger ring using trinomial f(X) with factor some field generator g(X) , afterwards reducing the result to the field.
Of course, engineers don't care greatly about proving that such a trinomial exists for every field degree: they're just content that some have been found for every degree up to 10,000, comfortably exceeding anything currently required.
I haven't uncovered a great deal about this in the literature:
Christophe Doche (2005) <doche@ics.mq.edu.au> "Redundant Trinomials for Finite Fields of Characteristic 2 " http://web.science.mq.edu.au/~doche/redundant.pdf is cited by most of the rest;
Ryul Kim, Wolfram Koepf <koepf@mathematik.uni-kassel.de> "Divisibility of Trinomials by Irreducible Polynomials over |F_2 " https://arxiv.org/pdf/1311.1366.pdf includes results about cofactor h(X) , along with baffling typos.
If required I can post lists of sample trinomials and cofactors, currently for prime r < 4096 (in 3 hrs), also all r < 1024 (in 12 mins).
Fred Lunnon
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
participants (2)
-
Fred Lunnon -
Joerg Arndt