Publications of Joachim von zur Gathen

sorted by year

Last generated: 01 February 2018, 04:06.

There is also a BibTeX file corresponding to this list.

The local PDFs contained in this page are included as a means to ensure timely dissemination of scholarly and technical work on a non-commercial basis. Copyright and all rights therein are maintained by the authors or by other copyright holders, notwithstanding that these works are posted here electronically. It is understood that all persons copying any of these documents will adhere to the terms and constraints invoked by each copyright holder, and in particular use them only for noncommercial purposes. These works may not be posted elsewhere without the explicit written permission of the copyright holder.

2017

Joachim von zur Gathen & Daniel Loebenberger (2017). Why one Cannot Estimate the Entropy of English by Sampling. Journal of Quantitative Linguistics 1-30. Link to electronic version. Local PDF (364KB).

2015

Joachim von zur Gathen (2015). CryptoSchool. Springer-Verlag, Berlin, Heidelberg. ISBN 978-3-662-48425-8, XII, 876. Link to electronic version.

Joachim von zur Gathen & Igor E. Shparlinski (2015). Circulant graphs and GCD and LCM of subsets. Information Processing Letters 115, 134-138. ISSN 0020-0190.

Joachim von zur Gathen & Konstantin Ziegler (2015). Survey on counting special types of polynomials. In Computer Algebra and Polynomials, Jaime Gutierrez, Josef Schicho & Martin Weimann, editors, volume 8942 of Lecture Notes in Computer Science, 1-26. Springer-Verlag, Berlin, Heidelberg. Link to electronic version. Also available at http://arxiv.org/abs/1407.2970.

2014

Joachim von zur Gathen (2014). Counting decomposable univariate polynomials. Combinatorics, Probability and Computing, Special Issue 01 24, 294-328. Link to electronic version. Extended abstract in Proceedings of the 2009 International Symposium on Symbolic and Algebraic Computation ISSAC ’09, Seoul, Korea (2009). Preprint (2008) available at http://arxiv.org/abs/0901.0054.

Joachim von zur Gathen (2014). Normal form for Ritt’s Second Theorem. Finite Fields and Their Applications 27, 41-71. ISSN 1071-5797. Link to electronic version. Also available at http://arxiv.org/abs/1308.1135.

Joachim von zur Gathen & Guillermo Matera (2014). Density of real and complex decomposable univariate polynomials. eprint arXiv:1407.0906v1 Link to electronic version.

Joachim von zur Gathen & Igor E. Shparlinski (2014). Circulant graphs and GCD and LCM of Subsets. e-print arXiv:1402.5449v1 Link to electronic version. Local PDF (163KB).

2013

Raoul Blankertz, Joachim von zur Gathen & Konstantin Ziegler (2013). Compositions and collisions at degree p². Journal of Symbolic Computation 59, 113-145. ISSN 0747-7171. Link to electronic version. Extended abstract in Proceedings of the 2012 International Symposium on Symbolic and Algebraic Computation ISSAC 2012, Grenoble, France (2012). Local PDF (875KB).

Eda Cesaratto, Joachim von zur Gathen & Guillermo Matera (2013). The number of reducible space curves over a finite field. Journal of Number Theory 133, 1409-1434. Link to electronic version.

Joachim von zur Gathen (2013). Lower bounds for decomposable univariate wild polynomials. Journal of Symbolic Computation 50, 409-430. Link to electronic version. Extended abstract in Proceedings of the 2009 International Symposium on Symbolic and Algebraic Computation ISSAC ’09, Seoul, Korea (2009). Local PDF (315KB).

Joachim von zur Gathen & Jürgen Gerhard (2013). Modern Computer Algebra. Cambridge University Press, Cambridge, UK, Third edition. ISBN 9781107039032. The book’s homepage. Other available editions: Chinese edition, Japanese translation.

Joachim von zur Gathen & Igor Shparlinski (2013). Generating safe primes. Journal of Mathematical Cryptology 7(4), 333-365. ISSN 1862-2984 (Online) 1862-2976 (Print). Link to electronic version. Local PDF (373KB).

Joachim von zur Gathen, Alfredo Viola & Konstantin Ziegler (2013). Counting reducible, powerful, and relatively irreducible multivariate polynomials over finite fields. SIAM Journal on Discrete Mathematics 27(2), 855-891. Link to electronic version. Also available at http://arxiv.org/abs/0912.3312. Extended abstract in Proceedings of LATIN 2010, Oaxaca, Mexico (2010). Local PDF (967KB).

2012

Raoul Blankertz, Joachim von zur Gathen & Konstantin Ziegler (2012). Compositions and collisions at degree p². In Proceedings of the 2012 International Symposium on Symbolic and Algebraic Computation ISSAC 2012, Grenoble, France, Joris van der Hoeven & Mark van Hoeij, editors, 91-98. ACM Press, New York, USA. Link to electronic version. Full version in Journal of Symbolic Computation (2013).

Joachim von zur Gathen, Daniel Panario & Bruce Richmond (2012). Interval Partitions and Polynomial Factorization. Algorithmica 63, 363-397. Link to electronic version. Local PDF (343KB).

2011

Joachim von zur Gathen (2011). Census of Polynomials. Plenary talk. Joint work with Raoul Blankertz, Mark Giesbrecht, Alfredo Viola, and Konstantin Ziegler. In Fq10 - The Tenth International Conference on Finite Fields and Their Applications, p.8. Local PDF (66KB).

Joachim von zur Gathen (2011). Counting decomposable multivariate polynomials. Applicable Algebra in Engineering, Communication and Computing 22(3), 165-185. Link to electronic version. Abstract in Abstracts of the Ninth International Conference on Finite Fields and their Applications, pages 21-22, Dublin, July 2009, Claude Shannon Institute, http://www.shannoninstitute.ie/fq9/AllFq9Abstracts.pdf. Local PDF (331KB).

2010

