Mathematik: Primzahlen und elliptische Kurven
Released by matroid on Di. 03. Oktober 2006 09:02:53 [Statistics]
Written by Gockel - 5020 x read [Outline] Printable version Printer-friendly version -  Choose language   
Mathematik

\(\begingroup\)
\geo ebene(160,160) noaxis() xy(-1,2) nolabel() punktform(.) p(-0.5,1.5,E1) p(1.5,1.5,E2) p(1.5,-0.5,E3) p(-0.5,-0.5,E4) fill(E1,E2,E3,E4,E0FFFF) color(aquamarine) s(E3,E4) s(E4,E1) #s(E1,E2) s(E2,E3) color(FFA500) pen(2) param(xx,-0.7,0.3,0.001) param(yy, 0.3,0.7,0.001) plot( sqrt((x-0.5)*x*(x+0.5))+2*x) plot(-sqrt((x-0.5)*x*(x+0.5))+2*x) kurve(xx, sqrt((xx-0.5)*xx*(xx+0.5))+2*xx) kurve(xx,-sqrt((xx-0.5)*xx*(xx+0.5))+2*xx) kurve(yy, sqrt((yy-0.5)*yy*(yy+0.5))+2*yy) kurve(yy, sqrt((yy-0.5)*yy*(yy+0.5))+2*yy) color(000000) pen(1) p(0,1,A) p(0,-1,B) g(A,B) p(1,0,C) p(-1,0,D) g(C,D) \geooff \geoprint()

Primzahlen und elliptische Kurven

Nach den zwei vorangegangenen Artikeln über das Gruppengesetz elliptischer Kurven und die Elliptic Curves Cryptography soll es nun im dritten Teil um zahlentheoretische Anwendungen elliptischer Kurven gehen. Ich werde dabei den Faktorisierungsalgorithmus nach Hendrik Lenstra und das Goldwasser-Kilian-Primalitätszertifikat vorstellen.

Inhalt


Mathematisches über elliptische Kurven

Bevor es richtig losgeht, möchte ich kurz etwas zur Mathematik der elliptischen Kurven sagen. Wir brauchen dieses Mal nämlich ein wenig mehr mathematisches Handwerkszeug als das reine Gruppengesetz.

Hasses Satz

Ein grundlegender, aber äußerst nützlicher Satz ist nach Helmut Hasse benannt. Er liefert eine Abschätzung für die Anzahl der Punkte einer elliptischen Kurve über endlichen Körpern: \darkred\ Ist E(\IF_q) eine elliptische Kurve, so gilt q+1-2\.sqrt(q)<=abs(E(\IF_q))<=q+1+2\.sqrt(q) Ich werde den Satz in diesem Artikel ohne Beweis benutzen, da der Beweis etwas länger ist, wenn man ihn von Anfang an aufbauen muss, und außerdem keine für diesen Artikel interessanten Erkenntnisse liefert. Es sind noch viele weitere Aussagen zur Gruppenordnung möglich und mit Schoofs Algorithmus ist es auch möglich, sie effizient zu berechnen.

Elliptische Kurven mod n

