Algorithmic number theory

from Wikipedia, the free encyclopedia

The algorithmic number theory is a branch of number theory , which in turn is a branch of mathematics . It deals with the question of efficient algorithmic solutions for number theoretic problems.

The most important areas of elementary algorithmic number theory are

For this one needs further procedures, which are also examined:

New research findings on algorithmic number theory are, among others, on the 1994 two-yearly conference ANTS presents (Algorithmic Number Theory Symposium).

Applications

The most important application of algorithmic number theory is cryptography . For example, the RSA method makes use of the fact that the prime number property of a number can be checked quickly, but so far no similarly fast methods are known to factor a composite number (that is a number that is not prime). The security of data transmission on the Internet is based on this fact. In this context, RSA Security offered larger sums of money to those who succeed in factoring certain numbers. Algorithms are also used in cryptography, for example when calculating discrete logarithms for other encryption and signature processes.

A much-studied problem with far-reaching applications is to find a base that generates the grid in a number grid, which base consists of base vectors that are as short as possible and as orthogonal as possible ( grid base reduction ).

people

literature

  • Willi Klösgen: Documentation on number theory problems that were dealt with with the help of electronic data processing systems. Message. Ges. F. Math. And Data processing No. 3, Birlinghoven 1970
  • Garrett Birkhoff , Marshall Hall Jr .: Computers in Algebra and Number Theory. (SIAM-AMS Proceedings IV) AMS, Providence 1971
  • Horst-Günter Zimmer : Computers and computations in algebraic number theory. In: SR Petrick (Ed.): SYMSAC '71, Proc. second ACM symposium on symbolic and algebraic manipulation, Los Angeles 1971 , pp. 172-179
  • H.-G. Zimmer: Computational Problems, Methods, and Results in Algebraic Number Theory . Lecture Notes Math. 262, Springer-Verlag 1972
  • Hendrik W. Lenstra, Robert Tijdeman (Ed.): Computational methods in number theory I, II. Math. Center Tracts 154/155, Math. Centrum Amsterdam, 1982
  • Attila Pethő , Michael Pohst, Hugh Williams, Horst-Günter Zimmer (Eds.): Computational Number Theory. Proc. Coll. Debrecen 1989. Walter de Gruyter, 1991, ISBN 978-3-11-012394-4 .
  • Michael Pohst, Hans Zassenhaus: Algorithmic Algebraic Number Theory. Cambridge University Press 1989, 1990, 1993, 1997, ISBN 0-521-59669-6 .
  • Carl Pomerance (Ed.): Cryptology and computational number theory. (Proc. Sympos. Appl. Math. Vol. 42, short course lecture notes). AMS, Providence 1990, ISBN 0-8218-0155-4 .
  • Igor E. Shparlinski: Computational and algorithmic problems in finite fields. Mathematics and Its Applications series vol. 88, Kluwer Academic Publishers, Dordrecht 1992; Softcover Springer 2012, ISBN 978-94-010-4796-8 .
  • Michael Pohst: Computational Algebraic Number Theory. DMV Seminar Vol. 21, Birkhäuser, Basel 1993, ISBN 3-7643-2913-0 .
  • Michel Waldschmidt , Pierre Moussa, Jean-Marie Luck, Claude Itzykson (Eds.): From number theory to physics. Winter school, Les Houches, 1989. Springer-Verlag 1992, 1995, ISBN 3-540-53342-7 .
  • Peter J. Giblin: Primes and programming: an introduction to number theory with computing. Cambridge University Press 1993, ISBN 0-521-40182-8 , ISBN 0-521-40988-8 .
  • H. Krishna, B. Krishna, K.-Y. Lin, J.-D. Sun: Computational Number Theory and Digital Signal Processing. Fast Algorithms and Error Control Techniques. CRC Press 1994, ISBN 0-8493-7177-5 .
  • Alf van der Poorten , Wieb Bosma (Ed.): Computational algebra and number theory (Sydney, 1992) (Mathematics and its applications 325) Kluwer, Dordrecht, 1995, ISBN 0-7923-3501-5 , Paperback, Springer 2010, ISBN 978-90-481-4560-7 .
  • Eric Bach, Jeffrey Shallit : Algorithmic Number Theory. Vol. I: Efficient Algorithms . MIT Press 1996, ISBN 0-262-02405-5 .
  • Otto Forster : Algorithmic Number Theory. Vieweg, 1996, ISBN 3-528-06580-X
    • See also the associated ARIBAS program
  • Duncan A. Buell, Jeremy T. Teitelbaum (Eds.): Computational Perspectives on Number Theory: Proc. Conf. in Honor of AOL Atkin, Chicago 1995. (AMS / IP Studies in Advanced Mathematics 7) AMS 1997, ISBN 0-8218-0880-X .
  • Kálmán Győry, Attila Pethő, Vera T. Sós (Eds.): Number Theory: Diophantine, Computational and Algebraic Aspects - Proc. Conf. Eger 1996. de Gruyter 1998, ISBN 978-3-11-015364-4 .
  • Ramanujachary Kumanduri, Cristina Romero: Number theory with computer applications. Prentice Hall 1998, ISBN 0-13-801812-X .
  • Nigel Smart : The algorithmic resolution of diophantine equations. (London Mathematical Society Student Texts 41) Cambridge University Press, 1998, ISBN 0-521-64156-X .
  • B. Heinrich Matzat, Gert-Martin Greuel, Gerhard Hiss (Eds.): Algorithmic algebra and number theory. Selected papers from a conference held at the University of Heidelberg in October 1997. Springer 1999, ISBN 3-540-64670-1 .
  • Melvyn B. Nathanson (Ed.): Unusual applications of number theory: DIMACS Workshop, 2000. (DIMACS Series in Discrete Mathematics and Theoretical Computer Science, Vol. 64) AMS 2004, ISBN 978-0-8218-2703-1 .
  • Song Y. Yan: Number theory for computing. 2nd edition, Springer-Verlag 2002, ISBN 3-540-43072-5 .
  • István Gaál: Diophantine equations and power integral bases: New computational methods. Birkhäuser 2002; Springer 2013, ISBN 0-8176-4271-4 .
  • Henri Cohen: A Course in Computational Algebraic Number Theory. 4th edition. Springer, Berlin 2003, ISBN 3-540-55640-0
  • Alf van der Poorten, Andreas Stein, Hugh C. Williams (Eds.): High Primes and Misdemeanours: Lectures in Honor of the 60th Birthday of Hugh Cowie Williams. (Fields Institute Communications, Vol. 41) AMS 2004, ISBN 0-8218-3353-7 .
  • Richard E. Crandall , Carl Pomerance: Prime Numbers - A Computational Perspective. 2nd Edition. Springer, 2005 ISBN 0-387-25282-7 .
  • Victor Shoup: A computational introduction to number theory and algebra. Cambridge 2005, 2008, ISBN 0-521-85154-8 .
  • David Bressoud , Stan Wagon: A course in computational number theory. John Wiley 2008, ISBN 0-470-41215-1 .
  • Harold M. Edwards : Higher Arithmetic: An algorithmic introduction to number theory. Student Mathematical Library vol. 45, American Mathematical Society 2008, ISBN 0-8218-4439-3 .
  • Abhijit Das: Computational number theory . Discrete Mathematics and Its Applications series, Chapman and Hall / CRC Press 2013, ISBN 978-1-4398-6615-3 .
  • Samuel S. Wagstaff, Jr .: The joy of factoring. Student Mathematical Library vol. 68, American Mathematical Society 2013, ISBN 1-4704-1048-6 .