Jean-Charles Faugère, Joachim von zur Gathen & Ludovic Perret (2010). Decomposition of Generic Multivariate Polynomials. In Proceedings of the 2010 International Symposium on Symbolic and Algebraic Computation ISSAC ’10, Munich, Germany, Stephen Watt, editor, 131-137. ACM Press. Link to electronic version. Local PDF (175KB).

Joachim von zur Gathen (2010). Shift-invariant polynomials and Ritt’s Second Theorem. In Finite Fields: Theory and Applications, Gary McGuire, Gary L. Mullen, Daniel Panario & Igor E. Shparlinski, editors, volume 518 of Contemporary Mathematics, 161-184. ISBN 0-8218-4786-4 (ISBN-10), 978-0-8218-4786-2 (ISBN-13). The Local PDF is a corrected version. Local PDF (338KB).

Joachim von zur Gathen, Mark Giesbrecht & Konstantin Ziegler (2010). Composition collisions and projective polynomials. Statement of results. In Proceedings of the 2010 International Symposium on Symbolic and Algebraic Computation ISSAC ’10, Munich, Germany, Stephen Watt, editor, 123-130. ACM Press. Link to electronic version. Preprint available at http://arxiv.org/abs/1005.1087.

Joachim von zur Gathen, Maurice Mignotte & Igor E. Shparlinski (2010). Approximate polynomial gcd: small degree and small height perturbations. Journal of Symbolic Computation Link to electronic version. The Local PDF is a corrected version. Local PDF (217KB).

Joachim von zur Gathen, Alfredo Viola & Konstantin Ziegler (2010). Counting Reducible, Powerful, and Relatively Irreducible Multivariate Polynomials over Finite Fields (Extended Abstract). In Proceedings of LATIN 2010, Oaxaca, Mexico, Alejandro López-Ortiz, editor, volume 6034 of Lecture Notes in Computer Science, 243-254. Springer-Verlag, Berlin, Heidelberg. ISBN 978-3-642-12199-9. ISSN 0302-9743 (Print) 1611-3349 (Online). Link to electronic version. Final version in SIAM Journal on Discrete Mathematics (2013).

2009

Joachim von zur Gathen (2009). The number of decomposable multivariate polynomials. In Abstracts of the Ninth International Conference on Finite Fields and their Applications, 21-22. Claude Shannon Institute, Dublin. Link to electronic version.

Joachim von zur Gathen (2009). The Number of Decomposable Univariate Polynomials — Extended Abstract. In Proceedings of the 2009 International Symposium on Symbolic and Algebraic Computation ISSAC ’09, Seoul, Korea, John P. May, editor, 359-366. ACM Press. ISBN 978-1-60558-609-0. Preprint (2008) available at http://arxiv.org/abs/0901.0054. Full version in Combinatorics, Probability and Computing (2014), Special Issue, to appear. Local PDF (226KB).

Joachim von zur Gathen & Igor E. Shparlinski (2009). Subset sum pseudorandom numbers: fast generation and distribution. Journal of Mathematical Cryptology 3(2), 149-163. ISSN (Online) 1862-2984, (Print) 1862-2976. Link to electronic version.

2008

Joachim von zur Gathen (2008). Counting decomposable multivariate polynomials. Preprint, 21 pages. Link to electronic version. Abstract in Abstracts of the Ninth International Conference on Finite Fields and their Applications, 21-22. Claude Shannon Institute, Dublin. July, 2009. http://www.shannoninstitute.ie/fq9/AllFq9Abstracts.pdf.

Joachim von zur Gathen (2008). Counting reducible and singular bivariate polynomials. Finite Fields and Their Applications 14(4), 944-978. Link to electronic version. Extended abstract in ISSAC’07. The Local PDF includes a single-page correction. Local PDF (409KB).

Joachim von zur Gathen (2008). Subset Sum Pseudorandom Generators. In Extended Abstracts of the Second Workshop on Mathematical Cryptology WMC 08, Álvar Ibeas & Jaime Gutiérrez, editors, 20. Link to electronic version.

Joachim von zur Gathen & Igor E. Shparlinski (2008). Approximate polynomial gcd: small degree and small height perturbations. In Proceedings of LATIN 2008, Búzios, Rio de Janeiro, Brazil, Eduardo Sany Laber, Claudson Bornstein, Loana Tito Nogueira & Luerbio Faria, editors, volume 4957 of Lecture Notes in Computer Science, 276-283. Springer-Verlag, Berlin, Heidelberg. ISSN 0302-9743. Link to electronic version. Local PDF (180KB).

2007

Joachim von zur Gathen (2007). Counting Reducible and Singular Bivariate Polynomials. Oberwolfach Report 31, 40-41.

Joachim von zur Gathen (2007). Fast arithmetic: tiger in your tank. In Proceedings of Conference on Algorithmic Number Theory, Anne-Maria Ernvall-Hytönen, Matti Jutila, Juhani Karhumäki & Arto Lepistö, editors, 50-63. Turku, Finland.

Joachim von zur Gathen (2007). Zimmermann Telegram: The Original Draft. Cryptologia 31(1), 2-37. Link to electronic version. Local PDF (2.8MB).

Joachim von zur Gathen, Amin Shokrollahi & Jamshid Shokrollahi (2007). Efficient Multiplication Using Type 2 Optimal Normal Bases. In International Workshop on the Arithmetic of Finite Fields, WAIFI 2007, Claude Carlet & Berk Sunar, editors, volume 4547 of Lecture Notes in Computer Science, 55-68. Springer-Verlag, Berlin/ Heidelberg. ISSN 0302-9743 (Print) 1611-3349 (Online). Link to electronic version. Local PDF (256KB).

Joachim von zur Gathen, Amin Shokrollahi & Jamshid Shokrollahi (2007). Efficient Multiplication Using Type 2 Optimal Normal Bases. In WAIFI, Claude Carlet & Berk Sunar, editors, volume 4547 of Lecture Notes in Computer Science, 55-68. Springer-Verlag, Berlin/ Heidelberg. ISSN 0302-9743 (Print) 1611-3349 (Online). Link to electronic version.

2006

