Article

Free access

Efficient computation of minimal polynomials in algebraic extensions of finite fields

Author:

Victor ShoupAuthors Info & Claims

ISSAC '99: Proceedings of the 1999 international symposium on Symbolic and algebraic computation

Pages 53 - 58

https://doi.org/10.1145/309831.309859

Published: 01 July 1999 Publication History

PDF eReader

References

[1]

BRENT, R. P., GUSTAVSON, F. G., AND YUN, D. Y. Y. Fast solution of Toeplitz systems of equations and computation of Pad4 approximants. J. Algorithms i (1980), 259-295.

Google Scholar

[2]

BRENT, R. P., AND KUNG, H. T. Faust algorithms fbr manipulating formal power series. J. Assoc. Comput. Mach. 25 (1978), 581 595.

Digital Library

Google Scholar

[3]

GORDON, J. Very simple inettlod to find the minimal polynomial of an arbitrary non-zero element of a finite field. Electronic Letters 12 (1976), 663-664.

Crossref

Google Scholar

[4]

KALToFEN, E. Challenges of symbolic computation: my favorite open problems. Preprint, 1998.

Google Scholar

[5]

KAMINSKI, M., KIRKPATRICK, D. G., AND BSHOUTY, N. H. Addition requirements for matrix and transposed matrix products. Journal of Algorithms 9 (1988), 354- 364.

Digital Library

Google Scholar

[6]

MASSEY, J. Shift-register synthesis and BCH coding. IEEE Trans. Inf. Theory IT-15 (1969), 122-127.

Crossref

Google Scholar

[7]

SHOUP, V. A fast deterministic algorithm for factoring polynomials over finite fields of small characteristic. In Proc. Int. Syrup. on Symbolic and Algebraic Comp. (1991), pp. 14-21.

Digital Library

Google Scholar

[8]

SHOUP, V. Fast construction of irreducible polynomials over finite fields. 3. Symbolic Comp. 17, 5 (1994), 371- 391.

Digital Library

Google Scholar

[9]

SHOUP, V. A new polynomial factorization algorithm and its implementation. J. Symbolic Comp. 20, 4 (1995), 363-397.

Digital Library

Google Scholar

[10]

YON ZUR GATItEN, J., AND SHOUP, V. Computing Frobenius maps and factoring polynomials. Computational Complexity 2 (1992), 187-224.

Crossref

Google Scholar

[11]

WIEDEMANN, D. Solving sparse lineax systems over finite fields. IEEE Trans. Inf. Theory IT-32 (1986), 54-62.

Digital Library

Google Scholar

Cited By

View all

Hwang V(2024)A Survey of Polynomial Multiplications for Lattice-Based CryptosystemsIACR Communications in Cryptology10.62056/a0ivr-10kOnline publication date: 8-Jul-2024
https://doi.org/10.62056/a0ivr-10k
Neiger VSalvy BSchost ÉVillard G(2024)Faster Modular CompositionJournal of the ACM10.1145/363834971:2(1-79)Online publication date: 10-Apr-2024
https://dl.acm.org/doi/10.1145/3638349
Eriksen JPanny LSotáková JVeroni M(2024)Deuring for the people: Supersingular elliptic curves with prescribed endomorphism ring in general characteristicLuCaNT: LMFDB, Computation, and Number Theory10.1090/conm/796/16008(339-373)Online publication date: 2024
https://doi.org/10.1090/conm/796/16008
Show More Cited By

Index Terms

Efficient computation of minimal polynomials in algebraic extensions of finite fields
1. Mathematics of computing
  1. Mathematical analysis
    1. Numerical analysis
      1. Computations on matrices
      2. Computations on polynomials
2. Theory of computation
  1. Logic
    1. Type theory

Recommendations

Finding small degree factors of multivariate supersparse (lacunary) polynomials over algebraic number fields
ISSAC '06: Proceedings of the 2006 international symposium on Symbolic and algebraic computation

We present algorithms that compute all irreducible factors of degree ≤ d of supersparse (lacunary) multivariate polynomials in n variables over an algebraic number field in deterministic polynomial-time in (l+d)ⁿ, where l is the size of the input ...
Power sums of polynomials over finite fields and applications

In this brief expository survey, we explain some results and conjectures on various aspects of the study of the sums of integral powers of monic polynomials of a given degree over a finite field. The aspects include non-vanishing criteria, formulas and ...
Factoring multivariate polynomials over algebraic number fields in MACSYMA

