Mathematik Informatik Philosophie Diverses Kontatkt FAQ
Benutzername:
Passwort:
 Home > News
Mittwoch, 26. April 2017 00:15 
Artikel zur Kategorie: Mathematik

27 Artikel (6 Seiten, 5 Artikel pro Seite)

zu Seite: 2 1 2 3 4 5 6 zu Seite: 4


Probabilistische Primzahltests (Mathematik)
mehr... (58 mehr Zeichen) Druckoptimierte Version Diesen Artikel an einen Freund senden Kommentare (0) 7822 mal gelesen
Primzahltests sind wichtige Beispiele so genannter probabilistischer Algorithmen. Der Solovay-Strassen-Test war sogar einer der ersten seiner Art und wird am Ende dieses Dokuments behandelt.

Die in diesem Dokument behandelten Primzahltests, der Fermat-Test bzw. Miller-Rabin-Test, sind eng miteinander verknüpft. Der Miller-Rabin-Test kann als Fort- bzw. Weiterentwicklung des Fermat-Tests angsehen werden. Beide Algorithmen basieren auf dem wichtigen und einfach zu beweisenden (kleinen) Satz von Fermat. Allerdings treten beim Fermat-Test Anomalien in Form von Carmichael-Zahlen auf, welche der Miller-Rabin-Test erfolgreich versucht zu umgehen.

Auch der Solovay-Strassen-Test ist eng mit den beiden anderen untersuchten Primzahltests verwandt. Dies äußert sich auch im Zusammenhang zwischen den einzelnen Pseudoprimzahlarten.



Im Einzelnen werden behandelt:
  • Grundsätzliches Vorgehen bei einem probabilistischen Primzahltest, Vorgehen bei einem negativen Testausgang um eine große Primzahl zu finden.
  • Brute-Force-Mathode um eine Zahl zu testen, Zusammenhang mit der Komplexitätstheorie, AKS-Test, deterministischer polynomieller Primzahltest.
  • Definition Zusammengesetzte Zahl, Primzahl, Primfaktorzerlegung, Primfaktoren, Hauptsatz der Zahlentheorie, es existieren unendlich viele Primzahlen, Primzahlsatz und Primzahlverteilung.
  • Anforderungen an ein Kryptosystem; Komplexität; deterministisch; stochastisch unabhängige Wahl der Basis, Zeugen (witness), nicht Zeugen (liar), randomisierten bzw. probabilistischer Algorithmus.
  • Der Fermat-Test, Lemma von Bézout, modulare Inverse, "kleiner" Satz von Fermat, Satz von Euler; a Einheit im Ring Zn genau dann, wenn ggT(n,a)=1; Pseudoprimzahl, Beispiele, Einheitengruppe, Restklassenring, erzeugende Elemente, Eulersche phi-Funktion, Menge aller Basen bilden eine Untergruppe von (Z/nZ)*, zusammengesetzte Zahl, Pseudoprimzahl für mind. die Hälfte aller Basen oder aber für alle Basen.
  • Carmichael-Zahl, Satz von Korselt, Verteilung der Carmichael-Zahlen, "wahrscheinlich prim", Charakterisierung von Carmichael-Zahlen, mindestens Produkt drei verschiedener Primzahlen.
  • Rabin-Miller-Test, Polynom T2-1 hat in einem endlichen Körper der Ordnung p die einzigen Nullstellen +1 und -1, Beweis bzw. Herleitung, triviale Wurzeln bzw. nicht triviale Wurzeln, Beispiele, starke Pseudoprimzahl, höchstens für die Hälfte aller Basen b kann eine zusammengesetzte Zahl eine starke Pseudoprimzahl sein, Laufzeituntersuchungen, O-Notation.
  • Quadratische Reste, quadratische Nichtreste, Anzahl der Quadratwurzeln, Legendre-Symbol, Jacobi-Symbol und quadratische Reste, Zusammenhang beider Symbole, Satz von Euler, Rechenrelgen des Jacobi- bzw. Legendre-Symbols, Eulersche Pseudoprimzahl, der Algorithmus.
Geschrieben von Alexander am Freitag, 12. Januar 2007 mehr...

Primzerlegung in Z (Mathematik)
mehr... (18 mehr Zeichen) Druckoptimierte Version Diesen Artikel an einen Freund senden Kommentare (0) 6505 mal gelesen
Die Zahlentheorie ist zusammen mit der Algebra das wohl älteste Gebiet der Mathematik. Das unvergängliche Problem der Zahlentheorie ist das der Teilbarkeit:

Ist eine Zahl durch eine andere teilbar oder nicht?

Fast alle Themen der elementaren Zahlentheorie sind Variationen dieses Themas oder wurden zumindest durch diese Fragestellung motiviert.
Untersucht man das Teilbarkeitsproblem näher so stößt man unweigerlich auf die Bausteine der natürlichen bzw. ganzen Zahlen, den Primzahlen. Zum Einen können Primzahlen als Spezialfall von Seiten der Algebra (Primelemente) betrachtet werden, zum Anderen kann man diese elementar über den zahlentheoretischen Zugang studieren. In diesem Dokument werden wir den letzteren Weg wählen.