Joachim von zur Gathen (2006). Who was Who in Polynomial Factorization. In Proceedings of the 2006 International Symposium on Symbolic and Algebraic Computation ISSAC ’06, Genova, Italy, Jean-Guillaume Dumas, editor, 1-2. ACM Press. ISBN 1-59593-276-3. Link to electronic version.

Joachim von zur Gathen & Jamshid Shokrollahi (2006). Fast arithmetic for polynomials over F₂ in hardware. In IEEE Information Theory Workshop (2006), 107-111. IEEE, Punta del Este, Uruguay. Local PDF (152KB).

Joachim von zur Gathen & Igor E. Shparlinski (2006). GCD of Random Linear Combinations. Algorithmica 46(1), 137-148. ISSN 0178-4617 (Print), 1432-0541 (Online). Link to electronic version. Local PDF (162KB).

2005

Joachim von zur Gathen & Michael Nöcker (2005). Polynomial and normal bases for finite fields. Journal of Cryptology 18(4), 337-355. ISSN 0933-2790. Link to electronic version. Local PDF (455KB).

Joachim von zur Gathen & Jamshid Shokrollahi (2005). Efficient FPGA-based Karatsuba multipliers for polynomials over F₂. In Selected Areas in Cryptography (SAC 2005), Bart Preneel & Stafford Tavares, editors, number 3897 in Lecture Notes in Computer Science, 359-369. Springer-Verlag, Kingston, ON, Canada. ISBN 3-540-33108-5. Link to electronic version. Local PDF (194KB).

2004

Michael P. Barnett, Joseph F. Capitani, Joachim Von Zur Gathen & Jürgen Gerhard (2004). Symbolic calculation in chemistry: Selected examples. International Journal of Quantum Chemistry 100(2), 80-104. Link to electronic version. Suplementary material: http://www.mrw.interscience.wiley.com/suppmat/0020-7608/suppmat/100/suppmat_barnett.pdf. Local PDF (475KB).

Joachim von zur Gathen (2004). Arithmetic Circuits for Discrete Logarithms. In Proceedings of LATIN 2004, Buenos Aires, Argentina, Martin Farach-Colton, editor, volume 2976 of Lecture Notes in Computer Science, 557-566. Springer-Verlag, Berlin, Heidelberg. ISBN 978-3-540-21258-4. ISSN 0302-9743 (Print) 1611-3349 (Online). Link to electronic version. Local PDF (297KB).

Joachim von zur Gathen (2004). Friederich Johann Buck: arithmetic puzzles in cryptography. Cryptologia XXVIII(4), 309-324. Link to electronic version. Local PDF (1.5MB).

Joachim von zur Gathen, Arnold Knopfmacher, Florian Luca, Lutz G. Lucht & Igor E. Shparlinski (2004). Average order in cyclic groups. Bordeaux Journal of Number Theory 16, 107-123. Local PDF (348KB).

Joachim von zur Gathen & Michael Nöcker (2004). Computing special powers in finite fields. Mathematics of Computation 73(247), 1499-1523. ISSN 0025-5718. Link to electronic version. Article electronically published on September 26, 2003. Local PDF (512KB).

Joachim von zur Gathen & Michael Nöcker (2004). Fast arithmetic with general Gauß periods. Theoretical Computer Science 315, 419-452. Link to electronic version. Local PDF (499KB).

Joachim von zur Gathen & Igor E. Shparlinski (2004). GCD of Random Linear Forms. In Proceedings of 15th International Symposium on Algorithms and Computation ISAAC ’04, Hong Kong, China, Rudolf Fleischer & Gerhard Trippen, editors, volume 3341 of Lecture Notes in Computer Science, 845-846. Springer-Verlag, Berlin, Heidelberg. ISBN 978-3-540-24131-7 (Print) 978-3-540-30551-4 (Online). ISSN 0302-9743. Link to electronic version. Local PDF (176KB).

Joachim von zur Gathen & Igor E. Shparlinski (2004). Polynomial Interpolation from Multiples. In Proceedings of the Fifteenth Annual ACM-SIAM Symposium on Discrete Algorithms, J. Ian Munro, editor, 1125-1130. Link to electronic version. Local PDF (254KB).

Joachim von zur Gathen & Igor E. Shparlinski (2004). Predicting Subset Sum Pseudorandom Generators. In Selected Areas in Cryptography, Helena Handschuh & M. Anwar Hasan, editors, volume 3357 of Lecture Notes in Computer Science, 241-251. Springer-Verlag, Berlin, Heidelberg. ISBN 3-540-24327-5. ISSN 0302-9743. Link to electronic version. Local PDF (250KB).

2003

Eric Allender, Anna Bernasconi, Carsten Damm, Joachim von zur Gathen, Michael Saks & Igor Shparlinski (2003). Complexity of some arithmetic problems for binary polynomials. computational complexity 12(1/2), 23-47. Link to electronic version. Local PDF (399KB).

Joachim von zur Gathen (2003). Claude Comiers: the first arithmetical cryptography. Cryptologia XXVII(4), 339-349. Link to electronic version. Local PDF (4.9MB).

Joachim von zur Gathen (2003). Efficient exponentiation in finite fields. In Tagungsband: Computeralgebra. Universität Kassel 15. - 17. Mai 2003, 8.

Joachim von zur Gathen (2003). Factorization of Polynomials. In Computer Algebra Handbook - Foundations, Applications, Systems, Johannes Grabmeier, Erich Kaltofen & Volker Weispfenning, editors, 24-26. Springer-Verlag, Berlin, Heidelberg, New York. ISBN 3-540-65466-6. Link to the book.

Joachim von zur Gathen (2003). Irreducible trinomials over finite fields. Mathematics of Computation 72, 1987-2000. Link to electronic version. Local PDF (339KB).

Joachim von zur Gathen & Jürgen Gerhard (2003). Modern Computer Algebra. Cambridge University Press, Cambridge, UK, Second edition. ISBN 0-521-82646-2, 800 pages. The book’s homepage. Other available editions: first edition [von zur Gathen & Gerhard (1999)], Chinese edition, Japanese translation.

