Skip to main content
Fachgebiete
Automobil + Motoren Bauwesen + Immobilien Business IT + Informatik Elektrotechnik + Elektronik Energie + Nachhaltigkeit Finance + Banking Management + Führung Marketing + Vertrieb Maschinenbau + Werkstoffe Versicherung + Risiko
DE
EN
Themenseiten
Organisationspsychologie Projektmanagement Marketing Smart Manufacturing
Bücher
Zeitschriften
Weitere Formate
Podcasts Webinare Technik Webinare Wirtschaft Kongresse Veranstaltungskalender Awards
Jetzt Einzelzugang starten
Zugang für Unternehmen
Referenzkunden
MTZ-Fachkongress

Antriebe und Energiesysteme von morgen


Austausch von Automobil- und Energiewirtschaft

Am 14./15. Mai geht es in Chemnitz um die Mobilitätswende durch Elektro- und Wasserstofffahrzeuge.
Erweiterte Suche
Anmelden
nach oben
Applicable Algebra in Engineering, Communication and Computing
Erschienen in: Applicable Algebra in Engineering, Communication and Computing 2/2024

03.01.2022 | Original Paper

Univariate polynomial factorization over finite fields with large extension degree

verfasst von: Joris van der Hoeven, Grégoire Lecerf

Erschienen in: Applicable Algebra in Engineering, Communication and Computing | Ausgabe 2/2024

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config
loading …

Abstract

The best known asymptotic bit complexity bound for factoring univariate polynomials over finite fields grows with \(d^{1.5 + o (1)}\) for input polynomials of degree d, and with the square of the bit size of the ground field. It relies on a variant of the Cantor–Zassenhaus algorithm which exploits fast modular composition. Using techniques by Kaltofen and Shoup, we prove a refinement of this bound when the finite field has a large extension degree over its prime field. We also present fast practical algorithms for the case when the extension degree is smooth.
Vorheriger Artikel In memoriam Kai-Uwe Schmidt
Nächster Artikel -double cyclic codes with respect to the Hermitian inner product

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

  • über 102.000 Bücher
  • über 537 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Maschinenbau + Werkstoffe
  • Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 340 Zeitschriften

aus folgenden Fachgebieten:

  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Versicherung + Risiko




Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 390 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Maschinenbau + Werkstoffe




 

Jetzt Wissensvorsprung sichern!

