research-article

Probabilistic Algorithms in Finite Fields

Author:

Michael O. RabinAuthors Info & Claims

SIAM Journal on Computing, Volume 9, Issue 2

Pages 273 - 280

https://doi.org/10.1137/0209024

Published: 01 May 1980 Publication History

Abstract

We present probabilistic algorithms for the problems of finding an irreducible polynomial of degree n over a finite field, finding roots of a polynomial, and factoring a polynomial into its irreducible factors over a finite field. All of these problems are of importance in algebraic coding theory, algebraic symbol manipulation, and number theory. These algorithms have a very transparent, easy to program structure. For finite fields of large characteristic p, so that exhaustive search through ${\text{Z}}_p $, is not feasible, our algorithms are of lower order in the degrees of the polynomial and fields in question, than previously published algorithms.

References

[1]

A. V. Aho, J. E. Hopcroft, J. D. Ullman, The Design and Analysis of Algorithms, Addison-Wesley, Reading, MA, 1974

Digital Library

Google Scholar

[2]

Elwyn R. Berlekamp, Algebraic coding theory, McGraw-Hill Book Co., New York, 1968xiv+466

Google Scholar

[3]

E. R. Berlekamp, Factoring polynomials over large finite fields, Math. Comp., 24 (1970), 713–735

Crossref

Google Scholar

[4]

A. Schonhage, Schnelle Multiplikation von Polynomen über Körpern der Charakteristik 2, Acta Informat., 7 (1976/77), 395–398

Digital Library

Google Scholar

Cited By

View all

Hoeven JLecerf G(2024)Univariate polynomial factorization over finite fields with large extension degreeApplicable Algebra in Engineering, Communication and Computing10.1007/s00200-021-00536-135:2(121-149)Online publication date: 1-Mar-2024
https://dl.acm.org/doi/10.1007/s00200-021-00536-1
Boneh DPartap ARotem L(2024)Traceable Secret Sharing: Strong Security and Efficient ConstructionsAdvances in Cryptology – CRYPTO 202410.1007/978-3-031-68388-6_9(221-256)Online publication date: 18-Aug-2024
https://dl.acm.org/doi/10.1007/978-3-031-68388-6_9
Lu GZhandry M(2024)Limits on the Power of Prime-Order Groups: Separating Q-Type from Static AssumptionsAdvances in Cryptology – CRYPTO 202410.1007/978-3-031-68388-6_3(46-74)Online publication date: 18-Aug-2024
https://dl.acm.org/doi/10.1007/978-3-031-68388-6_3
Show More Cited By

Index Terms

Probabilistic Algorithms in Finite Fields
1. Mathematics of computing
  1. Mathematical analysis
    1. Numerical analysis
      1. Computations in finite fields
      2. Computations on polynomials
  2. Probability and statistics
    1. Probabilistic reasoning algorithms
      1. Markov-chain Monte Carlo methods
      2. Sequential Monte Carlo methods
2. Theory of computation

Index terms have been assigned to the content through auto-classification.

Recommendations

Probabilistic algorithms for computing resultants
ISSAC '05: Proceedings of the 2005 international symposium on Symbolic and algebraic computation

Let A and B be two polynomials in ℤ [x,y] and let R = res_x(A,B) denote the resultant of A and B taken wrt x. In this paper we modify Collins' modular algorithm for computing R to make it output sensitive. The advantage of our algorithm is that it will ...
The number of roots of a lacunary bivariate polynomial on a line

We prove that a polynomial f@?R[x,y] with t non-zero terms, restricted to a real line y=ax+b, either has at most 6t-4 zeros or vanishes over the whole line. As a consequence, we derive an alternative algorithm for deciding whether a linear polynomial y-...
An effective description of the roots of bivariates mod pk and the related Igusa’s local zeta function
ISSAC '23: Proceedings of the 2023 International Symposium on Symbolic and Algebraic Computation

Finding roots of a bivariate polynomial f(x1, x2), over a prime field , is a fundamental question with a long history and several practical algorithms are now known. Effective algorithms for describing the roots modulo pk, k ≥ 2, for any general ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

SIAM Journal on Computing Volume 9, Issue 2

May 1980