Joachim von zur Gathen & Thomas Lücking (2003). Subresultants revisited. Theoretical Computer Science 297, 199-239. Link to electronic version. Extended Abstract in Proceedings of LATIN 2000, Punta del Este, Uruguay (2000). Local PDF (490KB).

Joachim von zur Gathen, Igor Shparlinski & Alistair Sinclair (2003). Finding points on curves over finite fields. SIAM Journal on Computing 32(6), 1436-1448. Link to electronic version. Extended abstract in von zur Gathen & Shparlinski (1995a). Local PDF (363KB).

C. Grabbe, M. Bednara, J. Shokrollahi, J. Teich & J. von zur Gathen (2003). A High Performance VLIW Processor for Finite Field Arithmetic. In Proc. of The 10th Reconfigurable Architectures Workshop (RAW-03). Local PDF (185KB).

C. Grabbe, M. Bednara, J. Shokrollahi, J. Teich & J. von zur Gathen (2003). FPGA Designs of parallel high performance GF(2²³³) Multipliers. In Proc. of the IEEE International Symposium on Circuits and Systems (ISCAS-03), volume II, 268-271. Bangkok, Thailand. Local PDF (244KB).

2002

M. Bednara, M. Daldrup, J. Shokrollahi, J. Teich & J. von zur Gathen (2002). Reconfigurable Implementation of Elliptic Curve Crypto Algorithms. In Proc. of The 9th Reconfigurable Architectures Workshop (RAW-02), 157-164. Fort Lauderdale FL, USA. Local PDF (193KB).

M. Bednara, M. Daldrup, J. Shokrollahi, J. Teich & J. von zur Gathen (2002). Tradeoff Analysis of FPGA Based Elliptic Curve Cryptography. In Proc. of the IEEE International Symposium on Circuits and Systems (ISCAS-02), volume V, 797-800. Scottsdale, Arizona, U.S.A. Link to PDF version. Local PDF (109KB).

Joachim von zur Gathen (2002). Factorization and Decomposition of Polynomials. In The Concise Handbook of Algebra, Alexander V. Mikhalev & Günter F. Pilz, editors, 159-161. Kluwer Academic Publishers. ISBN 0-7923-7072-4. Link to electronic version. Local PDF (170KB).

Joachim von zur Gathen (2002). Review of: Donald E. Knuth, Selected Papers on Analysis of Algorithms. IEEE Annals of the History of Computing 24(2), 98-99.

Joachim von zur Gathen & Jürgen Gerhard (2002). Polynomial factorization over F₂. Mathematics of Computation 71(240), 1677-1698. Link to electronic version. Local PDF (449KB).

2001

Eric Bach, Joachim von zur Gathen & Hendrik W. Lenstra, Jr. (2001). Factoring Polynomials over Special Finite Fields. Finite Fields and Their Applications 7, 5-28. Link to PDF version. Local PDF (293KB).

Olaf Bonorden, Joachim von zur Gathen, Jürgen Gerhard, Olaf Müller & Michael Nöcker (2001). Factoring a binary polynomial of degree over one million. ACM SIGSAM Bulletin 35(1), 16-18. Link to electronic version. Local PDF (195KB).

Joachim von zur Gathen (2001). Factorization of polynomials. In Encyclopaedia of Mathematics, Supplement III, M. Hazewinkel, editor, 146-147. Kluwer Academic Publishers. ISBN 1-4020-0198-3. Link to the book. Local PDF (207KB).

Joachim von zur Gathen (2001). Irreducible Trinomials over Finite Fields. In Proceedings of the 2001 International Symposium on Symbolic and Algebraic Computation ISSAC ’01, London, Canada, Bernard Mourrain, editor, 332-336. ACM Press. Final version in Mathematics of Computation.

Joachim von zur Gathen & Daniel Panario (2001). Factoring Polynomials Over Finite Fields: A Survey. Journal of Symbolic Computation 31(1-2), 3-17. Link to electronic version.

Joachim von zur Gathen & Francesco Pappalardi (2001). Density Estimates Related to Gauß periods. Progress in Computer Science and Applied Logic 20, 33-41. Link to electronic version. Local PDF (244KB).

Joachim von zur Gathen & Igor Shparlinski (2001). Gauß Periods in Finite Fields. In Finite Fields and Applications, Dieter Jungnickel & Harald Niederreiter, editors, 162-177. Springer-Verlag. Link to electronic version. Local PDF (316KB).

2000

Shuhong Gao, Joachim von zur Gathen, Daniel Panario & Victor Shoup (2000). Algorithms for Exponentiation in Finite Fields. Journal of Symbolic Computation 29(6), 879-889. Link to electronic version. Local PDF (2.1MB).

Joachim von zur Gathen (2000). Algebra und Algorithmik. In Lexikon der Mathematik, Guido Walz, editor, 43-47. Spektrum Verlag, Heidelberg. ISBN 3-8274-0303-0. Book online (accessible only from uni-paderborn). Local PDF (188KB).

Joachim von zur Gathen (2000). Factoring Polynomials Over Finite Fields. In Proceedings of An International Symposium on Applications of Computer Algebra ISACA ’2000, Kolhapur, India, Rajendra Akerkar, editor, 109-114. Allied Publishers Limited.

Joachim von zur Gathen (2000). Gauss periods — old tool, new results. In 5th Pan African Congress of Mathematics, 40. Johannesburg.

Joachim von zur Gathen (2000). Subresultants revisited. Abstract of Invited Talk at East Coast Computer Algebra Day 2000. SIGSAM Bulletin 34(3), 21.

Joachim von zur Gathen & Thomas Lücking (2000). Subresultants revisited. In Proceedings of LATIN 2000, Punta del Este, Uruguay, G. H. Gonnet, D. Panario & A. Viola, editors, volume 1776 of Lecture Notes in Computer Science, 318-342. Springer-Verlag, Berlin, Heidelberg. ISBN 3-540-67306-7. ISSN 0302-9743. Link to electronic version. Final version in Theoretical Computer Science (2003). Local PDF (413KB).

