Computing special powers in finite fields

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Computing special powers in finite fields: extended abstract

Full text

Pdf (897 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: 83 - 90

Year of Publication: 1999

ISBN:1-58113-073-2

Authors

Joachim von zur Gathen	Fachbereich 17, Mathematik-Informatik, Universität-GH, Paderborn, D-33095 Paderborn, Germany
Michael Nöcker	Fachbereich 17, Mathematik-Informatik, Universität-GH, Paderborn, D-33095 Paderborn, Germany

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): 3, Downloads (12 Months): 11, Citation Count: 0

Additional Information:

references 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.309869 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	BEILEI1, A. H. Recreations in the Theory of Numbers: The Queen of Mathe.matics Ent ".rtams. Dover Publications, Inc., New York, 1966.
	2	BERGERON, F., BE.RSTEI,, J., AND BRI.EK, S. Efficient computation of addition chains. Journal de Thdorie des Nombres de Bordeaux 6 (1994), 21-38.
	3	BRAt;ER, A. On addition chains. Bulletin of the American Mathematical Society ~5 (1939). 736-739.
	4	BRIC, KELL, E. F., GORDON, D., M~'.CUaLEY, K.: AND WXLSON, D. Fast exponentiation with precomputation. Iu Advances in Cryptology: Proceedings of EURO- CRYPT 1992, Balatonfiired, Hungary (Berlin, 1993), R. Ruept)el, Ed.. no. 658 in Lecture Notes in Computer Science, Springer-Verlag, pp. 200. 207.
	5	BRILI, HART, J., LEHMER, I). H.. SELFRIDCE, J. L., TUCKERMAN, B., AND \~AGSTAFF, JR., S. S. Factorizations of b'~ 4-1, b = 2,3,5, 6, 7, 10, 11:12 up to high powers, 2nd ed. No. 22 in Contemporary Mathematics. American Mathematical Society, Providence RI, 1988.
	6	BRLEK, S., CAS'I'ERAN, P., HABSIEGEI~, L., ANI) MAL- LETTE, R. On-line evaluation of powers using Euclid's algorithm. RAIRO, Inform. Theor. Appl. 29, 5 (1995), 431-450.
	7	David G. Gantor, On arithmetical algorithms over finite fields, Journal of Combinatorial Theory Series A, v.50 n.2, p.285-300, March 1989 [doi>10.1016/0097-3165(89)90020-4]
	8	DOWNEY, P., LEONG, B., AND SETItl, R. Computing sequences with addition chains. SIAM Journal on Computing 10, 3 (august 1981), 638-646.
	9	Shuhong Gao , Joachim von zur Gathen , Daniel Panario, Gauss Periods and Fast Exponentiation in Finite Fields (Extended Abstract), Proceedings of the Second Latin American Symposium on Theoretical Informatics, p.311-322, April 03-07, 1995
	10	Shuhong Gao , Hendrik W. Lenstra, Jr., Optimal normal bases, Designs, Codes and Cryptography, v.2 n.4, p.315-323, Dec. 1992 [doi>10.1007/BF00125200]
	11	V()N ZUR GATH{.:N, J. Efficient and optimal exponentiation in finite fields, computational complexity 1 (1991), 360-394.
	12	VON ZUR GATItEN, J.. ANI) GERHARD, J. Arithmetic and factorization of polynomials over Z~. Tech. Rep. trrsfb-96-018, University of Paderborn, Germany, 1996. 43 pages.
	13	Joachim von zur Gathen , Jürgen Gerhard, Modern computer algebra, Cambridge University Press, New York, NY, 1999
	14	Joachim von zur Gathen , Michael Nöcker, Exponentiation in Finite Fields: Theory and Practice, Proceedings of the 12th International Symposium on Applied Algebra, Algebraic Algorithms and Error-Correcting Codes, p.88-113, June 23-27, 1997
	15	GAUSS, C,. F. Disquisitiones Arithmeticae. Gerh. Fleischer Iun., Leipzig, 1801. English translation by ARTH~:R A. CLARKE. Springer-Verlag, New York, 1986.
	16	GIRSTMAIR, K. Periodische Dezimalbr/iche- was nicht jeder daxiiber weifl. In Jahrbuch ~}berblicke Mathematik 1995, A. Beutelspacher, Ed. Vieweg, 1995, pp. 163-179.
	17	Toshiya Itoh , Shigeo Tsujii, A fast algorithm for computing multiplicative inverses in GF(2m) using normal bases, Information and Computation, v.78 n.3, p.171-177, Sept. 1988 [doi>10.1016/0890-5401(88)90024-7]
	18	JUNGNICKEL, D. Finite Fields: Structure and Arithmetic.s. BI Wissenschaftsverlag, Mannheim, 1993.
	19	KARATSUBA, A., AND OFMAN. Y. ?YrMHO~t<eHHe MHOrO3Ha~HHX ~zcea Ha anToMaTax. 2Io~- ~a.~ A~a~eMz~ HayK CCCP 145 (1962), 293-294. A. KARATSIJBA and Yu. OFMAN, Multiplication of,nultidigit numbers on automata, Soviet Physics..-Doklady 7 (1963), 595-596.
	20	Donald E. Knuth, The art of computer programming, volume 2 (3rd ed.): seminumerical algorithms, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1997
	21	LEIIMER, D. H. Euclid's algorithm for large numbers. The American Mathematical Monthly ~5 (1938), 227- 233.
	22	MENEZES, A. J., BLAKE, I. F., GAO, X., h/IULLIN, a. C., VANSTONE, S. A., AND YAGHOOBIAN, T. Applications of finite fields. Kluwer Academic Publishers, Norwell MA. 1993.
	23	R. C. Mullin , I. M. Onyszchuk , S. A. Vanstone , R. M. Wilson, Optimal normal bases in GF(pn), Discrete Applied Mathematics, v.22 n.2, p.149-161, February 1989 [doi>10.1016/0166-218X(88)90090-X]
	24	SCHOLZ, A. Aufgabe 253. Jahresberichte der DMV 47 (1937), 41---42.
	25	SCHONHAGE, A. Schnelle Berechnung yon Kettenbruchentwicklungen. Acta Informatica 1 (1971), 139- 144.
	26	SCHONHAGE, A. A lower bound for the length of ad- (iition chains. Theoretical Computer Science 1 (1975), 1-12.
	27	SCH(~NHAGE, A. Sciulelle Multiplikation von Polynomen fiber KSrpern der Chaxakteristik 2. Acta Informatica 7 (1977), 395-398.
	28	SCtI(~NHAGE: A., AND STRASSEN, V. Schnelle Multiplikation gro6er Zahlen. Computing 7 (1971), 281-292.
	29	SHOUP. V. Exponentiation in GF(2n) using fewer polynomial multiplications. Preprint, november 1994.
	30	D. R. Stinson, Some observations on parallel algorithms for fast exponentiation in GF(2n), SIAM Journal on Computing, v.19 n.4, p.711-717, Aug. 1990 [doi>10.1137/0219049]
	31	STRASSEN. V. The computationa.1 complexity of contimled fractions. SIAM Journal on Computing 12, 1 (Februay 1983), 1-27.
	32	\~ASSEI~MANN, A. Zur Arithmetik in endlichen K5rpern. Bayreuther Math. Schriften ~4 (1993), 147- 251.
	33	YAO, A. C,. On the evaluation of powers. SIAM,lournal on Computing 5, 1 (1976), 10(}-103.