Jetzt informieren
Literatur
1.
Ben-Or, M. Probabilistic algorithms in finite fields. In 22nd Annual Symposium on Foundations of Computer Science (SFCS 1981), pages 394–398. Los Alamitos, CA, USA, 1981. IEEE Computer Society
2.
3.
4.
Bostan, A., Chyzak, F., Giusti, M., Lebreton, R., Lecerf, G., Salvy, B. É. Schost.: Algorithmes Efficaces en Calcul Formel. Frédéric Chyzak (self-published), Palaiseau, 2017. Electronic version available from https://​hal.​archives-ouvertes.​fr/​AECF
5.
Cantor, D.G., Zassenhaus, H.: A new algorithm for factoring polynomials over finite fields. Math. Comput. 36(154), 587–592 (1981)MathSciNetCrossRef
6.
Flajolet, Ph., Gourdon, X., Panario, D.: The complete analysis of a polynomial factorization algorithm over finite fields. J. Algorithm. 40(1), 37–81 (2001)MathSciNetCrossRef
7.
Flajolet, P., Steyaert, J.-M.: A branching process arising in dynamic hashing, trie searching and polynomial factorization. In M. Nielsen and E. Schmidt, editors, Automata, Languages and Programming, volume 140 of Lect. Notes Comput. Sci., pages 239–251. Springer–Verlag, 1982
8.
von zur Gathen, J.: Who was who in polynomial factorization. In ISSAC’06: International Symposium on Symbolic and Algebraic Computation, pages 1–2. New York, NY, USA, 2006. ACM
9.
von zur Gathen, J., Gerhard, J.: Modern computer algebra. Cambridge University Press, New York (2013)CrossRef
10.
von zur Gathen, J., Seroussi, G.: Boolean circuits versus arithmetic circuits. Inf. Comput. 91(1), 142–154 (1991)MathSciNetCrossRef
11.
von zur Gathen, J., Shoup., V.: Computing Frobenius maps and factoring polynomials. Comput. Complex. 2(3), 187–224 (1992)MathSciNetCrossRef
12.
Guo, Z., Narayanan, A.K., Umans, C.: Algebraic problems equivalent to beating exponent 3/2 for polynomial factorization over finite fields. arXiv:​1606.​04592, 2016
13.
Harvey, D., van der Hoeven, J.: Faster polynomial multiplication over finite fields using cyclotomic coefficient rings. J. Complex. 54, 101404 (2019)MathSciNetCrossRef
14.
15.
van der Hoeven, J.: The Jolly Writer. Scypress, Your Guide to GNU TeXmacs (2020)
16.
17.
18.
van der Hoeven, J., Lecerf, G.: Fast multivariate multi-point evaluation revisited. J. Complex. 56, 101405 (2020)MathSciNetCrossRef
19.
20.
Hopcroft, J., Musinski, J.: Duality applied to the complexity of matrix multiplication and other bilinear forms. SIAM J. Comput. 2(3), 159–173 (1973)MathSciNetCrossRef
21.
Kaltofen,E.: Polynomial factorization: a success story. In ISSAC ’03: Proceedings of the 2003 International Symposium on Symbolic and Algebraic Computation, pages 3–4. New York, NY, USA, 2003. ACM
22.
Kaltofen, E., Shoup, V.: Subquadratic-time factoring of polynomials over finite fields. In Proceedings of the Twenty-Seventh Annual ACM Symposium on Theory of Computing, STOC ’95, pages 398–406. New York, NY, USA, 1995. ACM
23.
Kaltofen,E., Shoup, V.: Fast polynomial factorization over high algebraic extensions of finite fields. In Proceedings of the 1997 International Symposium on Symbolic and Algebraic Computation, ISSAC ’97, pages 184–188. New York, NY, USA, 1997. ACM
24.
Kaltofen, E., Shoup, V.: Subquadratic-time factoring of polynomials over finite fields. Math. Comput. 67(223), 1179–1197 (1998)ADSMathSciNetCrossRef
25.
Kedlaya, K.S., Umans, C.: Fast modular composition in any characteristic. In Proceedings of the 49th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2008), pages 146–155. Los Alamitos, CA, USA, 2008. IEEE Computer Society
26.
Kedlaya, K.S., Umans, C.: Fast polynomial factorization and modular composition. SIAM J. Comput. 40(6), 1767–1802 (2011)MathSciNetCrossRef
27.
Le Gall,F., Urrutia, F.: Improved rectangular matrix multiplication using powers of the Coppersmith–Winograd tensor. In A. Czumaj, editor, Proceedings of the 2018 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 1029–1046. Philadelphia, PA, USA, 2018. SIAM
28.
Lecerf, G.: Fast separable factorization and applications. Appl. Algebra Engrg. Comm. Comput. 19(2), 135–160 (2008)MathSciNetCrossRef
29.
Mullen, G.L., Panario. D.: Handbook of Finite Fields. Chapman and Hall/CRC, 2013
30.
Neiger, V., Rosenkilde, J., Solomatov, G.: Generic bivariate multi-point evaluation, interpolation and modular composition with precomputation. In A. Mantzaflaris, editor, Proceedings of the 45th International Symposium on Symbolic and Algebraic Computation, ISSAC ’20, pages 388–395. New York, NY, USA, 2020. ACM
31.
Paterson, M.S., Stockmeyer, L.J.: On the number of nonscalar multiplications necessary to evaluate polynomials. SIAM J. Comput. 2(1), 60–66 (1973)MathSciNetCrossRef
32.
Poteaux, A., Schost, É.: Modular composition modulo triangular sets and applications. Comput. Complex. 22(3), 463–516 (2013)MathSciNetCrossRef
33.
34.
Shoup, V.: Fast construction of irreducible polynomials over finite fields. J. Symbolic Comput. 17(5), 371–391 (1994)MathSciNetCrossRef
35.
Shoup, V.: A new polynomial factorization algorithm and its implementation. J. Symbolic Comput. 20(4), 363–397 (1995)MathSciNetCrossRef
36.
Shoup, V.: A Computational Introduction to Number Theory and Algebra. Cambridge University Press, 2nd edition, 2008
Metadaten
Titel
Univariate polynomial factorization over finite fields with large extension degree
verfasst von
Joris van der Hoeven
Grégoire Lecerf
Publikationsdatum
03.01.2022
Verlag
Springer Berlin Heidelberg
Erschienen in
Applicable Algebra in Engineering, Communication and Computing / Ausgabe 2/2024
Print ISSN: 0938-1279
Elektronische ISSN: 1432-0622
DOI
https://doi.org/10.1007/s00200-021-00536-1

Weitere Artikel der Ausgabe 2/2024

Applicable Algebra in Engineering, Communication and Computing 2/2024 Zur Ausgabe

Original Paper

Decision problem for a class of univariate Pfaffian functions

Original Paper

Distance-regular graphs and new block designs obtained from the Mathieu groups

Obituary

In memoriam Kai-Uwe Schmidt

Original Paper

Normal bases and factorization of in finite fields

Original Paper

On Kostant’s weight q-multiplicity formula for

Original Paper

-double cyclic codes with respect to the Hermitian inner product

Premium Partner

    Bildnachweise