Efficient computation of minimal polynomials in algebraic extensions of finite fields

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Efficient computation of minimal polynomials in algebraic extensions of finite fields

Full text

Pdf (543 KB)

Source

International Conference on Symbolic and Algebraic Computation archive
Proceedings of the 1999 international symposium on Symbolic and algebraic computation table of contents

Vancouver, British Columbia, Canada

Pages: 53 - 58

Year of Publication: 1999

ISBN:1-58113-073-2

Author

Victor Shoup

IBM Zurich Research Lab, Säumerstr. 4, 8803 Rüschlikon, Switzerland

Sponsors

SIGSAM: ACM Special Interest Group on Symbolic and Algebraic Manipulation
SIGNUM: ACM Special Interest Group on Numerical Mathematics

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 6, Downloads (12 Months): 30, Citation Count: 8

Additional Information:

references cited by index terms collaborative colleagues

Tools and Actions:	Request Permissions Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/309831.309859 What is a DOI?

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked 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.
	2	R. P. Brent , H. T. Kung, Fast Algorithms for Manipulating Formal Power Series, Journal of the ACM (JACM), v.25 n.4, p.581-595, Oct. 1978 [doi>10.1145/322092.322099]
	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.
	4	KALToFEN, E. Challenges of symbolic computation: my favorite open problems. Preprint, 1998.
	5	Michael Kaminski , David G. Kirkpatrick , Nader H. Bshouty, Addition requirements for matrix and transposed matrix products, Journal of Algorithms, v.9 n.3, p.354-364, September 1988 [doi>10.1016/0196-6774(88)90026-0]
	6	MASSEY, J. Shift-register synthesis and BCH coding. IEEE Trans. Inf. Theory IT-15 (1969), 122-127.
	7	Victor Shoup, A fast deterministic algorithm for factoring polynomials over finite fields of small characteristic, Proceedings of the 1991 international symposium on Symbolic and algebraic computation, p.14-21, July 15-17, 1991, Bonn, West Germany [doi>10.1145/120694.120697]
	8	Victor Shoup, Fast construction of irreducible polynomials over finite fields, Journal of Symbolic Computation, v.17 n.5, p.371-391, May 1994 [doi>10.1006/jsco.1994.1025]
	9	Victor Shoup, A new polynomial factorization algorithm and its implementation, Journal of Symbolic Computation, v.20 n.4, p.363-397, October 1995 [doi>10.1006/jsco.1995.1055]
	10	YON ZUR GATItEN, J., AND SHOUP, V. Computing Frobenius maps and factoring polynomials. Computational Complexity 2 (1992), 187-224.
	11	D H Wiedemann, Solving sparse linear equations over finite fields, IEEE Transactions on Information Theory, v.32 n.1, p.54-62, Jan. 1986 [doi>10.1109/TIT.1986.1057137]

CITED BY 8

	A. Bostan , G. Lecerf , É. Schost, Tellegen's principle into practice, Proceedings of the 2003 international symposium on Symbolic and algebraic computation, p.37-44, August 03-06, 2003, Philadelphia, PA, USA
	Itnuit Janovitz-Freireich , Lajos Rónyai , Ágnes Szántó, Approximate radical of ideals with clusters of roots, Proceedings of the 2006 international symposium on Symbolic and algebraic computation, July 09-12, 2006, Genoa, Italy
	Christopher Umans, Fast polynomial factorization and modular composition in small characteristic, Proceedings of the 40th annual ACM symposium on Theory of computing, May 17-20, 2008, Victoria, British Columbia, Canada
	P. Gaudry , F. Morain, Fast algorithms for computing the eigenvalue in the Schoof-Elkies-Atkin algorithm, Proceedings of the 2006 international symposium on Symbolic and algebraic computation, July 09-12, 2006, Genoa, Italy
	Cyril Pascal , Éric Schost, Change of order for bivariate triangular sets, Proceedings of the 2006 international symposium on Symbolic and algebraic computation, July 09-12, 2006, Genoa, Italy
	P. Mihailescu , F. Morain , É. Schost, Computing the eigenvalue in the schoof-elkies-atkin algorithm using abelian lifts, Proceedings of the 2007 international symposium on Symbolic and algebraic computation, July 29-August 01, 2007, Waterloo, Ontario, Canada
	Hendrik Hubrechts, Quasi-quadratic elliptic curve point counting using rigid cohomology, Journal of Symbolic Computation, v.44 n.9, p.1255-1267, September, 2009
	Luca De Feo , Éric Schost, Fast arithmetics in artin-schreier towers over finite fields, Proceedings of the 2009 international symposium on Symbolic and algebraic computation, July 28-31, 2009, Seoul, Republic of Korea