www.wikidata.de-de.nina.az

Algorithmische Zahlentheorie Die algorithmische Zahlentheorie ist ein Teilgebiet der Zahlentheorie welche wiederum ein T

Algorithmische Zahlentheorie

Die algorithmische Zahlentheorie ist ein Teilgebiet der Zahlentheorie, welche wiederum ein Teilgebiet der Mathematik ist. Sie beschäftigt sich mit der Frage nach effizienten algorithmischen Lösungen für zahlentheoretische Fragestellungen.

Wichtigste Bereiche der elementaren algorithmischen Zahlentheorie sind

Hierfür benötigt man weitere Verfahren, die ebenfalls untersucht werden:

Neue Forschungsergebnisse zur algorithmischen Zahlentheorie werden unter anderem auf der seit 1994 zweijährlich stattfindenden Konferenz ANTS (Algorithmic Number Theory Symposium) präsentiert.

Anwendungen Bearbeiten

Die wichtigste Anwendung der algorithmischen Zahlentheorie ist die Kryptographie. Beispielsweise wird beim RSA-Verfahren ausgenutzt, dass die Primzahleigenschaft einer Zahl schnell überprüft werden kann, aber bislang keine ähnlich schnellen Verfahren bekannt sind, eine zusammengesetzte Zahl (das ist eine Zahl, die nicht prim ist), zu faktorisieren. Auf dieser Tatsache beruht insbesondere die Sicherheit der Datenübertragung im Internet. In diesem Zusammenhang hatte RSA Security größere Summen für diejenigen ausgelobt, denen es gelingt, bestimmte Zahlen zu faktorisieren. Weiter Anwendung in der Kryptographie finden Algorithmen etwa bei der Berechnung von diskreten Logarithmen für andere Verschlüsselungs- und Signaturverfahren.

Ein viel untersuchtes Problem mit weitreichenden Anwendungen ist es, in einem Zahlengitter eine das Gitter erzeugende Basis zu finden, die aus möglichst kurzen und möglichst orthogonalen Basisvektoren besteht (Gitterbasenreduktion).

Personen Bearbeiten

Literatur Bearbeiten

  • Willi Klösgen: Dokumentation über zahlentheoretische Probleme, die mit Hilfe elektronischer Datenverarbeitungsanlagen behandelt wurden. Mitteil. Ges. f. Math. u. Datenverarb. Nr. 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: S. R. Petrick (Hrsg.): SYMSAC '71, Proc. second ACM symposium on symbolic and algebraic manipulation, Los Angeles 1971, S. 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 (Hrsg.): Computational methods in number theory I, II. Math. Centre Tracts 154/155, Math. Centrum Amsterdam, 1982
  • Attila Pethő, Michael Pohst, Hugh Williams, Horst-Günter Zimmer (Hrsg.): 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 (Hrsg.): 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. Reihe Mathematics and Its Applications vol. 88, Kluwer Academic Publishers, Dordrecht 1992; Softcover Springer 2012, ISBN 978-94-010-4796-8.
  • Michael Pohst: Computational Algebraic Number Theory. DMV Seminar Bd. 21, Birkhäuser, Basel 1993, ISBN 3-7643-2913-0.
  • Michel Waldschmidt, Pierre Moussa, Jean-Marie Luck, Claude Itzykson (Hrsg.): 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 (Hrsg.): 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: Algorithmische Zahlentheorie. Vieweg, 1996, ISBN 3-528-06580-X
    • Vgl. auch das zugehörige Programm ARIBAS
  • Duncan A. Buell, Jeremy T. Teitelbaum (Hrsg.): Computational Perspectives on Number Theory: Proc. Conf. in Honor of A.O.L. 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 (Hrsg.): 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 (Hrsg.): 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 (Hrsg.): 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. 2. Aufl., 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. 4. Auflage. Springer, Berlin 2003, ISBN 3-540-55640-0
  • Alf van der Poorten, Andreas Stein, Hugh C. Williams (Hrsg.): High Primes and Misdemeanours: Lectures in Honour 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. 2. Auflage. 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. Reihe Discrete Mathematics and Its Applications, 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.

Weblinks Bearbeiten