Wir werden uns mit Algorithmen beschäftigen, die der Beantwortung wesentlicher Fragen der algorithmischen Zahlentheorie dienen, nämlich den Fragen, ob eine natürliche Zahl n prim ist und wenn sie es nicht ist, wie ihre Primfaktorzerlegung aussieht. Dabei werden wir mit elliptischen Kurven über Z/nZ hantieren. Auch wenn wir bisher nur elliptische Kurven über Körpern untersucht haben, ist das für die Praxis erst einmal kein Problem für uns. Die Algorithmen, die ich gleich vorstellen werde, funktionieren bestens, wenn man das Gruppengesetz der elliptischen Kurven völlig naiv eins zu eins übernimmt. Es ist trotzdem erwähnenswert, dass man mit der bekannten Berechnungsvorschrift i.A. keine Gruppe bekommt, da in der Definition der Verknüpfung Divisionen auftreten. Wie wir wissen, gibt es bei zusammengesetzten n aber Nullteiler in Z/nZ, die eine solche Division unmöglich machen. Die Verknüpfung ist also auf diese Weise nicht für alle Elemente der Menge definierbar. Wie gesagt, für die Praxis ist das kein Problem, denn sobald man bei den Berechnungen der nachfolgenden Algorithmen auf so einen Nullteiler stößt, hat man ja einen nichttrivialen Teiler von n zur Hand, indem man den ggT des Divisors mit n berechnet, und damit auch eine Antwort auf die jeweilige Fragestellung gefunden. Für die theoretischen Überlegungen ist dies aber zunächst doch ein Problem. Indem man jedoch eine verallgemeinerte Definition der Gruppenverknüpfung mittels projektiver Koordinaten benutzt, kann dies gelöst werden. Dann kann man elliptische Kurven über allen kommutativen Ringen mit 1 definieren (vergleiche hierzu den ersten Artikel): Die projektive Ebene über dem Ring R definiert man dann wie folgt: Zunächst führt man auf R^3 diese Relation ein: \nue_1~\nue_2:<=>\exists\lambda\el\ R^x: \nue_1=\lambda\nue_2 Die Äquivalenzklasse von (u,v,w)^T wird dann mit (u:v:w) bezeichnet, genau wie wir das schon von der projektiven Geometrie über Körpern kennen. Die projektive Ebene ist aber nur eine Teilmenge dieser Faktormenge: PR^2 := menge((u:v:w) | \exists\ r_u, r_v, r_w\el\ R: r_u\.u+r_v\.v+r_w\.w=1) Ist R ein Körper, so ergibt das die übliche Definition, da die Bedingung für jedes Tripel (u,v,w)!=(0,0,0) erfüllbar ist. Im Fall R=\IZ wäre die Bedingung äquivalent zu ggT(u,v,w)=1 und im Fall R=\IZ_n zu ggT(u,v,w,n)=1. Eine elliptische Kurve E(R) wird dann genauso definiert wie bei den Körpern: Als Nullstellenmenge eines homogenen Polynoms der Form y^2\.z+a_1\.xyz+a_3\.yz^2-x^3-a_2\.x^2\.z-a_4\.xz^2-a_6\.z^3\in\ R[x,y,z]. Es gibt i.A. mehrere unendliche Punkte bei elliptischen Kurven über Ringen, trotzdem ist (0:1:0) weiterhin das neutrale Element. Ein nützlicher Aspekt an dieser Definition ist, dass die Reduktion der Punktkoordinaten einer Kurve E(\IZ_n) modulo einer Primzahl p\|n einen array(Gruppenhomomorphismus E(\IZ_n)->E(\IZ_p) liefert). Das ist vor allem deswegen interessant, wenn man zwei Primteiler p und q von n sowie einen Punkt P\el\ E(\IZ_n) hat, der mod p den unendlich fernen Punkt ergibt, mod q aber nicht. Dieser Punkt liegt dann "teilweise im Unendlichen" und die dritte Koordinate ist dann durch p, aber nicht durch q teilbar. Die dritte Koordinate solcher "halbunendliche" Punkte hat also einen gemeinsamen Primteiler mit n. Man kann zeigen, dass das Auftreten eines solchen Punktes äquivalent dazu ist, dass bei seiner Berechnung durch das Gruppengesetz wie wir es kennen, eine unerlaubte Division durch einen Nullteiler auftrat.

ECM - Faktorisierung mit elliptischen Kurven