Joachim von zur Gathen & Francesco Pappalardi (2000). Density estimates for Gauß periods. In Proc. Workshop on Cryptography and Computational Number Theory (CCNT’99, Singapore), K.-Y. Lam, I. E. Shparlinski, H. Wang & C. Xing, editors. Birkhäuser Verlag. Final version in Progress in Computer Science and Applied Logic.

Joachim von zur Gathen & Igor Shparlinski (2000). The CREW PRAM complexity of modular inversion. SIAM Journal on Computing 29(6), 1839-1857. Link to electronic version. Local PDF (306KB).

1999

Gene Cooperman, Sandra Feisel, Joachim von zur Gathen & George Havas (1999). GCD of Many Integers. In COCOON ’99, T. Asano, H. Imai, D. T. Lee, S. Nakano & T. Tokuyama, editors, number 1627 in Lecture Notes in Computer Science, 310-317. Springer-Verlag. ISSN 302-9743 (Print) 1611-3349 (Online). Link to electronic version. Local PDF (2.3MB).

Sandra Feisel, Joachim von zur Gathen & M. Amin Shokrollahi (1999). Normal bases via general Gauß periods. Mathematics of Computation 68(225), 271-290. Link to electronic version. Local PDF (350KB).

Joachim von zur Gathen (1999). Gauß periods. In Abstracts of the Fifth International Conference on Finite Fields and Applications, 1999, University of Augsburg, 29.

Joachim von zur Gathen & Jürgen Gerhard (1999). Modern Computer Algebra. Cambridge University Press, Cambridge, UK, First edition. ISBN 0-521-64176-4. The book’s homepage. Other available editions: Second edition [von zur Gathen & Gerhard (2003)], Chinese edition, Japanese translation.

Joachim von zur Gathen & Michael Nöcker (1999). Computing Special Powers in Finite Fields: Extended Abstract. In Proceedings of the 1999 International Symposium on Symbolic and Algebraic Computation ISSAC ’99, Vancouver, Canada, Sam Dooley, editor, 83-90. ACM Press. Link to electronic version.

Joachim von zur Gathen & Michael Nöcker (1999). Normal bases, Gauss periods, and fast arithmetic. In Abstracts of the Fifth International Conference on Finite Fields and Applications, University of Augsburg, 70.

Joachim von zur Gathen & Igor Shparlinski (1999). Constructing Elements of Large Order in Finite Fields. In Applied Algebra, Algebraic Algorithms and Error-Correcting Codes, Marc Fossorier, Hideki Imai, Shu Lin & Alain Poli, editors, volume 1719 of Lecture Notes in Computer Science, 404-409. Springer-Verlag, Berlin, Heidelberg. ISBN 3-540-66723-7. ISSN 0302-9743. Link to electronic version.

1998

Shuhong Gao, Joachim von zur Gathen & Daniel Panario (1998). Gauss periods: orders and cryptographical applications. Mathematics of Computation 67(221), 343-352. Link to electronic version. With microfiche supplement. Local PDF (232KB).

Joachim von zur Gathen (1998). Algebra für Spione, Datenschützer und das Internet: Kryptographie und endliche Körper. Forschungsforum Paderborn 1-98, 8-13. Link to electronic version. Local PDF (428KB).

Joachim von zur Gathen & Silke Hartlieb (1998). Factoring Modular Polynomials. Journal of Symbolic Computation 26(5), 583-606. Link to electronic version. Extended abstract in Proceedings of the 1996 International Symposium on Symbolic and Algebraic Computation ISSAC ’96, Zürich, Switzerland(1996). Local PDF (4.3MB).

Joachim von zur Gathen & Igor E. Shparlinski (1998). Computing components and projections of curves over finite fields. SIAM Journal on Computing 28(3), 822-840. Link to electronic version. Local PDF (360KB).

Joachim von zur Gathen & Igor Shparlinski (1998). The CREW PRAM complexity of modular inversion. In Proceedings of LATIN ’98, Campinas, Brazil, C. L. Lucchesi & A. V. Moura, editors, volume 1380 of Lecture Notes in Computer Science, 305-315. Springer-Verlag, Berlin, Heidelberg. ISBN 3-540-64275-7. ISSN 0302-9743. Link to electronic version. Final version in SIAM Journal on Computing. Local PDF (264KB).

Joachim von zur Gathen & Igor Shparlinski (1998). Orders of Gauss Periods in Finite Fields. Applicable Algebra in Engineering, Communication and Computing 9(1), 15-24. Link to electronic version. Extended abstract in Proceedings of 6th International Symposium on Algorithms and Computation ISAAC ’95, Cairns, Australia (1995). Local PDF (232KB).

1997

Joachim von zur Gathen & Jürgen Gerhard (1997). Fast Algorithms for Taylor Shifts and Certain Difference Equations. In Proceedings of the 1997 International Symposium on Symbolic and Algebraic Computation ISSAC ’97, Maui HI, Wolfgang W. Küchlin, editor, 40-47. ACM Press. Link to electronic version. Local PDF (312KB).

Joachim von zur Gathen & Michael Nöcker (1997). Exponentiation in Finite Fields: Theory and Practice. In Applied Algebra, Algebraic Algorithms and Error-Correcting Codes: AAECC-12, Toulouse, France, Teo Mora & Harold Mattson, editors, number 1255 in Lecture Notes in Computer Science, 88-113. Springer-Verlag. ISSN 0302-9743. Link to electronic version. Local PDF (415KB).

Joachim von zur Gathen & James R. Roche (1997). Polynomials with two values. Combinatorica 17(3), 345-362. Link to electronic version. Local PDF (3.1MB).

1996

Joachim von zur Gathen & Jürgen Gerhard (1996). Arithmetic and Factorization of Polynomials over F₂. In Proceedings of the 1996 International Symposium on Symbolic and Algebraic Computation ISSAC ’96, Zürich, Switzerland, Y. N. Lakshman, editor, 1-9. ACM Press. Link to electronic version. Technical report tr-rsfb-96-018, University of Paderborn, Germany, 1996, 43 pages. Final version in Mathematics of Computation. Local PDF (355KB).