Einzelnachweise Bearbeiten

  1. siehe RSA Challenge
  2. Nr. 129 von Mathematics of Computation, Band 29, wurde Lehmer im Januar 1975 anlässlich seines 70. Geburtstags gewidmet.
  3. Nr. 203 von Mathematics of Computation, Band 61, wurde im Juli 1993 dem Gedenken an Lehmer gewidmet.
  4. Anlässlich der Verabschiedung von Lenstra nach 17 Jahren an der Universität Berkeley fand im März 2003 eine wissenschaftliche Konferenz statt, das (Memento vom 13. Februar 2003 im Internet Archive)
  5. Heft 3 von Band 18 (2006) des Journal de Théorie des Nombres de Bordeaux wurde Pohst anlässlich seines 60. Geburtstags gewidmet. (Memento vom 9. Oktober 2007 im Internet Archive)
  6. Band 12A (2012) der Zeitschrift Integers für kombinatorische Zahlentheorie und additive Kombinatorik ([1]) erschien als John Selfridge Memorial Volume.
  7. Nr. 177/178 von Mathematics of Computation, Band 48, wurde Shanks im Januar 1987 anlässlich seines 70. Geburtstags gewidmet.
  8. Zum 60. Geburtstag von Williams wurde 2003 in Banff (Canada) ihm zu Ehren eine wissenschaftliche Konferenz ausgerichtet (siehe Literatur). Fields Institute - Conference in Number Theory - 2003, (Memento vom 24. Juli 2020 im Internet Archive)
  9. A Computational Introduction to Number Theory and Algebra. Shoup.net, abgerufen am 19. September 2010.