Es existieren dutzende Verfahren zur Faktorisierung von speziellen natürlichen Zahlen. John M. Pollard beschrieb 1974 ein solches Verfahren, das man auch Pollards p-1 Algorithmus nennt. Schauen wir uns doch einmal kurz an, was seine Idee war: Angenommen die Zahl n=pqr sei gegeben, wobei hier p und q verschiedene Primzahlen und r einfach eine natürliche Zahl ist. Nehmen wir auch noch an, dass p-1 selbst keine allzu großen Primfaktoren hat. Wählt man dann eine genügend große Schranke B und berechnet das Produkt e aller Primpotenzen <=B, dann ist p-1 ein Teiler dieses Produkts. Es gilt dann nach Fermats kleinem Satz für jede natürliche Zahl a, die nicht von p geteilt wird: a^e==1 (mod p) Es ist hingegen nicht sehr wahrscheinlich, dass dies auch für alle Primfaktoren von n zutrifft, sofern man die Schranke B geschickt wählt. Es existiert also höchstwahrscheinlich ein zweiter Primteiler q, so dass a^e!==1(mod q) ist. Das heißt, dass a^e-1 von p, aber nicht von q geteilt wird. Bildet man also ggT(a^e-1,n)=ggT(a^e-1 mod n,n), so ist man effizient in der Lage einen nichttrivialen Faktor von n zu finden, nämlich p oder zumindest ein Vielfaches von p. Nun hat man aber das Problem, dass man p vorher nicht kennt und daher die Schranke B nur schlecht bestimmen kann. Wählen wir uns irgendein B, so besteht zwar eine gewisse Chance, dass p-1 "B-potenzglatt" ist - wie man die obige Eigenschaft auch nennt - aber wenn p-1 das nicht ist, haben wir ein Problem. Man könnte größere Werte von B ausprobieren, aber da die Wahl dieser Schranke den größten Anteil an der Laufzeit des Algorithmus hat, würde dies den Effizienzvorteil zu nichte machen. Das Verfahren ist so also nicht für allgemeine Zwecke zu gebrauchen. Es taugt nur für einige spezielle Zahlen. Glücklicherweise entwickelte Hendrik Lenstra 1980 aber eine abgewandelte Version dieses Verfahrens für elliptische Kurven, welche auch Lenstras Methode oder ECM - Elliptic Curves Method - genannt wird. Sie ist wesentlich vielseitiger einsetzbar und ist auf eine sehr viel größere Menge von natürlichen Zahlen anwendbar. Der Algorithmus ist erstaunlich einfach und rückblickend wieder einmal völlig naheliegend Wir haben wieder eine Zahl n und eine Schranke B wie oben. Aus dieser Schranke berechnen wir uns ebenfalls den Exponenten e. Dann geht es los mit der ECM: \ll(1)Wähle zufällig eine Elliptische Kurve E(\IZ_n) und einen Punkt P\el\ E(\IZ_n) \ll(2)Berechne das Element e*P \ll(3)Wird bei der Berechnung durch ein Element geteilt, was in \IZ_n nicht invertierbar ist \(also gemeinsame Teiler mit n hat\), so wird abgebrochen. \ll(4)Wenn nicht, dann starten wir noch einen Versuch. Warum funktioniert das? Nehmen wir wieder die Faktorisierung n=pqr an. Wählen wir dann eine elliptische Kurve E(\IZ_n) und reduzieren sie modulo p, so erhalten wir E(\IZ_p) und von dieser Kurve wissen wir, dass sie zwischen p+1-2\.sqrt(p) und p+1+2\.sqrt(p) Elemente hat. Jede natürliche Zahl im Intervall (p+1-2*sqrt(p),p+1+2*sqrt(p)) kommt dabei vor und die Ordnungen der elliptischen Kurven mod p sind auch einigermaßen gleichförmig verteilt in diesem Intervall, wenn p nicht sehr klein ist \(aber kleine Primfaktoren schließt man in der Praxis sowieso durch eine Probedivision von vornherein aus\). Nun gibt es höchstwahrscheinlich auch einige B\-potenzglatte Ordnungen in diesem Intervall, solange B eine vernünftige Größe hat. Treffen wir eine Kurve mit so einer Ordnung, dann ist e*P=\inf in E(\IZ_p), da e ja ein Vielfaches der Ordnung abs(E(\IZ_p)) ist. Wie schon bei der p-1 Methode ist es aber weniger wahrscheinlich, dass e*P auch modulo anderen Primteilern von n zu \inf wird. Wir haben also einen "halbunendlichen" Punkt gefunden, bei dessen Berechnung Nullteiler von \IZ_n aufgetreten sein müssen. In Schritt 2 finden wir somit einen der gesuchten Teiler von n. Betrachtet man die Unterschiede zwischen Pollards und Lenstras Vorgehen, so fällt ein wesentlicher Vorteil der ECM ins Auge: Beim p-1 Algorithmus hatte man wenig Möglichkeiten, wenn p-1 nun nicht B-potenzglatt war, und musste den Algorithmus dann ohne Ergebnis abbrechen. Die Faktorisierung mit elliptischen Kurven lässt sich davon jedoch nicht abschrecken, denn wir können einfach eine neue Kurve wählen. Hier kommt es nämlich darauf an, dass die Ordnung der zufällig gewählten Kurve die Glattheitseigenschaft erfüllt, und nicht die feste Zahl p-1. Ein weiterer nicht zu verachtender Vorteil ist die Tatsache, dass sich der Algorithmus parallel verarbeiten lässt. Hat man mehrere Prozessoren zur Verfügung, so kann man gleichzeitig mehrere elliptische Kurven abarbeiten lassen und den Algorithmus so kräftig beschleunigen. Auch hier ist allerdings die Größe von B bzw. e der entscheidende Faktor in der Laufzeit. Wählt man B kleiner, so sinkt die Dichte von B-potenzglatten Zahlen im Intervall, das durch den Satz von Hasse vorgegeben wird. Vergrößert man B, explodiert wieder die Laufzeit. In der Praxis sieht es deshalb heutzutage so aus: Einige High-End-Algorithmen wie das Quadratische Sieb und das allgemeine Zahlkörpersieb sind erheblich im Vorteil gegenüber der ECM, was die asymptotische Laufzeit betrifft. Allerdings haben sie große Konstanten, so dass man die Faktorisierung meist aufteilt: Kleine Primfaktoren findet man durch Probedivision. Für die mittelgroßen Primfaktoren benutzt man die Methode der elliptischen Kurven mit einem B in der Größenordnung 108. Damit findet man Faktoren mit ca. 40 Ziffern (~130 Bits) und nur für die größeren Faktoren nimmt man dann wieder die richtig schweren Geschütze. Wer an aktuellen Rekorden für die Faktorisierung mit der ECM interessiert ist, der kann ja mal auf dieser Seite nachschauen (Link gefunden von susi0815).

