Book contents
- Frontmatter
- Contents
- Introduction
- 1 Cyclohexane, cryptography, codes, and computer algebra
- I Euclid
- II Newton
- III Gauß
- IV Fermat
- V Hilbert
- Appendix
- Sources of illustrations
- Sources of quotations
- List of algorithms
- List of figures and tables
- References
- List of notation
- Index
- The Holy Qur'ān (732)
- References
References
Published online by Cambridge University Press: 05 May 2013
Book contents
- Frontmatter
- Contents
- Introduction
- 1 Cyclohexane, cryptography, codes, and computer algebra
- I Euclid
- II Newton
- III Gauß
- IV Fermat
- V Hilbert
- Appendix
- Sources of illustrations
- Sources of quotations
- List of algorithms
- List of figures and tables
- References
- List of notation
- Index
- The Holy Qur'ān (732)
- References
Summary
A summary is not available for this content so a preview has been provided. Please use the Get access link above for information on how to access this content.
- Type
- Chapter
- Information
- Modern Computer Algebra , pp. 734 - 767Publisher: Cambridge University PressPrint publication year: 2013
References
, , and (2000), Factorization in ℤ[x]: The Searching Phase. In Proceedings of the 2000 International Symposium on Symbolic and Algebraic Computation ISSAC2000, St. Andrews, Scotland, ed. , 1–7. [465]Google Scholar
(1971), О суммировании рациональІΧ функций. Журнаn еычuсnuмеnьноў Мамемамuкu u мамемамuческоu Φuзuκu 11(4), 1071–1075. S. A. Abramov, On the summation of rational functions, U.S.S.R. Computational Mathematics and Mathematical Physics 11(4), 324–330. [671, 675]Google Scholar
(1975), Рациοнальня компοнента решения линейного рекуррентного соотношения первого порядка с рациональной правой частью. Журнаn еычuсnuмеnьноў Μамемамuκu u мамемамuчeckοu Φuзuκu 15(4), 1035–1039. S. A. AБpamov, The rational component of the solution of a first-order linear recurrence relation with rational right side, U.S.S.R. Computational Mathematics and Mathematical Physics 15(4), 216–221. [671]Google Scholar
(1989a), Задачи компьютерной алгебры, связанные с поиском полиномиальных решений линейных дифференциалых и разностных уравнений. Весмнuк Москоєскоѕо Унuєерсмема. Серuя 15. Вычuсnuмеnьная Мамемамuка u Кuбернемка 3, 56–60. S. A. Abpamob, Problems of computer algebra involved in the search for polynomial solutions of linear differential and difference equations, Moscow University Computational Mathematics and Cybernetics 3, 63–68. [641, 671]Google Scholar
(1989b), Рациональные решения линейных дифференциалых и разностных уравнений с полиномиалыми коэффициентами. Журнаn еьlчuсnuмеnbноў Μаmемаmuκu u маmемаmuчeckοu Φuзuκu 29(11), 1611–1620. S. A. Abramov, Rational solutions of linear differential and difference equations with polynomial coefficients, U.S.S.R. Computational Mathematics and Mathematical Physics 29(6), 7–12. [641, 671]Google Scholar
(1995), Rational solutions of linear difference and q-difference equations with polynomial coefficients. In Proceedings of the 1995 International Symposium on Symbolic and Algebraic Computation ISSAC '95, Montreal, Canada, ed. , ACM Press, 285–289. [671]Google Scholar
, , and (1995), On Polynomial Solutions of Linear Operator Equations. In Proceedings of the 1995 International Symposium on Symbolic and Algebraic Computation ISSAC '95, Montreal, Canada, ed. , ACM Press, 290–296. [641]Google Scholar
and (1999), Integration of solutions of linear functional equations. Integral Transforms and Special Functions 8(1–2), 3–12. [671]Google Scholar
and [] (1991), Fast Algorithms to Search for the Rational Solutions of Linear Differential Equations with Polynomial Coefficients. In Proceedings of the 1991 International Symposium on Symbolic and Algebraic Computation ISSAC '91,Bonn, Germany, ed. , ACM Press, 267–270. [641]Google Scholar
and (2001), Canonical Representations of Hypergeometric Terms. In Formal Power Series and Algebraic Combinatorics (FPSAC01), Tempe AZ. [675]Google Scholar
(1983), On Breaking Generalized Knapsack Public Key Cryptosystems. In Proceedings of the Fifteenth Annual ACM Symposium on Theory of Computing, Boston MA, ACM Press, 402–412. [509]Google Scholar
(1994), Algorithmic Number Theory-The Complexity Contribution. In Proceedings of the 35th Annual IEEE Symposium on Foundations of Computer Science, Santa Fe NM, ed. , IEEE Computer Society Press, Santa Fe NM, 88–113. [531]Google Scholar
and . (1986), Finding Irreducible Polynomials over Finite Fields. In Proceedings of the Eighteenth Annual ACM Symposium on Theory of Computing, Berkeley CA, ACM Press, 350–355. [421]Google Scholar
, , and (1974), The Design and Analysis of Computer Algorithms. Addison-Wesley, Reading MA. [286, 332]Google Scholar
, , and (1975), Evaluating polynomials at fixed sets of points. SIAM Journal on Computing 4, 533–539. [286, 292]Google Scholar
(1997), The Shortest Vector Problem in L2 is NP-hard for Randomized Reductions. Electronic Colloquium on Computational Complexity TR97-047. 33 pages. [496]Google Scholar
, , , , and (1994), Priority Encoding Transmission. In Proceedings of the 35th Annual IEEE Symposium on Foundations of Computer Science, Santa Fe NM, ed. , IEEE Computer Society Press, Los Alamitos CA, 604–612. [215]Google Scholar
, , and (1994), There are infinitely many Carmichael numbers. Annals of Mathematics 140, 703–722. [529, 532]Google Scholar
and (1990), The Method of Differentiating under the Integral Sign. Journal of Symbolic Computation 10, 571–591. [641, 671]Google Scholar
, , and (1995), Linear Time Erasure Codes With Nearly Optimal Recovery. In Proceedings of the 36th Annual IEEE Symposium on Foundations of Computer Science, Milwaukee WI, IEEE Computer Society Press, Los Alamitos CA, 512–519. [215]Google Scholar
(1989), Tests d'appartenance d'après un théorème de Kollár. Comptes Rendus de l'Académie des Sciences Paris, série I 309, 691–694. [618]Google Scholar
(1994), The Death of Proof? Semi-Rigorous Mathematics?You've Got to Be Kidding! The Mathematical Intelligencer 16(4), 16–18. [697]Google Scholar
Anonymous (1835), Wie sich die Division mit Zahlen erleichtern und zugleich sicherer ausführen läß:t, als auf die gewöhnliche Weise. Journal für die reine und angewandte Mathematik 13(3), 209–218. [41]
(1979), Digital filters: analysis and design. McGraw-Hill electrical engineering series: Communications and information theory section, McGraw-Hill, New York. [353]Google Scholar
(1983), A Proof that Euler Missed: Evaluating ζ (2) the Easy Way. The Mathematical Intelligencer 5(3), 59–60. Reprinted in Berggren, Borwein & Borwein (1997), 456–457. [62]Google Scholar
(c. 250 BC), Κύκλου μέτρησις (Measurement of a circle). In Opera Omnia, vol. I, ed. I. , 231–243. B. G. Teubner, Stuttgart, Germany, 1910. Reprinted 1972. [82]
(1918), Über Kongruenzen von dem fünften und höheren Graden nach einem Primzahlmodulus. Arkiv för matematik, astronomi och fysik 14(7), 1–46. [418]Google Scholar
and (1982), Pooling, splitting and restituting information to overcome total failure of some channels of communication. In Proceedings 1982 Symposium on Security and Privacy, IEEE Computer Society Press, Los Alamitos CA, 156–159. [131]Google Scholar
and (1982), On a primality test of Solovay and Strassen. SIAM Journal on Computing 11(4), 789–791. [532]Google Scholar
(1979), Monte Carlo algorithms in graph isomorphism testing. Technical Report 79-10, Département de Mathématique et Statistique, Université de Montréal. [198, 724]Google Scholar
, , and (1988), Fast Management of Permutation Groups. In Proceedings of the 29th Annual IEEE Symposium on Foundations of Computer Science, White Plains NY, IEEE Computer Society Press, Washington DC, 272–282. [724]Google Scholar
(1990), Number-theoretic algorithms. Annual Review of Computer Science 4, 119–172. [531]Google Scholar
(1996), Weil Bounds for Singular Curves. Applicable Algebra in Engineering, Communication and Computing 7, 289–298. [568]Google Scholar
, , and (2001), Factoring Polynomials over Special Finite Fields. Finite Fields and Their Applications 7, 5–28. [421]Google Scholar
, , and (1986), Sums of divisors, perfect numbers and factoring. SIAM Journal on Computing 15(4), 1143–1154. [532, 535]Google Scholar
and (1988), Factoring with cyclotomic polynomials. Mathematics of Computation 52 (185), 201–219. [568]Google Scholar
and (1996), Algorithmic Number Theory, Vol.1: Efficient Algorithms. MIT Press, Cambridge MA. [61, 421, 531, 533, 534]Google Scholar
and (1993), Sieve algorithms for perfect power testing. Algorithmica 9, 313–328. [287]Google Scholar
and (1996), Explicit bounds for primes in residue classes. Mathematics of Computation 65(216), 1717–1735. [529]Google Scholar
(1722), Das Wohltemperierte Klavier. BWV 846–893, Part I appeared in 1722, Part II in 1738. [86]Google Scholar
(1612), Problèmes plaisans et délectables, qui se font par les nombres. Pierre Rigaud, Lyon. [61]Google Scholar
, , and (1990), Using Strassen's Algorithm to Accelerate the Solution of Linear Systems. The Journal of Supercomputing 4(4), 357–371. [2, 337]Google Scholar
. and (1996), Padé Approximants. Encyclopedia of Mathematics and its Applications 59, Cambridge University Press, Cambridge, UK, 2nd edition. First edition published in two volumes by Addison-Wesley, Reading MA, 1982. [132]Google Scholar
and (1947), Mathematical Recreations & Essays. The Macmillan Company, New York, American edition. First edition 1892. [531, 534]Google Scholar
(1948), Music and ternary continued fractions. The American Mathematical Monthly 55, 545–555. [91]Google Scholar
(1968), Sylvester's Identity and Multistep Integer-Preserving Gaussian Elimination. Mathematics of Computation 22(101–104), 565–578. [132]Google Scholar
and (1999), Multibasic and Mixed Hypergeometric Gosper-Type Algorithms. Journal of Symbolic Computation 28, 711–736. [671]Google Scholar
and (1983), The complexity of partial derivatives. Theoretical Computer Science 22, 317–330. [352]Google Scholar
and (1988), On the complexity of computing syzygies. Journal of Symbolic Computation 6, 135–147. [618]Google Scholar
, , , , and (1996), Lower bounds on Hilbert's Nullstellensatz and propositional proofs. Proceedings of the London Mathematical Society 3, 1–26. [697]Google Scholar
and (1998), Propositional Proof Complexity: Past, Present, and Future. Bulletin of the European Association for Theoretical Computer Science 65, 66–89. [697]Google Scholar
and (1993), Gröbner Bases—A Computational Approach to Commutative Algebra. Graduate Texts in Mathematics 141, Springer-Verlag, New York. [618]Google Scholar
(1964), Recreations in the Theory of Numbers: The Queen of Mathematics Entertains. Dover Publications, Inc., New York. [534]Google Scholar
(1937), Men of Mathematics. Penguin Books Ltd., Harmondsworth, Middlesex. [219, 725, 726, 729]Google Scholar
, , , , , and (1995), MOLGEN, a computer algebra system for the generation of molecular graphs. In Computer Algebra in Science and Engineering,Bielefeld, Germany, August 1994, eds. , , , and , World Scientific, Singapore, 260–272. [698]Google Scholar
(1981), Probabilistic algorithms in finite fields. In Proceedings of the 22nd Annual IEEE Symposium on Foundations of Computer Science, Nashville TN, 394–398. [421]Google Scholar
, , and (1986), The complexity of elementary algebra and geometry. Journal of Computer and System Sciences 32, 251–264. [619]Google Scholar
and (1988), A Deterministic Algorithm For Sparse Multivariate Polynomial Interpolation. In Proceedings of the Twentieth Annual ACM Symposium on Theory of Computing, Chicago IL, ACM Press, 301–309. [498]Google Scholar
and (1990), Bounds for the Degrees in the Division Problem. Michigan Mathematical Journal 37, 25–43. [618]Google Scholar
, , and , eds. (1997), Pi: A Source Book. Springer-Verlag, New York. [90, 729, 735, 737, 749, 751, 753, 761, 763]
(1967), Factoring polynomials over finite fields. Bell System Technical Journal 46, 1853–1859. [401, 417, 420, 462]Google Scholar
(1970), Factoring Polynomials Over Large Finite Fields. Mathematics of Computation 24(11), 713–735. [198, 401, 406, 417, 419, 420, 421, 462, 465, 530]Google Scholar
(1984), Algebraic Coding Theory. Aegean Park Press. First edition McGraw Hill, New York, 1968. [215, 467]Google Scholar
, , and (1978), On the Inherent Intractability of Certain Coding Problems. IEEE Transactions on Information Theory IT-24(3), 384–386. [215]Google Scholar
and (1994), Optical character recognition for typeset mathematics. In Proceedings of the 1994 International Symposium on Symbolic and Algebraic Computation ISSAC '94, Oxford, UK, eds. and , ACM Press, 348–353. [640]Google Scholar
(1998a), Composing Power Series Over a Finite Ring in Essentially Linear Time. Journal of Symbolic Computation 26(3), 339–341. [353]Google Scholar
(1998b), Detecting perfect powers in essentially linear time. Mathematics of Computation 67(223), 1253–1283. [287]Google Scholar
(2001), Multidigit multiplication for mathematicians. 19 pp. http://cr.yp.to/papers/m3.ps. [247]
(1970), Emploi des Machines à Commande Numérique. Masson & Cie, Paris. English translation: Numerical Control, John Wiley & Sons, 1972. [138]Google Scholar
ÉTienne Bézout (1764), Recherches sur le degré des Équations résultantes de l'évanouissement des inconnues, Et sur les moyens qu'il convient d'employer pour trouver ces Équations. Histoire de l'académie royale des sciences, 288–338. Summary 88–91. [197, 724, 728]
(1841), Recherches sur la théorie des nombres entiers et sur la résolution de l'équation indéterminée du premier degré qui n'admet que des solutions entières. Journal de Mathématiques Pures et Appliquées 6, 449–494. [61]Google Scholar
, , and (1999), Elliptic Curves in Cryptography. London Mathematical Society Lecture Note Series 265, Cambridge University Press. [580]Google Scholar
and (1995), Continued fractions of algebraic numbers. In Computational Algebra and Number Theory, eds. and , Kluwer Academic Publishers, 137–155. [90]Google Scholar
, , , , and (2001), Factoring a binary polynomial of degree over one million. ACM SIGSAM Bulletin 35(1), 16–18. [461]Google Scholar
(1860), Calculus of finite differences. Chelsea Publishing Company, New York. 5th edition 1970. [669]Google Scholar
and (1974), Fast Modular Transforms. Journal of Computer and System Sciences 8(3), 366–386. [286, 306]Google Scholar
and (1975), The Computational Complexity of Algebraic and Numeric Problems. Theory of computation series 1, American Elsevier Publishing Company, New York. [306]Google Scholar
and (1990), On the Decidability of Sparse Univariate Polynomial Interpolation. In Proceedings of the Twenty-second Annual ACM Symposium on Theory of Computing, Baltimore MD, ACM Press, 535–545. [498]Google Scholar
, , and (1989), Ramanujan, Modular Equations, and Approximations to Pi or How to Compute One Billion Digits of Pi. The American Mathematical Monthly 96(3), 201–219. Reprinted in Berggren, Borwein & Borwein (1997), 623-641. [83]Google Scholar
and (1960), On A Class of Error Correcting Binary Group Codes. Information and Control 3, 68–79. [215]Google Scholar
(1989), Inferring Sequences Produced by Pseudo-Random Number Generators. Journal of the ACM 36(1), 129–141. [505]Google Scholar
and (1996), Fundamentals of Algorithmics. Prentice-Hall, Inc., Englewood Cliffs NJ. First published as Algorithmics - Theory & Practice, 1988. [41, 720]Google Scholar
(1939), On addition chains. Bulletin of the American Mathematical Society 45, 736–739.Google Scholar
(1976), Analysis of the binary Euclidean algorithm. In Algorithms and Complexity, ed. , 321–355. Academic Press, New York. [61]Google Scholar
(1989), Factorization of the eleventh Fermat number (preliminary report). AMS Abstracts 10, 89T-11–73. [542]Google Scholar
(1999), Factorization of the tenth Fermat number. Mathematics of Computation 68(225), 429–451. [542, 567]Google Scholar
, , and (1980), Fast Solution of Toeplitz Systems of Equations and Computation of Padé Approximants. Journal of Algorithms 1, 259–295. [332]Google Scholar
and (1978), Fast Algorithms for Manipulating Formal Power Series. Journal of the ACM 25(4), 581–595. [353, 354]Google Scholar
and (1981), Factorization of the Eighth Fermat Number. Mathematics of Computation 36(154), 627–630. Preliminary announcement in AMS Abstracts 1 (1980), 565. [542, 567]Google Scholar
(1984), Solving low density knapsacks. In Advances in Cryptology: Proceedings of CRYPTO '83, Plenum Press, New York, 25–37. [509]Google Scholar
(1985), Breaking iterated knapsacks. In Advances in Cryptology: Proceedings of CRYPTO '84, Santa Barbara, CA. Lecture Notes in Computer Science 196, Springer-Verlag, 342–358. [509]Google Scholar
, , , , and (1988), Factorizations ofbn ± 1, b = 2,3,5,6,7,10,11,12 up to high powers. Contemporary Mathematics 22, American Mathematical Society, Providence RI, 2nd edition. [542]Google Scholar
(1990), The Transcendental Risch Differential Equation. Journal of Symbolic Computation 9, 49–60. [641]Google Scholar
(1991), The Risch Differential Equation on an Algebraic Curve. In Proceedings of the 1991 International Symposium on Symbolic and Algebraic Computation ISSAC '91, Bonn, Germany, ed. , ACM Press, 241–246. [641]Google Scholar
(1992), On solutions of linear ordinary differential equations in their coefficient field. Journal of Symbolic Computation 13, 413–439. [641]Google Scholar
(1997), Symbolic Integration I—Transcendental Functions. Algorithms and Computation in Mathematics 1, Springer-Verlag, Berlin Heidelberg. [640, 641, 642]Google Scholar
(2000), On Solutions of Linear Ordinary Difference Equations in their Coefficient Field. Journal of Symbolic Computation 29, 841–877. [671]Google Scholar
and (1999), Solving Linear Ordinary Differential Equations over C(x, e∫ f(x)dx). In Proceedings of the 1999 International Symposium on Symbolic and Algebraic Computation ISSAC '99, Vancouver, Canada, ed. , ACM Press, 173–180. [641]Google Scholar
(1971), On Euclid's Algorithm and the Computation of Polynomial Greatest Common Divisors. Journal of the ACM 18(4), 478–504. [62, 197, 198, 199]Google Scholar
(1978), The Subresultant PRS Algorithm. ACM Transactions on Mathematical Software 4(3), 237–249. [199]Google Scholar
and (1971), On Euclid's Algorithm and the Theory of Subresultants. Journal of the ACM 18(4), 505–514. [197, 199, 332]Google Scholar
(1987), Bounds for the degrees in the Nullstellensatz. Annals of Mathematics 126, 577–591. [618]Google Scholar
(1965), Ein Algorithmus zum Auffinden der Basiselemente des Restklassenringes nach einem nulldimensionalen Polynomideal. PhD thesis, Philosophische Fakultät an der Leopold-Franzens-Universität, Innsbruck, Austria. [591, 609, 618]Google Scholar
(1970), Ein algorithmisches Kriterium für die Lösbarkeit eines algebraischen Gleichungssystems. aequationes mathematicae 4(3), 271–272 and 374–383. English translation by Michael Abramson and Robert Lumbert in Buchberger & Winkler (1998), 535-545. [618]Google Scholar
(1976), A theoretical basis for the reduction of polynomials to canonical forms. ACM SIGSAM Bulletin 10(3), 19–29. [618]Google Scholar
(1985), Gröbner Bases: An Algorithmic Method in Polynomial Ideal Theory. In Multidimensional Systems Theory, ed. , Mathematics and Its Applications, chapter 6, 184–232. D. Reidel Publishing Company, Dordrecht. [618]Google Scholar
(1987), History and basic features of the critical—pair/completion procedure. Journal of Symbolic Computation 3, 3–38. [618]Google Scholar
and , eds. (1998), Gröbner Bases and Applications. London Mathematical Society Lecture Note Series 251, Cambridge University Press, Cambridge, UK. [618, 738]
and (1974), Triangular Factorization and Inversion by Fast Matrix Multiplication. Mathematics of Computation 28(125), 231–236. [352]Google Scholar
(1998), On the Parallel Complexity of the Polynomial Ideal Membership Problem. Journal of Complexity 14, 176–189. [616]Google Scholar
, , and (1997), Algebraic Complexity Theory. Grundlehren der mathematischen Wissenschaften 315, Springer-Verlag. [88, 222, 286, 338, 352]Google Scholar
and (1998), Fast Recursive Division. Research Report MPI-I-98-1-022, Max-Planck-Institut für Informatik, Saarbrücken, Germany. http://domino.mpi-inf.mpg.de/internet/reports.nsf/NumberView/1998-1-022, iv + 27 pages. [286]Google Scholar
, , , , , and (1996/1997), Proof complexity in algebraic systems and bounded depth Frege systems with modular counting. computational complexity 6(3), 256–298. [697]Google Scholar
(1954), On the reducibility of polynomials over a finite field. Quarterly Journal of Mathematics Oxford 5(2), 102–107. [420]Google Scholar
(1987), A modification of a broken public-key cipher. In Advances in Cryptology: Proceedings of CRYPTO '86, Santa Barbara, CA, ed. . Lecture Notes in Computer Science 263, Springer-Verlag, 64–83. [576]Google Scholar
(1980), Un algorithme de construction des idempotents primitifs d'idéaux d'algèbres sur Fq. Comptes Rendus de l'Académie des Sciences Paris 291, 479–482. [420]Google Scholar
(1982), Un algorithme de construction des idempotents primitifs d'idéaux d'algèbres sur Fq. Annals of Discrete Mathematics 12, 55–63. [419]Google Scholar
(1983), Improving an Algorithm for Factoring Polynomials over a Finite Field and Constructing Large Irreducible Polynomials. IEEE Transactions on Information Theory IT-29(3), 378–385. [419]Google Scholar
, , and (1983), On a problem of Oppenheim concerning ‘Factorisatio Numerorum’. Journal of Number Theory 17, 1–28. [567]Google Scholar
, , and (1988), Borne simple exponentielle pour les degrés dans le théorème des zéros sur un corps de caractéristique quelconque. Comptes Rendus de l'Académie des Sciences Paris, série I 307, 255–258. [619]Google Scholar
, , and (1989), Some new effectivity bounds in computational geometry. In Algebraic Algorithms and Error-Correcting Codes: AAECC-6, Rome, Italy, 1988, ed. , Lecture Notes in Computer Science 357, 131–152. Springer-Verlag. [618]Google Scholar
(1987), A New Algebraic Method for Robot Motion Planning and Real Geometry. In Proceedings of the 28th Annual IEEE Symposium on Foundations of Computer Science, Los Angeles CA, IEEE Computer Society Press, Washington DC, 39–48. [619]Google Scholar
(1988), The Complexity of Robot Motion Planning. ACM Doctoral Dissertation Award 1987, MIT Press, Cambridge MA. [619]Google Scholar
(1989), On Arithmetical Algorithms over Finite Fields. Journal of Combinatorial Theory, Series A 50, 285–300. [280, 281, 282, 287]Google Scholar
and (2000), Factoring Polynomials over p-Adic Fields. In Algorithmic Number Theory, Fourth International Symposium, ANTS-IV, Leiden, The Netherlands, ed. , Springer-Verlag, 185–208. [466]Google Scholar
and (1991), On Fast Multiplication of Polynomials Over Arbitrary Algebras. Acta Informatica 28, 693–701. [245, 247]Google Scholar
and (1981), A New Algorithm for Factoring Polynomials Over Finite Fields. Mathematics of Computation 36(154), 587–592. [405, 406, 417, 418]Google Scholar
(1932), The arithmetic of polynomials in a Galois field. American Journal of Mathematics 54, 39–50. [426]Google Scholar
(1909/1910), Note on a new number theory function. Bulletin of the American Mathematical Society 16, 232–238. [531]Google Scholar
(1912), On composite numbers P which satisfy the Fermat congruence aP-1 ≡ 1 mod P. The American Mathematical Monthly 19, 22–27. [531]Google Scholar
and (1988), Parallel implementation of the quadratic sieve. The Journal of Supercomputing 1, 273–290. [531, 567]Google Scholar
(1513), Trattato del modo brevissimo di trouare la radice quadra delli numeri. Bartolomeo Cochi, Bologna. [89]Google Scholar
(1821), Sur la formule de Lagrange relative à l'interpolation. In Cours d'analyse de l'École Royale Polytechnique (Analyse algébrique), Note V. Imprimerie royale Debure frères, Paris. Œuvres Complètes, IIe série, tome III, Gauthier-Villars, Paris, 1897, 429–433. [132]Google Scholar
(1840), Mémoire sur l'élimination d'une variable entre deux équations algébriques. In Exercices d'analyse et de physique mathématique, tome 1er. Bachelier, Paris. Œuvres Complètes, IIe série, tome 11. Gauthier-Villars, Paris, 1913, 466–509. [197]Google Scholar
(1841), Mémoire sur diverses formules relatives à l'Algèbre et à la théorie des nombres. Comptes Rendus de l'Académie des Sciences Paris 12, p. 813 ff. Œuvres Complètes, Ire série, tome 61, Gauthier-Villars, Paris, 1888, 113–146. [131]Google Scholar
(1847), Mémoire sur les racines des équivalences correspondantes à des modules quelconques premiers ou non premiers, et sur les avantages que présente l'emploi de ces racines dans la théorie des nombres. Comptes Rendus de l'Académie des Sciences Paris 25, p. 37 ff. Œuvres Complètes, Ire série, tome 10, Gauthier-Villars, Paris, 1897, 324–333. [286]Google Scholar
(1970), On Canonical Forms and Simplification. Journal of the Association for Computing Machinery 17(2), 385–396. [640]Google Scholar
(1848), On the theory of elimination. The Cambridge and Dublin Mathematical Journal 3, 116–120. Also Cambridge Mathematical Journal 7. [197]Google Scholar
(1615), El ingenioso cavallero Don Quixote de la Mancha, segunda parte. Francisco de Robles, Madrid. [90]Google Scholar
(1995), Manin's Proof of the Hasse Inequality Revisited. Nieuw Archief voor Wiskunde, Vierdeserie 13(2), 219–232. [568]Google Scholar
, , and (1989), GCDHEU: Heuristic Polynomial GCD Algorithm Based On Integer GCD Computation. Journal of Symbolic Computation 7, 31–48. Extended Abstract in Proceedings of EUROSAM '84, ed. John Fitch, Lecture Notes in Computer Science 174, Springer-Verlag, 285–296. [202]Google Scholar
[] (1926), Die Bestimmung der Dichtigkeit einer Menge von Primzahlen, welche zu einer gegebenen Substitutionsklasse gehören. Mathematische Annalen 95, 191–228. [441, 465]Google Scholar
(1849), Обь оπредњ леіи числа πростБІχБ чиселБ не πревосхо дяЩихБ данной величинБІ. Mémoires présentés à l'Académie Impériale des sciences de St.-Pétersbourg par divers savants 6, 141–157. P. L. Chebyshev, Sur la fonction qui détermine la totalité des nombres premiers inférieurs à une limite donnée. Journal de Mathématiques Pures et Appliquées, I série 17 (1852), 341-365. Œuvres I, eds. A. Markoff and N. Sonin, 1899, reprint by Chelsea Publishing Co., New York, 26–48. [533]Google Scholar
(1852), Mémoire sur les nombres premiers. Journal de Mathématiques Pures et Appliquées, I série 17, 366–390. Mémoires présentées à l'Académie Impériale des sciences de St.-Pétersbourg par divers savants 6 (1854), 17–33. Œuvres I, eds. A. Markoff and N. Sonin, 1899, reprint by Chelsea Publishing Co., New York, 49–70. [533]Google Scholar
and (1997), Reducing Randomness via Irrational Numbers. In Proceedings of the Twenty-ninth Annual ACM Symposium on Theory of Computing, El Paso Tx, ACM Press, 200–209. [199]Google Scholar
and (2000), Reducing randomness via irrational numbers. SIAM Journal on Computing 29(4), 1247–1256. [199]Google Scholar
(1990), Efficient Factoring Polynomials over Local Fields and Its Applications. In Proceedings of the International Congress of Mathematicians 1990, Kyoto, Japan, vol. II, 1509–1519. Springer-Verlag. [466]Google Scholar
and (1984), Complexity of quantifier elimination in the theory of algebraically closed fields. In Proceedings of the 11th International Symposium Mathematical Foundations of Computer Science 1984, Praha, Czechoslovakia. Lecture Notes in Computer Science 176, Springer-Verlag, Berlin, 17–31. [619]Google Scholar
and (1988), A knapsack-type public key cryptosystem based on arithmetic in finite fields. IEEE Transactions on Information Theory IT-34(5), 901–909. Advances in Cryptology: Proceedings of CRYPTO 1984, Santa Barbara CA, Lecture Notes in Computer Science 196, Springer-Verlag, New York, 1985, 54–65. [509]Google Scholar
, , , and (1995), Parallelizing Strassen's Method for Matrix Multiplication on Distributed-Memory MIMD Architectures. Computers & Mathematics with Applications 30(2), 49–69. [352]Google Scholar
(1998a), Fonctions holonomes en calcul formel. PhD thesis, École Polytechnique, Paris. [671]Google Scholar
(1998b), Gröbner Bases, Symbolic Summation and Symbolic Integration. In Gröbner Bases and Applications, eds. and . London Mathematical Society Lecture Note Series 251, Cambridge University Press, Cambridge, UK, 32–60. [671]Google Scholar
(2000), An extension of Zeilberger's fast algorithm to general holonomic functions. Discrete Mathematics 217, 115–134. [671]Google Scholar
and (1998), Non-commutative Elimination in Ore Algebras Proves Multivariate Identities. Journal of Symbolic Computation 26(2), 187–227. [671]Google Scholar
, , , and (1991), On Zero-Testing and Interpolation of k-Sparse Multivariate Polynomials over Finite Fields. Theoretical Computer Science 84, 151–164. [498]Google Scholar
, , and (1996), Using the Groebner basis algorithm to find proofs of unsatisfiability. In Proceedings of the Twenty-eighth Annual ACM Symposium on Theory of Computing, Philadelphia PA, ACM Press, 174–183. [679]Google Scholar
(1966), Polynomial remainder sequences and determinants. The American Mathematical Monthly 73, 708–712. [197, 199]Google Scholar
(1967), Subresultants and Reduced Polynomial Remainder Sequences. Journal of the ACM 14(1), 128–142. [197, 199, 332]Google Scholar
(1971), The Calculation of Multivariate Polynomial Resultants. Journal of the ACM 18(4), 515–532. [197, 198]Google Scholar
(1973), Computer algebra of polynomials and rational functions. The American Mathematical Monthly 80, 725–55. [199]Google Scholar
(1975), Quantifier elimination for real closed fields by cylindrical algebraic decomposition. Lecture Notes in Computer Science 33, Springer-Verlag. [619]Google Scholar
(1979), Factoring univariate integral polynomials in polynomial average time. In Proceedings of EUROSAM '79,Marseille, France. Lecture Notes in Computer Science 72, 317–329. [455, 465]Google Scholar
and (1996), Improved Techniques for Factoring Univariate Polynomials. Journal of Symbolic Computation 21, 313–327. [465]Google Scholar
(1966), On the minimum computation time of functions. Doctoral Thesis, Harvard University, Cambridge MA. [247, 286]Google Scholar
(1971), The Complexity of Theorem-Proving Procedures. In Proceedings of the Third Annual ACM Symposium on Theory of Computing, Shaker Heights OH, ACM Press, 151–158. [722]Google Scholar
(1987), The Re-Discovery of the Fast Fourier Transform Algorithm. Mikrochimica Acta 3, 33–45. [247, 727]Google Scholar
(1990), How the FFT Gained Acceptance. In A History of Scientific Computing, ed. , ACM Press, New York, and Addison-Wesley, Reading MA, 133–140. [247]Google Scholar
and (1965), An Algorithm for the Machine Calculation of Complex Fourier Series. Mathematics of Computation 19, 297–301. [233, 247]Google Scholar
(1993), Solving Linear Equations Over GF(2): Block Lanczos Algorithm. Linear Algebra and its Applications 192, 33–60. [353]Google Scholar
(1994), Solving homogeneous linear equations over GF(2) via block Wiedemann algorithm. Mathematics of Computation 62(205), 333–350. [353]Google Scholar
and (1990), Matrix Multiplication via Arithmetic Progressions. Journal of Symbolic Computation 9, 251–280. [352, 420]Google Scholar
, , and (2003), Hybrid Methods. In Computer Algebra Handbook - Foundations, Applications, Systems, eds. , , and , 112–125. Springer-Verlag, Berlin, Heidelberg, New York. [41]Google Scholar
, , , and (2009), Introduction to Algorithms. MIT Press, Cambridge MA, London UK, third edition. [41, 368]Google Scholar
, , , , , and (1996), A World Wide Number Field Sieve Factoring Record: On to 512 Bits. In Advances in Cryptology-ASIACRYPT '96. Lecture Notes in Computer Science 1163, Springer-Verlag, 382–394. [569]Google Scholar
(1989), Primes of the Form x2 + ny2 -Fermat, Class Field Theory, and Complex Multiplication. John Wiley & Sons, New York. [568]Google Scholar
, , and (1997), Ideals, Varieties, and Algorithms: An Introduction to Computational Algebraic Geometry and Commutative Algebra. Undergraduate Texts in Mathematics, Springer-Verlag, New York, 2nd edition. First edition 1992. [614, 617, 618]Google Scholar
, , and (1998), Using Algebraic Geometry. Graduate Texts in Mathematics 185, Springer-Verlag, New York. [617]Google Scholar
(1750), Introduction a l'analyse des lignes courbes algébriques. Frères Cramer &Cl. Philibert, Genève. [198, 724]Google Scholar
and (1990), Thus Spake al-Khwārizmī: A Translation of the Text of Cambridge University Library Ms. Ii.vi.5. Historia Mathematica 17, 103–131. [727]Google Scholar
and (1925), Factorization of (yn 1), y = 2, 3, 5, 6, 7, 10, 11, 12 up to high powers (n). Francis Hodgson, London. [541]Google Scholar
, , and (1993), Average case error estimates for the strong probable prime test. Mathematics of Computation 61(203), 177–194. [532]Google Scholar
(1986), The Risch differential equation problem. SIAM Journal on Computing 15(4), 903–918. [641]Google Scholar
(1996), Hilbert subsets and s-integral points. Manuscripta Mathematica 89, 107–137. [498]Google Scholar
and (1978), A probabilistic remark on algebraic program testing. Information Processing Letters 7(4), 193–195. [88, 198]Google Scholar
and (1995), On Computing Greatest Common Divisors with Polynomials Given By Black Boxes for Their Evaluations. In Proceedings of the 1995 International Symposium on Symbolic and Algebraic Computation ISSAC '95, Montreal, Canada, ed. , ACM Press, 232–239. [199]Google Scholar
and (1998), FOXBOX: A System for Manipulating Symbolic Objects in Black Box Representation. In Proceedings of the 1998 International Symposium on Symbolic and Algebraic Computation ISSAC '98, Rostock, Germany, ed. , ACM Press, 30–37. [498]Google Scholar
(1919), History of the Theory of Numbers, vol. 1. Carnegie Institute of Washington. Published in 1919, 1920, and 1923 as publication 256. Reprinted by Chelsea Publishing Company, New York, N.Y., 1971. [88]Google Scholar
and (1976), New directions in cryptography. IEEE Transactions on Information Theory IT-22(6), 644–654. [503, 575, 576, 578, 581]Google Scholar
(1837), Beweis des Satzes, dass jede unbegrenzte arithmetische Progression, deren erstes Glied und Differenz ganze Zahlen ohne gemeinschaftlichen Factor sind, unendlich viele Primzahlen enthält. Abhandlungen der Königlich Preussischen Akademie der Wissenschaften, 45–81. Werke, Erster Band, ed. L. Kronecker, 1889, 315-342. Reprint by Chelsea Publishing Co., 1969. [528]Google Scholar
(1842), Verallgemeinerung eines Satzes aus der Lehre von den Kettenbrüchen nebst einigen Anwendungen auf die Theorie der Zahlen. Bericht über die Verhandlungen der Königlich Preussischen Akademie der Wissenschaften, 93–95. Werke, Erster Band, ed. , 1889, 635-638. Reprint by Chelsea Publishing Co., 1969. [506, 509]Google Scholar
(1849), Über die Bestimmung der mittleren Werthe in der Zahlentheorie. Abhandlungen der Königlich Preussischen Akademie der Wissenschaften, 69–83. Werke, Zweiter Band, ed. , 1897, 51-66. Reprint by Chelsea Publishing Co., 1969. [62]Google Scholar
(1893), Vorlesungen über Zahlentheorie, herausgegeben von R. Dedekind. Friedrich Vieweg & Sohn, Braunschweig, 4th edition. Corrected reprint, Chelsea Publishing Co., New York, 1968. First edition 1863. [707]Google Scholar
(1970), The Number of Steps in the Euclidean Algorithm. Journal of Number Theory 2, 414–422. [61]Google Scholar
(1981), Asymptotically Fast Factorization of Integers. Mathematics of Computation 36(153), 255–260. [541, 549, 569]Google Scholar
and (1995), NFS with Four Large Primes: An Explosive Experiment. In Advances in Cryptology: Proceedings of CRYPTO '95, Santa Barbara, CA, ed. . Lecture Notes in Computer Science 963, Springer-Verlag, 372–385. [569]Google Scholar
(1926), Über die Seltenheit der reduziblen Polynome und der Normalgleichungen. Mathematische Annalen 95, 247–256. [466]Google Scholar
(1987), On the Equivalence Between Berlekamp's and Euclid's Algorithms. IEEE Transactions on Information Theory IT-33(3), 428–431. [215]Google Scholar
(1855), Über musikalische Tonbestimmung und Temperatur. Abhandlungen der Mathematisch-Physischen Classe der Königlich Sächsischen Gesellschaft der Wissenschaften 4, 1–120 plus 1 table. [91]Google Scholar
(1990), The structure of polynomial ideals and Gröbner bases. SIAM Journal on Computing 19(4), 750–773. [618]Google Scholar
(1971), Utilisation d'un théorème de Fermat à la découverte des nombres premiers et notes sur les nombres de Fibonacci. Albert Blanchard, Paris. [532]Google Scholar
(2000), Optimizations of the subresultant algorithm. Journal of Pure and Applied Algebra 145, 149–163. [199]Google Scholar
(1846), Sur le nombre des divisions a effectuer pour obtenir le plus grand commun diviseur entre deux nombres entiers. Journal de Mathématiques Pures et Appliquées 11, 41–64. [61]Google Scholar
and (1997), On Randomized Lanczos Algorithms. In Proceedings of the 1997 International Symposium on Symbolic and Algebraic Computation ISSAC '97, Maui HI, ed. , ACM Press, 176–183. [353]Google Scholar
(1967), Systems of Distinct Representatives and Linear Algebra. Journal of Research of the National Bureau of Standards 71B(4), 241–245. [132]Google Scholar
and , eds. (1993), Computational algebraic geometry and commutative algebra. Symposia Mathematica 34, Cambridge University Press, Cambridge, UK. [617]
(1844), Einfacher Algorithmus zur Bestimmung des Werthes von. Journal für die reine und angewandte Mathematik 27(4), 317–318. [533]Google Scholar
(1990), A Very Short Proof of Dixon's Theorem. Journal of Combinatorial Theory, Series A 54, 141–142. [697]Google Scholar
and (1990), A Purely Verification Proof of the First Rogers-Ramanujan Identity. Journal of Combinatorial Theory, Series A 54, 309–311. [697]Google Scholar
and (1999), Computer Algebra Methods for Studying and Computing Molecular Conformations. Algorithmica 25(2/3), 372–402. Special Issue on Algorithms for Computational Biology. [698]Google Scholar
(1732/1733), Observationes de theoremate quodam Fermatiano aliisque ad numeros primos spectantibus. Commentarii academiae scientiarum imperalis Petropolitanae 6, 103–107. Eneström 26. Opera Omnia, series 1, volume 2, B. G. Teubner, Leipzig, 1915, 1–5. [76, 88, 513, 542]Google Scholar
(1734/1735a), Solutio problematis arithmetici de inveniendo numero qui per datos numeros divisus relinquat data residua. Commentarii academiae scientiarum imperalis Petropolitanae 7, 46–66. Eneström 36. Opera Omnia, series 1, volume 2, B. G. Teubner, Leipzig, 1915, 18–32. [131]Google Scholar
(1734/1735b), De summis serierum reciprocarum. Commentarii Academiae Scientiarum Petropolitanae 7, 123–134. Eneström 41. Opera Omnia, series 1, volume 14, B. G. Teubner, Leipzig, 1925, 73–86. [62]Google Scholar
(1736a), Mechanica sive motus scientia analytice exposita, Tomus I. Typographia Academia Scientiarum, Petropolis. Opera Omnia, series 2, volume 1, B. G. Teubner, Leipzig, 1912. [90]Google Scholar
(1736b), Theorematum quorundam ad numeros primos spectantium demonstratio. Commentarii academiae scientiarum imperalis Petropolitanae 8, 1741, 141–146. Eneström 54. Opera Omnia, series 1, volume 2, B. G. Teubner, Leipzig, 1915, 33-37. [88]Google Scholar
(1737), De fractionibus continuis dissertatio. Commentarii academiae scientiarum imperalis Petropolitanae 9, 1744, 98–137. Eneström 71. Opera Omnia, series 1, volume 14, B. G. Teubner, Leipzig, 1925, 187–215. [89, 90, 91]Google Scholar
(1743), Démonstration de la somme de cette suite 1 + ¼ + + ⅙ + ⅖ + + etc.Journal littéraire d'Allemagne, de Suisse et du Nord (La Haye) 2, 115–127. Bibliotheca Mathematica, Serie 3, 8 1907–1908, 54–60. Eneström 63. Opera Omnia, series 1, volume 14, 177–186. [62]Google Scholar
(1747/1748), Theoremata circa divisores numerorum. Novi commentarii academiae scientiarum imperalis Petropolitanae 1, 20–48. Summarium Novi commentarii academiae scientiarum imperalis Petropolitanae 1, 35–37. Eneström 134. Opera Omnia, series 1, volume 2, B. G. Teubner, Leipzig, 1915, 62–85. [131, 513, 542]Google Scholar
(1748a), Introductio in analysin infinitorum, tomus primus et secundus. , Lausanne. Opera Omnia, series 1, volume 8 and 9. Teubner, Leipzig, 1922/1945. [62, 90, 132]Google Scholar
(1748b), Sur une contradiction apparente dans la doctrine des lignes courbes. Mémoires de l'Académie des Sciences de Berlin 4, 1750, 219–233. Eneström 147. Opera Omnia, series 1, volume 26, Orell Füssli, Zürich, 1953, 34-45. [198]Google Scholar
(1748c), Démonstration sur le nombre des points où deux lignes des ordres quelconques peuvent se couper. Mémoires de l'Académie des Sciences de Berlin 4, 1750, 234–248. Eneström 148. Opera Omnia, series 1, volume 26, Orell Füssli, Zürich, 1953, 46–59. [197, 198]Google Scholar
(1754/1755), Demonstratio theorematis Fermatiani omnem numerum sive integrum sive fractum esse summam quatuor pauciorumve quadratorum. Novi commentarii academiae scientiarum imperalis Petropolitanae 5, 13–58. Summarium Novi commentarii academiae scientiarum imperalis Petropolitanae 5 6–7. Eneström 242. Opera Omnia, series 1, volume 1, B. G. Teubner, Leipzig, 1915, 339–372. [418]Google Scholar
(1760/1761), Theoremata arithmetica nova methodo demonstrata. Novi commentarii academiae scientiarum imperalis Petropolitanae 8, 74–104. Summarium Novi commentarii academiae scientiarum imperalis Petropolitanae 8, 15–18. Eneström 271. Opera Omnia, series 1, volume 2, B. G. Teubner, Leipzig, 1915, 531–555. [131]Google Scholar
(1761), Theoremata circa residua ex divisione potestatum relicta. Novi commentarii academiae scientiarum imperalis Petropolitanae 7, 49–82. Eneström 262. Opera Omnia, series 1, volume 2, B. G. Teubner, Leipzig, 1915, 493–518. [76, 418]Google Scholar
(1762/1763), Specimen algorithmi singularis. Novi commentarii academiae scientiarum imperalis Petropolitanae 9, 1764, 53–69. Summarium Novi commentarii academiae scientiarum imperalis Petropolitanae 9, 10-13. Eneström 281. Opera Omnia, series 1, volume 15, B. G. Teubner, Leipzig, 1927, 31–49. [90]Google Scholar
(1764), Nouvelle méthode d'éliminer les quantités inconnues des équations. Mémoires de l'Académie des Sciences de Berlin 20, 1766, 91–104. Eneström 310. Opera Omnia, series 1, volume 6, B. G. Teubner, Leipzig, 1921, 197–211. [197, 198]Google Scholar
(1783), De eximio methodi interpolationum in serierum doctrina. Opuscula analytica 1, 157–210. Eneström 555. Opera Omnia, ser. 1, vol. 15, Teubner, Leipzig, 1927, 435–497. [134]Google Scholar
(1994), Factorization of Polynomials over Finite Fields in Subexponential Time under GRH. In Algorithmic Number Theory, First International Symposium, ANTS-I, Ithaca, NY, USA. Lecture Notes in Computer Science 877, 209–219. [421]Google Scholar
and (1963), Computational methods of linear algebra. Freeman, San Francisco, London. Translated by . [132]Google Scholar
(1949), The transmission of information. Technical Report 65, M.I.T., Research Laboratory of Electronics. [307]Google Scholar
, , , and (1993), Efficient computation of zero-dimensional Gröbner bases by change of ordering. Journal of Symbolic Computation 16, 329–344. [619]Google Scholar
(1971), An Introduction to Probability Theory and its Applications. John Wiley & Sons, 2nd edition. [717]Google Scholar
(1636), Letter to Mersenne. In Œuvres de Fermat, vol. 2, Correspondance, eds. and , 63–71. Gauthier-Villars, Paris, 1894. French translation in volume 3, 1894, 286–293. [669]Google Scholar
(1972a), Polynomial evaluation via the division algorithm: the fast Fourier transform revisited. In Proceedings of the Fourth Annual ACM Symposium on Theory of Computing, Denver CO, ACM Press, 88–93. [306]Google Scholar
(1972b), On obtaining upper bounds on the complexity of matrix multiplication. In Complexity of Computer Computations, eds. and , 31–40. Plenum Press, New York. [353]Google Scholar
(1973), On the Algebraic Complexity of Matrix Multiplication. PhD thesis, Brown University, Providence RI. [353]Google Scholar
(1841), Traité élémentaire d'arithmétique à l'usage des candidats aux écoles spéciales. Derivaux, Strasbourg. [61]Google Scholar
, , and (1987), Algorithmes rapides en séquentiel et en parallèle pour l'élimination de quantificateurs en géometrie élémentaire. Séminaire Structures Ordonnées, U. E. R. de Mathématiques, Université de Paris VII. [619]Google Scholar
, , and (1990), Precise sequential and parallel complexity bounds for quantifier elimination over algebraically closed fields. Journal of Pure and Applied Algebra 67, 1–14. [619]Google Scholar
, , and (2001), The Complete Analysis of a Polynomial Factorization Algorithm over Finite Fields. Journal of Algorithms 40(1), 37–81. Extended Abstract in Proceedings of the 23rd International Colloquium on Automata, Languages and Programming ICALP 1996, Paderborn, Germany, ed. F. Meyer Auf der Heide and B. Monien, Lecture Notes in Computer Science 1099, Springer-Verlag, 1996, 232-243. [419]Google Scholar
and (1990), Singularity analysis of generating functions. SIAM Journal on Discrete Mathematics 3(2), 216–240. [697]Google Scholar
, , and (1989a), Lambda–Upsilon–Omega: An Assistant Algorithms Analyzer. In Algebraic Algorithms and Error-Correcting Codes: AAECC-6, Rome, Italy, 1988, ed. . Lecture Notes in Computer Science 357, Springer-Verlag, 201–212. [697]Google Scholar
, , and (1989b), Lambda–Upsilon–Omega—The 1989 CookBook. Rapport de Recherche 1073, INRIA. 116 pages, http://hal.inria.fr/docs/00/07/54/86/PDF/RR-1073.pdf. [697]Google Scholar
, , and (1991), Automatic average-case analysis of algorithms. Theoretical Computer Science 79, 37–109. [697]Google Scholar
(1997), Die älteste lateinische Schrift über das indische Rechnen nach al-Hwārizmī. Abhandlungen der Bayerischen Akademie der Wissenschaften, Philosophisch-historische Klasse, neue Folge 113, Verlag der Bayerischen Akademie der Wissenschaften, München. C. H. Beck'sche Verlagsbuchhandlung, München. [286, 727]Google Scholar
, , , and (1988), Dagwood: A System for Manipulating Polynomials Given by Straight-Line Programs. ACM Transactions on Mathematical Software 14(3), 218–240. [498]Google Scholar
(1977), Probabilistic machines can use less running time. In Information Processing 77—Proceedings of IFIP Congress 77, ed. , North-Holland, Amsterdam, 839–842. [88]Google Scholar
, , , , and (1988), Reconstructing truncated integer variables satisfying linear congruences. SIAM Journal on Computing 17(2), 262–280. [505]Google Scholar
(1881), Über Relationen zwischen den Näherungsbrüchen von Potenzreihen. Journal für die reine und angewandte Mathematik 90, 1–17. Gesammelte Abhandlungen, Band 2, herausgegeben von J.-P. Serre, Springer-Verlag, Berlin, 1968, 47–63. [132, 197]Google Scholar
(1896), Über Beziehungen zwischen den Primidealen eines algebraischen Körpers und den Substitutionen seiner Gruppe. Sitzungsberichte der Königlich Preussischen Akademie der Wissenschaften, Berlin, 689–702. [441, 465]Google Scholar
and (1955–1956), Effective procedures in field theory. Philosophical Transactions of the Royal Society of London 248, 407–432. [419]Google Scholar
(2009), Faster Integer Multiplication. SIAM Journal on Computing 39(3), 979–1005. [222, 244, 247]Google Scholar
(1973), The large sieve and probabilistic Galois theory. In Analytic Number Theory, ed. . Proceedings of Symposia in Pure Mathematics 24, American Mathematical Society, Providence RI, 91–101. [466]Google Scholar
and (1991), Wu-Ritt Characteristic sets and Their Complexity. In Discrete and Computational Geometry: Papers from the DIMACS Special Year, eds. , , and . DIMACS Series in Discrete Mathematics and Theoretical Computer Science 6, American Mathematical Society and ACM, 111–136. [619]Google Scholar
(1830), Sur la théorie des nombres. Bulletin des sciences mathématiques Férussac 13, 428–435. See also Journal de Mathématiques Pures et Appliquées 11 (1846), 398–407, and Écrits et mémoires d'évariste Galois, eds. Robert Bourgne and J.-P. Azra, Gauthier-Villars, Paris, 1962, 112–128. [198, 418, 421, 724, 728]Google Scholar
(1985), A Public Key Cryptosystem and a Signature Scheme Based on Discrete Logarithms. IEEE Transactions on Information Theory IT-31(4), 469–472. [580]Google Scholar
(2003), Factoring multivariate polynomials via partial differential equations. Mathematics of Computation 72(242), 801–822. [420]Google Scholar
and (1994), Berlekamp's and Niederreiter's Polynomial Factorization Algorithms. In Finite Fields: Theory, Applications and Algorithms, eds. and . Contemporary Mathematics 168, American Mathematical Society, 101–115. [420]Google Scholar
, , and (1998), Gauss periods: orders and cryptographical applications. Mathematics of Computation 67(221), 343–352. With microfiche supplement. [88, 580]Google Scholar
, , , and (2000), Algorithms for Exponentiation in Finite Fields. Journal of Symbolic Computation 29(6), 879–889. [88, 580]Google Scholar
and (1997), Tests and Constructions of Irreducible Polynomials over Finite Fields. In Foundations of Computational Mathematics, eds. and , 346–361. Springer Verlag. [419, 421]Google Scholar
and (1979), Computers and intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman and Co., San Francisco CA. [509, 722]Google Scholar
(1959), The Residue Number System. IRE Transactions on Electronic Computers, 140–147. [132]Google Scholar
(1984a), Hensel and Newton methods in valuation rings. Mathematics of Computation 42(166), 637–661. [419, 466, 497, 500]Google Scholar
(1984b), Parallel algorithms for algebraic problems. SIAM Journal on Computing 13(4), 802–824. [197, 199]Google Scholar
(1985), Irreducibility of Multivariate Polynomials. Journal of Computer and System Sciences Sciences 31(2), 225–264. [466, 497, 498, 724]Google Scholar
(1986), Representations and parallel computations for rational functions. SIAM Journal on Computing 15(2), 432–452. [131]Google Scholar
(1987), Factoring polynomials and primitive elements for special primes. Theoretical Computer Science 52, 77–89. [421]Google Scholar
(1988), Algebraic complexity theory. Annual Review of Computer Science 3, 317–347. [352]Google Scholar
(1990a), Functional Decomposition of Polynomials: the Tame Case. Journal of Symbolic Computation 9, 281–299. [286, 580, 581]Google Scholar
(1990b), Functional Decomposition of Polynomials: the Wild Case. Journal of Symbolic Computation 10, 437–452. [580]Google Scholar
(1991a), Tests for permutation polynomials. SIAM Journal on Computing 20(3), 591–602. [497]Google Scholar
(1991b), Values of polynomials over finite fields. Bulletin of the Australian Mathematical Society 43, 141–146. [425]Google Scholar
and (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, ed. , ACM Press, 1–9. Technical report tr-rsfb-96-018, University of Paderborn, Germany, 1996, 43 pages. Final version in Mathematics of Computation. http://www.juergen-gerhard.net/polyfactTR.ps. [279, 287, 467]Google Scholar
and (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, ed. , ACM Press, 40–47. [669, 670]Google Scholar
and (1998), Factoring Modular Polynomials. Journal of Symbolic Computation 26(5), 583–606.Google Scholar
Extended abstract in Proceedings of the 1996 International Symposium on Symbolic and Algebraic Computation ISSAC '96, Zürich, Switzerland, 10–17. [466]
and (1985), Factoring Sparse Multivariate Polynomials. Journal of Computer and System Sciences 31(2), 265–287. [497]Google Scholar
, , and (1996), Counting curves and their projections. computational complexity 6, 64–99. Extended abstract in Proceedings of the Twenty-fifth Annual ACM Symposium on Theory of Computing, San Diego CA (1993), 805–812. [198]Google Scholar
and (2000), Subresultants revisited. In Proceedings of LATIN 2000, Punta del Este, Uruguay, eds. Gastón H. Gonnet, , and . Lecture Notes in Computer Science 1776, Springer-Verlag, 318–342. Final version in von zur Gathen & Lücking (2003). [197]Google Scholar
and (2003), Subresultants revisited. Theoretical Computer Science 297, 199–239. [199, 746]Google Scholar
and (1997), Exponentiation in Finite Fields: Theory and Practice. In Applied Algebra, Algebraic Algorithms and Error-Correcting Codes: AAECC-12, Toulouse, France, eds. and . Lecture Notes in Computer Science 1255, Springer-Verlag, 88–113. [88, 580]Google Scholar
and (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, ed. , ACM Press, 83–90. [88]Google Scholar
and (2001), Factoring Polynomials Over Finite Fields: A Survey. Journal of Symbolic Computation 31(1–2), 3–17. [419]Google Scholar
and (1992), Computing Frobenius maps and factoring polynomials. computational complexity 2, 187–224. [405, 406, 419, 420, 467]Google Scholar
(1801), Disquisitiones Arithmeticae. Gerh. Fleischer Iun., Leipzig. English translation by , Springer-Verlag, New York, 1986. [131, 197, 372, 497, 728]Google Scholar
(1809), Theoria motus corporum coelestium in sectionibus conicis solem ambientum. Perthes und Besser, Hamburg. Werke VII, Königliche Gesellschaft der Wissenschaften, Göttingen, 1906, 1–288. Reprinted by Georg Olms Verlag, Hildesheim New York, 1973. [131]Google Scholar
(1810), Disquisitio de elementis ellipticis Palladis ex oppositionibus annorum 1803, 1804, 1805, 1807, 1808, 1809. Commentationes societatis regiae scientarium Gottingensis recentiores 1(1811), 3–24. Werke VI, Königliche Gesellschaft der Wissenschaften, Göttingen, 1874, 3–24. Reprinted by Georg Olms Verlag, Hildesheim New York, 1973. Announcement in Göttingische gelehrte Anzeigen (1810), Werke VI, 1874, 61–64. [131]Google Scholar
(1831), Theoria residuorum biquadraticorum, commentatio secunda. Commentationes societatis regiae scientiarum Gottingensis recentiores 7(1832). Werke II, Königliche Gesellschaft der Wissenschaften, Göttingen, 1863, 93–148. Reprinted by Georg Olms Verlag, Hildesheim New York, 1973. Announcement in Göttingische gelehrte Anzeigen (1831), Werke II, 1863, 169–178. [724]Google Scholar
(1849), Brief an Encke, 24. Dezember 1849. In Werke II, Handschriftlicher Nachlass, 444–447. Königliche Gesellschaft der Wissenschaften, Göttingen, 1863. Reprinted by Georg Olms Verlag, Hildesheim New York, 1973. [533]
(1863a), Solutio congruentiae Xm − 1 ≡ 0. Analysis residuorum. Caput sextum. Pars prior. In Werke II, Handschriftlicher Nachlass, ed. , 199–211. Königliche Gesellschaft der Wissenschaften, Göttingen. Reprinted by Georg Olms Verlag, Hildesheim New York, 1973. [417, 466, 724]Google Scholar
(1863b), Disquisitiones generales de congruentiis. Analysis residuorum caput octavum. In Werke II, Handschriftlicher Nachlass, ed. , 212–240. Königliche Gesellschaft der Wissenschaften, Göttingen. Reprinted by Georg Olms Verlag, Hildesheim New York, 1973. [62, 197, 373, 417, 418, 419, 421, 466, 729]Google Scholar
(1863c), Zur Theorie der complexen Zahlen. In Werke II, Handschriftlicher Nachlass, 387–398. Königliche Gesellschaft der Wissenschaften, Göttingen. Reprinted by Georg Olms Verlag, Hildesheim New York, 1973. [724]Google Scholar
(1866), Theoria interpolationis methodo nova tractata. In Werke III, Nachlass, 265–330. Königliche Gesellschaft der Wissenschaften, Göttingen. Reprinted by Georg Olms Verlag, Hildesheim New York, 1973. [90, 247]Google Scholar
(1884), Asymptotische Gesetze der Zahlentheorie. Denkschriften der kaiserlichen Akademie der Wissenschaften Wien 49, 37–80. [62]Google Scholar
and (1966), Fast Fourier transforms—for fun and profit. In Proceedings of the Fall Joint Computer Conference, San Francisco CA. AFIPS Conference Proceedings 29, Spartan books, Washington DC, 563–578. [247]Google Scholar
(1822), De la recherche des facteurs rationnels des polynomes. Annales de mathématiques pures et appliquées 12, 309–316. [465]Google Scholar
(1998), High degree solutions of low degree equations. In Proceedings of the 1998 International Symposium on Symbolic and Algebraic Computation ISSAC '98, Rostock, Germany, ed. , ACM Press, 284–289. [674]Google Scholar
(2001a), Fast Modular Algorithms for Squarefree Factorization and Hermite Integration. Applicable Algebra in Engineering, Communication and Computing 11(3), 203–226. [470, 640]Google Scholar
(2001b), Modular algorithms in symbolic summation and symbolic integration. Lecture Notes in Computer Science 3218, Springer-Verlag, Berlin, Heidelberg. [641, 670]Google Scholar
, , , and (2003), Shiftless Decomposition and Polynomial-time Rational Summation. In Proceedings of the 2003 International Symposium on Symbolic and Algebraic Computation ISSAC2003, Philadelphia PA, ed. , ACM Press, 119–126. [671]Google Scholar
, , and (1998), Certifying Inconsistency of Sparse Linear Systems. In Proceedings of the 1998 International Symposium on Symbolic and Algebraic Computation ISSAC '98, Rostock, Germany, ed. , ACM Press, 113–119. [353]Google Scholar
, , and (2003), Algorithms for Matrix Canonical Forms. In Computer Algebra Handbook – Foundations, Applications, Systems, eds. , , and , 38–41. Springer-Verlag, Berlin, Heidelberg, New York. [353]Google Scholar
(1977), Computational complexity of probabilistic Turing machines. SIAM Journal on Computing 6(4), 675–695. [198]Google Scholar
, , , , and (1991), “One sugar cube, please” or Selection strategies in the Buchberger algorithm. In Proceedings of the 1991 International Symposium on Symbolic and Algebraic Computation ISSAC '91, Bonn, Germany, ed. , ACM Press, 49–54. [619]Google Scholar
(1984), Some effectivity problems in polynomial ideal theory. In Proceedings of EUROSAM '84, Cambridge, UK, ed. , Lecture Notes in Computer Science 174, 159–171. Springer-Verlag, Berlin. [618]Google Scholar
and (1991), Algorithmes – disons rapides – pour la décomposition d'une variété algébrique en composantes irréductibles et équidimensionnelles. In Proceedings of Effective Methods in Algebraic Geometry MEGA '90, eds. and . Progress in Mathematics 94, Birkhäuser Verlag, Basel, 169–193. [619]Google Scholar
and (1970), Ring Closure and Local Conformational Deformations of Chain Molecules. Macromolecules 3(2), 178–187. [698]Google Scholar
(1977), A History of Numerical Analysis from the 16th through the 19th Century. Studies in the History of Mathematics and Physical Sciences 2, Springer-Verlag, New York. [286]Google Scholar
and (1984), A New Trapdoor Knapsack Public Key Cryptosystem. In Advances in Cryptology: Proceedings of EUROCRYPT 1984, Paris, France, eds. , , and . Lecture Notes in Computer Science 209, Springer-Verlag, Berlin, 150–158. [509]Google Scholar
(1885), Vorlesungen über Invariantentheorie. Erster Band: Determinanten. B. G. Teubner, Leipzig. Herausgegeben von Georg Kerschensteiner. [199, 332]Google Scholar
(1993), Discrete logarithms in GF(p) using the number field sieve. SIAM Journal on Discrete Mathematics 6(1), 124–138. [579]Google Scholar
(1978), Decision procedure for indefinite hypergeometric summation. Proceedings of the National Academy of Sciences of the USA 75(1), 40–42. [641, 662, 670, 671, 675]Google Scholar
(1994), An acceleration of the Niederreiter factorization algorithm in characteristic 2. Mathematics of Computation 62(206), 831–839. [420]Google Scholar
(1996), Combinatoire, Algorithmique et Géométrie des Polynômes. PhD thesis, École Polytechnique, Paris. [419]Google Scholar
, , and (1994), Concrete Mathematics. Addison-Wesley, Reading MA, 2nd edition. First edition 1989. [571, 669, 670, 717, 720]Google Scholar
(1883), Ueber die Entwickelung reeller Functionen in Reihen mittelst der Methode der kleinsten Quadrate. Journal für die reine und angewandte Mathematik 94, 41–73. [496]Google Scholar
(1990), Bounding the Coefficients of a Divisor of a Given Polynomial. Monatshefte für Mathematik 109, 271–277. [198]Google Scholar
(1988), Complexity of deciding Tarski algebra. Journal of Symbolic Computation 4(1/2). [619]Google Scholar
, , and (1990), Fast parallel algorithms for sparse multivariate polynomial interpolation over finite fields. SIAM Journal on Computing 19(6), 1059–1063. [498]Google Scholar
, , and (1994), Computational complexity of sparse rational interpolation. SIAM Journal on Computing 23(1), 1–11. [498]Google Scholar
(1987), Lectures on the Complexity of Bilinear Problems. Lecture Notes in Computer Science 245, Springer-Verlag. [352]Google Scholar
, , and (1993), Geometric Algorithms and Combinatorial Optimization. Algorithms and Combinatorics 2, Springer-Verlag, Berlin, Heidelberg, 2nd edition. First edition 1988. [496]Google Scholar
and (1980), Long Repetitive Patterns in Random Sequences. Zeitschrift für Wahrscheinlichkeitstheorie und verwandte Gebiete 53, 241–262. [205]Google Scholar
(1975), How to factor a number. In Proceedings of the Fifth Manitoba Conference on Numerical Mathematics, 49–89. [568, 569]Google Scholar
(1948), Eine Verallgemeinerung des Sturmschen Wurzelzählverfahrens. Commentarii Mathematici Helvetici 21, 99–116. [199]Google Scholar
(1893), Résolution d'une question relative aux déterminants. Bulletin des Sciences Mathématiques 17, 240–246. [496]Google Scholar
(1896), Sur la distribution des zéros de la fonction ζ(s) et ses conséquences arithmétiques. Bulletin de la Société mathématique de France 24, 199–220. [533]Google Scholar
(1985), The intractability of resolution. Theoretical Computer Science 39, 297–308. [678]Google Scholar
(1970), A retrospective and prospective survey of the Monte Carlo method. SIAM Review 12(1), 1–63. [198]Google Scholar
(1986), Coding and Information Theory. Prentice-Hall, Inc., Englewood Cliffs NJ, 2nd edition. First edition 1980. [308]Google Scholar
(1937), The Indian Mathematician Ramanujan. The American Mathematical Monthly 44, 137–155. Collected Papers, volume VII, Clarendon Press, Oxford, 1979, 612–630. [535]Google Scholar
(1940), A mathematician's apology. Cambridge University Press, Cambridge, UK. [26, 726, 728]Google Scholar
and (1985), An introduction to the theory of numbers. Clarendon Press, Oxford, 5th edition. First edition 1938. [62, 421, 532, 534]Google Scholar
, , and (2011), Practical Polynomial Factoring in Polynomial Time. In Proceedings of the 2011 International Symposium on Symbolic and Algebraic Computation ISSAC2011, San Jose CA, ed. , ACM Press, 163–170. [497]Google Scholar
(1977), Algebraic Geometry. Graduate Texts in Mathematics 52, Springer-Verlag, New York. [568]Google Scholar
(1891/1892), Note on resultants. Bulletin of the New York Mathematical Society 1, 223–224. [332]
(1933), Beweis des Analogons der Riemannschen Vermutung für die Artinschen und F. K. Schmidtschen Kongruenzzetafunktionen in gewissen elliptischen Fällen. Vorläufige Mitteilung.Google Scholar
Nachrichten von der Gesellschaft der Wissenschaften zu Göttingen, Mathematisch-Physikalische Klasse 42, 253–262. [568]
and (1998), The Security of Individual RSA Bits. In Proceedings of the 39th Annual IEEE Symposium on Foundations of Computer Science, Palo Alto CA, IEEE Computer Society Press, Los Alamitos CA, 510–519. [580]Google Scholar
and (1995), A new system of equations, based on geometric algebra, for the ring closure in cyclic molecules. In Computer Algebra in Science and Engineering, Bielefeld, Germany, August 1994, eds. , , , and , World Scientific, Singapore, 243–259. [698]Google Scholar
and (1951), The isomers of cyclohexane. Discussions of the Faraday Society 10, 88–93. [698]Google Scholar
, ed. (1925), The thirteen books of Euclid's elements, vol. 1. Dover Publications, Inc., New York, Second edition. First edition appeared 1908. Translated from the text of Heiberg. [24, 25]
, , and (1984), Gauss and the history of the Fast Fourier Transform. IEEE ASSP Magazine, 14–21. [247]Google Scholar
(1968), On the average length of a class of finite continued fractions. In Abhandlungen aus Zahlentheorie und Analysis. Zur Erinnerung an Edmund Landau (1877–1938), ed. , 87–96. VEB Deutscher Verlag der Wissenschaften, Berlin. Also in Number Theory and Analysis, a Collection of Papers in Honor of Edmund Landau (1877–1938), Plenum Press, New York, 1969. [61]Google Scholar
, , and (1991), Algorithms in Real Algebraic Geometry and Applications to Computational Geometry. In Discrete and Computational Geometry: Papers from the DIMACS Special Year, eds. , , and . DIMACS Series in Discrete Mathematics and Theoretical Computer Science 6, American Mathematical Society and ACM, 137–163. [619]Google Scholar
and (1981), Absolute Primality of Polynomials is Decidable in Random Polynomial Time in the Number of Variables. In Proceedings of the 8th International Colloquium on Automata, Languages and Programming ICALP 1981, Acre ('Akko), Israel. Lecture Notes in Computer Science 115, Springer-Verlag, 16–27. [497]Google Scholar
and (1999), Solving Difference Equations in Finite Terms. Journal of Symbolic Computation 27, 239–259. [671]Google Scholar
(1918), Eine neue Theorie der algebraischen Zahlen. Mathematische Zeitschrift 2, 433–452. [444, 466]Google Scholar
(1926), Die Frage der endlich vielen Schritte in der Theorie der Polynomideale. Mathematische Annalen 95, 736–788. [616]Google Scholar
(1872), Sur l'intégration des fractions rationnelles. Annales de Mathématiques, 2ème série 11, 145–148. [640]Google Scholar
(1990), Exploiting Fast Matrix Multiplication Within the Level 3 BLAS. ACM Transactions on Mathematical Software 16(4), 352–368. [337]Google Scholar
(1890), Ueber die Theorie der algebraischen Formen. Mathematische Annalen 36, 473–534. [586, 616, 618]Google Scholar
(1892), Ueber die Irreducibilität ganzer rationaler Functionen mit ganzzahligen Coefficienten. Journal für die reine und angewandte Mathematik 110, 104–129. [495, 586]Google Scholar
(1893), Ueber die Transcendenz der Zahlen e und π. Mathematische Annalen 43, 216–219. Nachrichten von der Königlichen Gesellschaft der Wissenschaften und der Georg-Augusts-Universität zu Göttingen 2 (1893), 113–116. Reprinted in Berggren, Borwein & Borwein (1997), 226–229. [90]Google Scholar
(1900), Mathematische Probleme. Nachrichten von der Königlichen Gesellschaft der Wissenschaften zu Göttingen, 253–297. Archiv für Mathematik und Physik, 3. Reihe 1 (1901), 44–63 and 213–237. English translation: Mathematical Problems, Bulletin of the American Mathematical Society 8 (1902), 437–479. [587, 726]Google Scholar
(1930), Probleme der Grundlegung der Mathematik. Mathematische Annalen 102, 1–9. [419]Google Scholar
(1964), Resolution of singularities of an algebraic variety over a field of characteristic zero. Annals of Mathematics 79(1), I: 109–203, II: 205–326. [591]Google Scholar
(1998), Rational Solutions of Linear Difference Equations. In Proceedings of the 1998 International Symposium on Symbolic and Algebraic Computation ISSAC '98, Rostock, Germany, ed. , ACM Press, 120–123. [671]Google Scholar
(1999), Finite singularities and hypergeometric solutions of linear recurrence equations. Journal of Pure and Applied Algebra 139, 109–131. [671]Google Scholar
(2002), Factoring polynomials and the knapsack problem. Journal of Number Theory 96(2), 167–189. [497]Google Scholar
(1997), Lazy Multiplication of Formal Power Series. In Proceedings of the 1997 International Symposium on Symbolic and Algebraic Computation ISSAC '97, Maui HI, ed. , ACM Press, 17–20. [469]Google Scholar
, , and , eds. (1997), Parametric Algebraic Curves and Applications. Special Issue of the Journal of Symbolic Computation 23(2/3). [618]Google Scholar
, , , , , and (1991), Coding Theory: The Essentials. Marcel Dekker, Inc., New York. [215]Google Scholar
(1971), Algorithms for partial fraction decomposition and rational function integration. In Proceedings 2nd ACM Symposium on Symbolic and Algebraic Manipulation, Los Angeles CA, ed. , ACM Press, 441–457. [627]Google Scholar
(1972), A fast method for interpolation using preconditioning. Information Processing Letters 1, 157–163. [306]Google Scholar
and (2002), Random Cayley Digraphs and the Discrete Logarithm. In Algorithmic Number Theory Symposium V, ANTS-V, eds. and . Lecture Notes in Computer Science 2369, Springer-Verlag, 100–114. [567]Google Scholar
(1985), Riemann Hypothesis and Finding Roots over Finite Fields. In Proceedings of the Seventeenth Annual ACM Symposium on Theory of Computing, Providence RI, ACM Press, 121–130. [421]Google Scholar
and (1998), Extended Hilbert Irreducibility and its Applications. In Proceedings of the 9th Annual ACM-SIAM Symposium on Discrete Algorithms SODA '98, 50–58. [498]Google Scholar
and (1998), Fast Rectangular Matrix Multiplication and Applications. Journal of Complexity 14, 257–299. [353, 405, 420]Google Scholar
(1952), A Method for the Construction of Minimum-Redundancy Codes. Proceedings of the I.R.E. 40(9), 1098–1101. [307, 368]Google Scholar
[] (1703), Descriptio Automati Planetarii. In Opuscula postuma, quae continent: Dioptricam. Commentarios de vitris figurandis. Dissertationem de corona & parheliis. Tractatum de motu/de vi centrifuga. Descriptionem automati planetarii. Cornelius Boutesteyn, Leyden. [89]Google Scholar
(1990), Abstract Algebra: An Introduction. Saunders College Publishing, Philadelphia PA. [703]Google Scholar
(1891), Ueber die angenäherte Darstellung der Irrationalzahlen durch rationale Brüche. Mathematische Annalen 39, 279–284. [90]Google Scholar
(1986), A Superexponential Lower Bound for Gröbner Bases and Church-Rosser Commutative Thue Systems. Information and Control 68(1–3), 196–206. [618]Google Scholar
(1836), De eliminatione variabilis e duabus aequationibus algebraicis. Journal für die reine und angewandte Mathematik 15, 101–124. [197]Google Scholar
(1846), Über die Darstellung einer Reihe gegebner Werthe durch eine gebrochne rationale Function. Journal für die reine und angewandte Mathematik 30, 127–156. [132, 197]Google Scholar
(1868), Allgemeine Theorie der kettenbruchähnlichen Algorithmen, in welchen jede Zahl aus drei vorhergehenden gebildet wird. Journal für die reine und angewandte Mathematik 69, 29–64. [91]Google Scholar
(1997), Practical Integer Division with Karatsuba Complexity. In Proceedings of the 1997 International Symposium on Symbolic and Algebraic Computation ISSAC '97, Maui HI, ed. , ACM Press, 339–341. [286]Google Scholar
(1990), A Catalog of Complexity Classes. In Handbook of Theoretical Computer Science, vol. A, ed. , 67–161. Elsevier Science Publishers B.V., Amsterdam, and The MIT Press, Cambridge MA. [724]Google Scholar
(1706), Synopsis Palmariorum Matheseos: or, a New Introduction to the Mathematics, London. [90]Google Scholar
(1965), Calculus of finite differences. Chelsea Publishing Company, New York. First edition Röttig and Romwalter, Sopron, Hungary, 1939. [669]Google Scholar
and (1998), A Survey of User Interfaces for Computer Algebra Systems. Journal of Symbolic Computation 25, 127–159. [21]Google Scholar
(1993), Inverting polynomials and formal power series. SIAM Journal on Computing 22(3), 552–559. [286]Google Scholar
(1982), Factorization of Polynomials. In Computer Algebra, Symbolic and Algebraic Computation, eds. , , and , 95–113. Springer-Verlag, New York, 2nd edition. [419]Google Scholar
(1983), On the Complexity of Finding Short Vectors in Integer Lattices. In Proceedings of EUROCAL 1983, London, UK. Lecture Notes in Computer Science 162, Springer-Verlag, Berlin / New York, 236–244. [497]Google Scholar
(1984), A Note on the Risch Differential Equation. In Proceedings of EUROSAM '84, Cambridge, UK, ed. . Lecture Notes in Computer Science 174, Springer-Verlag, Berlin, 359–366. [641]Google Scholar
(1985a), Polynomial-time reductions from multivariate to bi- and univariate integral polynomial factorization. SIAM Journal on Computing 14(2), 469–489. [497]Google Scholar
(1985b), Effective Hilbert Irreducibility. Journal of Computer and System Sciences 66, 123–137. [498]Google Scholar
(1989), Factorization of Polynomials Given by Straight-Line Programs. In Randomness and Computation, ed. , JAI Press, Greenwich CT, 375–412. [495, 497]Google Scholar
(1990), Polynomial factorization 1982–1986. In Computers in Mathematics, eds. and , Marcel Dekker, Inc., New York, 285–309. [419]Google Scholar
(1992), Polynomial Factorization 1987–1991. In Proceedings of LATIN '92, São Paulo, Brazil, ed. . Lecture Notes in Computer Science 583, Springer-Verlag, 294–313. [419]Google Scholar
(1995a), Effective Noether Irreducibility Forms and Applications. Journal of Computer and System Sciences 50(2), 274–295. [498]Google Scholar
(1995b), Analysis of Coppersmith's block Wiedemann algorithm for the parallel solution of sparse linear systems. Mathematics of Computation 64(210), 777–806. [353]Google Scholar
(2000), Challenges of Symbolic Computation: My Favourite Open Problems. Journal of Symbolic Computation 29(6), 891–919. With an Additional Open Problem By Robert M. Corless and David J. Jeffrey. [353]Google Scholar
and (1988), Improved Sparse Multivariate Polynomial Interpolation Algorithms. In Proceedings of the 1988 International Symposium on Symbolic and Algebraic Computation ISSAC '88, Rome, Italy, ed. . Lecture Notes in Computer Science 358, Springer-Verlag, 467–474. [498]Google Scholar
and (1994), Factoring High-Degree Polynomials by the Black Box Berlekamp Algorithm. In Proceedings of the 1994 International Symposium on Symbolic and Algebraic Computation ISSAC '94, Oxford, UK, eds. and , ACM Press, 90–98. [404, 405]Google Scholar
, , and (1983), A generalized class of polynomials that are hard to factor. SIAM Journal on Computing 12(3), 473–483. [465]Google Scholar
and (1989), Computing greatest common divisors and factorizations in quadratic number fields. Mathematics of Computation 53(188), 697–720. [132]Google Scholar
and (1991), On Wiedemann's Method of Solving Sparse Linear Systems. In Algebraic Algorithms and Error-Correcting Codes: AAECC-10, San Juan de Puerto Rico. Lecture Notes in Computer Science 539, Springer-Verlag, 29–38. [340, 351, 404]Google Scholar
and (1997), Fast Polynomial Factorization Over High Algebraic Extensions of Finite Fields. In Proceedings of the 1997 International Symposium on Symbolic and Algebraic Computation ISSAC '97, Maui HI, ed. , ACM Press, 184–188. [420]Google Scholar
and (1998), Subquadratic-Time Factoring of Polynomials over Finite Fields. Mathematics of Computation 67(223), 1179–1197. Extended Abstract in Proceedings of the Twenty-seventh Annual ACM Symposium on the Theory of Computing, Las Vegas NV, ACM Press, 1995, 398–406. [401, 405, 406, 420]Google Scholar
and (1990), Computing with Polynomials Given By Black Boxes for Their Evaluations: Greatest Common Divisors, Factorization, Separation of Numerators and Denominators. Journal of Symbolic Computation 9, 301–320. [496, 498]Google Scholar
, , and (1988), Addition Requirements for Matrix and Transposed Matrix Products. Journal of Algorithms 9, 354–364. [353]Google Scholar
(1988), Vectorization of Multiple-Precision Arithmetic Program and 201,326,000 Decimal Digits of π Calculation. In Supercomputing '88, Volume II: Science and Applications, 117–128. Reprinted in Berggren, Borwein & Borwein (1997), 576–587. [247]Google Scholar
(1987), Algorithmic geometry of numbers. Annual Review of Computer Science 2, 231–267. [496]Google Scholar
(1995), The Complexity of Computations. Proceedings of the Steklov Institute of Mathematics 211, 169–183. Translated from ТрудьІ Ϻатематичесκого Института имени B. A. Стеклова 211 (1995), 186–202. [247]Google Scholar
(1962), Умножение многозначньІх чисел на автоматах. Доκла∂ьι Ака∂емuu Ηаук CCCP 145, 293–294. A. Karatsuba and Yu. Ofman, Multiplication of multidigit numbers on automata, Soviet Physics–Doklady 7 (1963), 595–596. [223, 245]
and (1997), High-Precision Division and Square Root. ACM Transactions on Mathematical Software 23(4), 561–589. [286]Google Scholar
(1972), Reducibility among combinatorial problems. In Complexity of computer computations, eds. and , 85–103. Plenum Press, New York. [509, 722]Google Scholar
(1985), Theory of Summation in Finite Terms. Journal of Symbolic Computation 1, 303–315. [671]Google Scholar
and (2008), Fast modular composition in any characteristic. In Proceedings of the 49th Annual IEEE Symposium on Foundations of Computer Science, Philadelphia, PA, IEEE Computer Society Press, 146–155. [751]Google Scholar
and (2009), Fast polynomial factorization and modular composition. Merged work of Kedlaya & Umans (2008) and Umans (2008). SIAM Journal on Computing, to appear. Conference version in Proceedings of the 49th Annual IEEE Symposium on Foundations of Computer Science, Philadelphia, PA, 481–490. IEEE Computer Society Press. [339, 405, 406, 408, 420]Google Scholar
(1985), Fast algorithms for the characteristic polynomial. Theoretical Computer Science 36, 309–317. [352]Google Scholar
(1969), On the Factorization of Polynomials. Journal of Number Theory 1, 116–120. [417, 466]Google Scholar
, , , , , , , , , , and (2010), Factorization of a 768-Bit RSA Modulus. In Advances in Cryptology: Proceedings of CRYPTO '10, Santa Barbara, CA, ed. . Lecture Notes in Computer Science 6223, Springer-Verlag, Berlin, Heidelberg, New York, 333–350. [542]Google Scholar
(1995), Enumerating basic properties of polynomials over a finite field. South African Journal of Science 91, 10–11. [419]Google Scholar
and (1993), Counting irreducible factors of polynomials over a finite field. Discrete Mathematics 112, 103–118. [419]Google Scholar
and (1995), Distinct degree factorizations for polynomials over a finite field. Transactions of the American Mathematical Society 347(6), 2235–2243. [419]Google Scholar
(1970), The analysis of algorithms. In Proceedings of the International Congress of Mathematicians 1970, Nice, France, vol. 3, 269–274. [332, 724]Google Scholar
(1993), Johann Faulhaber and sums of powers. Mathematics of Computation 61(203), 277–294. [670]Google Scholar
(1997), The Art of Computer Programming, vol. 1, Fundamental Algorithms. Addison-Wesley, Reading MA, 3rd edition. First edition 1969. [308]Google Scholar
(1998), The Art of Computer Programming, vol. 2, Seminumerical Algorithms. Addison-Wesley, Reading MA, 3rd edition. First edition 1969. [25, 40, 61, 62, 88, 90, 247, 286, 417, 505, 531, 567]Google Scholar
and (1976), Analysis of a simple factorization algorithm. Theoretical Computer Science 3(3), 321–348. [567]Google Scholar
(1987a), A Course in Number Theory and Cryptography. Graduate Texts in Mathematics 114, Springer-Verlag, New York. [531, 568]Google Scholar
(1987b), Elliptic Curve Cryptosystems. Mathematics of Computation 48(177), 203–209. [580]Google Scholar
(1904), Sur une courbe continue sans tangente obtenue par une construction géométrique élémentaire. Arkiv för matematik, astronomi och fysik 1, 681–702. [287]Google Scholar
(1995), Algorithms for m-fold Hypergeometric Summation. Journal of Symbolic Computation 20, 399–417. [671]Google Scholar
(1998), Hypergeometric Summation. Advanced Lectures in Mathematics, Friedrich Vieweg & Sohn, Braunschweig / Wiesbaden. [670, 697]Google Scholar
(1988), Sharp effective Nullstellensatz. Journal of the American Mathematical Society 1(4), 963–975. [618]Google Scholar
and (2001a), Segment LLL-Reduction of Lattice Bases. In Cryptography and Lattices, International Conference (CaLC 2001), Providence RI, ed. . Lecture Notes in Computer Science 2146, Springer-Verlag, 67–80. [497]Google Scholar
and (2001b), Segment LLL-Reduction with Floating Point Orthogonalization. In Cryptography and Lattices, International Conference (CaLC 2001), Providence RI, ed. . Lecture Notes in Computer Science 2146, Springer-Verlag, 81–96. [497]Google Scholar
and (1986), Polynomial Decomposition Algorithms. Technical Report 86-773, Department of Computer Science, Cornell University, Ithaca NY. [752]Google Scholar
and (1989), Polynomial Decomposition Algorithms. Journal of Symbolic Computation 7, 445–456. An earlier version was published as Kozen & Landau (1986). [576, 581]Google Scholar
(1949), A Device for Quantizing, Grouping, and Coding Amplitude Modulated Pulses. M.Sc. thesis, Electrical Engineering Department, M.I.T. [307]Google Scholar
(1995), Bounded arithmetic, propositional logic and complexity theory. Encyclopedia of Mathematics and its Applications 60, Cambridge University Press, Cambridge, UK. [697]Google Scholar
(1873), Die verschiedenen Sturmschen Reihen und ihre gegenseitigen Beziehungen. Monatsberichte der Königlich Preussischen Akademie der Wissenschaften, Berlin, 117–154. [197]Google Scholar
(1878), Über Sturmsche Functionen. Monatsberichte der Königlich Preussischen Akademie der Wissenschaften, Berlin, 95–121. Werke, Zweiter Band, ed. , Leipzig, 1897, 37–70. Reprint by Chelsea Publishing Co., New York, 1968. [197]Google Scholar
(1881a), Zur Theorie der Elimination einer Variabeln aus zwei algebraischen Gleichungen. Monatsberichte der Königlich Preussischen Akademie der Wissenschaften, Berlin, 535–600. Werke, Zweiter Band, ed. , Leipzig, 1897, 113–192. Reprint by Chelsea Publishing Co., New York, 1968. [132, 137, 353]Google Scholar
(1881b), Auszug aus einem Briefe des Herrn Kronecker an E. Schering. Nachrichten der Akademie der Wissenschaften, Göttingen, 271–279. [197]Google Scholar
(1882), Grundzüge einer arithmetischen Theorie der algebraischen Grössen. Journal für die reine und angewandte Mathematik 92, 1–122. Werke, Zweiter Band, ed. K. Hensel, Leipzig, 1897, 237–387. Reprint by Chelsea Publishing Co., New York, 1968. [247, 465]Google Scholar
(1883), Die Zerlegung der ganzen Grössen eines natürlichen Rationalitäts-Bereichs in ihre irreductibeln Factoren. Journal für die reine und angewandte Mathematik 94, 344–348. Werke, Zweiter Band, ed. K. HENSEL, Leipzig, 1897, 409–416. Reprint by Chelsea Publishing Co., New York, 1968. [465]Google Scholar
A. H. ΚрьΙлов [A. ] (1931), О численном решении уравнения, которьІм в технических воπросах определяются частотьІ мальІх колебаний материальньІх систем (On numerical solutions which determine the frequencies of small oscillations of material systems in technical problems). ИзՅесмuя Ака∂емuu Наук CCCP, Ом∂епенuе Мамемамuческuх u есмесмՅенньιх наук (Bulletin de l'académie des sciences de l'URSS, Classe des sciences mathématiques et naturelles) 4, 491–539. [353]
and (1992), The Chinese Remainder Theorem. Journal of the Franklin Institute 329, 93–97. [131]Google Scholar
and (1996), Exponential Space Computation of Gröbner Bases. In Proceedings of the 1996 International Symposium on Symbolic and Algebraic Computation ISSAC '96, Zürich, Switzerland, ed. , ACM Press, 63–71. [616, 617]Google Scholar
(1974), On Computing Reciprocals of Power Series. Numerische Mathematik 22, 341–348. [286]Google Scholar
(1983), Summation in Finite Terms. In Computer Algebra, Symbolic and Algebraic Computation, eds. , , and , 71–77. Springer-Verlag, New York, 2nd edition. [671]Google Scholar
(1982a), Best simultaneous Diophantine approximations. I. Growth rates of best approximation denominators. Transactions of the American Mathematical Society 272(2), 545–554. [509]Google Scholar
(1982b), Best simultaneous Diophantine approximations. II. Behavior of consecutive best approximations. Pacific Journal of Mathematics 102(1), 61–88. [509]Google Scholar
(1985), The computational complexity of simultaneous Diophantine approximation problems. SIAM Journal on Computing 14(1), 196–209. [506, 509]Google Scholar
(1990), Pseudorandom Number Generators in Cryptography and Number Theory. In Cryptology and Computational Number Theory, ed. . Proceedings of Symposia in Applied Mathematics 42, American Mathematical Society, 115–143. [509, 580]Google Scholar
and (1977), Effective Versions of the Chebotarev Density Theorem. In Algebraic Number Fields, ed. , 409–464. Academic Press, London. [443]Google Scholar
and (1985), Solving Low-Density Subset Sum Problems. Journal of the ACM 32(1), 229–246. [509]Google Scholar
(1759), Recherches sur la méthode de maximis et minimis. Miscellanea Taurinensia 1. Œuvres, publiées par J.-A. Serret, vol. 1, 1867, Gauthier-Villars, Paris, 1–20. [131]Google Scholar
(1769), Sur la résolution des équations numériques. Mémoires de l'Académie des Sciences et Belles-Lettres de Berlin 23. Œuvres, publiées par J.-A. Serret, vol. 2, 1868, Gauthier-Villars, Paris, 539–578. [419]Google Scholar
(1770a), Additions au mémoire sur la résolution des équations numériques. Mémoires de l'Académie des Sciences et Belles-Lettres de Berlin 24. Œuvres, publiées par J.-A. Serret, vol. 2, 1868, Gauthier-Villars, Paris, 581–652. [90]Google Scholar
(1770b), Nouvelle méthode pour résoudre les problèmes indéterminés en nombres entiers. Mémoires de l'Académie des Sciences et Belles-Lettres de Berlin 24. Œuvres, publiées par J.-A. Serret, vol. 2, 1868, Gauthier-Villars, Paris, 655–726. [131]Google Scholar
(1795), Sur l'usage des courbes dans la solution des Problèmes. In Leçons élémentaires sur les mathématiques, Leçon cinquième. École Polytechnique, Paris. Œuvres, publiées par J.-A. Serret, vol. 7, 1877, Gauthier-Villars, Paris, 271–287. [131, 728]Google Scholar
(1798), Additions aux éléments d'algèbre d'Euler. Analyse indéterminée. In , Éléments d'algèbre, St. Petersburg. Œuvres, publiées par J.-A. Serret, vol. 7, 1877, Gauthier-Villars, Paris, 5–180. [90, 91]Google Scholar
(1990), On the Complexity of Computing a Gröbner Basis for the Radical of a Zero Dimensional Ideal. In Proceedings of the Twenty-second Annual ACM Symposium on Theory of Computing, Baltimore MD, ACM Press, 555–563. [618]Google Scholar
And (1990), Solving large sparse linear systems over finite fields. In Advances in Cryptology: Proceedings of CRYPTO '90, Santa Barbara, CA. Lecture Notes in Computer Science 537, Springer-Verlag, Berlin and New York, 109–133. [353]Google Scholar
, ed. (1997), Special Issue on Applications of Symbolic Computation to Research and Education. Journal of Symbolic Computation 23(5/6). [21]
(1761), Mémoire sur quelques propriétés remarquables des quantités transcendentes circulaires et logarithmiques. Histoire de l'Académie Royale des Sciences et des Belles-Lettres de Berlin 17, 265–322. Reprint of pages 265–276 in Berggren, Borwein & Borwein (1997), 129–140. [82]
(1844), Note sur la limite du nombre des divisions dans la recherche du plus grand commun diviseur entre deux nombres entiers. Comptes Rendus de l'Académie des Sciences Paris 19, 867–870. [61]Google Scholar
(1952), Solutions of systems of linear equations by minimized iterations. Journal of Research of the National Bureau of Standards 49, 33–53. [353]Google Scholar
(1905), Sur quelques théorèmes de M. Petrovitch relatifs aux zéros des fonctions analytiques. Bulletin de la Société Mathématique de France 33, 251–261. [165]Google Scholar
(1880), Note sur la décomposition du nombre 264 + 1 (Extrait). Comptes Rendus de l'Académie des Sciences Paris 91, p. 138. [542]Google Scholar
and (2000), Factoring polynomials over arbitrary finite fields. Theoretical Computer Science 234, 301–308. [421]Google Scholar
(1772), Recherches sur le calcul intégral et sur le système du monde. Mémoires de l'Académie Royale des Sciences II. Œuvres complètes de Laplace, vol. 8, Gauthier-Villars, Paris, 1891, 367–501. [724]Google Scholar
(2000), Effiziente Algorithmen zur Berechnung von Resultanten und Subresultanten. Berichte aus der Informatik, Shaker Verlag, Aachen. PhD thesis, University of Bonn, Germany. [198, 466]Google Scholar
and (1990), Integration of Rational Functions: Rational Computation of the Logarithmic Part. Journal of Symbolic Computation 9, 113–115. [640]Google Scholar
(1847), Sur le symbole a et quelques-unes de ses applications. Journal de Mathématiques Pures et Appliquées 12, 497–517. [533]Google Scholar
(1785), Recherches d'analyse indéterminée. Mémoires de l'Académie Royale des Sciences, 465–559. [198, 418, 420, 466, 468, 569]Google Scholar
(1982), On primality tests. SIAM Journal on Computing 11, 374–375. [537]
(1930), An extended theory of Lucas' functions. Annals of Mathematics, Series II 31, 419–448. [530]Google Scholar
(1935), On Lucas's test for the primality of Mersenne's numbers. Journal of the London Mathematical Society 10, 162–165. [530]Google Scholar
(1938), Euclid's algorithm for large numbers. The American Mathematical Monthly 45, 227–233. [332]Google Scholar
and (1931), On factoring large numbers. Bulletin of the American Mathematical Society 37, 770–776. [569]Google Scholar
(1683), Draft letter to Tschirnhaus. In Der Briefwechsel von Gottfried Wilhelm Leibniz mit Mathematikern, Erster Band, ed. , 446–450. Mayer & Müller, Berlin, 1899. Reprinted by Georg Olms Verlag, Hildesheim, 1987. [197]Google Scholar
(1697), Nova algebrae promotio. Undated manuscript, c. 1697. In Mathematische Schriften, vol. 7, ed. , 154–189. Halle, 1863. In: Gesammelte Werke aus den Handschriften der Königlichen Bibliothek zu Hannover, Band VII, Kapitel XV, reprinted by Georg Olms Verlag, Hildesheim, 1971. [88]Google Scholar
(1701), Initia mathematica. De ratione et proportione. Undated manuscript, c. 1701. In Mathematische Schriften, vol. 7, ed. , 1863, 40–49. Reprinted by Georg Olms Verlag, Hildesheim, 1971. [89]Google Scholar
[Gottfried Wilhelm Leibniz] (1703), Continuatio analyseos quadraturarum rationalium. Acta eruditorum, 19–26. [640]Google Scholar
(1995), The Euclidean algorithm in algebraic number fields. Expositiones Mathematicae 13, 385–416. [724]Google Scholar
(1984), Factoring Polynomials over Algebraic Number Fields. In Proceedings of the 11th International Symposium Mathematical Foundations of Computer Science 1984, Praha, Czechoslovakia. Lecture Notes in Computer Science 176, 389–396. [465]Google Scholar
(1987), Factoring multivariate polynomials over algebraic number fields. SIAM Journal on Computing 16, 591–598. [465]Google Scholar
(1990), Primality Testing. In Cryptology and Computational Number Theory, ed. . Proceedings of Symposia in Applied Mathematics 42, American Mathematical Society, 13–25. [531]Google Scholar
and (1990), Algorithms in Number Theory. In Handbook of Theoretical Computer Science, vol. A, ed. , 673–715. Elsevier Science Publishers B.V., Amsterdam, and The MIT Press, Cambridge MA. [531]Google Scholar
and , eds. (1993), The development of the number field sieve. Lecture Notes in Mathematics 1554, Springer-Verlag, Berlin. [569]
, , and (1982), Factoring Polynomials with Rational Coefficients. Mathematische Annalen 261, 515–534. [474, 497, 506]Google Scholar
, , , and (1990), The number field sieve. In Proceedings of the Twenty-second Annual ACM Symposium on Theory of Computing, Baltimore MD, ACM Press, 564–572. [569]Google Scholar
, , , and (1993), The factorization of the ninth Fermat number. Mathematics of Computation 61(203), 319–349. [534, 542]Google Scholar
and (1990), Factoring by electronic mail. In Advances in Cryptology: Proceedings of EUROCRYPT 1989, Houthalen, Belgium. Lecture Notes in Computer Science 434, Springer-Verlag, Berlin, 355–371. [531]Google Scholar
(1980b), Euclidean Number Fields 3. The Mathematical Intelligencer 2(2), 99–103. [724]Google Scholar
(1987), Factoring integers with elliptic curves. Annals of Mathematics 126, 649–673. [541, 557, 558, 565, 568]Google Scholar
(1990), Algorithms for finite fields. In Number theory and cryptography, ed. , London Mathematical Society Lecture Note Series 154, 76–85. Cambridge University Press, Cambridge, UK. [569]Google Scholar
(1991), Finding isomorphisms between finite fields. Mathematics of Computation 56(193), 329–347. [419]Google Scholar
and (1992), A rigorous time bound for factoring integers. Journal of the American Mathematical Society 5(3), 483–516. [569]Google Scholar
(1997), The cycloheptane molecule – a challenge to computer algebra. Invited lecture given at the 1997 International Symposium on Symbolic and Algebraic Computation ISSAC '97, Maui HI. [698]Google Scholar
(1973), Universal sequential search problems. Problems of Information Transmission 9, 265–266. Translated from Problemy Peredachi Informatsii 9(3) (1973), 115–116. [724]Google Scholar
and (1998), Checking Polynomial Identities over any Field: Towards a Derandomization? In Proceedings of the Thirtieth Annual ACM Symposium on Theory of Computing, Dallas TX, ACM Press, 438–447. [199]Google Scholar
(1987), The computational complexity of division in quadratic extension fields. SIAM Journal on Computing 16, 278–311.Google Scholar
and (2001), Sylvester-Habicht Sequences and Fast Cauchy Index Computation. Journal of Symbolic Computation 31, 315–341. [184, 199, 332]Google Scholar
and (1997), Finite Fields. Encyclopedia of Mathematics and its Applications 20, Cambridge University Press, Cambridge, UK, 2nd edition. First published by Addison-Wesley, Reading MA, 1983. [421, 711]Google Scholar
(1982), Introduction to Coding Theory. Graduate Texts in Mathematics 86, Springer-Verlag, New York. [215]Google Scholar
(1833a), Sur la détermination des Intégrales dont la valeur est algébrique. Journal de l'École Polytechnique 14, Premier Mémoire: 124–148, Second Mémoire: 149–193. [640]Google Scholar
(1833b), Note sur la détermination des intégrales dont la valeur est algébrique. Journal für die reine und angewandte Mathematik 10, 347–359. Errata 11 (1834), 406. [640]Google Scholar
(1835), Mémoire sur l'intégration d'une classe de fonctions transcendantes. Journal für die reine und angewandte Mathematik 13(2), 93–118. [623, 640]Google Scholar
(1971), Chinese remainder and interpolation algorithms. In Proceedings 2nd ACM Symposium on Symbolic and Algebraic Manipulation, Los Angeles CA, ed. , ACM Press, 372–391. [306]Google Scholar
(1981), Elements of Algebra and Algebraic Computing. Addison-Wesley, Reading MA. [247]Google Scholar
, , and (1993), Improvement of the degree setting in Gosper's algorithm. Journal of Symbolic Computation 16, 243–258. [670, 671]Google Scholar
(1964), Factorization of the general polynomial by means of its homomorphic congruential functions. The American Mathematical Monthly 71, 863–870. [419]Google Scholar
and (1966), Polynomial factor tables over finite fields. Mathematical Algorithms 1, 85–99. [419]Google Scholar
, , and (2000), New Structure Theorem for Subresultants. Journal of Symbolic Computation 29, 663–689. [199]Google Scholar
(1983), Computing rational zeroes of integral polynomials by p-adic expansion. SIAM Journal on Computing 12(2), 286–293. [466]Google Scholar
and (1979), A simple and effective public-key cryptosystem. COMSAT Technical Review 9(1), 15–24. [509]Google Scholar
Édouard Lucas (1878), Théorie des fonctions numériques simplement périodiques. American Journal of Mathematics 1, I: 184–240, II: 289–321. [530]
(1951), Die Rechenkunst bei Ǧamšīd b. Masͨūd al-Kāšī. Abhandlungen für die Kunde des Morgenlandes, XXXI, 1, Kommissionsverlag Franz Steiner GmbH, Wiesbaden. Herausgegeben von der Deutschen Morgenländischen Gesellschaft. [725]Google Scholar
(1953), Der Lehrbrief über den Kreisumfang (Ar-risāla al-muḥītīya) von Ǧamšīd B. Masḥūd Al-Kāšī. Abhandlungen der Deutschen Akademie der Wissenschaften zu Berlin, Klasse für Mathematik und allgemeine Naturwissenschaften 6, Akademie-Verlag, Berlin. [90]Google Scholar
, , and (1986), On the Zeros of the Riemann Zeta Function in the Critical Strip. IV. Mathematics of Computation 46(174), 667–681. [533]Google Scholar
and (1990), Analysis of Euclidean Algorithms for Polynomials over Finite Fields. Journal of Symbolic Computation 9, 429–455. [62]
(1902), Some formulæ in elimination. Proceedings of the London Mathematical Society 35, 3–27. [197, 619]Google Scholar
(1916), The algebraic theory of modular systems. Cambridge University Press, Cambridge, UK. Reissued 1994. [197, 619, 728, 729]Google Scholar
(1922), Note on the resultant of a number of polynomials of the same degree. Proceedings of the London Mathematical Society, Second Series 21, 14–21. [197, 619]Google Scholar
(1975), On rational integration. Technical Report UCP-38, Department of Computer Science, University of Utah. [642]Google Scholar
(1742), A treatise of fluxions. 2 volumes, Edinburgh. 2nd ed., London, 1801; French translation Paris, 1749. [286]Google Scholar
and (1977), The Theory of Error-Correcting Codes. Mathematical Library 16, North-Holland, Amsterdam. [215]Google Scholar
(1912/1913), Leibniz auf der Suche nach einer allgemeinen Primzahlgleichung. Bibliotheca Mathematica, Serie 3, 13, 29–61. [88, 531]Google Scholar
(1993), On Computing Closed Forms for Indefinite Summations. Journal of Symbolic Computation 16, 355–376. [671]Google Scholar
(1956), О сравнениях третьей степени по простому модулю. Извесмuя Ака∂емuu Ηаук CCCP, Серuя Маmемаuческая 20, 673–678. YU. I. MANIN, On cubic congruences to a prime modulus, American Mathematical Society Translations, Series 2, 13 (1960), 1–7. [568]Google Scholar
(1965), Step by step decoding of the Bose-Chaudhuri-Hocquenghem codes. IEEE Transactions on Information Theory IT–11, 580–585. [215]Google Scholar
(1970), Диоϕантовость перечислимих множеств. Докла∂ьι Ακа∂емuu Наук CCCP 191(2), 279–282. Yu. V. Matiyasevich, Enumerable sets are Diophantine, Soviet Mathematics Doklady 11(2), 354–358. [89]Google Scholar
(1993), Докла∂ьι Ακа∂емuu Наук. Nauka, Moscow. Yuri V. Matiyasevich, Hilbert's Tenth Problem, Foundations of Computing Series, The MIT Press, Cambridge MA, 1993. [89, 640]Google Scholar
and (1999), The relationship between breaking the Dif?e-Hellman protocol and computing discrete logarithms. SIAM Journal on Computing 28(5), 1689–1721. [580]Google Scholar
(1984), An algorithm for the general Petri net reachability problem. SIAM Journal on Computing 13(3), 441–460. [697]Google Scholar
(1989), Membership in Polynomial Ideals over Q Is Exponential Space Complete. In Proceedings of the 6th Annual Symposium on Theoretical Aspects of Computer Science STACS '89, Paderborn, Germany, eds. and . Lecture Notes in Computer Science 349, Springer-Verlag, 400–406. [616]Google Scholar
(1992), Polynomial ideals and applications. Mitteilungen der Mathematischen Gesellschaft in Hamburg 12(4), 1207–1215. Festschrift zum 300jährigen Bestehen der Gesellschaft. [616, 697]Google Scholar
(1995), On Polynomial Ideals, Their Complexity, and Applications. In Proceedings of the 10th International Conference on Fundamentals of Computation Theory FCT '95, Dresden, Germany, ed. . Lecture Notes in Computer Science 965, Springer-Verlag, 89–105. [616, 697]Google Scholar
(1997), Some complexity results for polynomial ideals. Journal of Complexity 13, 303–325. [618]Google Scholar
and (1982), The Complexity of the Word Problems for Commutative Semigroups and Polynomial Ideals. Advances in Mathematics 46, 305–329. [616, 617, 618]Google Scholar
and (2010), Degree Bounds for Gröbner Bases of Low-Dimensional Polynomial Ideals. Proceedings of the 2010 International Symposium on Symbolic and Algebraic Computation ISSAC2010, Munich, Germany, 21–27. [617]Google Scholar
(1990), The Discrete Logarithm Problem. In Cryptology and Computational Number Theory, ed. . Proceedings of Symposia in Applied Mathematics 42, American Mathematical Society, 49–74. [580]Google Scholar
(1969), Factorization of Polynomials over Finite Fields. Mathematics of Computation 23, 861–867. [419]Google Scholar
(1993), Elliptic curve public key cryptosystems. Kluwer Academic Publishers, Boston MA. [580]Google Scholar
and (1978), Hiding information and signatures in trapdoor knapsacks. IEEE Transactions on Information Theory IT–24(5), 525–530. [503, 504, 509, 576]Google Scholar
(1636), Harmonie universelle contenant la théorie et la pratique de la musique. Sebastien Cramoisy, Paris. Reprinted by Centre National de la Recherche Scientifique, Paris, 1975. [86]Google Scholar
(1897), Über eine zahlentheoretische Function. Sitzungsberichte der Akademie der Wissenschaften, Wien, Mathematisch-Naturwissenschaftliche Classe 106, 761–830. [508]Google Scholar
and (1949), The Monte Carlo Method. Journal of the American Statistical Association 44, 335–341. [198]Google Scholar
and (1998), Efficient algorithms for computing the Jacobi symbol. Journal of Symbolic Computation 26(4), 509–523. [533]Google Scholar
(1974), An Inequality About Factors of Polynomials. Mathematics of Computation 28(128), 1153–1157. [198]Google Scholar
(1982), Some Useful Bounds. In Computer Algebra, Symbolic and Algebraic Computation, eds. , , and , 259–263. Springer-Verlag, New York, 2nd edition. [198]Google Scholar
(1988), An Inequality about Irreducible Factors of Integer Polynomials. Journal of Number Theory 30, 156–166. [198]Google Scholar
(1989), Mathématiques pour le calcul formel. Presses Universitaires de France, Paris. English translation: Mathematics for Computer Algebra, Springer-Verlag, New York, 1992. [198]Google Scholar
and (1994), On the Smallest Divisor of a Polynomial. Journal of Symbolic Computation 17, 277–282. [198]Google Scholar
and (1988), Calcul des racines d-ièmes dans un corps fini. Comptes Rendus de l'Académie des Sciences Paris 290, 205–206. [421]Google Scholar
[] (1948), О разложении определителя, элементами которого служат полиномьІ (On the expansion of a determinant whose entries are polynomials). Πрuкла∂ная маmемаmuка u механuка (Prikladnaya matematika i mekhanika) 12, 219–222. [132]
(1976), Riemann's Hypothesis and Tests for Primality. Journal of Computer and System Sciences 13, 300–317. [532]Google Scholar
(1986), Use of Elliptic Curves in Cryptography. In Advances in Cryptology: Proceedings of CRYPTO '85, Santa Barbara, CA, ed. . Lecture Notes in Computer Science 218, Springer-Verlag, Berlin, 417–426. [580]Google Scholar
(1973), Fast computation of gcd's. In Proceedings of the Fifth Annual ACM Symposium on Theory of Computing, Austin TX, ACM Press, 142–151. [332]Google Scholar
(1976), Practical Fast Polynomial Multiplication. In Proceedings of the 1976 ACM Symposium on Symbolic and Algebraic Computation SYMSAC '76, Yorktown Heights NY, ed. , ACM Press, 136–148. [247]Google Scholar
(1977a), On the Efficiency of Algorithms for Polynomial Factoring. Mathematics of Computation 31(137), 235–250. [421]Google Scholar
(1977b), On computing closed forms for summation. In Proceedings of the 1977 MACSYMA Users Conference, Berkeley CA, NASA, Washington DC, 225–236. [671, 673]Google Scholar
and (1972), Fast modular transform via division. In Proceedings of the 13th Annual IEEE Symposium on Switching and Automata Theory, Yorktown Heights NY, IEEE Press, New York, 90–96. [306]Google Scholar
and (1984), Upper and lower bounds for the degree of Gröbner bases. In Proceedings of EUROSAM '84, Cambridge, UK, ed. . Lecture Notes in Computer Science 174, Springer-Verlag, New York, 172–183. [618]Google Scholar
(1980), Evaluation and comparison of two ef?cient probabilistic primality testing algorithms. Theoretical Computer Science 12, 97–108. [532, 533]Google Scholar
(1985), Modular Multiplication Without Trial Division. Mathematics of Computation 44(170), 519–521. [288]Google Scholar
(1991), Factorization of X216091 + X +1 mod 2—A problem of Herb Doughty. Manuscript. [280]
(1992), An FFT Extension of the Elliptic Curve Method of Factorization. PhD thesis, University of California, Los Angeles CA. http://research.microsoft.com/en-us/um/people/petmon/thesis.pdf. [287, 308]Google Scholar
(1995), A Block Lanczos Algorithm for Finding Dependencies over GF(2). In Advances in Cryptology: Proceedings of EUROCRYPT1995, Saint-Malo, France, eds. and . Lecture Notes in Computer Science 921, Springer-Verlag, 106–120. [353]Google Scholar
(1896), A doubly-infinite system of simple groups. In Mathematical papers read at the International Mathematical Congress: held in connection with the World's Columbian exposition, Chicago, 1893, Macmillan, New York, 208–242. [88]Google Scholar
and (1971), The factorization of F7. Bulletin of the American Mathematical Society 77(2), p. 264. [542, 568]Google Scholar
and (1975), A Method of Factoring and the Factorization of F7. Mathematics of Computation 29(129), 183–205. [541, 568]Google Scholar
and (1973), The EZGCD Algorithm. In Proceedings of the ACM National Conference, Atlanta GA, 159–166. [198, 466]Google Scholar
and (1995), Randomized Algorithms. Cambridge University Press, Cambridge, UK. [88, 198]Google Scholar
(1997), A note on subresultants and the Lazard/Rioboo/Trager formula in rational function integration. Journal of Symbolic Computation 24(1), 45–50. [199, 640]Google Scholar
and (2000), On Lattice Reduction for Polynomial Matrices. Technical Report 356, Department of Computer Science, ETH Zürich. 26 pages, ftp://ftp.inf.ethz.ch/pub/publications/tech-reports/3xx/356.ps.gz. [501]Google Scholar
, , , and (1989), Optimal normal bases in GF(pn). Discrete Applied Mathematics 22, 149–161. [88]Google Scholar
(1971), Algorithms for Polynomial Factorization. PhD thesis, Computer Science Department, University of Wisconsin. Technical Report #134, 174 pages. [465]Google Scholar
(1998), Bit Extraction, Hard-Core Predicates, and the Bit Security of RSA. PhD thesis, Department of Numerical Analysis and Computing Science, Kungl Tekniska Högskolan (Royal Institute of Technology), Stockholm. [580]Google Scholar
(1691/1692), De quadratura curvarum. The revised and augmented treatise. Unpublished manuscript. In: , The mathematical papers of Isaac Newton vol. VII, Cambridge University Press, Cambridge, UK, 1976, pp. 48–128. [641]Google Scholar
(1707), Arithmetica Universalis, sive de compositione et resolutione arithmetica liber. J. Senex, London. English translation as Universal Arithmetick: or, A Treatise on Arithmetical composition and Resolution, translated by the late Mr. Raphson and revised and corrected by Mr. Cunn, London, 1728. Reprinted in: Derek T. Whiteside, The mathematical works of Isaac Newton, Johnson Reprint Co, New York, 1967, p. 4 ff. [61, 203, 725, 726]Google Scholar
(1710), Quadrature of Curves. In Lexicon Technicum. Or, an Universal Dictionary of Arts and Sciences, vol. 2, John Harris. Reprinted in: Derek T. Whiteside, The mathematical works of Isaac Newton, vol. 1, Johnson Reprint Co, New York, 1967. [286]Google Scholar
and (2001), The Two Faces of Lattices in Cryptology. In Cryptography and Lattices, International Conference (CaLC 2001), Providence RI, ed. . Lecture Notes in Computer Science 2146, Springer-Verlag, 146–180. [509, 580]Google Scholar
(1996), Enumeration to 1014 of the Twin Primes and Brun's Constant. Virginia Journal of Science 46(3), 195–204. [83]Google Scholar
(1986), Knapsack-type cryptosystems and algebraic coding theory. Problems of Control and Information Theory 15, 159–166. [509]Google Scholar
(1993a), A New Efficient Factorization Algorithm for Polynomials over Small Finite Fields. Applicable Algebra in Engineering, Communication and Computing 4, 81–87. [420]Google Scholar
(1993b), Factorization of Polynomials and Some Linear Algebra Problems over Finite Fields. Linear Algebra and its Applications 192, 301–328. [420]Google Scholar
(1994a), Factoring polynomials over finite fields using differential equations and normal bases. Mathematics of Computation 62(206), 819–830. [420]Google Scholar
(1994b), New deterministic factorization algorithms for polynomials over finite fields. In Finite fields: theory, applications and algorithms, eds. and . Contemporary Mathematics 168, American Mathematical Society, 251–268. [420]Google Scholar
and (1993), Factorization of Polynomials over Finite Fields and Characteristic Sequences. Journal of Symbolic Computation 16, 401–412. [420]Google Scholar
and (1995), On a new factorization algorithm for polynomials over finite fields. Mathematics of Computation 64(209), 347–353. [420]Google Scholar
(1567), Libro de algebra en arithmetica y geometrica. Iuan Stelfio, widow and heirs, Anvers. [41]Google Scholar
(1990), The Rise and Fall of Knapsack Cryptosystems. In Cryptology and Computational Number Theory, ed. . Proceedings of Symposia in Applied Mathematics 42, American Mathematical Society, 75–88. [497, 509]Google Scholar
(1995a), Asymptotic Enumeration Methods. In Handbook of Combinatorics, eds. , , and . Elsevier Science Publishers B.V., Amsterdam, and The MIT Press, Cambridge MA. [697]Google Scholar
(1995c), Analytic computations in number theory. In Mathematics of Computation 1943–1993: A Half-Century of Computational Mathematics, ed. . Proceedings of Symposia in Applied Mathematics 48, American Mathematical Society, 451–463. [533]Google Scholar
and (1985), Disproof of the Mertens conjecture. Journal für die reine und angewandte Mathematik 357, 138–160. [508]Google Scholar
and (1988), Fast algorithms for multiple evaluations of the Riemann zeta function. Transactions of the American Mathematical Society 309(2), 797–809. [533]Google Scholar
(1979), Versions effectives du théorème de Chebotarev sous l'hypothèse de Riemann généralisée. Société Mathématique de France, Astérisque 61, 165–167. [443]Google Scholar
, , and (1984), An efficient signature scheme based on quadratic equations. In Proceedings of the Sixteenth Annual ACM Symposium on Theory of Computing, Washington DC, ACM Press, 208–216. [509]Google Scholar
(1949), Restricted free rotation and cyclic molecules. PhD thesis, Rijksuniversiteit te Leiden. [698]Google Scholar
and (1975), Digital Signal Processing. Prentice-Hall, Inc., Englewood Cliffs NJ. [368]Google Scholar
, , and (1983), Signals and Systems. Prentice-Hall signal processing series, Prentice-Hall, Inc., Englewood Cliffs NJ. [368]Google Scholar
(1845), De l'intégration des fractions rationnelles. Bulletin de la classe physicomathématique de l'Académie Impériale des Sciences de Saint-Pétersbourg 4(82/83), 145–167. [640]Google Scholar
(1892), Sur la représentation approchée d'une fonction par des fractions rationnelles. Annales Scientifiques de l'Ecole Normale Supérieure, 3e série 9, Supplément S3–S93. [132]Google Scholar
(1960) О ϲπосбах вцчсления значении многочленов. Усnехu мамемамuческuх Наук 21(1(127)), 103–134. V. Ya. Pan, Methods of computing values of polynomials, Russian Mathematical Surveys 21 (1966), 105-136. [306]Google Scholar
(1984), How to multiply matrices faster. Lecture Notes in Computer Science 179, Springer-Verlag, New York. [352]Google Scholar
(1997), Faster Solution of the Key Equation for Decoding BCH Error-Correcting Codes. In Proceedings of the Twenty-ninth Annual ACM Symposium on Theory of Computing, El Paso TX, ACM Press, 168–175. [332]Google Scholar
and (2004), On Rational Number Reconstruction and Approximation. SIAM Journal on Computing 33(2), 502–503. [327]Google Scholar
(1997), Combinatorial and Algebraic Aspects of Polynomials over Finite Fields. PhD thesis, Department of Computer Science, University of Toronto. Technical Report 306/97, 154 pages. [419]Google Scholar
, , and (1998), An Analytic Approach to Smooth Polynomials over Finite Fields. In Algorithmic Number Theory, Third International Symposium, ANTS-HI, Portland, Oregon, USA, ed. . Lecture Notes in Computer Science 1423, Springer-Verlag, 226–236. [419]Google Scholar
and (1998), Analysis of Ben-Or's Polynomial Irreducibility Test. Random Structures and Algorithms 13(3/4), 439–456. [419, 421]Google Scholar
and (1998), Analysis of Rabin's polynomial irreducibility test. In Proceedings of LATIN ′98, Campinas, Brazil, eds. and . Lecture Notes in Computer Science 1380, Springer-Verlag, 1–10. [419, 421]Google Scholar
and (1994), Geometric Problems in Molecular Biology and Robotics. In Proceedings 2nd International Conference on Intelligent Systems for Molecular Biology, Palo Alto CA, 322–330. [698]Google Scholar
(1994), Short and Easy Computer Proofs of the Rogers-Ramanujan Identities and of Identities of Similar Type. The Electronic Journal of Combinatorics 1(# R10). 9 pages. [697]Google Scholar
(1995), Greatest Factorial Factorization and Symbolic Summation. Journal of Symbolic Computation 20, 235–268. [670, 671]Google Scholar
and (1995), Symbolic summation – some recent developments. In Computer Algebra in Science and Engineering, Bielefeld, Germany, August 1994, eds. , , , and , World Scientific, Singapore, 138–162. [671]Google Scholar
, , and (1992), Chaos and Fractals: New Frontiersof Sience. Springer-Verlag, New York. [278]Google Scholar
and (1993), JPEG still image data compression standard. Van Nostrand Reinhold, New York. [368]Google Scholar
(1877), Sur la formule 22n + 1. Comptes Rendus des Séances del'Académie des Sciences, Paris 85, 329–331. [530, 538]Google Scholar
(1929), Die Lehre von den Kettenbrüchen. , Leipzig, 2nd edition. Reprinted by Chelsea Publishing Co., New York. First edition 1913. [90]Google Scholar
(1981), Petri net theory and the modeling of systems. Prentice-Hall, Inc., Englewood Cliffs NJ. [697]Google Scholar
(1992), Hypergeometric solutions of linear recurrences with polynomial coefficients. Journal of Symbolic Computation 14, 243–264. [671, 675]Google Scholar
(1994), A generalization of Gosper's algorithm. Discrete Mathematics 134, 125–131. [671]Google Scholar
and (1993), Finding All Hypergeometric Solutions of Linear Differential Equations. In Proceedings of the 1993 International Symposium on Symbolic and Algebraic Computation ISSAC ′93, , ed. Manuel Bronstein, ACM Press, 27–33. [641]Google Scholar
(1937), Über die Reduzibilität eines Polynoms mit ganzzahligen Koeffizienten nach einem Primzahlmodul. Časopis pro pěstování matematiky a fysiky 66, 85–94. [402, 420]Google Scholar
(1997), An Algorithm for Computing Exponential Solutions of First Order Linear Differential Systems. In Proceedings of the 1997 International Symposium on Symbolic and Algebraic Computation ISSAC ′97, Maui HI, ed. , ACM Press, 164–171. [641]Google Scholar
(1993), Some Primality Testing Algorithms. Notices of the American Mathematical Society 40(9), 1203–1210. [532]Google Scholar
(1992), Algorithmen zur Summation rationaler Funktionen. Diplomarbeit, Universität Erlangen-Nürnberg, Germany. [670, 673]Google Scholar
(1996), On Combinatorial Identities: Symbolic Summation and Umbral Calculus. PhD thesis, Johannes Kepler Universität, Linz. [671]Google Scholar
and (1995), Rational Summation and Gosper-Petkovšek Representation. Journal of Symbolic Computation 20, 617–635. [671]Google Scholar
(1997), Algebraic Propositional Proof Systems. In Descriptive Complexity and Finite Models: Proceedings of aDIMACS Workshop, January 14-17, 1996, Princeton NJ, eds. and . DIMACS Series in Discrete Mathematics and Theoretical Computer Science 31, American Mathematical Society, Providence RI, 215–244. [697]Google Scholar
(1917), The Direct Solution of the Quadratic and Cubic Binomial Congruences with Prime Moduli. Proceedings of the Cambridge Philosophical Society 19, 57–59. [88, 198]Google Scholar
(1971), The Fast Fourier Transform in a Finite Field. Mathematics of Computation 25(114), 365–374. [247, 280]Google Scholar
(1974), Theorems on factorization and primality testing. Proceedings of the Cambridge Philosophical Society 76, 521–528. [198, 541, 567]Google Scholar
(1982), Analysis and comparison of some integer factoring algorithms. In Computational Methods in Number Theory, Part 1, eds. and , Mathematical Centre Tracts 154, 89–139. Mathematisch Centrum, Amsterdam. [557, 567, 569]Google Scholar
(1985), The quadratic sieve factoring algorithm. In Advancesin Cryptology: Proceedings of EUROCRYPT 1984, Paris, France, eds. , , and . Lecture Notes in Computer Science 209, Springer-Verlag, Berlin, 169–182. [557]Google Scholar
(1990), Factoring. In Cryptology and Computational Number Theory, ed. . Proceedings of Symposia in Applied Mathematics 42, American Mathematical Society, 27–47. [520, 567]Google Scholar
, , and (1980), The pseudoprimes to 25 · 109. Mathematics of Computation 35, 1003–1025. [532]Google Scholar
and (1983), Implementation of the continued fraction integer factoring algorithm. Congressus Numerantium 37, 99–118. [569]Google Scholar
(1978), A proof that Euler missed … Apéry's proof of the irrationality of ς(3). The Mathematical Intelligencer 1, 195–203. [697]Google Scholar
(1996), Notes on Fermat's Last Theorem. Canadian Mathematical Society series of monographs and advanced texts, John Wiley & Sons, New York. [514]Google Scholar
(1959), An algorism for factoring Xn – 1 over a finite field. Technical Report AFCRC-TN-59-775, Air Force Cambridge Research Center, Bedford MA. [419, 430]Google Scholar
(1983), Fast Compact Prime Number Sieves (among Others). Journal of Algorithms 4, 332–344. [533]Google Scholar
(1987), Linear prime-number sieves: a family tree. Science of Computer Programming 9, 17–35. [533]Google Scholar
(1974), A high-security log-in procedure. Communications of the ACM 17(8), 442–445. [581]Google Scholar
(1976), Probabilistic algorithms. In Algorithms and Complexity, ed. , Academic Press, New York, 21–39. [532]Google Scholar
(1980a), Probabilistic Algorithms for Testing Primality. Journal of Number Theory 12, 128–138. [532]Google Scholar
(1980b), Probabilistic algorithms in finite fields. SIAM Journal on Computing 9(2), 273–280. [421, 424]Google Scholar
(1989), Efficient Dispersal of Information for Security, Load Balancing, and Fault Tolerance. Journal of the Association for Computing Machinery 36(2), 335–348. [131, 215]Google Scholar
(1690), Analysis Æquationum Universalis seu Ad Æquationes Algebraicas Resolvendas Methodus Generalis, et Expedita, Ex nova Infinitarum serierum Doctrina Deducta ac Demonstrata. Abel Swalle, London. [219]Google Scholar
(1998), Lower bounds for the polynomial calculus. computational complexity 7(4), 291–324. [697]Google Scholar
(1995), Schnelle Multiplikation von Polynomen über GF(2) und Anwendungen. Diplomarbeit, Institut für Informatik II, Rheinische Friedrich-Wilhelm-Universität Bonn, Germany. [279]Google Scholar
(1997), Asymptotically Fast Computation of Subresultants. In Proceedings of the 1997 International Symposium on Symbolic and Algebraic Computation ISSAC ′97, Maui HI, ed. , ACM Press, 233–240. [332]Google Scholar
(1985), Petri Nets: An Introduction. EATCS Monographs on Theoretical Computer Science 4, Springer-Verlag, Berlin. Translation of the German edition Petrinetze: eine Einführung, Springer-Verlag, 1982. [697]Google Scholar
(1950), An ENIAC Determination of π and e to more than 2000 Decimal Places. Mathematical Tables and other Aids to Computation 4, 11–15. Reprinted in Berggren, Borwein & Borwein (1997), 277-281. [82]Google Scholar
(1991), Recent Progress on the Complexity of the Decision Problem for the Reals. In Discrete and Computational Geometry: Papers from the DIMACS Special Year, eds. , , and . DIMACS Series in Discrete Mathematics and Theoretical Computer Science 6, American Mathematical Society and ACM, 287–308. [619]Google Scholar
(1992a), On the Computational Complexity of the First-order Theory of the Reals. Part I: Introduction. Preliminaries. The Geometry of Semi-algebraic Sets. The Decision Problem for the Existential Theory of the Reals. Journal of Symbolic Computation 13(3), 255–299. [619]Google Scholar
(1992b), On the Computational Complexity of the First-order Theory of the Reals. Part II: The General Decision Problem. Preliminaries for Quantifier Elimination. Journal of Symbolic Computation 13(3), 301–327. [619]Google Scholar
(1992c), On the Computational Complexity of the First-order Theory of the Reals. Part III: Quantifier Elimination. Journal of Symbolic Computation 13(3), 329–352. [619]Google Scholar
(1824), Traité d'arithmétique à l'usage des élèves qui se destinent à l'école royale polytechnique à l'école spéciale militaire et à l'école de marine. Courcier, Paris, 12th edition. [61]Google Scholar
(1968), Some undecidable problems involving elementary functions of a real variable. Journal ofSymbolicLogic 33(4), 514–520. [640]Google Scholar
(1859), Ueber die Anzahl der Primzahlen unter einer gegebenen Grösse. Monatsberichte der Berliner Akademie, 145–153. Gesammelte Mathematische Werke, ed. , Teubner Verlag, Leipzig, 1892, 177–185. [533]Google Scholar
(1969), The problem of integration in finite terms. Transactions of the American Mathematical Society 139, 167–189. [640, 641]Google Scholar
(1970), The solution of the problem of integration in finite terms. Bulletin of the American MathematicalSociety 76(3), 605–608. [640, 641]Google Scholar
(1950), Differential Algebra. AMS Colloquium Publications XXXIII, American Mathematical Society, Providence RI. Reprint by Dover Publications, Inc., New York, 1966. [619]Google Scholar
, , and (1978), A Method for Obtaining Digital Signatures and Public-Key Cryptosystems. Communications of the ACM 21(2), 120–126. [576]Google Scholar
(1984), The umbral calculus. Pure and applied mathematics 111, Academic Press, Orlando FL. [669]Google Scholar
(1988), Factoring Polynomials over Finite Fields. Journal of Algorithms 9, 391–400. [421]Google Scholar
(1989), Galois groups and factoring over finite fields. In Proceedings of the 30th Annual IEEE Symposium on Foundations of Computer Science, Research Triangle Park NC, IEEE Computer Society Press, Los Alamitos CA, 99–104. [421]Google Scholar
(1831), The Algebra of Mohammed ben Musa. Oriental Translation Fund, London. Reprint by Georg Olms Verlag, Hildesheim, 1986. [726]Google Scholar
and (1962), Approximate formulas for some functions of prime numbers. Illinois Journal of Mathematics 6, 64–94. [527, 532, 536]Google Scholar
(1976), Aspects of symbolic integration and simplification of exponential andprimitive functions. PhD thesis, University of Wisconsin-Madison. [640, 641]Google Scholar
(1977), A new algorithm for the integration of exponential and logarithmic functions. In Proceedings of the 1977 MACSYMA Users Conference, Berkeley CA, NASA, Washington DC, 263–274. [640, 641]Google Scholar
and (1986), Small Sample Algorithms for the Identification of Polynomials. Journal of the ACM 33(4), 822–829. [199]Google Scholar
(1890), Ueber die geometrischen Isomerien der Hexamethylenderivate. Berichte der Deutschen Chemischen Gesellschaft 23, 1363–1370. [698]Google Scholar
(1892), Über die Konfigurationen der Polymethylenringe. Zeitschrift für physikalische Chemie 10, 203–241. [698]Google Scholar
(1991), Asymptotique automatique et fonctions génératrices. PhD thesis, École Polytechnique, Paris. [697]Google Scholar
(1907), Zur Theorie der linearen und nichtlinearen Integralgleichungen, I. Teil: Entwicklung willkürlicher Funktionen nach Systemen vorgeschriebener. Mathematische Annalen 63, 433–476. Reprint of Erhard Schmidt's Dissertation, Göttingen, 1905. [496]Google Scholar
(1982), Refined Analysis and Improvements on Some Factoring Algorithms. Journal of Algorithms 3, 101–127. [567]Google Scholar
(1987), A hierarchy ofpolynomial time lattice basis reduction algorithms. Theoretical Computer Science 53, 201–224. [497]Google Scholar
(1988), A More Efficient Algorithm for Lattice Basis Reduction. Journal of Algorithms 9, 47–62. [497]Google Scholar
and (1991), Lattice Basis Reduction: Improved Practical Algorithms and Solving Subset Sum Problems. In Proceedings of the 8th International Conference on Fundamentals of ComputationTheory 1991, Gosen, Germany, ed. . Lecture Notes in Computer Science 529, Springer-Verlag, 68–85. [497]Google Scholar
(1971), Schnelle Berechnung von Kettenbruchentwicklungen. Acta Informatica 1, 139–144. [332]Google Scholar
(1977), Schnelle Multiplikation von Polynomen über Körpern der Charakteristik 2. Acta Informatica 7, 395–398. [245, 247, 253]Google Scholar
(1984), Factorization of univariate integer polynomials by Diophantine approximation and an improved basis reduction algorithm. In Proceedings of the 11th International Colloquium on Automata, Languages and Programming ICALP 1984, Antwerp, Belgium. Lecture Notes in Computer Science 172, Springer-Verlag, 436–447. [497]Google Scholar
(1988), Probabilistic Computation of Integer Polynomial GCDs. Journal of Algorithms 9, 365–371. [202]Google Scholar
, , and (1994), Fast Algorithms – A Multitape Turing Machine Implementation. BI Wissenschaftsverlag, Mannheim. [279, 286, 292, 727]Google Scholar
and (1971), Schnelle Multiplikation großer Zahlen. Computing 7, 281–292. [221, 222, 243, 245, 247, 254, 283]Google Scholar
(1793), De inventione divisorum. Nova Acta Academiae Scientiarum Imperalis Petropolitanae 11, 172–186. [465]Google Scholar
(1980), Fast Probabilistic Algorithms for Verification of Polynomial Identities. Journal of the ACM 27(4), 701–717. [198, 332]Google Scholar
(1939), Contribution à la réductibilité des polynômes dans la théorie des congruences. Věstník Královské Ceské Společnosti Nauk, Třída Matemat.-Př Ročník Praha, 1–7. [420]Google Scholar
(1940), Sur le nombre des racines et des facteurs irréductibles d'une congruence donnée. Časopis pro pěstování matematiky a fysiky 69, 128–145. [420]Google Scholar
(1956), On the reducibility of polynomials over a finite field. Quarterly Journal of Mathematics Oxford 7(2), 110–124. [420]Google Scholar
ШтеΦан Шварц [] (1960), Об одном класе многочленов над конечным телом (On a class of polynomials over a finite field). 'Matematicko-Fyzikálny Časopis 10, 68–80. [420]Google Scholar
ШтеΦан Шварц [] (1961) О числе неприводимЫх Факторов данного многочлена над конечнЫм полем (On the number of irreducible factors of a polynomial over a finite field). Чехословачкчu мамемаuческuu мсурнал (Czechoslovak Mathematical Journal) 11(86), 213–225. [420]Google Scholar
(1636), Deliciæ Physico-Mathematicœ. Jeremias Dümler, Nürnberg. Reprint by Keip Verlag, Frankfurt am Main, 1991. [61, 131, 697]Google Scholar
and (1996), An Introduction to the Analysis of Algorithms. Addison-Wesley, Reading MA. [697]Google Scholar
(1990), On the Worst Case of Three Algorithms for Computing the Jacobi Symbol. Journal of Symbolic Computation 10, 593–610. [533]Google Scholar
(1994), Origins of the Analysis of the Euclidean Algorithm. Historia Mathematica 21, 401–419. [61]Google Scholar
(1984), A polynomial-time algorithm for breaking the basic Merkle-Hellman cryptosystem. IEEE Transactions on Information Theory IT-30(5), 699–704. [503, 509]Google Scholar
(1993), On the Generation of Polynomials which are Hard to Factor. In Proceedings of the Twenty-fifth Annual ACM Symposium on Theory of Computing, San Diego CA, ACM Press, 796–804. [469]Google Scholar
and (1980), On the Security of the Merkle-Hellman Cryptographic Scheme. IEEE Transactions on In formation Theory IT-26(3), 339–340. [509]Google Scholar
and (1962), Calculation of π to 100,000 Decimals. Mathematics of Computation 16, 76–99. [82]Google Scholar
(1853), Contributions to Mathematics Comprising Chiefly the Rectification of the Circle to 607 Places of Decimals. G. Bell, London. Excerpt reprinted in Berggren, Borwein & Borwein (1997), 147-161. [82, 90, 729]Google Scholar
(1948), A Mathematical Theory of Communication. Bell System Technical Journal 27, 379–423 and 623–656. Reprinted in Claude E. Shannon and Warren Weaver, The Mathematical Theory Of Communication, University of Illinois Press, Urbana IL, 1949. [209, 215, 307]Google Scholar
(1988), Historical Development of the Chinese Remainder Theorem. Archive of the History of Exact Sciences 38, 285–305. [131]Google Scholar
and (1966), Ordered cycle lengths in a random permutation. Transactions of the American Mathematical Society 121, 340–357. [421]Google Scholar
(1990), On the deterministic complexity of factoring polynomials over finite fields. Information Processing Letters 33, 261–267. [421]Google Scholar
(1991), Topics in the theory of computation. Lecture Notes for CSC 2429, Spring term, Department of Computer Science, University of Toronto. [205]Google Scholar
(1994), Fast Construction of Irreducible Polynomials over Finite Fields. Journal of Symbolic Computation 17, 371–391. [421]Google Scholar
(1995), A New Polynomial Factorization Algorithm and its Implementation. Journal of Symbolic Computation 20, 363–397. [246, 279, 462]Google Scholar
(1999), Efficient Computation of Minimal Polynomials in Algebraic Extensions of Finite Fields. In Proceedings of the 1999 International Symposium on Symbolic and Algebraic Computation ISSAC ′99, Vancouver, Canada, ed. , ACM Press, 53–58. [354]Google Scholar
(1992), Computational and Algorithmic Problems in Finite Fields. Mathematics and Its Applications 88, Kluwer Academic Publishers. [419]Google Scholar
(1999), Finite Fields: Theory and Computation. Mathematics and Its Applications, Kluwer Academic Publishers, Dordrecht/Boston/London. [419]Google Scholar
and (2010), Arithmetic Circuits: a survey of recent results and open questions. Foundations and Trends in Theoretical Computer Science 5(3–4), 207–388. [199]Google Scholar
(1986), The Arithmetic of Elliptic Curves. Graduate Texts in Mathematics 106, Springer-Verlag, New York. [568]Google Scholar
(1987), The Multiple Polynomial Quadratic Sieve. Mathematics of Computation 48(177), 329–339. [567]Google Scholar
(1991), Liouvillian Solutions of Linear Differential Equations with Liouvillian Coefficients. Journal of Symbolic Computation 11, 251–273. [641]Google Scholar
(1997), Fermat's Enigma: The epic quest to solve the world's greatest mathematical problem. Anchor Books, New York. [514]Google Scholar
(1997), Introduction to the Theory of Computation. PWS Publishing Company, Boston MA. [89, 721]Google Scholar
(1981), Complexity problems in computational theory. Ycnexu Mame mamuqecku Hayk (Uspekhi Matematicheski Nauk) 36(6), 21–103. Russian Mathematical Surveys 36 (1981), 23-125. [419]Google Scholar
and (1977), A fast Monte-Carlo test for primality. SIAM Journal on Computing 6(1), 84–85. Erratum in 7 (1978), p. 118. [198, 529, 530, 533]Google Scholar
(1998), Trading Time for Space in Prime Number Sieves. In Algorithmic Number Theory, Third International Symposium, ANTS-III, Portland, Oregon, USA, ed. . Lecture Notes in Computer Science 1423, Springer-Verlag, Berlin, Heidelberg, 179–195. [533]Google Scholar
В.Г. СпринѬкук (1981), ДиоФантовЫ уравенения с неизвестными простыми числами. Труәы Мамемамuцескоѕо uнсмuмума АН СССР 158, 180–196. , Diophantine equations with unknown prime numbers, Proc. Steklov Institute of Mathematics 158 (1983), 197–214. [498]Google Scholar
(1983), Arithmetic specializations in polynomials. Journal für die reine und angewandte Mathematik 340, 26–52. [498]Google Scholar
(1967), Computational Problems Associated with Racah Algebra. Journal of Computational Physics 1, 397–405. [61]Google Scholar
and (1996), Chebotarëv and his density theorem. The Mathematical Intelligencer 18(2), 26–37. [441]Google Scholar
(1585), De Thiende. Christoffel Plantijn, Leyden. Übersetzt und erläutert von Helmuth Gericke und Kurt Vogel, Akademische Verlagsgesellschaft, Frankfurt am Main, 1965. [41, 61]Google Scholar
(1730), Methodus Differential: sive Tractatus de Summatione et Interpolation Serierum Infinitarum. Gul. Bowyer, London. Translated into English with the Author's Approbation By Francis Holliday, Master of the Grammar Free-School at Haughton-Park near Retford, Nottinghamshire, London, 1749. [670]Google Scholar
(1996), Faster Algorithms for Integer Lattice Basis Reduction. Technical Report 249, Eidgenössische Technische Hochschule Zürich. 24 pages, ftp://ftp.inf.ethz.ch/pub/publications/tech-reports/2xx/249.ps.gz. [497]Google Scholar
(2000), Algorithms for Matrix Canonical Forms. PhD thesis, Swiss Federal Institute of TechnologyZürich. [353]Google Scholar
(1980), Linear Algebra and Its Applications. Academic Press, New York, second edition. [713]Google Scholar
(1969), Gaussian Elimination is not Optimal. Numerische Mathematik 13, 354–356. [335, 337, 352]Google Scholar
(1973a), Vermeidung von Divisionen. Journal für die reine und angewandte Mathematik 264, 182–202. [286, 352, 497]Google Scholar
(1976), Einige Resultate über Berechnungskomplexität. Jahresberichte der DMV 78, 1–8. [541, 567]Google Scholar
(1983), The computational complexity of continued fractions. SIAM Journal on Computing 12(1), 1–27. [324, 332]Google Scholar
(1984), Algebraische Berechnungskomplexität. In Perspectives in Mathematics, Anniversary of Oberwolfach 1984, 509–550. Birkhäuser Verlag, Basel. [352]Google Scholar
(1990), Algebraic Complexity Theory. In Handbook of Theoretical Computer Science, vol. A, ed. , 633–672. Elsevier Science Publishers B.V., Amsterdam, and The MIT Press, Cambridge MA. [352]Google Scholar
(1835), Mémoire sur la résolution des équations numériques. Mémoires présentés par divers savants à l'Acadèmie des Sciences de l'Institut de France 6, 273–318. [94]Google Scholar
(1957), Rational numerical system of residual classes. Stroje na Zpracování Informací, Sborník V, Nakl. ČSAV 5, 9–37. [132]Google Scholar
and (1955), Operatorové obvody (Operational Circuits). With summaries in Russian and English. Stroje na Zpracování Informací 3, 247–295. [132]Google Scholar
(1962), Factorization of polynomials over finite fields. Pacific Journal of Mathematics 12, 1099–1106. [207, 332]Google Scholar
(1840), A method of determining by mere inspection the derivatives from two equations of any degree. Philosophical Magazine 16, 132–135. Mathematical Papers 1, Chelsea Publishing Co., New York, 1973, 54–57. [197, 199]Google Scholar
(1853), On the explicit values of Sturm's quotients. Philosophical Magazine VI, 293–296.Google Scholar
Mathematical Papers 1, Chelsea Publishing Co., New York, 1973, 637–640. [197, 727]
(1881), On the resultant of two congruences. Johns Hopkins University Circulars 1, p. 131. Mathematical Papers 3, Chelsea Publishing Co., New York, 1973, p. 475. [197]Google Scholar
and (1967), Residue arithmetic and its applications to computer technology. McGraw-Hill, New York. [132]Google Scholar
(1898), Question 1401. Le problème chinois. L'Intermédiaire des Mathématiciens 5, 266–267. Solution by Korselt. [531]Google Scholar
(1948), A decision method for elementary algebra and geometry. The Rand Corporation, Santa Monica CA, 2nd edition. Project Rand, R-109. [619]Google Scholar
and (1995), Ring-theoretic properties of certain Hecke algebras. Annals of Mathematics 141, 553–572. [514]Google Scholar
(1995), Introduction to analytic and probabilistic number theory. Cambridge studies in advanced mathematics 46, Cambridge University Press, Cambridge, UK. [536]Google Scholar
(1902), Et par andtydninger til en talteoretisk methode. Videnskabers Selskab Forhandlinger Christiana 7. [132]Google Scholar
А.Л. Тоом (1963), О сложности схемы из функцоинальных әлементов, реализирующей умножене целых чисел. ДоклаӘы Акаәемuu Наук СССР 150(3), 496-498. , The complexity of a scheme of functional elements realizing the multiplication of integers, Soviet Mathematics Doklady 4 (1963), 714–716. [247]Google Scholar
(1976), Algebraic Factoring and Rational Function Integration. In Proceedings of the 1976 ACM Symposium on Symbolic and Algebraic Computation SYMSAC ′76, Yorktown Heights NY, ed. , ACM Press, 219–226. [466, 640]Google Scholar
(1988), Gröbner trace algorithms. In Proceedings of the 1988 International Symposium on Symbolic and Algebraic Computation ISSAC ′88, Rome, Italy, ed. . Lecture Notes in Computer Science 358, Springer-Verlag, Berlin, 125–138. [619]Google Scholar
(1862), Teoria de' determinanti e loro applicazioni Libreria Scientifica e Industriale de B. Pellerano, Napoli. [199]Google Scholar
(1937), On computable numbers, with an application to the Entscheidungsproblem. Proceedings of the London Mathematical Society, Second Series, 42, 230–265, and 43, 544–546. [419]Google Scholar
(2008), Fast Polynomial Factorization and Modular Composition in Small Characteristic. In Proceedings of the Fourtieth Annual ACM Symposium on Theory of Computing, Victoria, BC, Canada, ACM Press, 481–490. Invited to the STOC 2008 special issue of SICOMP. [339, 751]Google Scholar
(1995), The complexity of propositional proofs. The Bulletin of Symbolic Logic 1(4), 425–467. [697]Google Scholar
(1894), Intorno alla prima dimostrazione di un teorema di Fermat. Bibliotheca Mathematica, Serie 2, 8, 46–48. [88]Google Scholar
(2003), Dynamical Analysis of a Class of Euclidean Algorithms. Theoretical Computer Science 297, 447–486. [61]Google Scholar
(1896), Recherches analytiques sur la théorie des nombres premiers. Annales de la Société Scientifique de Bruxelles 20, 183–256 and 281–397. [533]Google Scholar
(1974), Bounds for the coefficients of cyclotomic polynomials. Michigan Mathematical Journal 21, 289–295. [198]Google Scholar
(1926), Cipher Printing Telegraph Systems. Journal of the American Institute of Electrical Engineers 45, 109–115. [580]Google Scholar
(1997), Further Analysis of Coppersmith's Block Wiedemann Algorithm for the Solution of Sparse Linear Systems. In Proceedings of the 1997 International Symposium on Symbolic and Algebraic Computation ISSAC ′97, Maui HI, ed. , ACM Press, 32–39. [353]Google Scholar
and (1990), Average-Case Analysis of Algorithms and Data Structures. In Handbook of Theoretical Computer Science, vol. A, ed. , 431–524. Elsevier Science Publishers B.V., Amsterdam, and The MIT Press, Cambridge MA. [697]Google Scholar
(1995), Organic Chemistry. Prentice-Hall, Inc., Englewood Cliffs NJ, 3rd edition. [698]Google Scholar
(1930a), Eine Bemerkung über die Unzerlegbarkeit von Polynomen. Mathematische Annalen 102, 738–739. [419]Google Scholar
(1930b), Moderne Algebra, Erster Teil. Die Grundlehren der mathematischen Wissenschaften in Einzeldarstellungen 33, Julius Springer, Berlin. English translation: Algebra, Volume I, Springer Verlag, 1991. [586, 703]Google Scholar
(1931), Moderne Algebra, Zweiter Teil. Die Grundlehren der mathematischen Wissenschaften in Einzeldarstellungen 34, Julius Springer, Berlin. English translation: Algebra, Volume II., Springer Verlag, 1991. [349, 586, 703]Google Scholar
(1934), Die Seltenheit der Gleichungen mit Affekt. Mathematische Annalen 109, 13–16. [465]Google Scholar
(1938), Eine Bemerkung zur numerischen Berechnung von Determinanten und Inversen von Matrizen. Jahresberichte der DMV 48, 29–30. [352]Google Scholar
(1983), Divisors of Mersenne numbers. Mathematics of Computation 40(161), 385–397. [534]Google Scholar
(1991), The JPEG Still Picture Compression Standard. Communications of the ACM 34(4), 30–44. [368]Google Scholar
(1993), A p-adic lifting lemma and its applications to permutation polynomials. In Proceedings 1992 Conference on Finite Fields, CodingTheory, and Advancesin Communications and Computing, eds. and . Lecture Notes in Pure and Applied Mathematics 141, Marcel Dekker, Inc., 209–216. [425]Google Scholar
and (2003), Acceleration of Euclidean algorithm and rational number reconstruction. SIAM Journal on Computing 32(2), 548–556. [327]Google Scholar
(1770), Meditationes Algebraicx. J. Woodyer, Cambridge, England, second edition. English translation by Dennis Weeks, American Mathematical Society, 1991. [286]Google Scholar
(1779), Problems concerning Interpolations. Philosophical Transactions of the Royal Society of London 69(7), 59–67. [131]Google Scholar
and , eds. (1998), Symbolic-Numeric Algebra for Polynomials. Special Issue of the Journal of Symbolic Computation 26(6). [41]
(1987), The Complexity of Boolean Functions. Wiley-Teubner Series in Computer Science, B. G. Teubner, Stuttgart, and John Wiley & Sons. [721]Google Scholar
(1989), Algorithms for Diophantine equations. CWI Tract no. 65, Centrum voor Wiskunde en Informatica, Amsterdam. 212 pages. [497]Google Scholar
(1984), Number theory: An approach through history; From Hammurapi to Legendre. Birkhäuser Verlag. xxi+375 pages. [513]Google Scholar
(2000), (1 + i)-ary GCD Computation in Z[i] as an Analogue to the Binary GCD Algorithm. Journal of Symbolic Computation 30(5), 605–617. [61]Google Scholar
(1691), Musicalische Temperatur. Theodorus Philippus Calvisius, Franckfurt und Leipzig. First edition 1686/87. Reprint edited by Guido Bimberg and Rüdiger Pfeiffer, Denkmäler der Musik in Mitteldeutschland: Ser. 2., Documenta theoretica musicae; Bd. 1: Werckmeister-Studien. Verlag Die Blaue Eule, Essen, 1996. [86]Google Scholar
(1986), Solving Sparse Linear Equations Over Finite Fields. IEEE Transactions on Information Theory IT-32(1), 54–62. [340, 346, 351, 352, 355, 556]Google Scholar
(1995), Modular elliptic curves and Fermat's Last Theorem. Annals of Mathematics 142, 443–551. [514]Google Scholar
(1994), generatingfunctionology. Academic Press, 2nd edition. First edition 1990. [466, 697]Google Scholar
and (1990), Rational functions certify combinatorial identities. Journal of the American Mathematical Society 3(1), 147–158. [697]Google Scholar
and (1992), An algorithmic proof theory for hypergeometric (ordinary and “q”) multisum/integral identities. Inventiones mathematicae 108, 575–633. [671, 697]Google Scholar
(1978), Factoring polynomials over a finite field. SIAM Journal on Applied Mathematics 35, 333–337. [419]Google Scholar
(1982), A p + 1 Method of Factoring. Mathematics of Computation 39(159), 225–234. [568]Google Scholar
and (1986), The primality of R1031. Mathematics of Computation 47(176), 703–711. [530]Google Scholar
and (1987), On the Parallel Generation of the Residues for the Continued Fraction Factoring Algorithm. Mathematics of Computation 48(177), 405–423. [569]Google Scholar
(1961), Algebra of Polynomials in Several Variables for a Digital Computer. Journal of the ACM 8, 29–40. [20]Google Scholar
(2011), Breaking the Coppersmith-Winograd barrier. http://www.cs.berkeley.edu/~virgi/.Last visited 08 December 2011. 72 pp. [352]
(1971), On Multiplication of 2 × 2 matrices. Linear Algebra and its Applications 4, 381–388. [352]Google Scholar
(1994), Mechanical Theorem Proving in Geometries: Basic Principles. Texts and Monographs in Symbolic Computation, Springer-Verlag, Wien and New York. English translation by Xiaofan Jin and dongming Wang. Originally published as “Basic Principles of Mechanical Theorem Proving in Geometry” in Chinese language by Science Press, Beijing, 1984, XIV and 288 pp. [618, 619]Google Scholar
(1991), A New Lower Bound Construction for Commutative Thue Systems with Applications. Journal of Symbolic Computation 12, 1–27. [618]Google Scholar
and (2011), Pi – 10 Trillion Digits. Last visited 16 October 2011. [90]
(1976), On Square-free Decomposition Algorithms. In Proceedings of the 1976 ACM Symposium on Symbolic and Algebraic Computation SYMSAC ′76, Yorktown Heights NY, ed. , ACM Press, 26–35. [419, 466]Google Scholar
(1977a), Fast algorithm for rational function integration. In Information Processing 77—Proceedings of the IFIP Congress 77, ed. , North-Holland, Amsterdam, 493–498. [640]Google Scholar
(1977b), On the equivalence of polynomial gcd and squarefree factorization problems. In Proceedings of the 1977 MACSYMA Users Conference, Berkeley CA, NASA, Washington DC, 65–70. [425]Google Scholar
(1969), On Hensel Factorization, I. Journal of Number Theory 1, 291–311. [417, 444, 466]Google Scholar
(1990a), A holonomic systems approach to special function identities. Journal of Computational and Applied Mathematics 32, 321–368. [671, 697]Google Scholar
(1990b), A fast algorithm for proving terminating hypergeometric identities. Discrete Mathematics 80, 207–211. [671, 697]Google Scholar
(1991), The Method of Creative Telescoping. Journal of Symbolic Computation 11, 195–204. [671, 697]Google Scholar
(1993), Theorems for a Price: Tomorrow's Semi-Rigorous Mathematical Culture. Notices of the American Mathematical Society 40(8), 978–981. [697]Google Scholar
(1991), Séries génératrices et analyse automatique d'algorithmes. PhD thesis, École Polytechnique, Paris. [697]Google Scholar
(1979), Probabilistic Algorithms for sparse Polynomials. In Proceedings of EUROSAM ′79, Marseille, France. Lecture Notes in Computer Science 72, Springer-Verlag, 216–226. [198, 498]Google Scholar
(1993), Effective polynomial computation. Kluwer Academic Publishers, Boston MA. [204]Google Scholar