2022
Joachim von zur Gathen, Unicity distance of the Zodiac-340 cipher. Proc. HistoCrypt 2022, Amsterdam. number 188 in Linköping Electronic Conference Proceedings, pages 91– 100, 2022. URL https://doi.org/10.3384/ecp188. Also https://eprint.iacr.org/2021/1620. Cryptologia, to appear.
Local PDF (6.7 MB).
Joachim von zur Gathen & Guillermo Matera (2022). Shifted varieties and discrete neighborhoods around varieties. Journal of Symbolic Computation 109, pages 31-49. DOI https://doi.org/10.1016/j.jsc.2021.07.001. Also eprint arXiv:1812.07020. Local PDF (252 KB).
2021
Joachim von zur Gathen and Guillermo Matera, Interpolation by decomposable univariate polynomials. March 2021, preprint, ArXiv 2103.15926. Local PDF (408 kB).
2020
Joachim von zur Gathen, Mark Giesbrecht & Konstantin Ziegler (2020). Counting invariant subspaces and decompositions of additive polynomials. Journal of Symbolic Computation.
DOI https://doi.org/10.1016/j.jsc.2020.06.008.
Local PDF (1.1 MB).
Johannes vom Dorp, Joachim von zur Gathen, Daniel Loebenberger, Jan Lühr & Simon Schneider (2020). Comparative analysis of random generators. Algorithmic Combinatorics – Enumerative Combinatorics, Special Functions and Computer Algebra. Texts & Monographs in Symbolic Computation – A Series of the Research Institute for Symbolic Computation, Johannes Kepler University, Linz, Austria. Editors Veronika Pillwein and Carsten Schneider, Springer Nature Switzerland, DOI: https://doi.org/10.1007/978-3-030-44559-1_10.
Local PDF (627 KB)
Lucas Boppré Niehues, Joachim von zur Gathen, Lucas Pandolfo Perin & Ana Zumalacárregui (2020). Sidon sets and statistics of the ElGamal function, Cryptologia 44 (5), 438-450. DOI: 10.1080/01611194.2020.1790128
Local PDF (1.7 MB).
2019
Juan José Cabezas, Francisco Castro, Joachim von zur Gathen, Jorge Tiscornia & Alfredo Viola (2019). Uruguayan cryptography: printed book covers. Proceedings HistoCrypt 2019, 58-67. URL http://www.ep.liu.se/ecp/contents.asp?issue=156.
Local PDF (1.1 MB)
2018
Juan José Cabezas, Joachim von zur Gathen & Jorge Tiscornia (2018). Uruguayan cryptographic carpet.Proceedings HistoCrypt 2018, 21-27. URL http://www.ep.liu.se/ecp/contents.asp?issue=149.
Local PDF (222.2MB)
Joachim von zur Gathen (2018). Iteration entropy. Mathematics of Computation 88 (318), pages 1991-2003. DOI https://doi.org/10.1090/mcom/3382. Local PDF (819KB).
Joachim von zur Gathen & Guillermo Matera (2018). Explicit estimates for polynomial systems defining irreducible smooth complete intersections. Acta Arithmetica, to appear. eprint arXiv:1512.05598. Local PDF (328KB).
2017
Joachim von zur Gathen & Daniel Loebenberger (2017). Why one cannot estimate the entropy of English by sampling. Journal of Quantitative Linguistics 25, 77-106. https://doi.org/10.1080/09296174.2017.1341724. Local PDF (561KB).
Joachim von zur Gathen & Guillermo Matera (2017). Density of real and complex decomposable univariate polynomials. Quarterly Journal of Mathematics 68, 1227-1246. doi:10.1093/qmath/hax019. eprint arXiv:1407.0906v1. Link to electronic version. Local PDF (224KB).
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. e-print arXiv:1402.5449v1.Link to electronic version. Local PDF (238KB).
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. Local PDF (347KB). Extended abstract in Proceedings of the 2009 International Symposium on Symbolic and Algebraic Computation ISSAC ’09, Seoul, Korea (2009). Preprint 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.
2013
Raoul Blankertz, Joachim von zur Gathen & Konstantin Ziegler (2013). Compositions and collisions at degree p2. Journal of Symbolic Computation 59, 113-145. ISSN 0747-7171. Link to electronic version. Local PDF (875KB). Extended abstract 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.
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. Local PDF (315KB).
Extended abstract in Proceedings of the 2009 International Symposium on Symbolic and Algebraic Computation ISSAC ’09, Seoul, Korea (2009).
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.
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).
2012
Joachim von zur Gathen, Daniel Panario & Bruce Richmond (2012). Interval Partitions and Polynomial Factorization. Algorithmica 63, 363-397. Link to electronic version.
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. Local PDF (331KB). 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.
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 .
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.
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).
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.
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.
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.
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.
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 F2 in hardware. In IEEE Information Theory Workshop (2006), 107-111. IEEE, Punta del Este, Uruguay.
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.
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.
Joachim von zur Gathen & Jamshid Shokrollahi (2005). Efficient FPGA-based Karatsuba multipliers for polynomials over F2. 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.
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. Supplementary material:
http://www.mrw.interscience.wiley.com/suppmat/0020-7608/suppmat/100/suppmat_barnett.pdf.
http://www.mrw.interscience.wiley.com/suppmat/0020-7608/suppmat/100/suppmat_barnett.pdf.
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.
Joachim von zur Gathen (2004). Friederich Johann Buck: arithmetic puzzles in cryptography. Cryptologia XXVIII(4), 309-324. Link to electronic version.
Joachim von zur Gathen & Jürgen Gerhard (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.
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.
Joachim von zur Gathen & Michael Nöcker (2004). Fast arithmetic with general Gauß periods. Theoretical Computer Science 315, 419-452. Link to electronic version.
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.
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.
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.
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.
Joachim von zur Gathen (2003). Claude Comiers: the first arithmetical cryptography. Cryptologia XXVII(4), 339-349. Link to electronic version.
Joachim von zur Gathen, Jaime Gutierrez & Rosario Rubio (2003). Multivariate polynomial decomposition. Applicable Algebra in Engineering, Communication and Computing 14(1), 11-31.
Extended abstract in Proceedings of the Second Workshop on Computer Algebra in Scientific Computing, CASC ’99, München, Germany (1999).
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.
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).
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).
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).
C. Grabbe, M. Bednara, J. Shokrollahi, J. Teich & J. von zur Gathen (2003). FPGA Designs of parallel high performance GF(2233) Multipliers. In Proc. of the IEEE International Symposium on Circuits and Systems (ISCAS-03), volume II, 268-271. Bangkok, Thailand.
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.
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.
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.
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 F2. Mathematics of Computation 71(240), 1677-1698. Link to electronic version.
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.
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.
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.
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.
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.
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.
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).
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 Bulletin34(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).
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.
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.
Sandra Feisel, Joachim von zur Gathen & M. Amin Shokrollahi (1999). Normal bases via general Gauß periods. Mathematics of Computation68(225), 271-290. Link to electronic version.
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.
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.
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).
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.
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.
<a”>Local PDF (264KB).</a”>
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).
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.
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.
Joachim von zur Gathen & James R. Roche (1997). Polynomials with two values. Combinatorica 17(3), 345-362. Link to electronic version.
1996
Joachim von zur Gathen & Jürgen Gerhard (1996). Arithmetic and Factorization of Polynomials over F2. 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.
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).
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).
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.
K. Ma & J. von zur Gathen (1995). Tests for Permutation Functions. Finite Fields and Their Applications 1, 31-56. Link to electronic version.
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.
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.
Joachim von zur Gathen (1993). Parallel linear algebra. In Synthesis of parallel algorithms, J. Reif, editor, 573-617. Morgan Kaufmann Publishers.
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).
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.
Joachim von zur Gathen (1992). Processor-efficient exponentiation in finite fields. Information Processing Letters 41, 81-86. Link to electronic version.
Joachim von zur Gathen & Victor Shoup (1992). Computing Frobenius maps and factoring polynomials. computational complexity 2, 187-224. Link to electronic version.
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.
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.
Joachim von zur Gathen (1991). Tests for permutation polynomials. SIAM Journal on Computing 20(3), 591-602. Link to electronic version.
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).
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).
Joachim von zur Gathen (1990). Functional Decomposition of Polynomials: the Wild Case. Journal of Symbolic Computation 10, 437-452. Link to electronic version.
Joachim von zur Gathen (1990). Inversion in finite fields using logarithmic depth. Journal of Symbolic Computation 9, 175-183. Link to electronic version.
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.
Keju Ma & Joachim von zur Gathen (1990). Analysis of Euclidean Algorithms for Polynomials over Finite Fields. Journal of Symbolic Computation9, 429-455. Link to electronic version.
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.
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).
Joachim von zur Gathen (1987). Factoring polynomials and primitive elements for special primes. Theoretical Computer Science 52, 77-89. Link to electronic version.
Joachim von zur Gathen (1987). Feasible Arithmetic Computations: Valiant’s Hypothesis. Journal of Symbolic Computation 4, 137-172. Link to electronic version.
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).
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.
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).
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).
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.
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.
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).
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).
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).
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).
Joachim von zur Gathen (1983). Secant spaces to curves. Canadian Journal of Mathematics 35(4), 589-612. Link to electronic version.
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).
J. von zur Gathen & V. Strassen (1983). Некоторюе многочленю, имеющие бюсокую сложност вючисления Some polynomials that are hard to compute. (Russian). Kiberneticeskij sbornik, Nov. Ser. 20 59-63.
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).
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).
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.
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.