Zertifizierung von Primzahlen

Was ist eigentlich ein Zertifikat?

Dieser Frage gehen wir zuerst nach. Für viele Anwendungen z.B. in der Kryptographie werden Primzahlen benötigt und nicht immer hat der Anwender diese dabei selbst erzeugt. Oft genug bekommt er öffentliche Schlüssel zugeschickt und muss sie anwenden. In sehr vielen Algorithmen sind dabei eine oder mehrere Primzahlen im Spiel und die Sicherheit hängt nicht selten genau von dieser Primalität ab. Besonders in sicherheitskritischen Bereichen braucht man deshalb Beweise, dass die jeweilige Zahl wirklich prim ist. Hier kommen dann die Zertifikate ins Spiel. Allgemein formuliert ist ein Zertifikat ein Satz von Daten, die es effizient erlauben, eine bestimmte Eigenschaft zu überprüfen und zweifelsfrei zu beweisen. ("zweifelsfrei" ist natürlich abstrahiert zu verstehen. Völlige Sicherheit vor z.B. Hardwarefehlern kann es naturbedingt nicht geben.) Ein simples Beispiel: Angenommen, man möchte die Eigenschaft "n ist eine zusammengesetzte Zahl" zertifizieren. Dazu ist es völlig ausreichend, einen Teiler von n anzugeben. Wer immer das Zertifikat prüfen möchte, kann dies dann durch eine simple Probedivision tun. Geht sie ohne Rest auf, so hat der Prüfer damit einen todsicheren Beweis, dass n keine Primzahl ist. Bleibt ein Rest, so wird das Zertifikat abgelehnt und der Kommunikationspartner als Betrüger entlarvt. An diesem Beispiel fällt schon ein wesentliches Kriterium für Zertifikate auf: Nur das Überprüfen muss effizient möglich sein. Das konkrete Finden eines Teilers ist z.B. ziemlich aufwändig, während die Division sehr effizient implementiert werden kann. Noch etwas fällt auf: Zertifikate sind i.A. so angelegt, dass nur die positive Antwort etwas bringt. Wenn die Probedivision aus dem Beispiel fehlschlägt, dann wissen wir weiterhin nicht, ob n zusammengesetzt oder prim ist. Wir wollen nun ein Zertifikat kennenlernen, dass einer gegebenen Zahl p bescheinigt, wirklich eine Primzahl zu sein.

Das Goldwasser-Kilian-Zertifikat