Joachim von zur Gathen & Silke Hartlieb (1996). Factoring Modular Polynomials. In Proceedings of the 1996 International Symposium on Symbolic and Algebraic Computation ISSAC ’96, Zürich, Switzerland, Y. N. Lakshman, editor, 10-17. ACM Press. ISBN 0-89791-796-0. Link to electronic version. Final version in Journal of Symbolic Computation (1998). Local PDF (343KB).

Joachim von zur Gathen, Marek Karpinski & Igor E. Shparlinski (1996). Counting curves and their projections. computational complexity 6, 64-99. Link to electronic version. Extended abstract in von zur Gathen et al. (1993). Local PDF (423KB).

1995

Shuhong Gao, Joachim von zur Gathen & Daniel Panario (1995). Gauss periods and fast exponentiation in finite fields. In Proceedings of LATIN ’95, Valparaíso, Chile, Ricardo Baeza-Yates, Eric Goles & Patricio V. Poblete, editors, number 911 in Lecture Notes in Computer Science, 311-322. Springer-Verlag. ISSN 0302-9743. Link to electronic version. Final versions in Mathematics of Computation and Journal of Symbolic Computation.

Joachim von zur Gathen & Igor E. Shparlinski (1995). Finding points on curves over finite fields. In Proceedings of the 36th Annual IEEE Symposium on Foundations of Computer Science, Milwaukee WI, 284-292. IEEE Computer Society Press. Final version see von zur Gathen et al. (2003). Local PDF (290KB).

Joachim von zur Gathen & Igor E. Shparlinski (1995). Orders of Gauss Periods in Finite Fields. In Proceedings of 6th International Symposium on Algorithms and Computation ISAAC ’95, Cairns, Australia, J. Staples, P. Eades, N. Katoh & A. Moffat, editors, volume 1004 of Lecture Notes in Computer Science, 208-215. Springer-Verlag, Berlin, Heidelberg. ISBN 3-540-60573-8. ISSN 0302-9743. Link to electronic version. Final version in Applicable Algebra in Engineering, Communication and Computing (1998).

J. von zur Gathen & J. Weiss (1995). Homogeneous Bivariate Decompositions. Journal of Symbolic Computation 19, 409-434. Link to electronic version. Local PDF (382KB).

K. Ma & J. von zur Gathen (1995). The computational complexity of recognizing permutation functions. computational complexity 5(1), 76-97. Link to electronic version. Local PDF (3.7MB).

K. Ma & J. von zur Gathen (1995). Tests for Permutation Functions. Finite Fields and Their Applications 1, 31-56. Link to electronic version. Local PDF (4.0MB).

1994

Shuhong Gao & Joachim von zur Gathen (1994). Berlekamp’s and Niederreiter’s Polynomial Factorization Algorithms. In Finite Fields: Theory, Applications and Algorithms, G. L. Mullen & P. J.-S. Shiue, editors, number 168 in Contemporary Mathematics, 101-115. American Mathematical Society. Local PDF (3.0MB).

Joachim von zur Gathen & Igor E. Shparlinski (1994). Components and projections of curves over finite fields. In Proceedings of 5th International Symposium on Algorithms and Computation ISAAC ’94, Beijing, China, Ding-Zhu Du & Kiang-Sun Zhang, editors, volume 834 of Lecture Notes in Computer Science, 297-305. Springer-Verlag, Berlin, Heidelberg. ISBN 3-540-58325-4. ISSN 0302-9743. Link to electronic version. Final version in SIAM Journal on Computing.

K. Ma & J. von zur Gathen (1994). The computational complexity of recognizing permutation functions - Extended Abstract. In Proceedings of the Twenty-sixth Annual ACM Symposium on Theory of Computing, Montréal, Québec, Canada, 392-401. ACM Press, New York, USA. ISBN 0-89791-663-8. Link to electronic version.

1993

Joachim von zur Gathen (1993). Factoring Polynomials Over Finite Fields. In Second International Conference on Finite Fields: Theory, Applications and Algorithms, Las Vegas NV, 115.

Joachim von zur Gathen (1993). Faktorisieren von Polynomen. In Computeralgebra in Deutschland, 20-22 and 25-26. Fachgruppe Computeralgebra. Local PDF (108KB).

Joachim von zur Gathen (1993). Parallel linear algebra. In Synthesis of parallel algorithms, J. Reif, editor, 573-617. Morgan Kaufmann Publishers. Local PDF (5.6MB).

Joachim von zur Gathen, Marek Karpinski & Igor E. Shparlinski (1993). Counting curves and their projections. In Proceedings of the Twenty-fifth Annual ACM Symposium on Theory of Computing, San Diego CA, 805-812. ACM Press. Link to electronic version. Final version see von zur Gathen et al. (1996). Local PDF (430KB).

K. Ma & J. von zur Gathen (1993). Counting value sets of functions and testing permutation functions. In Abstracts of Int. Conf. Number Theoretic and Algebraic Methods in Computer Science, Moscow, Russia, 62-65. Final version in computational complexity and Finite Fields and Their Applications. See Ma & von zur Gathen (1995b).

1992

Joachim von zur Gathen (1992). A polynomial factorization challenge. ACM SIGSAM Bulletin 26, 22-24. Link to electronic version. Local PDF (842KB).

Joachim von zur Gathen (1992). Processor-efficient exponentiation in finite fields. Information Processing Letters 41, 81-86. Link to electronic version. Local PDF (1.2MB).

Joachim von zur Gathen & Victor Shoup (1992). Computing Frobenius maps and factoring polynomials. computational complexity 2, 187-224. Link to electronic version. Local PDF (6.6MB).

Joachim von zur Gathen & Victor Shoup (1992). Computing Frobenius maps and factoring polynomials. In Proceedings of the Twenty-fourth Annual ACM Symposium on Theory of Computing, Victoria, British Columbia, Canada, 97-105. ACM Press. Link to electronic version. Final version in computational complexity, see von zur Gathen & Shoup (1992a).

