article

On the deterministic complexity of factoring polynomials over finite fields

Author:

V. ShoupAuthors Info & Claims

Information Processing Letters, Volume 33, Issue 5

Pages 261 - 267

https://doi.org/10.1016/0020-0190(90)90195-4

Published: 10 January 1990 Publication History

Abstract

No abstract available.

Cited By

View all

Kuang RPerepechaenko MToth RBarbeau M(2022)Benchmark Performance of the Multivariate Polynomial Public Key Encapsulation MechanismRisks and Security of Internet and Systems10.1007/978-3-031-31108-6_18(239-255)Online publication date: 7-Dec-2022
https://dl.acm.org/doi/10.1007/978-3-031-31108-6_18
Dutta PRajasree M(2022)Algebraic Algorithms for Variants of Subset SumAlgorithms and Discrete Applied Mathematics10.1007/978-3-030-95018-7_19(237-251)Online publication date: 10-Feb-2022
https://dl.acm.org/doi/10.1007/978-3-030-95018-7_19
Harvey Dvan der Hoeven J(2019)Faster polynomial multiplication over finite fields using cyclotomic coefficient ringsJournal of Complexity10.1016/j.jco.2019.03.00454:COnline publication date: 1-Oct-2019
https://dl.acm.org/doi/10.1016/j.jco.2019.03.004
Show More Cited By

Index Terms

On the deterministic complexity of factoring polynomials over finite fields
1. Mathematics of computing
  1. Mathematical analysis
    1. Numerical analysis
      1. Computations on polynomials
      2. Number-theoretic computations

Recommendations

Factoring polynomials over finite fields
SFCS '87: Proceedings of the 28th Annual Symposium on Foundations of Computer Science

We propose a new deterministic method of factoring polynomials over finite fields. Assuming the Generalized Riemann Hypothesis (GRH), we obtain, in polynomial time, the factorization of any polynomial with a bounded number of irreducible factors. Other ...
On the complexity of factoring bivariate supersparse (Lacunary) polynomials
ISSAC '05: Proceedings of the 2005 international symposium on Symbolic and algebraic computation

We present algorithms that compute the linear and quadratic factors of supersparse (lacunary) bivariate polynomials over the rational numbers in polynomial-time in the input size. In supersparse polynomials, the term degrees can have hundreds of digits ...
On the complexity of factoring polynomials with integer coefficients

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

Information Processing Letters Volume 33, Issue 5

January 1990

51 pages

ISSN:0020-0190

Editor:
S. G. Aki
Queen's Univ., Kingston, Canada

Issue’s Table of Contents

Publisher

Elsevier North-Holland, Inc.

United States

Publication History

Published: 10 January 1990

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

15
Total Citations
View Citations
0
Total Downloads

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

Reflects downloads up to 18 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

View all

Kuang RPerepechaenko MToth RBarbeau M(2022)Benchmark Performance of the Multivariate Polynomial Public Key Encapsulation MechanismRisks and Security of Internet and Systems10.1007/978-3-031-31108-6_18(239-255)Online publication date: 7-Dec-2022
https://dl.acm.org/doi/10.1007/978-3-031-31108-6_18
Dutta PRajasree M(2022)Algebraic Algorithms for Variants of Subset SumAlgorithms and Discrete Applied Mathematics10.1007/978-3-030-95018-7_19(237-251)Online publication date: 10-Feb-2022
https://dl.acm.org/doi/10.1007/978-3-030-95018-7_19
Harvey Dvan der Hoeven J(2019)Faster polynomial multiplication over finite fields using cyclotomic coefficient ringsJournal of Complexity10.1016/j.jco.2019.03.00454:COnline publication date: 1-Oct-2019
https://dl.acm.org/doi/10.1016/j.jco.2019.03.004
Grenet BHoeven JLecerf G(2016)Deterministic root finding over finite fields using Graeffe transformsApplicable Algebra in Engineering, Communication and Computing10.1007/s00200-015-0280-527:3(237-257)Online publication date: 1-Jun-2016
https://dl.acm.org/doi/10.1007/s00200-015-0280-5
Phan DPointcheval DShahandashti SStrefler M(2013)Adaptive CCA broadcast encryption with constant-size secret keys and ciphertextsInternational Journal of Information Security10.1007/s10207-013-0190-012:4(251-265)Online publication date: 1-Aug-2013
https://dl.acm.org/doi/10.1007/s10207-013-0190-0
Harasawa RSueyoshi YKudo A(2012)Improving the berlekamp algorithm for binomials x-aProceedings of the 4th international conference on Arithmetic of Finite Fields10.1007/978-3-642-31662-3_16(225-235)Online publication date: 16-Jul-2012
https://dl.acm.org/doi/10.1007/978-3-642-31662-3_16
Petit CLauter KQuisquater J(2008)Full Cryptanalysis of LPS and Morgenstern Hash FunctionsProceedings of the 6th international conference on Security and Cryptography for Networks10.1007/978-3-540-85855-3_18(263-277)Online publication date: 10-Sep-2008
https://dl.acm.org/doi/10.1007/978-3-540-85855-3_18
von zur Gathen JPanario D(2001)Factoring Polynomials Over Finite FieldsJournal of Symbolic Computation10.5555/2791618.279218831:1(3-17)Online publication date: 1-Jan-2001
https://dl.acm.org/doi/10.5555/2791618.2792188
Flajolet PGourdon XPanario D(2001)The Complete Analysis of a Polynomial Factorization Algorithm over Finite FieldsJournal of Algorithms10.1006/jagm.2001.115840:1(37-81)Online publication date: 23-Jul-2001
https://dl.acm.org/doi/10.1006/jagm.2001.1158
Kaltofen EShoup VLeighton FBorodin A(1995)Subquadratic-time factoring of polynomials over finite fieldsProceedings of the twenty-seventh annual ACM symposium on Theory of computing10.1145/225058.225166(398-406)Online publication date: 29-May-1995
https://dl.acm.org/doi/10.1145/225058.225166
Show More Cited By

Abstract

Cited By

Index Terms

Recommendations

Factoring polynomials over finite fields

On the complexity of factoring bivariate supersparse (Lacunary) polynomials

On the complexity of factoring polynomials with integer coefficients

Comments

Information

Published In

Publisher

Publication History

Qualifiers

Contributors

Other Metrics

Bibliometrics

Article Metrics

Other Metrics

Citations

Cited By

View options

Figures

Other

Share

Share this Publication link

Share on social media

Affiliations