Das Zertifikat nach Goldwasser-Kilian (benannt nach der amerikanischen Informatikerin Shafi Goldwasser und ihrem Kollegen Joe Kilian), das die Primalität der natürlichen Zahl n beweist, besteht aus folgenden Daten: \ll(a)Einer elliptischen Kurve E(\IZ_n) zusammen mit einem Punkt P\el\ E(\IZ_n) \ll(b)Einer Primzahl q>(wurzel(4,p)+1)^2, sodass es eine Zahl m=k*q gibt mit m*P=\inf und k*P=(u:v:w) mit w\el\IZ_n^x. \ll(c)Einem weiteren Zertifikat, welches beweist, dass q prim ist. Das Goldwasser-Kilian-Zertifikat ist also ein rekursives Zertifikat, das eine Folge von immer kleiner werdenden (q kann immer kleiner als n gewählt werden) Primzahlen und den entsprechenden Daten enthält. Die Folge endet selbstverständlich, sobald die Zahlen klein genug sind, um sie sofort als Primzahlen zu erkennen. Die natürliche Frage ist nun, warum das Zertifikat funktioniert. Das ist aber schnell zu beantworten: \darkred\ Liegt ein gültiges Goldwasser\-Kilian\-Zertifikat für n vor, so ist n eine Primzahl \blue\ Beweis: Aus dem Zertifikat wissen wir, dass es einen Punkt der Ordnung q in E(\IZ_n) gibt, nämlich den Punkt k*P \(Es ist ja kP!=\inf=(0:1:0) und q(kP)=mP=\inf\). Gäbe es nun einen Primteiler p<=sqrt(n), so können wir E(\IZ_n) mod p reduzieren. Da die dritte Koordinate von k*P teilerfremd zu n ist, ist sie auch teilerfremd zu p und insbesondere modulo p von 0 verschieden. Auch in E(\IZ_p) ist also kP!=\inf. Daher muss kP mod p auch die Ordnung q haben. Nun wissen wir aber aus Hasses Theorem, dass E(\IZ_p) maximal die Ordnung p+1+2\.sqrt(p)<=sqrt(n)+1+2\.wurzel(4,n)=(wurzel(4,n)+1)^212n) ein solches Zertifikat für eine Primzahl n generiert. (Diese Laufzeit gilt - sofern einige Vermutungen wahr sind, die man aber heutzutage für richtig hält - für fast alle Eingaben): Gegeben sei eine natürliche Zahl n, die höchstwahrscheinlich prim ist \(Also z.B. einen Miller\-Rabin\-Test mit 10-20 Basen bestanden hat\). \ll(1)Wähle zufällig eine elliptische Kurve E(\IZ_n) und berechne mit Schoofs Algorithmus die Ordnung m, die E(\IZ_n) haben müsste, wenn n prim ist. Tritt in Schoofs Algorithmus ein Fehler auf, so ist n nicht prim. \ll(2)Spalte kleine Primfaktoren von m durch Probedivision ab und prüfe, ob der Rest eine wahrscheinliche Primzahl (wurzel(4,n)+1)^24n). Dies ist deutlich schneller, als es selbst der AKS-Test sein könnte. Da AKS im Moment sowieso noch unpraktikabel ist, ist der Goldwasser-Kilian-Test noch immer verbreitet. Meistens allerdings in der verbesserten Version von Atkin und Morain, die das Zertifikat nochmal ein paar Größenordnungen schneller erzeugen kann, nämlich in erwarteten O(log6n). Ihr Vorgehen wandelt den Schritt 1 ab, indem nicht mehr aus der Kurve die Ordnung berechnet wird und stattdessen ein m vorgegeben wird, zu dem eine passende Kurve konstruiert wird. Der Beweis der Primeigenschaft ist mit der Methode nach Goldwasser-Kilian sogar so effizient, dass damit schon für über 20000-stellige Primzahlen Zertifikate erstellt werden konnten. Das Programm PRIMO, welches diesen Test implementiert, ist eines der meistgenutzten Tools für das Testen auf Primalität allgemeiner Zahlen.

Am Beispiel der vierten Fermat-Zahl