The algorithm for factoring polynomials over the integers by Wang and Rothschild is generalized to an algorithm for the irreducible factorization of multivariate polynomials over any given algebraic number field. The extended method makes use of recent ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

ISSAC '99: Proceedings of the 1999 international symposium on Symbolic and algebraic computation

July 1999

314 pages

ISBN:1581130732

DOI:10.1145/309831

Chairmen:
Keith Geddes
Univ. of Waterloo, Waterloo, Ont., Canada
,
Bruno Salvy
INRIA Rocquencourt, France
,
Editor:
Sam Dooley
IBM Research, Yorktown Heights, NY

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]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 01 July 1999

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Qualifiers

Article

Conference

ISSAC99

Sponsor:

ISSAC99: International Symposium on Symbolic and Algebraic Computation

July 28 - 31, 1999

British Columbia, Vancouver, Canada

Acceptance Rates

Overall Acceptance Rate 395 of 838 submissions, 47%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

34
Total Citations
View Citations
475
Total Downloads

Downloads (Last 12 months)40
Downloads (Last 6 weeks)5

Reflects downloads up to 18 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

View all

Hwang V(2024)A Survey of Polynomial Multiplications for Lattice-Based CryptosystemsIACR Communications in Cryptology10.62056/a0ivr-10kOnline publication date: 8-Jul-2024
https://doi.org/10.62056/a0ivr-10k
Neiger VSalvy BSchost ÉVillard G(2024)Faster Modular CompositionJournal of the ACM10.1145/363834971:2(1-79)Online publication date: 10-Apr-2024
https://dl.acm.org/doi/10.1145/3638349
Eriksen JPanny LSotáková JVeroni M(2024)Deuring for the people: Supersingular elliptic curves with prescribed endomorphism ring in general characteristicLuCaNT: LMFDB, Computation, and Number Theory10.1090/conm/796/16008(339-373)Online publication date: 2024
https://doi.org/10.1090/conm/796/16008
Villard G(2024)Bivariate polynomial reduction and elimination ideal over finite fieldsJournal of Symbolic Computation10.1016/j.jsc.2024.102367(102367)Online publication date: Jul-2024
https://doi.org/10.1016/j.jsc.2024.102367
Corte-Real Santos MEriksen JMeyer MReijnders K(2024)AprèsSQI: Extra Fast Verification for SQIsign Using Extension-Field SigningAdvances in Cryptology – EUROCRYPT 202410.1007/978-3-031-58716-0_3(63-93)Online publication date: 29-Apr-2024
https://doi.org/10.1007/978-3-031-58716-0_3
Abelard SBerardini ECouvreur ALecerf G(2022)Computing Riemann–Roch spaces via Puiseux expansionsJournal of Complexity10.1016/j.jco.2022.101666(101666)Online publication date: Apr-2022
https://doi.org/10.1016/j.jco.2022.101666
Abelard SCouvreur ALecerf G(2022)Efficient computation of Riemann–Roch spaces for plane curves with ordinary singularitiesApplicable Algebra in Engineering, Communication and Computing10.1007/s00200-022-00588-x35:6(739-804)Online publication date: 1-Dec-2022
https://doi.org/10.1007/s00200-022-00588-x
Bois ACascudo IFiore DKim D(2021)Flexible and Efficient Verifiable Computation on Encrypted DataPublic-Key Cryptography – PKC 202110.1007/978-3-030-75248-4_19(528-558)Online publication date: 1-May-2021
https://doi.org/10.1007/978-3-030-75248-4_19
Deryabin MChervyakov NTchernykh ABerezhnoy VDjurabaev ANazarov ABabenko M(2019)Comparative Performance Analysis of Information Dispersal MethodsProceedings of the 24th Conference of Open Innovations Association FRUCT10.5555/3338290.3338300(67-74)Online publication date: 15-Apr-2019
https://dl.acm.org/doi/10.5555/3338290.3338300
Deryabin MChervyakov NTchernykh ABerezhnoy VDjurabaev ANazarov ABabenko M(2019)Comparative Performance Analysis of Information Dispersal Methods2019 24th Conference of Open Innovations Association (FRUCT)10.23919/FRUCT.2019.8711955(67-74)Online publication date: Apr-2019
https://doi.org/10.23919/FRUCT.2019.8711955
Show More Cited By

View Options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Login options

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

Cited By

Index Terms

Recommendations

Finding small degree factors of multivariate supersparse (lacunary) polynomials over algebraic number fields

Power sums of polynomials over finite fields and applications

Factoring multivariate polynomials over algebraic number fields in MACSYMA