Individual evidence

  1. ↑ see RSA Challenge
  2. ↑ No. 129 of Mathematics of Computation , Volume 29, was dedicated to Lehmer in January 1975 on the occasion of his 70th birthday.
  3. ↑ No. 203 of Mathematics of Computation , Volume 61, was dedicated in July 1993 to the memory of Lehmer.
  4. ↑ On the occasion of the departure of Lenstra after 17 years at the University of Berkeley, a scientific conference took place in March 2003, the Lenstra Treurfeest - A Farewell Conference, March 21-23, 2003 ( Memento of February 13, 2003 in the Internet Archive )
  5. ↑ Issue 3 of Volume 18 (2006) of the Journal de Théorie des Nombres de Bordeaux was dedicated to Pohst on the occasion of his 60th birthday. Journal de théorie des nombres de Bordeaux Volume 18, number 3 (2006)
  6. ↑ Volume 12A (2012) of the journal Integers for combinatorial number theory and additive combinatorics ( [1] ) appeared as John Selfridge Memorial Volume .
  7. ↑ No. 177/178 of Mathematics of Computation , Volume 48, was dedicated to Shanks in January 1987 on the occasion of his 70th birthday.
  8. ↑ For Williams' 60th birthday, a scientific conference was held in his honor in Banff (Canada) in 2003 (see literature). Fields Institute - Conference in Number Theory - 2003 , Number Theory Conference in honor of Professor HC Williams | CISaC
  9. ^ A Computational Introduction to Number Theory and Algebra . Shoup.net. Retrieved September 19, 2010.

Web links