1991

Joachim von zur Gathen (1991). Efficient and optimal exponentiation in finite fields. computational complexity 1, 360-394. Link to electronic version. Local PDF (5.1MB).

Joachim von zur Gathen (1991). Efficient exponentiation in finite fields. In Proceedings of the 32nd Annual IEEE Symposium on Foundations of Computer Science, San Juan PR, 384-391. IEEE Computer Society Press, Los Alamitos CA. Final version in computational complexity, see von zur Gathen (1991a).

Joachim von zur Gathen (1991). Maximal Bilinear Complexity and Codes. Linear Algebra and its Applications 144, 49-61. Link to electronic version. Local PDF (1.9MB).

Joachim von zur Gathen (1991). Tests for permutation polynomials. SIAM Journal on Computing 20(3), 591-602. Link to electronic version. Local PDF (2.7MB).

Joachim von zur Gathen (1991). Values of polynomials over finite fields. Bulletin of the Australian Mathematical Society 43, 141-146. Link to electronic version. Local PDF (1.1MB).

Joachim von zur Gathen & Gadiel Seroussi (1991). Boolean Circuits versus Arithmetic Circuits. Information and Computation 91, 142-154. Link to electronic version. Extended abstract in Proc. 6th Int. Conf. Computer Science, Santiago, Chile (1986). Local PDF (826KB).

1990

Joachim von zur Gathen (1990). Functional Decomposition of Polynomials: the Tame Case. Journal of Symbolic Computation 9, 281-299. Link to electronic version. Extended abstract in Proceedings of the 28th Annual IEEE Symposium on Foundations of Computer Science, Los Angeles CA (1987). Local PDF (3.8MB).

Joachim von zur Gathen (1990). Functional Decomposition of Polynomials: the Wild Case. Journal of Symbolic Computation 10, 437-452. Link to electronic version. Local PDF (3.1MB).

Joachim von zur Gathen (1990). Inversion in finite fields using logarithmic depth. Journal of Symbolic Computation 9, 175-183. Link to electronic version. Local PDF (1.8MB).

Joachim von zur Gathen (1990). Polynomials over finite fields with large images. In Proceedings of the 1990 International Symposium on Symbolic and Algebraic Computation ISSAC ’90, Tokyo, Japan, Shunro Watanable & Morio Nagata, editors, 140-144. ACM Press. Link to electronic version. Final version in Bulletin of the Australian Mathematical Society.

J. von zur Gathen & M. Giesbrecht (1990). Constructing Normal Bases in Finite Fields. Journal of Symbolic Computation 10, 547-570. ISSN 0747-7171. Link to electronic version. Local PDF (4.5MB).

Keju Ma & Joachim von zur Gathen (1990). Analysis of Euclidean Algorithms for Polynomials over Finite Fields. Journal of Symbolic Computation 9, 429-455. Link to electronic version. Local PDF (4.8MB).

1989

Joachim von zur Gathen (1989). Testing permutation polynomials. In Proceedings of the 30th Annual IEEE Symposium on Foundations of Computer Science, Research Triangle Park NC, 88-92. IEEE Computer Society Press, Los Alamitos CA. Link to electronic version. Final version in SIAM Journal on Computing.

1988

Joachim von zur Gathen (1988). Algebraic complexity theory. Annual Review of Computer Science 3, 317-347. Link to electronic version. Local PDF (6.0MB).

1987

Joachim von zur Gathen (1987). Computing powers in parallel. SIAM Journal on Computing 16, 930-945. Link to electronic version. Extended abstract in Proceedings of the 25th Annual IEEE Symposium on Foundations of Computer Science, Singer Island FL (1984). Local PDF (3.2MB).

Joachim von zur Gathen (1987). Factoring polynomials and primitive elements for special primes. Theoretical Computer Science 52, 77-89. Link to electronic version. Local PDF (2.6MB).

Joachim von zur Gathen (1987). Feasible Arithmetic Computations: Valiant’s Hypothesis. Journal of Symbolic Computation 4, 137-172. Link to electronic version. Local PDF (6.2MB).

Joachim von zur Gathen (1987). Permanent and determinant. Linear Algebra and its Applications 96, 87-100. Link to electronic version. Extended abstract in Proceedings of the 27th Annual IEEE Symposium on Foundations of Computer Science, Toronto, Ontario, Canada (1986). Local PDF (2.1MB).

Joachim von zur Gathen, Dexter Kozen & Susan Landau (1987). Functional Decomposition of Polynomials. In Proceedings of the 28th Annual IEEE Symposium on Foundations of Computer Science, Los Angeles CA, 127-131. IEEE Computer Society Press, Washington DC. Link to electronic version.

1986

Joachim von zur Gathen (1986). Irreducible Polynomials over Finite Fields. In Proc. 6th Conf. Foundations of Software Technology and Theoretical Computer Science, Delhi, India, number 241 in Lecture Notes in Computer Science, 252-262. Springer-Verlag. ISSN 0302-9743. Link to electronic version.

Joachim von zur Gathen (1986). Irreducible polynomials over finite fields. Technical Report 188/86, Department of Computer Science, University of Toronto, Toronto, Ontario, Canada. Local PDF (5.8MB).

Joachim von zur Gathen (1986). Parallel Arithmetic computations: a survey. In Proceedings of the 12th International Symposium Mathematical Foundations of Computer Science 1986, Bratislava, Czechosolvakia, Jozef Gruska, Branislav Rovan & Juraj Wiedermann, editors, volume 233 of Lecture Notes in Computer Science, 93-112. Springer-Verlag, Berlin, Heidelberg. ISBN 3-540-16783-8. ISSN 0302-9743. Link to electronic version. Extended version: Local PDF. Local PDF (10.9MB).

Joachim von zur Gathen (1986). Permanent and determinant. In Proceedings of the 27th Annual IEEE Symposium on Foundations of Computer Science, Toronto, Ontario, Canada, 398-401. IEEE Computer Society Press, Washington DC. Final version in Linear Algebra and its Applications (1987).