Ich möchte das Goldwasser-Kilian-Verfahren nun direkt am Beispiel der vierten Fermat-Zahl 224+1 demonstrieren. Wer ein bisschen programmieren kann oder geduldig mit dem Taschenrechner durch 54 Primzahlen divieren will, der kann sich natürlich einfach davon überzeugen, dass diese Zahl prim ist. Aber das ist ja viel weniger spannend als der Weg über die elliptischen Kurven Sei also p=2^2^4+1=65537. Wenn man ein wenig Glück \(oder wahlweise mehr Hintergrundwissen\) hat, dann findet man schnell die Kurve E_1, die durch die Gleichung y^2=x^3+2 über \IF_p gegeben ist und m=p+1 Punkte hat \(sofern p wirklich prim ist\). Durch Probedivision mit den Primzahlen unterhalb von 20 findet man: m=2*3^2*11*331 331 kommt also für das gesuchte q in Frage, denn 331>(wurzel(4,p)+1)^2\approx\ 289. Fehlt uns also noch ein Punkt P, der m*P=\inf und (m/q)P!=\inf erfüllt. Man sieht sofort, dass P=(-1:1:1) ein Punkt auf der Kurve ist. Man kann jetzt überprüfen, ob (2*3^2*11)P!=\inf ist. Wenn ich mich nicht vertan habe, erhält man 198P=(11137:-19443:1). Jetzt nehmen wir diesen Punkt und multiplizieren ihn mit 331. Das ergibt in der Tat (0:1:0)=\inf. P ist also für unser Zertifikat geeignet. Was jetzt noch zu tun bleibt, ist ein Zertifikat für q=331 auszustellen. Hier findet man schnell die Kurve E_2, die durch y^2=x^3+x über \IF_q gegeben ist und m=q+1=332 Elemente hat, wenn q wirklich prim ist. Durch Probedivision erhalten wir m=2^2*83 und mit ein wenig Probieren findet man heraus, dass P=(3:19:1) ein Punkt der Kurve ist, der 4P=(14:21:1) und 332P=(0:1:0)=\inf erfüllt. Da wir 83 ohne Probleme direkt als Primzahl erkennen können und 83>(wurzel(4,331)+1)^2\approx\ 27.7 gilt, ist damit bewiesen, dass 331 prim ist, und damit wissen wir wiederum, dass 65537 prim ist.

Abschluss

So, das war dann der letzte Artikel über elliptische Kurven und ihre Anwendungen. Ich hoffe, er hat euch gefallen. Es gäbe noch unendlich viel mehr über elliptische Kurven zu erzählen und wer weiterhin Interesse an diesem spannenden Thema zeigt, dem sei ein weiteres Mal das Buch Elliptic Curves - Number Theory and Cryptography von Lawrence C. Washington empfohlen. E(\IZ_mfg)->E(\IZ_Gockel)

 
Dieser Artikel ist enthalten in unserem Buch
Mathematisch für fortgeschrittene Anfänger
Mathematisch für fortgeschrittene Anfänger

\(\endgroup\)
Get link to this article Get link to this article  Printable version Printer-friendly version -  Choose language     Kommentare zeigen Comments  
pdfpdf-Datei zum Artikel öffnen, 198 KB, vom 03.10.2006 13:17:50, bisher 4775 Downloads


Arbeitsgruppe Alexandria Dieser Artikel ist im Verzeichnis der Arbeitsgruppe Alexandria eingetragen:
: Mathematik :: Angewandte Mathematik :: Algebraische Kurven :: Elliptische Kurven :: Zahlentheorie :: Primzahlen :: Faktorisierung :: Sonstige Mathematik :
Primzahlen und elliptische Kurven [von Gockel]  
Dritter und Letzter Teil der Artikelreihe über elliptische Kurven und ihre Anwendungen. Dieses Mal gehts um die Anwendungen in der Zahlentheorie, speziell die Elliptic-Curves-Method zur Faktorisierung natürlicher Zahlen und das Goldwasser-Kilian-Zertifikat, das die Primalität einer Zahl beweist.
[Die Arbeitsgruppe Alexandria katalogisiert die Artikel auf dem Matheplaneten]

 
 
Aufrufzähler 5020
 
Aufrufstatistik des Artikels
Insgesamt 446 externe Seitenaufrufe zwischen 2012.01 und 2021.10 [Anzeigen]
DomainAnzahlProz
https://google.com327.2%7.2 %
http://google.de33575.1%75.1 %
https://google.de296.5%6.5 %
http://google.it112.5%2.5 %
https://duckduckgo.com81.8%1.8 %
https://www.ecosia.org51.1%1.1 %
https://www.bing.com61.3%1.3 %
http://de.yhs4.search.yahoo.com20.4%0.4 %
http://search.conduit.com10.2%0.2 %
https://www.startpage.com10.2%0.2 %
http://www.bing.com92%2 %
http://google.com10.2%0.2 %
http://google.at10.2%0.2 %
http://de.search.yahoo.com20.4%0.4 %
https://startpage.com10.2%0.2 %
https://metager.de10.2%0.2 %
http://www.website-unavailable.com10.2%0.2 %