In alt bewährter Manier werden viele Beispiele zur Veranschulichung aufgeführt; ferner werden Beweise sehr ausführlich behandelt.

Im Einzelnen werden behandelt:

  • Das Teilbarkeitsproblem, Voraussetzungen und Überblick.
  • Prinzip vom kleinsten Element, Prinzip der vollständigen Induktion, Beweis der logischen Äquivalenz bzw. Zusammenhang beider Prinzipien.
  • Teilbarkeit und der Ring Z der ganzen Zahlen, Verknüpfungen Addition, (Subtraktion), Multiplikation, (Division), ganzzahlige Division, a teilt b, Beispiele, Integritätsring, aufgehende Zahl, Vielfaches, Lösen linearer Gleichungen ax-b=0 über Z, Rechenregeln für die ganzzahlige Division und Beweise, triviale Teiler, echte Teiler, absolute Betrag, Abschätzungen für Zahlen a|b.
  • Division mit Rest, Beweis der Existenz und Eindeutigkeit, Quotienten, Rest bei der Division, modulo, Modul, Rest, a kongruent b, Kongruenz, Modulus, Äquivalenzrelation für Restklassenringe bzw. Restklassen.
  • Primzahlen, Definition, zusammengesetzte Zahlen, Charakterisierung der Primzahlen, Unzerlegbarkeitseigenschaft, Primeigenschaft, Einheiten 1 und 0 der Addition und Multiplikation, Existenzsatz des kleinsten Teilers einer natürlichen Zahl der eine Primzahl ist, Unendlichkeit der Primzahlen, Satz von Euklid, Euklidscher Beweis, Konstruktionsverfahren von Euklid am Beispiel, Abschätzungen für Primzahlen, Fundamentallemma, p|ab dann folgt p teilt einen der beiden Faktoren.
  • Hauptsatz der elementaren Zahlentheorie, Primfaktoren, Primfaktorzerlegung, Primzerlegung, Eindeutigkeit der Primzerlegung, Existenz der Primzerlegung, jede natürliche Zahl ungleich 0 besitzt genau eine Primzerlegung, Hauptsatz für Z und N.
Geschrieben von Alexander am Freitag, 12. Januar 2007 mehr...

Faktorgruppen, Nebenklassen und Normalteiler (Mathematik)
mehr... (30 mehr Zeichen) Druckoptimierte Version Diesen Artikel an einen Freund senden 5730 mal gelesen
Faktorgruppen und Normalteiler sind unmittelbar mit dem so genannten Homomorphiesatz verbunden. So ist es auch nicht verwunderlich, dass sich bei der Konstruktion der Faktorgruppen der Homomorphiesatz in natürlicher Weise einfügt.

Ebenso ergibt sich ein weiterer grundlegender und bedeutender Satz - der Satz von Lagrange, der weitreichende Folgen nach sich zieht. Diese Folgerungen sind bspw. sehr nützlich um Gruppen zu klassifizieren.

Im Einzelnen werden behandelt:

  • Linksnebenklassen modulo H, Rechtsnebenklassen modulo H, Linkstranslation bzw. Linksmultiplikation, Rechtstranslation bzw. Rechtsmultiplikation. Äquivalenzrelation, Repräsentant bzw. Vertreter, Beispiele
  • Zwei Nebenklassen sind gleichmächtig, Nebenklassen (Äquivalenzklassen) sind entweder gleich oder disjunkt, disjunkte Vereinigung, Index einer Untergruppe H von G, Satz von Lagrange, Anzahl der Linksnebenklassen ist gleich der Anzahl der Rechtsnebenklassen
  • Folgerungen aus dem Satz von Lagrange: Ist G von Primzahlordnung, so hat G nur die trivialen Untergruppen G und {e}, Ordnung eines jeden Elements a aus G ist ein Teiler der Gruppenordnung, jede Gruppe mit Primzahlordnung ist zyklisch, ...
  • Im Allgemeinen entsprechen sich Rechtsnebenklassen und Linksnebenklassen nicht, Beispiel, Kriterium für die Gleichheit von Normalteilern, Definition Normalteiler, Charakterisierung von Normalteilern, jeder Kern eines Homomorphismus ist ein Normalteiler.
  • Definition Faktorgruppe G/S bzw. Quotientengruppe von G nach S, Zuordnung wohldefiniert, Beweis, kanonische Projektion
  • Homomorphiesatz für Gruppen, Beweis, Beispiel und Folgerung
Geschrieben von Alexander am Mittwoch, 04. Oktober 2006 mehr...

Analytische Fortsetzung und der Monodromiesatz (Mathematik)
mehr... (39 mehr Zeichen) Druckoptimierte Version Diesen Artikel an einen Freund senden Kommentare (1) 4889 mal gelesen
Die analytische Fortsetzung einer Funktion hat -lax formuliert- zur Aufgabe den Entwicklungsbereich einer Potenzreihe "auszudehnen". Motivation dieser Übung ist die Mehrdeutigkeit der so bedeutenden Funktionen, wie Log, allen Wurzelfunktionen oder Arccos, usw. einen Definitionsbereich zu konstruieren auf welchen diese eindeutig leben können. Den so genannten Riemannschen Flächen bzw. Gebieten.

