Download e-book for kindle: Algorithmische Zahlentheorie by Otto Forster

By Otto Forster

ISBN-10: 3658065397

ISBN-13: 9783658065393

Das Buch gibt eine Einführung in die Zahlentheorie bis hin zu den quadratischen Zahlkörpern. Dabei wird durchgehend auch der algorithmische Aspekt betrachtet. So werden Existenzsätze (z.B. für die Darstellung von Primzahlen der shape p=4n+1 als Summe von zwei Quadratzahlen) stets durch Algorithmen zur Konstruktion ergänzt. Neben den klassischen Inhalten der elementaren Zahlentheorie werden in dem Buch u.a. auch die Multiplikation großer ganzer Zahlen mittels der schnellen Fourier-Transformation sowie Faktorisierung ganzer Zahlen mit elliptischen Kurven behandelt.

Für die Neuauflage wurden bekannt gewordene Fehler der ersten Auflage korrigiert und an mehreren Stellen Umarbeitungen vorgenommen. Außerdem gibt es neue Abschnitte über die Faktorisierung mit dem Quadratischen Sieb, den Diskreten Logarithmus (der in der Kryptographie eine große Rolle spielt) sowie über den deterministischen AKS-Primzahltest mit polynomialer Laufzeit. Damit der Leser die Algorithmen auf seinem desktop oder computing device auch konkret testen kann, werden die Algorithmen in einem pascalähnlichen Code für den vom Autor entwickelten Multipräzisions-Interpreter ARIBAS beschrieben, der zum kostenlosen obtain zur Verfügung steht.

Show description

Read Online or Download Algorithmische Zahlentheorie PDF

Similar number theory books

New PDF release: Invitations to the Mathematics of Fermat

Assuming in basic terms modest wisdom of undergraduate point math, Invitation to the math of Fermat-Wiles provides varied suggestions required to realize Wiles' amazing facts. additionally, it locations those recommendations of their old context. This booklet can be utilized in advent to arithmetic theories classes and in targeted themes classes on Fermat's final theorem.

Download PDF by Jozsef Beck, William W. L. Chen: Irregularities of Distribution

This e-book is an authoritative description of a number of the methods to and techniques within the concept of irregularities of distribution. the topic is essentially thinking about quantity conception, but in addition borders on combinatorics and likelihood idea. The paintings is in 3 components. the 1st is worried with the classical challenge, complemented the place acceptable with more moderen effects.

Read e-book online Arithmetic and geometry PDF

The 'Arithmetic and Geometry' trimester, held on the Hausdorff examine Institute for arithmetic in Bonn, focussed on contemporary paintings on Serre's conjecture and on rational issues on algebraic kinds. The ensuing complaints quantity presents a contemporary review of the topic for graduate scholars in mathematics geometry and Diophantine geometry.

Extra resources for Algorithmische Zahlentheorie

Example text

Allgemeiner wird bei einer Zerlegung m = m1 m2 . . mr mit teilerfremden mi die Arithmetik des Ringes Z/mZ auf die Arithmetik der kleineren Ringe Z/mi Z zur¨ uckgef¨ uhrt. Dies kann man zur Implementation von Big-Integer-Arithmetik ben¨ utzen, wobei sich diese Methode gut zur Parallelisierung eignet, denn die arithmetischen Operationen im Ring Z/mi Z k¨onnen komponentenweise v¨ollig unabh¨angig voneinander durchgef¨ uhrt werden. 6 in Aribas implementieren. Wir fassen die als teilerfremd vorausgesetzten Zahlen mi zu einem Array M zusammen.

Sei zun¨achst vorausgesetzt, dass k und m teilerfremd sind. Dann gibt es ganze Zahlen ν, μ mit νk + μm = 1. Daraus folgt bν = akν = a1−μm = a, da a−μm = e. Das erzeugende Element a von G liegt also in der von b erzeugten Untergruppe. Daraus folgt, dass auch b die Gruppe G erzeugt. Sei umgekehrt vorausgesetzt, dass b die Gruppe G erzeugt. Dann gibt es eine ganze Zahl ν, so dass bν = a. h. akν−1 = e. Also muss kν − 1 ein ganzzahliges Vielfaches von m sein, es gibt also eine ganze Zahl μ mit kν − 1 = μm.

Satz. Sei G eine zyklische Gruppe der Ordnung m und a ein erzeugendes Element von G. Genau dann ist ak ein erzeugendes Element von G, wenn k und m teilerfremd sind. Beweis. Wir setzen b := ak . Sei zun¨achst vorausgesetzt, dass k und m teilerfremd sind. Dann gibt es ganze Zahlen ν, μ mit νk + μm = 1. Daraus folgt bν = akν = a1−μm = a, da a−μm = e. Das erzeugende Element a von G liegt also in der von b erzeugten Untergruppe. Daraus folgt, dass auch b die Gruppe G erzeugt. Sei umgekehrt vorausgesetzt, dass b die Gruppe G erzeugt.

Download PDF sample

Algorithmische Zahlentheorie by Otto Forster


by Daniel
4.3

Rated 4.86 of 5 – based on 28 votes