Algorithmische Zahlentheorie - download pdf or read online

By Otto Forster

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 computing device oder notebook 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

Best number theory books

New Visual Perspectives on Fibonacci Numbers by V. Atanassova, A. G. Shannon, J. C. Turner, Krassimir T. PDF

Little or no earlier mathematical wisdom is believed, except the rudiments of algebra and geometry, so the publication can be utilized as a resource of enrichment fabric and undertaking paintings for students. A bankruptcy on video games utilizing goldpoint tiles is integrated on the finish, and it may possibly supply a lot fabric for exciting mathematical actions concerning geometric puzzles of a combinatoric nature.

Get Local fields and their extensions PDF

This e-book is dedicated to the learn of entire discrete valuation fields with excellent residue fields. One certain characteristic is the absence of cohomology; even supposing such a lot experts could locate it tough to conceive of great discussions during this region with no the appliance of cohomology teams, the authors think that many difficulties should be awarded extra rationally while in accordance with extra common, specific structures.

Download e-book for kindle: Number theory: Paris 1993-4 by Sinnou David

This booklet covers the entire spectrum of quantity conception and consists of contributions from recognized, overseas experts. those lectures represent the newest advancements in quantity conception and are anticipated to shape a foundation for extra discussions. it truly is a useful source for college students and researchers in quantity idea.

Basic Analytic Number Theory - download pdf or read online

This English translation of Karatsuba's uncomplicated Analytic quantity conception follows heavily the second one Russian version, released in Moscow in 1983. For the English version, the writer has significantly rewritten bankruptcy I, and has corrected a number of typographical and different minor error through the the textual content.

Additional resources for Algorithmische Zahlentheorie

Example text

Haben alle Ringe Ai ein Einselement, so ist (1, . . , 1) das Einselement des direkten Produkts. Ein Element x = (x1 , . . , xr ) ∈ A ist genau dann invertierbar, wenn alle −1 xi ∈ Ai invertierbar sind und es gilt x−1 = (x−1 1 , . . , xr ). Wir bezeichnen allge∗ mein f¨ ur einen Ring R mit Einselement mit R die multiplikative Gruppe seiner invertierbaren Elemente. Mit dieser Bezeichnung hat man also A∗ = A∗1 × . . × A∗r . B. gilt im direkten Produkt zweier Ringe mit Einselement stets (1, 0) · (0, 1) = (0, 0).

R¨ uckgabewert ist der letzte Primfaktor von x bzw. der letzte Cofaktor. Ist der R¨ uckgabewert < 232 = 42949 67296, so ist er sicher prim, da durch keine Primzahl < 216 teilbar. In der Zeile while q := factor16(x,q) do beachte man, dass in Aribas (wie in der Programmiersprache C) eine Zuweisung als Wert weiterverwendet werden kann und dass u ¨ berall dort, wo ein boolescher Wert erwartet wird (wie hier als Bedingung f¨ ur die while-Schleife), auch ein IntegerWert eingegeben werden kann. Der Wert 0 wird dann als false interpretiert, jeder Wert ungleich 0 als true.

Sei zun¨achst vorausgesetzt, dass gcd(x, m) = 1. 11 ganze Zahlen s, t, so dass sx + tm = 1. h. s mod m ist ein Inverses von x mod m. Sei jetzt umgekehrt vorausgesetzt, dass x mod m in Z/mZ invertierbar ist mit Inversem y mod m. h. xy = 1 + km mit einer ganzen Zahl k. d. Bemerkung. Eine effiziente Berechnung des Inversen im Ring Z/mZ kann mit dem erweiterten euklidischen Algorithmus (§4) erfolgen. 4. Corollar. F¨ ur jede Primzahl p ist Z/pZ ein K¨orper. Beweis. h. das Element x ∈ Z/pZ besitzt ein Inverses.

Download PDF sample

Rated 4.27 of 5 – based on 34 votes