Anzahl Primteiler |
02.06.2012, 21:33 | carm561 | Auf diesen Beitrag antworten » | ||||||||||
Anzahl Primteiler Hallo zusammen, ich hätte da gern mal ein Problem. Es stammt aus Buchmann, Einführung in die Kryptographie, 2. Auflage, und gehört in den Dunstkreis Miller-Rabin-Test. In einem Beweis wählt Buchmann ein gewisses und definiert damit für (das ist die Primfaktorzerlegung von ) folgende Untergruppen von Dann behauptet er: Ist der Index von L in K gleich 2, dann hat n genau zwei Primteiler. Ist der Index von L in K gleich 1, dann ist n Primzahlpotenz. Meine Ideen: Definiere durch ist die Vorzeichenfunktion und sorgt dafür, dass die erste Komponenten immer gleich 1 ist. Mit komponentenweiser Multiplikation ist H eine Gruppe. Der Kern von ist und somit Bei surjektivem ist man fertig, aber eben die Surjektivität kann ich nicht zeigen. Der Chinesische Restsatz liefert zu beliebigem ein mit für jedes . Aber warum gibt es mit ? |
||||||||||||
03.06.2012, 16:17 | Reksilat | Auf diesen Beitrag antworten » | ||||||||||
RE: Anzahl Primteiler Hi carm561, Ich finde die Aussage merkwürdig. Setze zum Beispiel m=2. Dann gibt es genügend Primzahlen , für die -1 kein Quadrat ist, d.h. . Damit sollte sich ein Gegenbeispiel konstruieren lassen. Gruß, Reksilat. |
||||||||||||
03.06.2012, 20:38 | carm561 | Auf diesen Beitrag antworten » | ||||||||||
RE: Anzahl Primteiler Hi Reksilat. Danke für deine Antwort, dachte schon, mit mir möchte keiner über meine Probleme reden Ich teile deine Skepsis, aber wenn nicht surjektiv ist, habe ich keine Ahnung, wie ich Buchmanns Behauptung zeigen soll. Das ist wie schon angedeutet allerdings nicht beliebig, sondern wird während des Beweises konstruiert: Setze mit ungeradem . Sei die größte Zahl in , für die es ein mit und gibt. Ich werde es trotzdem mal für den Fall , also insbesondere durchrechnen. Grüße carm561 aha, warum auch immer funktioniert die Darstellung nicht. Bin aber in Eile, muss ich mir später anschauen. Gruß Edit: LaTeX-Tags mit [/latex] statt mit [\latex] schließen. Gruß, Reksilat. |
||||||||||||
04.06.2012, 09:33 | Reksilat | Auf diesen Beitrag antworten » | ||||||||||
RE: Anzahl Primteiler Jetzt sind noch , und hinzugekommen, aber was sein soll, hast Du noch nicht gesagt. Gruß, Reksilat. |
||||||||||||
04.06.2012, 11:05 | Mystic | Auf diesen Beitrag antworten » | ||||||||||
RE: Anzahl Primteiler
Ja lustig, das Wichtigste hat er weggelassen, nämlich ... |
||||||||||||
04.06.2012, 17:53 | carm561 | Auf diesen Beitrag antworten » | ||||||||||
RE: Anzahl Primteiler Ihr sollt euch nicht über mich lustig machen sondern mein Problem lösen. Grummel Ah, XML-End-Tags statt Latex-Befehl, danke Reksilat. Der Editor hat sogar eine passende Schaltfläche, die ich in der Eile gestern glatt übersehen habe. Mystic hat mit seiner Definition von ins Schwarze getroffen. |
||||||||||||
Anzeige | ||||||||||||
|
||||||||||||
04.06.2012, 20:12 | Reksilat | Auf diesen Beitrag antworten » | ||||||||||
RE: Anzahl Primteiler Ich bin in der Thematik nicht ganz so bewandert und habe leider gerade auch nicht die Zeit, länger drüber nachzudenken. Ich hoffe also, dass Mystic ein paar Tipps für Dich hat. Gruß, Reksilat. |
||||||||||||
04.06.2012, 21:36 | Mystic | Auf diesen Beitrag antworten » | ||||||||||
RE: Anzahl Primteiler @carm561 Mit deinem kann ich irgendwie nichts anfangen... Warum definierst es nicht so: Damit gilt dann offensichtlich Was ferner deine Frage bez. der Lösbarkeit von bzw. betrifft, so brauchst du natürlich die Definition von m dazu, du kannst da nicht einfach irgendein m nehmen, das war wohl ein bißchen sehr naiv von dir gedacht... Probiers mal selbst mit der nachgereichten Definition von m, bei Unklarheiten helfe ich dir gern weiter... |
||||||||||||
04.06.2012, 22:02 | carm561 | Auf diesen Beitrag antworten » | ||||||||||
RE: Anzahl Primteiler So kann man natürlich auch definieren. Aber das kann dann nicht surjektiv sein, wenn Buchmann recht hat. Es erschien mir günstiger, die Funktion so zu definieren, dass ich nur Surjektivität zeigen muss. Kannst du bei deiner Definition angeben? So sehr naiv war das von mir nicht gedacht: Ich kann nicht einmal zeigen, dass es zu irgendein gibt, mit und . Ganz zu schweigen davon, dass gilt. Edit: Hm, dein könnte doch surjektiv sein. Die erste Komponente von ist ja auch immer gleich 1. |
||||||||||||
04.06.2012, 22:31 | carm561 | Auf diesen Beitrag antworten » | ||||||||||
RE: Anzahl Primteiler Edit2: Vergiss was ich schrieb, bei deiner Defintion von muss die erste Komponente nicht 1 sein. Für ist und . |
||||||||||||
04.06.2012, 22:38 | Mystic | Auf diesen Beitrag antworten » | ||||||||||
RE: Anzahl Primteiler Ja, ich versteh auch nicht, warum du so "auf die erste Komponente" fixiert bist... Was ist so besonders an ihr? Wir wissen ja rein gar nichts über die Primzahl , außer dass sie ungerade ist... Edit: Hm, du verwendest n=12 in deinem Beispiel? Du weisst aber schon, dass n für diesen Beweis ungerade sein muss? |
||||||||||||
04.06.2012, 23:02 | carm561 | Auf diesen Beitrag antworten » | ||||||||||
RE: Anzahl Primteiler Ah, jetzt verstehe ich, was dich stört. Ich will mit dem Vorzeichenfaktor nur irgend eine Komponente auf den Wert 1 fixieren. Welche ist mir egal. Die Idee dabei ist, dass meine Zielmenge genau Elemente hat. Bei surjektivem kann ich dann direkt die Behauptungen von Buchmann ablesen. Ja, mir ist klar, dass n ungerade sein muss. Nimm stattdessen |
||||||||||||
05.06.2012, 07:01 | Mystic | Auf diesen Beitrag antworten » | ||||||||||
RE: Anzahl Primteiler Ich denke, dass durch diesen ganzen Formalismus die doch sehr einfache Grundidee "zugedeckt" wird... Diese besteht einfach darin, dass in den definierenden Eigenschaften der Elemente von K bzw. L, nämlich die Vorzeichenwahl für K bei auf alle Arten erfolgen kann, während für L nur zwei Fälle zugelassen sind, nämlich alle Werte sind +1 oder alle Werte sind -1... Du siehst nun hoffentlich auch. warum ich gerade so gewählt habe.. Für die Frage, warum es in K wirklich für jede der möglichen Vorzeichenwahlen ein a dazu gibt muss man natürlich die speziellen Eigenschaften von m heranziehen: Wir wissen ja, dass es ein a gibt, sodass ist und daher wissen wir auch, dass speziell die Kongruenzen für alle i lösbar sind, denn für dieses a ist ja Lösung für alle diese.. |
||||||||||||
08.06.2012, 17:27 | carm561 | Auf diesen Beitrag antworten » | ||||||||||
RE: Anzahl Primteiler @Mystic: Also ich komme weder mit deiner noch mit meiner Definition von weiter. Kannst du bei deiner Definition angeben? |
||||||||||||
08.06.2012, 19:50 | Mystic | Auf diesen Beitrag antworten » | ||||||||||
RE: Anzahl Primteiler
Ja, ich fürchte, ich hab mich da auch geirrt... Wo immer du deine Definition von her hast, aber sie macht jetzt - wo ich mir die Sache doch etwas genauer angesehen habe - durchaus Sinn und ich bin zu ihr (reumütig!) zurückgekehrt... Ich habe nachfolgend den Fall mal im Detail durchgerechnet und das sollte dann auch alle Fragen bisher dann beantworten... Falls noch welche übrig bleiben, dann melde dich einfach wieder...
|
||||||||||||
09.06.2012, 00:01 | carm561 | Auf diesen Beitrag antworten » | ||||||||||
RE: Anzahl Primteiler Allem Anschein nach bin ich zu dusselig. Mir ist nicht einmal klar, was du in Zeile 3 als J berechnest. Die volle ist es jedenfalls nicht, denn die hat bekanntlich 48 Elemente. Ist das eine schlaue Repräsentierung davon bzw. warum kann man die fehlenden Elemente für die weitere Betrachtung einfach weglassen? |
||||||||||||
09.06.2012, 07:50 | Mystic | Auf diesen Beitrag antworten » | ||||||||||
RE: Anzahl Primteiler
Hm, warum hast du nicht einfach für ein einziges "fehlendes" Element a, z.B. a=2 nachgerechnet, dass wirklich gilt? Offenbar hast du irgendwo im Hinterkopf die Beziehung die aber bekanntlich nur für primes n gilt... |
||||||||||||
09.06.2012, 12:02 | carm561 | Auf diesen Beitrag antworten » | ||||||||||
RE: Anzahl Primteiler Dann andersherum gefragt, warum kannst du dich auf Elemente beschränken, für die gilt? In der Definition von steht und das ist etwas anderes. |
||||||||||||
09.06.2012, 13:53 | Mystic | Auf diesen Beitrag antworten » | ||||||||||
RE: Anzahl Primteiler
Naja, unser Ziel ist ja für eine ungerade zusammengesetzte Zahl n>1 den Anteil der falschen Zeugen in {1,2,...,n-1} nach oben hin abzuschätzen... Und jeder falsche Zeuge a erfüllt nun einmal die Kongruenz denn der Miller-Rabin-Test ist ja bekanntlich nur eine Verschärfung des Fermattests, der auf dem "Kleinen Fermat" angewandt auf n für die Basis a beruht... D.h. also, die falschen Zeugen bilden jedenfalls eine Teilmenge von dem J, das aus allen a besteht, welche (*) erfüllen...Und ich hoffe, du siehst auch sofort, dass die Bedingung (*) für ein a automatisch auch ggT(a,n)=1 zur Folge hat, d.j., J ist seinerseits Teilmenge von ... Und ja, es gibt da noch ein weiteres Problem, das dich seit Beginn dieses Threads verfolgt, und das besteht darin, dass du einfach die wichtige Rolle von m aufgrund seiner überaus speziellen Gestalt konsequent unterschätzt...Diese spezielle Gestalt ist wobei kleinstmöglich gewählt ist, sodass die Kongruenz eine Lösung hat...Aufgrund dieser Wahl von m liegt dann jedes Element von K auch automatisch in J, denn man muss, um das zu sehen, ja nur die definierenden Kongruenzen von K j-mal quadrieren (beachte dabei auch, dass j>0 ist!)... Kannst du mal checken, ob dir das soweit klar ist? |
||||||||||||
09.06.2012, 14:25 | carm561 | Auf diesen Beitrag antworten » | ||||||||||
RE: Anzahl Primteiler Du hast einfach die Definition von von Buchmann abgeschrieben. Bei Buchmann steht ausführlich und ja, das ist mir alles klar. Einem Beweis der ursprünglichen Aussage bin ich aber noch keinen Schritt näher. Also mal Klartext: Hast du eine Beweis oder nicht? |
||||||||||||
09.06.2012, 16:16 | Mystic | Auf diesen Beitrag antworten » | ||||||||||
RE: Anzahl Primteiler
Merk dir bitte eines: Ich habe es nicht notwendig, von Buchmann oder irgendjemanden sonst etwas abzuschreiben... Aber es ist richtig, dass ich mich an den Bezeichnungen in seinem Beweis orientiert habe, um es dir leichter zu machen... Das hat man nun davon...
Hm, eben noch klang es anders, nämlich so:
Woher diese plötzliche "Erleuchtung"?
Mag sein, ist aber jetzt nicht unbedingt meine Schuld...
Ok, dann auch von meiner Seite Klartext: Natürlich habe ich den Beweis, inzwischen ja sogar mit deinem Homomorphismus , obwohl ich das vorher noch nicht so kannte... Die Frage sollte also eher lauten, ob ich ihn dir unter diesen Umständen noch mitteilen will... Ich denke, die Antwort darauf sollte dir aber jetzt nicht ganz so schwer fallen, wie manches andere hier... |
||||||||||||
10.06.2012, 11:56 | carm561 | Auf diesen Beitrag antworten » | ||||||||||
Ich hatte schlicht übersehen, dass dein sein ist und ja, es war eine gute Idee von dir, für das Beispiel statt der vollen Restklassengruppe zu nehmen. Mir war und ist aber noch immer nicht klar, was das zum Beweis der ursprünglichen Aussage beiträgt. Die Erleuchtung, von der du sprachst, fehlt so gesehen noch immer. Merk du dir bitte, dass auch ich nicht nötig habe, einen Homomorphismus abzuschreiben. Wenn du deinen Beweis behalten willst, bitte. Mag sein, dass du was von Mathe verstehst, aber du bist sicher nicht halb so gut wie du arrogant bist. |
||||||||||||
10.06.2012, 17:28 | Mystic | Auf diesen Beitrag antworten » | ||||||||||
Naja, im Unterschied zu dir hab ich das auch nicht dezidiert behauptet... Angesichts der einfachen Frage, um die es hier geht, nämlich
waren meine Zweifel aber mehr als nur berechtigt...Immerhin ist die Antwort ja für beide Fälle b=-1 und b=1 vollkommen trivial...Im Fall b=-1 wissen wir ja, dass nach Wahl von m die Kongruenz lösbar ist... Ist a eine Lösung davon, so ist dieses a dann auch Lösung von Der Fall b=1 ist aber wegen der Lösung x=1 ohnehin klar...
Wie sagt man doch (was du aber vielleicht auch noch lernen musst!): Man soll nicht die Hand beissen, die einen füttert... |
||||||||||||
10.06.2012, 17:59 | sulo | Auf diesen Beitrag antworten » | ||||||||||
@carm561 Du ahnst vermutlich nicht einmal, wie sehr du dich irrst. Deine mehrfach gezeigte arrogante Haltung widerspricht der Netiquette hier im Board. |
||||||||||||
11.06.2012, 19:09 | carm561 | Auf diesen Beitrag antworten » | ||||||||||
@sulo: Mir gefällt der Umgangston auch nicht. Ich will auch gar nicht bestreiten, dass ich Anteil an dieser Entgleisung habe. Aber wenn mich die Hand nicht füttert sondern schlägt – und der Vorwurf der Naivität ist eine Ohrfeige – dann beiße ich eben irgendwann. Ist das nachvollziehbar? Aus meiner Sicht haben Mystic und ich uns gegenseitig unterstellt, abgeschrieben zu haben, er nennt mich naiv, ich ihn arrogant. Eine gute Stelle, das Kriegsbeil reumütig zu begraben, wie ich finde. @Mystic: Aus deiner Sicht akzeptabel? |
||||||||||||
11.06.2012, 23:06 | carm561 | Auf diesen Beitrag antworten » | ||||||||||
also ich verstehe, dass du b=-1 und b=1 in der Form schreiben kannst. und wenn ich es weiter richtig verstehe, gehört b=-1 zu , das wegen der negativen ersten Komponente gar nicht in ist. Soweit richtig? Entsprechend gehört b=1 zu . Was ich nicht verstehe ist, wie du mit diesen beiden Fällen z.B das Element erledigst. |
||||||||||||
12.06.2012, 00:36 | Mystic | Auf diesen Beitrag antworten » | ||||||||||
ok, ich rechne dazu ein etwas größeres Beispiel, nämlich n=561, wo man das besser sieht:
Hab den Maple-Code ein bißchen kommentiert... Daraus sollte eigentlich die Anwort auf deine Frage ablesbar sein... Findest du dich damit zurecht? P.S.: Zu dem, was du oben geschrieben hast, möchte ich nur sagen, dass dies deine Sicht der Dinge ist und ich um des lieben Friedens willen nicht im Detail darauf eingehen werde (jeder der den Thread mitliest kann sich ohnehin sein eigenes Urteil bilden)... Eine einzige Anmerkung dazu aber dennoch: "Naiv" hat für mich - und ich habe mich da extra im Internet versichert, dass dies auch stimmt- die Hauptbedeutung von "blauäugig" bzw. "gutgläubig"...Wenn ich sage, es ist naiv anzunehmen, dass man für diesen Beweis ohne die speziellen Eigenschaften von m auskommt, so ist dies keine Aussage über dich als Person allgemein, sondern heißt, dass du in diesem speziellen Fall eine "zu einfache Sicht" der Dinge hast... Was ist daran so fürchterlich? |
||||||||||||
12.06.2012, 10:44 | carm561 | Auf diesen Beitrag antworten » | ||||||||||
Ich habe es eben als Aussage über meine Person aufgefasst und dabei den Duden im Kopf gehabt, der naiv mit kindlich und einfältig gleichsetzt. Das kam dann nicht gut an. Das Beispiel schaue ich mir später an. Danke einstweilen. |
||||||||||||
12.06.2012, 11:08 | Mystic | Auf diesen Beitrag antworten » | ||||||||||
RE: Anzahl Primteiler Übrigens haben ich inzwischen eingesehen, dass mein Mißtrauen bezüglich deiner Autorschaft von , wie hier definiert
sehr wahrscheinlich unberechtigt war... Ein "Profi" hätte nämlich sofort gesehen, dass man die signum-Funktion hier gar nicht braucht, da der kleinste Absolutrest der ersten Komponente ohnehin nur sein kann... |
||||||||||||
12.06.2012, 11:12 | carm561 | Auf diesen Beitrag antworten » | ||||||||||
RE: Anzahl Primteiler Da hat meine Ungenauigkeit doch noch etwas gutes Im maple code hast du es ja schon weggelassen. Habs verstanden, Zeile 26 fehlte mir. Danke |
||||||||||||
12.06.2012, 11:33 | Mystic | Auf diesen Beitrag antworten » | ||||||||||
RE: Anzahl Primteiler Eines würde mich aber doch noch interessieren, da ich den Beweis des Satzes von Rabin-Monier wie meine Westentasche kenne (oder soll ich jetzt sagen, zu kennen glaubte ) und ich selber schon unzählige Male darüber vorgetragen habe: Wozu in aller Welt brauchst du dein überhaupt?... Das übliche Argument ist doch (und so macht's ja, glaube ich, auch der Buchmann), dass die Quadrate von K in liegen müssen, d.h., K/M ist eine abelsche Gruppe mit Exponenten 2 und die Ordnung von K/M daher eine Potenz von 2...Wegen dem 2. Isomorphiesatz für Gruppen, d.h., gilt das dann auch für K/L selbst... Dabei tritt der Fall K=L genau dann ein, wenn n eine Primzahlpotenz ist... Was genau gefällt dir an diesem Argument nicht bzw. ist dir unklar? Edit: Übrigens würde ich in den Definitionen von J,K,L und M die Bedingung ggT(a,n)=1 überall weglassen, da ja die jeweils zweite Bedingung viel stärker ist... Allerdings steht das auch bei Buchmann so ...Warum, das weiß vermutlich nicht einmal er selber... |
||||||||||||
12.06.2012, 12:01 | carm561 | Auf diesen Beitrag antworten » | ||||||||||
RE: Anzahl Primteiler Ich wollte das ganze mit den Mitteln machen, die Buchmann vorher bereitgestellt hat. Der 2. Isomorphiesatz gehört nicht dazu. Dass die Ordnung von K/M eine Potenz von 2 ist habe ich dann aber auch nur hinbekommen, indem ich mich letztlich auf den 1. Sylowschen Satz berufe - der natürlich auch nicht da war. Hat man die Ordnung von K/M, dann ergibt sich aus |K/M|=|K/L| |L/M| - was eine Verallgemeinerung von Lagrange ist und ich mir deshalb erlaubt habe - auch die Ordnung von K/L als Potenz von 2. Von da aus kam ich eben nicht anders an N als mit dem . Edit: Vielleicht ein Zugeständnis von Buchmann an die naiven |
||||||||||||
12.06.2012, 12:06 | Mystic | Auf diesen Beitrag antworten » | ||||||||||
RE: Anzahl Primteiler
Endliche Gruppen mit Exponent 2 sind 1. abelsch (das weiß man hier aber ohnehin) 2. endlichdimensionale Vektorräume über ... Speziell aus 2. folgt dann, nach Wahl einer Basis, dass die Ordnung eine Potenz von 2 ist... |
||||||||||||
16.06.2012, 21:03 | carm561 | Auf diesen Beitrag antworten » | ||||||||||
RE: Anzahl Primteiler ah. sorry, hatte nicht damit gerechnet, dass du nochmal schreiben würdest u deswegen nicht mehr in den thread reingeschaut. öh, ja, das mit dem VR ist sehr schick Danke |
|
Verwandte Themen
Die Beliebtesten » |
Die Größten » |
|
Die Neuesten » |
|