wikipedia, wiki, deutsches, deutschland, buch, bücher, bibliothek artikel lesen, herunterladen kostenlos kostenloser herunterladen, MP3, Video, MP4, 3GP, JPG, JPEG, GIF, PNG, Bild, Musik, Lied, Film, Buch, Spiel, Spiele
Veröffentlichungsdatum:
Die algorithmische Zahlentheorie ist ein Teilgebiet der Zahlentheorie welche wiederum ein Teilgebiet der Mathematik ist Sie beschaftigt sich mit der Frage nach effizienten algorithmischen Losungen fur zahlentheoretische Fragestellungen Wichtigste Bereiche der elementaren algorithmischen Zahlentheorie sind Primzahltests Verfahren zur Faktorisierung einer ganzen Zahl Berechnung des diskreten LogarithmusHierfur benotigt man weitere Verfahren die ebenfalls untersucht werden schnelle Multiplikation schnelles Potenzieren Berechnung des grossten gemeinsamen Teilers mit Hilfe des Euklidischen Algorithmus Berechnung des Jacobi Symbols mit Hilfe des quadratischen Reziprozitatsgesetzes Faktorisierung von Polynomen insbesondere auch schnelles Wurzelziehen Neue Forschungsergebnisse zur algorithmischen Zahlentheorie werden unter anderem auf der seit 1994 zweijahrlich stattfindenden Konferenz ANTS Algorithmic Number Theory Symposium prasentiert Inhaltsverzeichnis 1 Anwendungen 2 Personen 3 Literatur 4 Weblinks 5 EinzelnachweiseAnwendungen BearbeitenDie wichtigste Anwendung der algorithmischen Zahlentheorie ist die Kryptographie Beispielsweise wird beim RSA Verfahren ausgenutzt dass die Primzahleigenschaft einer Zahl schnell uberpruft werden kann aber bislang keine ahnlich schnellen Verfahren bekannt sind eine zusammengesetzte Zahl das ist eine Zahl die nicht prim ist zu faktorisieren Auf dieser Tatsache beruht insbesondere die Sicherheit der Datenubertragung im Internet In diesem Zusammenhang hatte RSA Security grossere Summen fur diejenigen ausgelobt denen es gelingt bestimmte Zahlen zu faktorisieren 1 Weiter Anwendung in der Kryptographie finden Algorithmen etwa bei der Berechnung von diskreten Logarithmen fur andere Verschlusselungs und Signaturverfahren Ein viel untersuchtes Problem mit weitreichenden Anwendungen ist es in einem Zahlengitter eine das Gitter erzeugende Basis zu finden die aus moglichst kurzen und moglichst orthogonalen Basisvektoren besteht Gitterbasenreduktion Personen BearbeitenLeonard Adleman A O L Atkin Daniel Bernstein Jonathan Borwein Peter Borwein Richard P Brent John Brillhart Johannes Buchmann Henri Cohen Allan Joseph Champneys Cunningham Noam Elkies Maurice Kraitchik Jeffrey Lagarias Derrick Henry Lehmer 2 3 Emma Lehmer Arjen Lenstra Hendrik Lenstra Jr 4 Edouard Lucas Mark S Manasse Preda Mihăilescu Victor S Miller Peter Montgomery Francois Morain Andrew Odlyzko Michael Pohst 5 John M Pollard Carl Pomerance Hans Riesel Rene Schoof Richard Schroeppel John L Selfridge 6 Daniel Shanks 7 Herman te Riele Samuel Wagstaff Hugh C Williams 8 Marvin Wunderlich Don Zagier Hans ZassenhausLiteratur BearbeitenWilli Klosgen Dokumentation uber zahlentheoretische Probleme die mit Hilfe elektronischer Datenverarbeitungsanlagen behandelt wurden Mitteil Ges f Math u Datenverarb Nr 3 Birlinghoven 1970 Garrett Birkhoff Marshall Hall Jr Computers in Algebra and Number Theory SIAM AMS Proceedings IV AMS Providence 1971 Horst Gunter Zimmer Computers and computations in algebraic number theory In S R Petrick Hrsg SYMSAC 71 Proc second ACM symposium on symbolic and algebraic manipulation Los Angeles 1971 S 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 Hrsg Computational methods in number theory I II Math Centre Tracts 154 155 Math Centrum Amsterdam 1982 Attila Petho Michael Pohst Hugh Williams Horst Gunter Zimmer Hrsg 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 Hrsg 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 Reihe Mathematics and Its Applications vol 88 Kluwer Academic Publishers Dordrecht 1992 Softcover Springer 2012 ISBN 978 94 010 4796 8 Michael Pohst Computational Algebraic Number Theory DMV Seminar Bd 21 Birkhauser Basel 1993 ISBN 3 7643 2913 0 Michel Waldschmidt Pierre Moussa Jean Marie Luck Claude Itzykson Hrsg 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 Hrsg 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 Algorithmische Zahlentheorie Vieweg 1996 ISBN 3 528 06580 X Vgl auch das zugehorige Programm ARIBAS Duncan A Buell Jeremy T Teitelbaum Hrsg Computational Perspectives on Number Theory Proc Conf in Honor of A O L Atkin Chicago 1995 AMS IP Studies in Advanced Mathematics 7 AMS 1997 ISBN 0 8218 0880 X Kalman Gyory Attila Petho Vera T Sos Hrsg 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 Hrsg 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 Hrsg 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 2 Aufl Springer Verlag 2002 ISBN 3 540 43072 5 Istvan Gaal Diophantine equations and power integral bases New computational methods Birkhauser 2002 Springer 2013 ISBN 0 8176 4271 4 Henri Cohen A Course in Computational Algebraic Number Theory 4 Auflage Springer Berlin 2003 ISBN 3 540 55640 0 Alf van der Poorten Andreas Stein Hugh C Williams Hrsg High Primes and Misdemeanours Lectures in Honour 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 2 Auflage 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 9 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 Reihe Discrete Mathematics and Its Applications 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 Weblinks Bearbeiten7th Algorithmic Number Theory Symposium Webauftritt zur Konferenz 2006 History of ANTS Ubersicht der bisher stattgefundenen ANTS Konferenzen H Lenstra C Pomerance J Pila Future directions in algorithmic number theory Workshop at the American Institute of Mathematics Palo Alto 2003 Joseph P Buhler Peter Stevenhagen Hrsg Algorithmic Number Theory MSRI Publications Vol 44 Cambridge University Press 2008 ISBN 978 0 521 80854 5 Einzelnachweise Bearbeiten siehe RSA Challenge Nr 129 von Mathematics of Computation Band 29 wurde Lehmer im Januar 1975 anlasslich seines 70 Geburtstags gewidmet Nr 203 von Mathematics of Computation Band 61 wurde im Juli 1993 dem Gedenken an Lehmer gewidmet Anlasslich der Verabschiedung von Lenstra nach 17 Jahren an der Universitat Berkeley fand im Marz 2003 eine wissenschaftliche Konferenz statt das Lenstra Treurfeest A Farewell Conference March 21 23 2003 Memento vom 13 Februar 2003 im Internet Archive Heft 3 von Band 18 2006 des Journal de Theorie des Nombres de Bordeaux wurde Pohst anlasslich seines 60 Geburtstags gewidmet Journal de theorie des nombres de Bordeaux Volume 18 number 3 2006 Memento vom 9 Oktober 2007 im Internet Archive Band 12A 2012 der Zeitschrift Integers fur kombinatorische Zahlentheorie und additive Kombinatorik 1 erschien als John Selfridge Memorial Volume Nr 177 178 von Mathematics of Computation Band 48 wurde Shanks im Januar 1987 anlasslich seines 70 Geburtstags gewidmet Zum 60 Geburtstag von Williams wurde 2003 in Banff Canada ihm zu Ehren eine wissenschaftliche Konferenz ausgerichtet siehe Literatur Fields Institute Conference in Number Theory 2003 Number Theory Conference in honour of Professor H C Williams CISaC Memento vom 24 Juli 2020 im Internet Archive A Computational Introduction to Number Theory and Algebra Shoup net abgerufen am 19 September 2010 Abgerufen von https de wikipedia org w index php title Algorithmische Zahlentheorie amp oldid 233061352