Appendix B References

B.1 Books

• Jonathan M. Borwein and Peter B. Borwein, “Pi and the AGM: A Study in Analytic Number Theory and Computational Complexity”, Wiley, 1998.
• Richard Crandall and Carl Pomerance, “Prime Numbers: A Computational Perspective”, 2nd edition, Springer-Verlag, 2005. https://www.math.dartmouth.edu/~carlp/
• Henri Cohen, “A Course in Computational Algebraic Number Theory”, Graduate Texts in Mathematics number 138, Springer-Verlag, 1993. https://www.math.u-bordeaux.fr/~cohen/
• Donald E. Knuth, “The Art of Computer Programming”, volume 2, “Seminumerical Algorithms”, 3rd edition, Addison-Wesley, 1998. https://www-cs-faculty.stanford.edu/~knuth/taocp.html
• John D. Lipson, “Elements of Algebra and Algebraic Computing”, The Benjamin Cummings Publishing Company Inc, 1981.
• Alfred J. Menezes, Paul C. van Oorschot and Scott A. Vanstone, “Handbook of Applied Cryptography”, http://www.cacr.math.uwaterloo.ca/hac/
• Richard M. Stallman and the GCC Developer Community, “Using the GNU Compiler Collection”, Free Software Foundation, 2008, available online https://gcc.gnu.org/onlinedocs/, and in the GCC package https://ftp.gnu.org/gnu/gcc/

B.2 Papers

• Yves Bertot, Nicolas Magaud and Paul Zimmermann, “A Proof of GMP Square Root”, Journal of Automated Reasoning, volume 29, 2002, pp. 225-252. Also available online as INRIA Research Report 4475, June 2002, https://hal.inria.fr/docs/00/07/21/13/PDF/RR-4475.pdf
• Christoph Burnikel and Joachim Ziegler, “Fast Recursive Division”, Max-Planck-Institut fuer Informatik Research Report MPI-I-98-1-022, https://www.mpi-inf.mpg.de/~ziegler/TechRep.ps.gz
• Torbjörn Granlund and Peter L. Montgomery, “Division by Invariant Integers using Multiplication”, in Proceedings of the SIGPLAN PLDI’94 Conference, June 1994. Also available https://gmplib.org/~tege/divcnst-pldi94.pdf.
• Niels Möller and Torbjörn Granlund, “Improved division by invariant integers”, IEEE Transactions on Computers, 11 June 2010. https://gmplib.org/~tege/division-paper.pdf
• Torbjörn Granlund and Niels Möller, “Division of integers large and small”, to appear.
• Tudor Jebelean, “An algorithm for exact division”, Journal of Symbolic Computation, volume 15, 1993, pp. 169-180. Research report version available ftp://ftp.risc.uni-linz.ac.at/pub/techreports/1992/92-35.ps.gz
• Tudor Jebelean, “Exact Division with Karatsuba Complexity - Extended Abstract”, RISC-Linz technical report 96-31, ftp://ftp.risc.uni-linz.ac.at/pub/techreports/1996/96-31.ps.gz
• Tudor Jebelean, “Practical Integer Division with Karatsuba Complexity”, ISSAC 97, pp. 339-341. Technical report available ftp://ftp.risc.uni-linz.ac.at/pub/techreports/1996/96-29.ps.gz
• Tudor Jebelean, “A Generalization of the Binary GCD Algorithm”, ISSAC 93, pp. 111-116. Technical report version available ftp://ftp.risc.uni-linz.ac.at/pub/techreports/1993/93-01.ps.gz
• Tudor Jebelean, “A Double-Digit Lehmer-Euclid Algorithm for Finding the GCD of Long Integers”, Journal of Symbolic Computation, volume 19, 1995, pp. 145-157. Technical report version also available ftp://ftp.risc.uni-linz.ac.at/pub/techreports/1992/92-69.ps.gz
• Werner Krandick and Tudor Jebelean, “Bidirectional Exact Integer Division”, Journal of Symbolic Computation, volume 21, 1996, pp. 441-455. Early technical report version also available ftp://ftp.risc.uni-linz.ac.at/pub/techreports/1994/94-50.ps.gz
• Makoto Matsumoto and Takuji Nishimura, “Mersenne Twister: A 623-dimensionally equidistributed uniform pseudorandom number generator”, ACM Transactions on Modelling and Computer Simulation, volume 8, January 1998, pp. 3-30. Available online http://www.math.sci.hiroshima-u.ac.jp/~m-mat/MT/ARTICLES/mt.pdf
• R. Moenck and A. Borodin, “Fast Modular Transforms via Division”, Proceedings of the 13th Annual IEEE Symposium on Switching and Automata Theory, October 1972, pp. 90-96. Reprinted as “Fast Modular Transforms”, Journal of Computer and System Sciences, volume 8, number 3, June 1974, pp. 366-386.
• Niels Möller, “On Schönhage’s algorithm and subquadratic integer GCD computation”, in Mathematics of Computation, volume 77, January 2008, pp. 589-607, https://www.ams.org/journals/mcom/2008-77-261/S0025-5718-07-02017-0/home.html
• Peter L. Montgomery, “Modular Multiplication Without Trial Division”, in Mathematics of Computation, volume 44, number 170, April 1985.
• Arnold Schönhage and Volker Strassen, “Schnelle Multiplikation grosser Zahlen”, Computing 7, 1971, pp. 281-292.
• Kenneth Weber, “The accelerated integer GCD algorithm”, ACM Transactions on Mathematical Software, volume 21, number 1, March 1995, pp. 111-122.
• Paul Zimmermann, “Karatsuba Square Root”, INRIA Research Report 3805, November 1999, https://hal.inria.fr/inria-00072854/PDF/RR-3805.pdf
• Paul Zimmermann, “A Proof of GMP Fast Division and Square Root Implementations”, https://homepages.loria.fr/PZimmermann/papers/proof-div-sqrt.ps.gz
• Dan Zuras, “On Squaring and Multiplying Large Integers”, ARITH-11: IEEE Symposium on Computer Arithmetic, 1993, pp. 260 to 271. Reprinted as “More on Multiplying and Squaring Large Integers”, IEEE Transactions on Computers, volume 43, number 8, August 1994, pp. 899-908.
• Niels Möller, “Efficient computation of the Jacobi symbol”, https://arxiv.org/abs/1907.07795