Hierzu ist es zunächst notwendig, die Theorie der analytischen Fortsetzungen näher zu untersuchen und evtl. Grenzen dieser Methode aufzuzeigen.
Der Zusammenhang zur holomorphen Fortsetzung wird an Beispielen verdeutlicht und durch Skizzen visualisiert. Da der Identitätsatz von so großer Bedeutung für dieses Thema ist, wird dieser eingeführt, erläutert und bewiesen.

Sodann gehen wir daran die Idee der analytischen Fortsetzung auszudehnen und stoßen damit auf das so genannte Kreiskettenverfahren. Dieses wird erläutert und der Kreiskettensatz bewiesen.

Zum Abschluss führen wir noch den Begriff der Homotopie ein und verbinden diesen mit dem Kreiskettenverfahren. Es wird sich herausstellen, dass homotope Kurven, welche sich fortsetzen lassen und homotop sind, dieselbe Fortsetzung besitzen.

Im Einzelnen werden folgende Themen behandelt:

  • Diskrete Menge und die Koinzidenzmenge, Identitätssatz mit Beweis, Fortsetzung reeller Funktionen ins Komplexe, Diskussion der Voraussetzungen des Identitätssatzes,
  • Folgerungen aus dem Identitätssatz: Jede holomorphe Fortsetzung ist eindeutig bestimmt, Charakterisierung (nicht-)konstanter Funktionen
  • Holomorphe Fortsetzung, analytische Fortsetzung, Beispiel
  • Das Kreiskettenverfahren, Heuristik, Beispiel, Konstruktionsprinzip, Binomialreihe, Funktionselement, direkte bzw. unmittelbare analytische Fortsetzung, unmittelbare Umformung, Beispiel Log, Kreiskette, analytische Fortsetzung längs einer (Kreis-)kette/Kurve
  • Analytischer Zweig des Logarithmus, Beweis, analytische Potenz einer Funktion
  • Homotopie, Beispiel, Homotopieklassen, Äquivalenzrelation, homotop, Fundamentalgruppe
  • Monodromiesatz mit Beweis

 

Geschrieben von Alexander am Montag, 28. August 2006 mehr...

Der Faktorraum von V nach U resp. Quotientenraum V modulo U (Mathematik)
mehr... (11 mehr Zeichen) Druckoptimierte Version Diesen Artikel an einen Freund senden 4347 mal gelesen
Faktorräume von Vektorräumen werden überall in der Mathematik benötigt. Eingeführt werden sie dagegen oftmals in einer Vorlesung zur linearen Algebra, seltener im Rahmen einer Analysis-Vorlesung.

Ein Vektorraum und ein Unterraum wird zur Konstruktion eines Faktorraums benötigt.
Ob man damit elliptischen Funktionen definiert, einen Beweis über nilpotente Endomorphismen erbringt oder aber den Homomorphiesatz beweist - überall erweisen sich diese, zunächst scheinbar schwer zu begreifenden Räume, als überaus gewinnbringend.

Im folgenden Dokument werden Faktorräume prägnant dargestellt, dabei wurde insbesondere auf die Anschaulichkeit Wert gelegt, deshalb findet man auch viele Skizzen und Beispiele.

Im Einzelnen werden behandelt:

  • Nebenklassen und Repräsentanten, wohldefiniert
  • Unterraumkriterium, Untervektorraum, Beispiele
  • Kriterium für die Gleichheit von Nebenklassen, Äquivalenzrelation (Reflexivität, Transitivität, Symmetrie)
  • Basen von Faktorräumen, Faktorraum ist ein Vektorraum
Geschrieben von Alexander am Mittwoch, 19. April 2006 mehr...


27 Artikel (6 Seiten, 5 Artikel pro Seite)

zu Seite: 2 1 2 3 4 5 6 zu Seite: 4


Umfrage
Ganz klar, das schönste Ressort der Mathematik ist die

Zahlentheorie
(Lineare) Algebra
Topologie, Maßtheorie, Integrationstheorie
Statistik, Wahrscheinlichkeitstheorie, Stochastik
Analysis, Funktionalanalysis
Funktionentheorie
Kombinatorik, Graphentheorie
Diskrete Mathematik
Lineare Optimierung

Ergebnisse
Stimmen: 662
Kommentare: 0
Umfragen

Login
Benutzername:

Passwort:



Alle Logos und Warenzeichen auf dieser Seite sind Eigentum der jeweiligen Besitzer und Lizenzhalter.
Im übrigen gilt Haftungsausschluss. Weitere Details finden Sie im Impressum.
Die Inhalte dieser Seite sind als RSS/RDF-Quelle verfügbar.
Die Artikel sind geistiges Eigentum des/der jeweiligen Autoren,
alles andere © 2004 - 2017 by mathematik-netz.de

Seitenerstellung in 0.0775 Sekunden, mit 52 Datenbank-Abfragen