Joachim von zur Gathen (1986). Representations and parallel computations for rational functions. SIAM Journal on Computing 15(2), 432-452. Link to electronic version. Extended abstract in Proceedings of the 24th Annual IEEE Symposium on Foundations of Computer Science, Tucson AZ (1983). Local PDF (4.5MB).

J. von zur Gathen & G. Seroussi (1986). Boolean Circuits versus Arithmetic Circuits. In Proc. 6th Int. Conf. Computer Science, Santiago, Chile, 171-184. Final version in Information and Computation (1991).

1985

Joachim von zur Gathen (1985). Irreducibility of Multivariate Polynomials. Journal of Computer and System Sciences 31(2), 225-264. Link to electronic version. Local PDF (6.7MB).

J. von zur Gathen & E. Kaltofen (1985). Factorization of Multivariate Polynomials Over Finite Fields. Mathematics of Computation 45, 251-261. Link to electronic version. Extended Abstract in Proceedings of the 10th International Colloquium on Automata, Languages and Programming ICALP 1983, Barcelona, Spain (1983). Local PDF (3.2MB).

Joachim von zur Gathen & Erich Kaltofen (1985). Factoring Sparse Multivariate Polynomials. Journal of Computer and System Sciences 31(2), 265-287. Link to electronic version. Extended abstract in Proceedings of the 24th Annual IEEE Symposium on Foundations of Computer Science, Tucson AZ (1983).

1984

Joachim von zur Gathen (1984). Ecuaciones Lineales sobre Anillos de Valuación. In Proc. 4th Int. Conf. Computer Science Santiago, Chile, 110-120. Local PDF (316KB).

Joachim von zur Gathen (1984). Hensel and Newton methods in valuation rings. Mathematics of Computation 42(166), 637-661. Link to electronic version.

Joachim von zur Gathen (1984). Hensel and Newton Methods in Valuation Rings. Mathematics of Computation 42(166), 637-661. Local PDF (4.5MB).

Joachim von zur Gathen (1984). Parallel algorithms for algebraic problems. SIAM Journal on Computing 13(4), 802-824. Link to electronic version. Extended abstract in Proceedings of the Fifteenth Annual ACM Symposium on Theory of Computing, Boston MA (1983). Local PDF (17.9MB).

Joachim von zur Gathen (1984). Parallel powering. In Proceedings of the 25th Annual IEEE Symposium on Foundations of Computer Science, Singer Island FL, 31-36. IEEE Computer Society Press. Final version in SIAM Journal on Computing (1987). Local PDF (298KB).

1983

Joachim von zur Gathen (1983). Computations in rings with valuations. Record of the Third Conference on Foundations of Software Technology and Theoretical Computer Science, Bangalore, ed. Joseph Mathai, 111-128.

Joachim von zur Gathen (1983). Factoring sparse multivariate polynomials. In Proceedings of the 24th Annual IEEE Symposium on Foundations of Computer Science, Tucson AZ, 172-179. Link to electronic version. Final version in Journal of Computer and System Sciences (1985). Local PDF (225KB).

Joachim von zur Gathen (1983). Parallel algorithms for algebraic problems. In Proceedings of the Fifteenth Annual ACM Symposium on Theory of Computing, Boston MA, 17-23. Link to electronic version. Final version in SIAM Journal on Computing (1984).

Joachim von zur Gathen (1983). Representations of rational Functions. In Proceedings of the 24th Annual IEEE Symposium on Foundations of Computer Science, Tucson AZ, 133-137. IEEE Computer Society Press. Link to electronic version. Final version in SIAM Journal on Computing (1986). Local PDF (178KB).

Joachim von zur Gathen (1983). Secant spaces to curves. Canadian Journal of Mathematics 35(4), 589-612. Link to electronic version. Local PDF (364KB).

J. von zur Gathen & E. Kaltofen (1983). Polynomial-time factorization of multivariate polynomials over finite fields. In Proceedings of the 10th International Colloquium on Automata, Languages and Programming ICALP 1983, Barcelona, Spain, J. Diaz, editor, volume 154 of Lecture Notes in Computer Science, 250-263. Springer-Verlag, Berlin. ISBN 3-540-12317-2. Link to electronic version. Final version in Mathematics of Computation (1985). Local PDF (209KB).

J. von zur Gathen & V. Strassen (1983). Некоторюе многочленю, имеющие бюсокую сложност вючисления Some polynomials that are hard to compute. (Russian). Kiberneticeskij sbornik, Nov. Ser. 20 59-63. Local PDF (2.1MB).

1982

A. Borodin, J. von zur Gathen & J. E. Hopcroft (1982). Fast parallel matrix and GCD Computations. Information and Control 52, 241-256. Link to electronic version. Extended Abstract in Proceedings of the 23rd Annual IEEE Symposium on Foundations of Computer Science, Chicago IL (1982). Local PDF (199KB).

A. Borodin, J. von zur Gathen & J. E. Hopcroft (1982). Fast parallel matrix and GCD Computations. In Proceedings of the 23rd Annual IEEE Symposium on Foundations of Computer Science, Chicago IL, 65-71. Link to electronic version. Final version in Information and Control (1982).

1980

J. von zur Gathen & V. Strassen (1980). Some polynomials that are hard to compute. Theoretical Computer Science 11, 331-335. Link to electronic version. Russian version in Kiberneticeskij sbornik (1983). Local PDF (2.0MB).

1978

Joachim von zur Gathen & Malte Sieveking (1978). A bound on solutions of linear integer equalities and inequalities. Proceedings of the American Mathematical Society 72(1), 155-158. Link to electronic version. Local PDF (97KB).

1976

J. von zur Gathen & M. Sieveking (1976). Weitere zum Erfüllungsproblem polynomial äquivalente kombinatorische Aufgaben. In Komplexität von Entscheidungsproblemen, volume 43 of Lecture Notes in Computer Science, 49-71. Springer-Verlag. Link to electronic version. Local PDF (528KB).