Primzahlfaktoren < Sonstiges < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 16:42 Di 20.07.2004 | | Autor: | Atlana |
Hallo,
kann mir jemand vielleicht sagen ob es eine einfache Möglichkeit ohne Taschenrechner gibt eine Zahl in ihren Primfaktorzerlegungen darzustellen??
Also wenn ich zb die Zahl 600,woher weiß ich daß ihre Primfaktorzerlegung [mm] 2^3*3*5^2 [/mm] ist?? Gibt es da ne Formel für wie ich drauf komm??? Ohne Taschenrechner auszuprobieren??
Danke schonmal.
LG Sandra
Ich habe diese Frage in keinem weiteren Forum gestellt
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 17:02 Di 20.07.2004 | | Autor: | Josef |
Wie weist man eine natürliche Zahl als Primzahl nach?
Es wäre sicherlich sehr aufwendig, müßte man jede kleinere Primzahl auf die Teilereigenschaft bezüglich der vorgegebenen natürlichen Zahl hin untersuchen. Erforderlich ist lediglich eine Untersuchung auf Primteiler, deren Quadrate kleiner sind als die zu untersuchende natürliche Zahl selbst. Denn wäre eine größere Primzahl Teiler, so müßte wegen der vorhandenen eindeutigen Primfaktorzerlegung außerdem noch ein kleinerer Primteiler existieren, so dass ihr Produkt die natürliche Zahl ergibt.
Beispiel:
Ist 563 eine Primzahl?
Wir brauchen wegen [mm] 24^2 [/mm] > 563 nur die Primzahlen 2, 3, 5, 7, 11, 13, 17, 19 und 23 auf Teilbarkeit zu untersuchen. Die Primzahlen 2, 3, 5, und 11 kommen wegen der allgemeinen Teilbarkeitsregeln nicht in Frage.
Bleiben nur noch die Divisionen durch 7, 13, 17, 19 und 23 zu überprüfen, die zeigen, dass 563 eine Primzahl ist.
|
|
|
| |
|
Hallo Sandra,
> kann mir jemand vielleicht sagen ob es eine einfache
> Möglichkeit ohne Taschenrechner gibt eine Zahl in ihren
> Primfaktorzerlegungen darzustellen??
eine einfache Moeglichkeit (mehr im Sinne von effizient bzw. schnell) gibt es (zumindest zur Zeit) nicht. Wuerde es diese Moeglichkeit geben, eine natuerliche Zahl in relativ kurzer Zeit in ihre Primfaktoren zu zerlegen, dann waeren viele Verfahren der Kryptographie unsicher. Denn diese bauen oftmals genau auf das Prinzip auf, dass eine Rechnung in eine Richtung relativ leicht bewerkstelligt werden kann, die Umkehrung jedoch ueberproportional schwierig ist. Also z.B. ist es einfach zwei (grosse) Primzahlen zu multiplizieren, jedoch ist es um einiges schwieriger die zwei Primfaktoren des erhaltenen Produktes zu bestimmen (wenn man nur dieses kennt).
Ein anderes klassisches Beispiel: es ist einfach in einem Telefonbuch die Nummer einer bestimmten Person zu finden, aber es ist ungleich schwieriger zu einer gegebenen Nummer die Person ausfindig zu machen. Ein Verfahren, das sich im Prinzip dieses "Problems" bedient ist RSA (kannst Du Dir evtl. sogar mal anschauen, da es relativ leicht zu verstehen ist).
Natuerlich gibt es verschiedene Wege, die Primfaktoren zu einer gegebenen Zahl zu bestimmen, die effizienter als stupides Durchprobieren aller moeglichen Zahlen sind. Wie man die Sache etwas besser gestalten kann hat ja bereits Josef gezeigt. Interessant dazu ist auch das sogenannte Sieb des Eratosthenes (speziell zum Finden von Primzahlen bzw. Primzahlenlisten). Es gibt nur weitere Algorithmen, von denen mir momentan leider kein Name einfaellt (irgendwas mit "Koerper..."); vielleicht findest Du via google etwas. Ansonsten kann ich Dir noch ein paar Namen nennen, die aber eher zum Ueberpruefen, ob eine Zahl prim ist, verwendet werden: Fermat-Test (dabei gibt es Probleme mit sogenannten Carmichael-Zahlen -> pseudoprim), Miller-Rabin-Test (umgeht das Problem dieser Zahlen), Lucas-Lehmer-Test (wird z.B. von GIMPS verwendet), ... .
So, ich hoffe, das hilft Dir schonmal weiter.
Viele Gruesse,
Michael
|
|
|
|
