Download Algorithmische Zahlentheorie by Otto Forster PDF

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 machine oder computer 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 or Download Algorithmische Zahlentheorie PDF

Best number theory books

An Introduction to the Theory of Numbers

The 5th variation of 1 of the traditional works on quantity idea, written by means of internationally-recognized mathematicians. Chapters are quite self-contained for better flexibility. New gains contain multiplied remedy of the binomial theorem, concepts of numerical calculation and a bit on public key cryptography.

Reciprocity Laws: From Euler to Eisenstein

This e-book is set the improvement of reciprocity legislation, ranging from conjectures of Euler and discussing the contributions of Legendre, Gauss, Dirichlet, Jacobi, and Eisenstein. Readers an expert in simple algebraic quantity thought and Galois concept will locate unique discussions of the reciprocity legislation for quadratic, cubic, quartic, sextic and octic residues, rational reciprocity legislation, and Eisenstein's reciprocity legislations.

Discriminant Equations in Diophantine Number Theory

Discriminant equations are a huge classification of Diophantine equations with shut ties to algebraic quantity concept, Diophantine approximation and Diophantine geometry. This ebook is the 1st entire account of discriminant equations and their functions. It brings jointly many elements, together with potent effects over quantity fields, potent effects over finitely generated domain names, estimates at the variety of strategies, functions to algebraic integers of given discriminant, strength critical bases, canonical quantity structures, root separation of polynomials and aid of hyperelliptic curves.

Additional resources for Algorithmische Zahlentheorie

Example text

9. Satz. Sei F ∈ Z[X] ein primitives Polynom. Ist F irreduzibel in Z[X], so ist es auch irreduzibel in Q[X]. Beweis. Angenommen, F sei reduzibel in Q[X], also F = g 1 g2 mit gi ∈ Q[X], deg(gi ) > 0. asst sich darstellen als gi = ci Gi mit einem primitiven Polynom Gi ∈ Z[X] Jedes gi l¨ und ci ∈ Q∗ . Dann gilt F = c1 c2 G1 G2 . 8 ein primitives Polynom ist, folgt c1 c2 = ±1. d. 10. Satz (Eisenstein’sches Irreduzibilit¨ats-Kriterium). Sei F (X) = X n + a1 X n−1 + . . + an−1 X + an ∈ Z[X] ur ein Polynom mit ganzzahligen Koeffizienten und p eine Primzahl mit p | ai f¨ 1 i n und p2 an .

Substituiert man darin X durch Y + 1, erh¨ alt man p Φp (Y + 1)Y = (Y + 1) − 1 = p ν=1 p Yν ν p−1 p ν ν=0 ( ν+1 )Y . p sind und ( 1 ) also F (Y ) := Φp (Y + 1) = Da die Binomial-Koeffizienten ( kp ) f¨ ur 1 k p − 1 durch p teilbar = p, erf¨ ullt das Polynom F das Eisenstein’sche Irreduzibilit¨ats-Kriterium. Daher ist F und damit auch Φp irreduzibel. Bemerkung. Geht man zum K¨orper C der komplexen Zahlen u ¨ ber, so gilt nach dem sog. B. [FrBu]), dass jedes Polynom F (X) = X n + a1 X n−1 + . . + an−1 X + an ∈ C[X] n in ein Produkt von Linearfaktoren zerf¨allt, F (X) = ν=1 (X − ζν ).

Man schreibe eine Aribas-Funktion erat_sieve2(start,len: integer): byte_string; die f¨ ur nat¨ urliche Zahlen start 1010 und len 105 das Intervall von start bis start + len siebt und einen Bit-Vektor liefert, in dem das k-te Bit genau dann gesetzt ist, wenn √ 2·(start div 2)+2k+1 eine Primzahl ist. Die zum Sieben n¨otigen Primzahlen start + len erzeuge man dabei durch die Funktion erat_sieve. 4. Man berechne die Anzahl der Primzahlen im Intervall von 10n bis 10n + 1000 f¨ ur n = 3, 4, . . , 10.

Download PDF sample

Rated 4.92 of 5 – based on 43 votes