Aufrufer der letzten 5 Tage im Einzelnen
Insgesamt 2 Aufrufe in den letzten 5 Tagen. [Anzeigen]
DatumAufrufer-URL
2021.10.13-2021.10.16 (2x)https://google.com/

Häufige Aufrufer in früheren Monaten
Insgesamt 415 häufige Aufrufer [Anzeigen]
DatumAufrufer-URL
2013-2018 (117x)http://google.de/url?sa=t&rct=j&q=
201211-11 (47x)http://google.de/url?sa=t&rct=j&q=zeitaufwand der größenordnung ellipti...
2020-2021 (29x)https://google.com/
202103-06 (27x)https://google.de/
201201-02 (21x)http://google.de/url?sa=t&rct=j&q=primzahlen kurve
2013-2016 (19x)http://google.de/url?sa=t&rct=j&q=elliptische kurven primzahltest
201203-03 (15x)http://google.de/url?sa=t&rct=j&q=primzahlen neueste erkenntnisse
201205-05 (15x)http://google.de/url?sa=t&rct=j&q=punktordnung elliptische kurve
201212-12 (14x)http://google.de/url?sa=t&rct=j&q=wahl schranke b ecm lenstra
201403-03 (11x)http://google.it/search?q=elliptische kurven erzeugen
201303-03 (11x)http://google.de/url?sa=t&rct=j&q=primzahlenkurve
201309-09 (8x)http://google.de/url?sa=t&rct=j&q=primzahlen parallel in elliptischen kurven
2020-2021 (8x)https://duckduckgo.com/
201302-02 (7x)http://google.de/url?sa=t&rct=j&q=methode der elliptischen kurven
201301-01 (7x)http://google.de/url?sa=t&rct=j&q=primzahl elliptische kurve
201210-10 (7x)http://google.de/url?sa=t&rct=j&q=uni mathematik ellipische kurvenmethode
201204-04 (7x)http://google.de/url?sa=t&rct=j&q=warum funktioniert elliptische kurven metho...
201209-09 (6x)http://google.de/url?sa=t&rct=j&q=homogene koordinaten ecm algorithmus
201208-08 (6x)http://google.de/url?sa=t&rct=j&q=elliptische kurven primzahlen
2020-2021 (5x)https://www.ecosia.org/
201305-05 (5x)http://google.de/url?sa=t&rct=j&q=primzahlzerlegung ecm test
201503-03 (5x)http://google.de/url?sa=t&rct=j&q=faktorisierung mit elliptischen kurven
202105-07 (5x)https://www.bing.com/
201307-07 (5x)http://google.de/url?sa=t&rct=j&q=faktorisieren elliptische kurven wahl a und...
201702-11 (4x)http://google.de/
201206-06 (4x)http://google.de/url?sa=t&rct=j&q=potenzglatte Ordnung Mathe

[Top of page]

"Mathematik: Primzahlen und elliptische Kurven" | 5 Comments
The authors of the comments are responsible for the content.

Re: Primzahlen und elliptische Kurven
von: Ex_Mitglied_40174 am: Di. 03. Oktober 2006 09:14:18
\(\begingroup\)Wie beweist man den grob den Satz von Hasse?\(\endgroup\)
 