221 pages

ISSN:0097-5397

DOI:10.1137/smjcat.1980.9.issue-2

Issue’s Table of Contents

Publisher

Society for Industrial and Applied Mathematics

United States

Publication History

Published: 01 May 1980

Author Tags

Qualifiers

Research-article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

10
Total Citations
View Citations
0
Total Downloads

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

Reflects downloads up to 31 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

View all

Hoeven JLecerf G(2024)Univariate polynomial factorization over finite fields with large extension degreeApplicable Algebra in Engineering, Communication and Computing10.1007/s00200-021-00536-135:2(121-149)Online publication date: 1-Mar-2024
https://dl.acm.org/doi/10.1007/s00200-021-00536-1
Boneh DPartap ARotem L(2024)Traceable Secret Sharing: Strong Security and Efficient ConstructionsAdvances in Cryptology – CRYPTO 202410.1007/978-3-031-68388-6_9(221-256)Online publication date: 18-Aug-2024
https://dl.acm.org/doi/10.1007/978-3-031-68388-6_9
Lu GZhandry M(2024)Limits on the Power of Prime-Order Groups: Separating Q-Type from Static AssumptionsAdvances in Cryptology – CRYPTO 202410.1007/978-3-031-68388-6_3(46-74)Online publication date: 18-Aug-2024
https://dl.acm.org/doi/10.1007/978-3-031-68388-6_3
Kalai YLombardi AVaikuntanathan V(2023)SNARGs and PPAD Hardness from the Decisional Diffie-Hellman AssumptionAdvances in Cryptology – EUROCRYPT 202310.1007/978-3-031-30617-4_16(470-498)Online publication date: 23-Apr-2023
https://dl.acm.org/doi/10.1007/978-3-031-30617-4_16
Rotem LSegev G(2020)Algebraic Distinguishers: From Discrete Logarithms to Decisional Uber AssumptionsTheory of Cryptography10.1007/978-3-030-64381-2_13(366-389)Online publication date: 16-Nov-2020
https://dl.acm.org/doi/10.1007/978-3-030-64381-2_13
Ball MChattopadhyay ELiao JMalkin TTan L(2020)Non-malleability Against Polynomial TamperingAdvances in Cryptology – CRYPTO 202010.1007/978-3-030-56877-1_4(97-126)Online publication date: 17-Aug-2020
https://dl.acm.org/doi/10.1007/978-3-030-56877-1_4
Hu JMonagan MAbramov SZima EGao X(2016)A Fast Parallel Sparse Polynomial GCD AlgorithmProceedings of the 2016 ACM International Symposium on Symbolic and Algebraic Computation10.1145/2930889.2930903(271-278)Online publication date: 20-Jul-2016
https://dl.acm.org/doi/10.1145/2930889.2930903
Grenet Bvan der Hoeven JLecerf GRobertz DLinton SYokoyama K(2015)Randomized Root Finding over Finite FFT-fields using Tangent Graeffe TransformsProceedings of the 2015 ACM International Symposium on Symbolic and Algebraic Computation10.1145/2755996.2756647(197-204)Online publication date: 24-Jun-2015
https://dl.acm.org/doi/10.1145/2755996.2756647
Sengupta ASaha DGhosh SMehta DChowdhury D(2014)AEC: A Practical Scheme for Authentication with Error CorrectionSecurity, Privacy, and Applied Cryptography Engineering10.1007/978-3-319-12060-7_11(155-170)Online publication date: 18-Oct-2014
https://dl.acm.org/doi/10.1007/978-3-319-12060-7_11
Javadi SMonagan M(2010)Parallel sparse polynomial interpolation over finite fieldsProceedings of the 4th International Workshop on Parallel and Symbolic Computation10.1145/1837210.1837233(160-168)Online publication date: 21-Jul-2010
https://dl.acm.org/doi/10.1145/1837210.1837233

Abstract

References

Cited By

Index Terms

Recommendations

Probabilistic algorithms for computing resultants

The number of roots of a lacunary bivariate polynomial on a line

An effective description of the roots of bivariates mod pk and the related Igusa’s local zeta function

Comments

Information

Published In

Publisher

Publication History

Author Tags

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