More Web Proxy on the site http://driver.im/

research-article

Composition collisions and projective polynomials: statement of results

Authors:

Joachim von zur Gathen,

Mark Giesbrecht,

Konstantin ZieglerAuthors Info & Claims

ISSAC '10: Proceedings of the 2010 International Symposium on Symbolic and Algebraic Computation

Pages 123 - 130

https://doi.org/10.1145/1837934.1837962

Published: 25 July 2010 Publication History

Abstract

The functional decomposition of polynomials has been a topic of great interest and importance in pure and computer algebra and their applications. The structure of compositions of (suitably normalized) polynomials f = g o h in F_q[x] is well understood in many cases, but quite poorly when the degrees of both components are divisible by the characteristic p. This work investigates the decomposition of polynomials whose degree is a power of p. An (equal-degree) i-collision is a set of i distinct pairs (g, h) of polynomials, all with the same composition and deg g the same for all (g, h). Abhyankar (1997) introduced the projective polynomials xⁿ+ ax + b, where n is of the form (r^m -- 1)/(r -- 1) and r is a power of p. Our first tool is a bijective correspondence between i-collisions of certain additive trinomials, projective polynomials with i roots, and linear spaces with i Frobenius-invariant lines.

Bluher (2004b) has determined the possible number of roots of projective polynomials for m = 2, and how many polynomials there are with a prescribed number of roots. We generalize her first result to arbitrary m, and provide an alternative proof of her second result via elementary linear algebra.

If one of our additive trinomials is given, we can efficiently compute the number of its decompositions, and similarly the number of roots of a projective polynomial. The runtime of these algorithms depends polynomially on the sparse input size, and thus on the input degree only logarithmically.

For non-additive polynomials, we present certain decompositions and conjecture that these comprise all of the prescribed shape.

References

[1]

Shreeram S. Abhyankar. Projective Polynomials. Proceedings of the American Mathematical Society, 125(6):1643--1650, 1997. ISSN 00029939. URL http://www.jstor.org/stable/2162203.

[2]

Leonard M. Adleman & Hendrik W. Lenstra, Jr. Finding Irreducible Polynomials over Finite Fields. In Proceedings of the Eighteenth Annual ACM Symposium on Theory of Computing, Berkeley CA, pages 350--355. ACM Press, 1986.

Digital Library

[3]

David R. Barton & Richard Zippel. Polynomial Decomposition Algorithms. Journal of Symbolic Computation, 1:159--168, 1985.

Digital Library

[4]

Antonia W. Bluher. On x ⁶ + x + a in Characteristic Three. Designs, Codes and Cryptography, 30:85--95, 2003. URL http://www.springerlink.com/content/r213567443r63360/fulltext.pdf.

Digital Library

[5]

Antonia W. Bluher. Explicit formulas for strong Davenport pairs. Acta Arithmetica, 112(4):397--403, 2004a.

[6]

Antonia W. Bluher. On x^q+1 + ax + b. Finite Fields and Their Applications, 10(3):285--305, 2004b. URL http://dx.doi.org/10.1016/j.ffa.2003.08.004.

Digital Library

[7]

Antonia W. Bluher & Alain Lasjaunias. Hyperquadratic power series of degree four. Acta Arithmetica, 124(3):257--268, 2006.

[8]

John J. Cade. A New Public-key Cipher Which Allows Signatures. In Proceedings of the 2nd SIAM Conference on Applied Linear Algebra, Raleigh NC A11. SIAM, 1985.

[9]

J. F. Dillon. Geometry, codes and difference sets: exceptional connections. In Codes and designs (Columbus, OH, 2000), volume 10 of Ohio State Univ. Math. Res. Inst. Publ., pages 73--85. de Gruyter, Berlin, 2002. URL http://dx.doi.org/10.1515/9783110198119.73.

[10]

F. Dorey & G. Whaples. Prime and Composite Polynomials. Journal of Algebra, 28:88--101, 1974. URL http://dx.doi.org/10.1016/0021-8693(74)90023-4.

[11]

Joachim von zur Gathen. Functional Decomposition of Polynomials: the Tame Case. Journal of Symbolic Computation, 9:281--299, 1990a. URL http://dx.doi.org/10.1016/S0747-7171(08)80014-4.

Digital Library

[12]

Joachim von zur Gathen. Functional Decomposition of Polynomials: the Wild Case. Journal of Symbolic Computation, 10:437--452, 1990b. URL http://dx.doi.org/10.1016/S0747-7171(08)80054-5.

Digital Library