Re: Primzahlen und elliptische Kurven
von: Gockel am: Di. 03. Oktober 2006 23:55:41
\(\begingroup\)Hi Anonymous. Ein grober Beweisansatz ist folgender (aus dem verlinkten Buch entnommen): Zu zeigen ist also folgendes: \darkred\ q+1-2\.sqrt(q)<=abs(E(\IF_q))<=q+1+2\.sqrt(q) Man betrachtet dazu eine Weierstrass\-Gleichung mit Koeffizienten in \IF_q und die dazugehörige Kurve über dem algebraischen Abschluss E(array(\IF_q)^-) sowie den Endomorphismus \(elliptischer Kurven\) \phi2_q, der durch den Frobenius\-Automorphismus x\mapsto\ x^q induziert wird. Es gilt dann Ker(\phi2_q-1)=E(\IF_q). Außerdem ist \phi2_q-1 ein so genannter separabler Endomorphismus. Ein EC\-Endomorphismus ist ein Gruppenhomomorphismus, der durch birationale Abbildungen gegeben ist, und Separabilität ist eine Eigenschaft, die den Grad dieser Abbildungen zur Größe des Kerns in Verbindung setzt. Man setzt dann a:=q+1-abs(E(\IF_q))=q+1-abs(Ker(\phi2_q-1)) und zeigt abs(Ker(r*\phi2_q-s))=r^2*q+s^2-rsa für ggT(q,s)=1. Daraus folgt dann r^2*q+s^2-rsa>=0 <=> (r/s)^2*q+1-a(r/s)>=0 für alle r/s mit ggT(s,q)=1. Da diese Brüche dicht in \IR liegen, gilt x^2*q-ax+1>=0 für alle x\el\IR. Daraus folgt, dass die Diskriminante a^2-4q<=0 sein muss, also abs(a)<=2\.sqrt(q). \blue\ q.e.d. Wie gesagt: Die Details sind länglich und hätten für diesen Artikel nichts Interessantes gebracht, auch wenn die Betrachtung der Endomorphismen wirklich spannend sein kann. Insbesondere, da man bei elliptischen Kurven über endlichen Körpern interessante Endomorphismenringe (oft bekommt man Gitter in IC), welche dann Rückschlüsse auf die Gruppenordnung zulassen etc. Aber das fällt alles unter den "unendlich viel mehr"-Teil, die ich wohl nicht mehr in Artikeln verarbeiten werde, das würde einfach zu speziell. mfg Gockel.\(\endgroup\)
 

Re: Primzahlen und elliptische Kurven
von: Wally am: Mo. 09. Oktober 2006 11:38:24
\(\begingroup\)Hallo, Gockel, Primzahlen und elliptische Kurven sind Gebiete, an denen ich bisher völlig vorbeigelebt habe. Wenn ich deine Artikel überfliege (zum genauen Nachrechnen fehlt doch leider die Zeit), bekomme ich Lust, mit damit doch noch mal zu beschäftigen. Viele Grüße Wally\(\endgroup\)
 

Re: Primzahlen und elliptische Kurven
von: KlausLange am: Mo. 20. November 2006 14:46:57
\(\begingroup\)Eine interessante Entwicklung im Zusammenhang mit der Primzahlzwillingsvermutung zeichnet sich ab. Für elliptische Kurven lässt sich eine Analogie zur Primzahlzwillingsvermutung formulieren und so in Angriff nehmen. Ein Seminar findet dazu am 22.11.2006 statt: www.utoronto.ca/reg/list_full.pl?20061022-1410.30812 Wird über die elliptischen Kurven die Primzwillingsvermutung geklärt?\(\endgroup\)
 

Re: Primzahlen und elliptische Kurven
von: Gockel am: Mo. 20. November 2006 19:13:28
\(\begingroup\)Hi Klaus. Wenn man das beweisen könnte, wäre zumindest einen Schritt dichter an einem Beweis der Primzwillingsvermutung, denke ich. Man müsste dann nämlich "nur" eine (Familie) von Kurven über den rationalen Zahlen finden, so dass es eben nach dieser Vermutung von Koblitz unendliche viele Primzahlen p gibt, so dass die mod p reduzierte Kurve ebenfalls von Primzahlordnung ist. Der Haken ist eben das Finden solcher Kurven, man kann zwar beliebig viele Kurven finden, deren Reduktion mod p genau p+1 Elemente hat, aber Kurven zu finden, deren Reduktion p+2 bzw. p-2 Elemente hat, dürfte um einiges schwieriger sein. mfg Gockel.\(\endgroup\)
 

 
All logos and trademarks in this site are property of their respective owner. The comments are property of their posters, all the rest © 2001-2021 by Matroids Matheplanet
This web site was originally made with PHP-Nuke, a former web portal system written in PHP that seems no longer to be maintained nor supported. PHP-Nuke is Free Software released under the GNU/GPL license.
Ich distanziere mich von rechtswidrigen oder anstößigen Inhalten, die sich trotz aufmerksamer Prüfung hinter hier verwendeten Links verbergen mögen.
Lesen Sie die Nutzungsbedingungen, die Distanzierung, die Datenschutzerklärung und das Impressum.
[Seitenanfang]