[13]

Joachim von zur Gathen. Counting decomposable univariate polynomials. Preprint, 92 pages, 2008. URL http://arxiv.org/abs/0901.0054.

[14]

Joachim von zur Gathen. An algorithm for decomposing univariate wild polynomials. Journal of Symbolic Computation, to appear, 32 pages, 2010.

[15]

Joachim von zur Gathen. The Number of Decomposable Univariate Polynomials. In John P. May, editor, Proceedings of the 2009 International Symposium on Symbolic and Algebraic Computation ISSAC2009, Seoul, Korea, pages 359--366. 2009. ISBN 978-1-60558-609-0.

Digital Library

[16]

Joachim von zur Gathen, Mark Giesbrecht & Konstantin Ziegler. Composition collisions and projective polynomials, 2010. URL http://arxiv.org/abs/1005.1087.

Digital Library

[17]

Mark William Giesbrecht. Complexity Results on the Functional Decomposition of Polynomials. Technical Report 209/88, University of Toronto, Department of Computer Science, Toronto, Ontario, Canada, 1988. Available as http://arxiv.org/abs/1004.5433.

[18]

Mark Giesbrecht. Nearly Optimal Algorithms for Canonical Matrix Forms. SIAM J. Comp., 24:948--969, 1995.

Digital Library

[19]

Mark Giesbrecht. Factoring in Skew-Polynomial Rings over Finite Fields. Journal of Symbolic Computation, 26(4):463--486, 1998. URL http://dx.doi.org/10.1006/jsco.1998.0224.

Digital Library

[20]

G. H. Hardy & S. Ramanujan. Asymptotic formulae in combinatory analysis. Proceedings of the London Mathematical Society, 17(2):75--115, 1918.

[21]

Tor Helleseth & Alexander Kholosha. x² ^l+¹ + x + a and related affine polynomials over GF(2 ^k). Cryptography and Communications, 2(1):85--109, 2010.

[22]

Tor Helleseth, Alexander Kholosha & Aina Johanssen. m-Sequences of Different Lengths with Four-Valued Cross Correlation. IEEE International Symposium on Information Theory, 2008.

[23]

Dexter Kozen & Susan Landau. Polynomial Decomposition Algorithms. Journal of Symbolic Computation, 7:445--456, 1989. An earlier version was published as Technical Report 86--773, Department of Computer Science, Cornell University, Ithaca NY, 1986.

Digital Library

[24]

S. Landau & G. L. Miller. Solvability by Radicals is in Polynomial Time. Journal of Computer and System Sciences, 30:179--208, 1985.

[25]

Rudolf Lidl & Harald Niederreiter. Finite Fields. Number 20 in Encyclopedia of Mathematics and its Applications. Addison-Wesley, Reading MA, 1983.

[26]

Robert Winston Keith Odoni. On additive polynomials over a finite field. Proceedings of the Edinburgh Mathematical Society, 42:1--16, 1999.

[27]

O. Ore. On a Special Class of Polynomials. Transactions of the American Mathematical Society, 35:559--584, 1933.

[28]

Andrzej Schinzel. Selected Topics on Polynomials. Ann Arbor; The University of Michigan Press, 1982. ISBN 0-472-08026-1.

[29]

Andrzej Schinzel. Polynomials with special regard to reducibility. Cambridge University Press, Cambridge, UK, 2000. ISBN 0521662257.

[30]

Xiangyong Zeng, Nian Li & Lei Hu. A class of nonbinary codes and their weight distribution. ArXiv e-prints, arxiv 0802.3430v1, 2008. URL http://arxiv.org/PS_cache/arxiv/pdf/0802/0802.3430v1.pdf.

[31]

Richard Zippel. Rational Function Decomposition. In Stephen M. Watt, editor, Proceedings of the 1991 International Symposium on Symbolic and Algebraic Computation ISSAC '91, Bonn, Germany, pages 1--6. ACM Press, Bonn, Germany, 1991. ISBN 0-89791-437-6.

Digital Library

Cited By

Caruso XLe Borgne J(2017)A new faster algorithm for factoring skew polynomials over finite fieldsJournal of Symbolic Computation10.1016/j.jsc.2016.02.01679:P2(411-443)Online publication date: 1-Mar-2017
https://dl.acm.org/doi/10.1016/j.jsc.2016.02.016
Blankertz R(2014)A polynomial time algorithm for computing all minimal decompositions of a polynomialACM Communications in Computer Algebra10.1145/2644288.264429248:1/2(13-23)Online publication date: 10-Jul-2014
https://dl.acm.org/doi/10.1145/2644288.2644292
Von Zur Gathen J(2013)Lower bounds for decomposable univariate wild polynomialsJournal of Symbolic Computation10.1016/j.jsc.2011.01.00850(409-430)Online publication date: 1-Mar-2013
https://dl.acm.org/doi/10.1016/j.jsc.2011.01.008
Show More Cited By

Index Terms

Composition collisions and projective polynomials: statement of results
1. Mathematics of computing
  1. Mathematical analysis
    1. Numerical analysis
      1. Computations on polynomials

Recommendations

Tame decompositions and collisions
ISSAC '14: Proceedings of the 39th International Symposium on Symbolic and Algebraic Computation

A univariate polynomial f over a field is decomposable if f = g o h = g(h) for nonlinear polynomials g and h. It is intuitively clear that the decomposable polynomials form a small minority among all polynomials over a finite field. The tame case, where ...
Factorization of a class of composed polynomials
Abstract
In this paper, we provide the degree distribution of irreducible factors of the composed polynomial f(L(x)) over $$\mathbb {F}_q$$, where $$f(x)\in \mathbb {F}_q[x]$$ is irreducible and $$L(x)\in \mathbb {F}_q[x]$$ is a linearized polynomial. We ...
r-fat linearized polynomials over finite fields
Abstract
r-fat polynomials are a natural generalization of scattered polynomials. They define linear sets of the projective line PG ( 1 , q n ) of rank n with r points of weight larger than one. Using techniques on algebraic ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Other conferences

ISSAC '10: Proceedings of the 2010 International Symposium on Symbolic and Algebraic Computation

July 2010

366 pages

ISBN:9781450301503

DOI:10.1145/1837934

Program Chair:
Wolfram Koepf
London, Ontario, Canada

Copyright © 2010 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

Gesellschaft fur Informtatik

In-Cooperation

SIGSAM: ACM Special Interest Group on Symbolic and Algebraic Manipulation

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 25 July 2010

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Conference

ISSAC '10

Sponsor:

ISSAC '10: International Symposium on Symbolic and Algebraic Computation

July 25 - 28, 2010

Munich, Germany

Acceptance Rates

ISSAC '10 Paper Acceptance Rate 45 of 110 submissions, 41%;

Overall Acceptance Rate 395 of 838 submissions, 47%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

6
Total Citations
View Citations
138
Total Downloads

Downloads (Last 12 months)1
Downloads (Last 6 weeks)0

Reflects downloads up to 09 Mar 2025

Other Metrics

View Author Metrics

Citations

Cited By

Caruso XLe Borgne J(2017)A new faster algorithm for factoring skew polynomials over finite fieldsJournal of Symbolic Computation10.1016/j.jsc.2016.02.01679:P2(411-443)Online publication date: 1-Mar-2017
https://dl.acm.org/doi/10.1016/j.jsc.2016.02.016
Blankertz R(2014)A polynomial time algorithm for computing all minimal decompositions of a polynomialACM Communications in Computer Algebra10.1145/2644288.264429248:1/2(13-23)Online publication date: 10-Jul-2014
https://dl.acm.org/doi/10.1145/2644288.2644292
Von Zur Gathen J(2013)Lower bounds for decomposable univariate wild polynomialsJournal of Symbolic Computation10.1016/j.jsc.2011.01.00850(409-430)Online publication date: 1-Mar-2013
https://dl.acm.org/doi/10.1016/j.jsc.2011.01.008
Blankertz Rvon zur Gathen JZiegler Kvan der Hoeven Jvan Hoeij M(2012)Compositions and collisions at degree p2Proceedings of the 37th International Symposium on Symbolic and Algebraic Computation10.1145/2442829.2442846(91-98)Online publication date: 22-Jul-2012
https://dl.acm.org/doi/10.1145/2442829.2442846
von zur Gathen J(2011)Counting decomposable multivariate polynomialsApplicable Algebra in Engineering, Communication and Computing10.1007/s00200-011-0141-922:3(165-185)Online publication date: 7-May-2011
https://doi.org/10.1007/s00200-011-0141-9
von zur Gathen JGiesbrecht MZiegler KKoepf W(2010)Composition collisions and projective polynomialsProceedings of the 2010 International Symposium on Symbolic and Algebraic Computation10.1145/1837934.1837962(123-130)Online publication date: 25-Jul-2010
https://dl.acm.org/doi/10.1145/1837934.1837962

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Figures

Tables

Media

View Table of Conten