Primfaktorzerlegung |
04.01.2004, 20:42 | Gust | Auf diesen Beitrag antworten » |
Primfaktorzerlegung |
||
04.01.2004, 22:17 | jama | Auf diesen Beitrag antworten » |
400 wurde faktorisiert. die faktoren sind keine primzahlen... falls deine frage darauf abzielen sollte die faktoren könnte man aber weiter zerlegen. |
||
05.01.2004, 00:05 | Gust | Auf diesen Beitrag antworten » |
Ich meine Beliebige Zahlen. Klar ist die Methode mit der Primfaktorzerlegung das einfachste, und diese kann man dann ja beliebig Kombinieren [; (2*2*5)*(2*2*5)] Aber wenn den schwierigsten (bis nahezu unmöglichen) Teil die Primfaktorzerlegung ausmacht, was kann man dann machen? |
||
05.01.2004, 17:10 | alpha | Auf diesen Beitrag antworten » |
gehen wirs doch mal anders an: wie bekommt man denn die primfaktorzerlegung raus? man kann sie nämlich nicht berechnen... nur "ertesten"... und genau so ist das bei den allgemeinen teilern auch... |
||
05.01.2004, 21:07 | Gust | Auf diesen Beitrag antworten » |
Ich weiß schon, wie man die Primfaktorzerlegung Macht, aber ich meine wenn die Zahl zu groß dazu ist. Apropos ertesten: bei 2,3 und 5 kann man schon noch rechnen, aber das nur nebenbei. |
||
05.01.2004, 21:31 | alpha | Auf diesen Beitrag antworten » |
du errechnest aber in dem du ausprobierst... x:2 x:3 x:5... oder wurde inzwischen eine neue methode entwickelt? das würde mich auch mal interessieren... sowas kann ich immer gebrauchen... |
||
Anzeige | ||
|
||
05.01.2004, 21:51 | epikur | Auf diesen Beitrag antworten » |
Es gibt eine Menge besserer Verfahren zur Faktorisierung einer Zahl n als das blosse Ausprobieren aller Primzahlen <= sqrt(n). Die benötigen alle aber ein tiefes Verständnis von Algebra. |
||
06.01.2004, 01:09 | Gust | Auf diesen Beitrag antworten » |
Könntest du das Thema mal anreißen? Wenn es mir zu kompliziert ist, sag ich bescheid, und du brauchst nicht weiter darauf einzugehen. |
||
06.01.2004, 01:26 | epikur | Auf diesen Beitrag antworten » |
Ich hab auch erst ein Semester Algebra Vorlesung hinter mir, und damit noch nicht ganz den Stoff intus den man braucht um das zu verstehen. Der in der Praxis gebräuchlichste Algorithmus ist meines Wissens die Lenstra-Faktorisierung, die mit Elliptischen Kurven über endlichen Körpern arbeiten, d.h. Lösungen der Gleichung y^2 = x^3 + a*x +b über F_(p^n) vereinigt mit oo. Vielleicht findest du mit Google eine Seite die das nett erklärt, aber ich fürchte dem wird nicht so sein. Schliesslich ist das auch bei uns Stoff den man sich erst im Hauptstudium anschauen kann. |
||
06.01.2004, 22:42 | phil | Auf diesen Beitrag antworten » |
Jede Menge Information zu verschieden Faktorisierungs-Methoden gibts hier: http://www.crypto-world.com/FactorPapers.html Soweit ich das richtig verstanden habe ist die zur Zeit schnellste Methode große Zahlen zu Faktorisieren der "number field sieve". Allerdings soll das mit Hilfe von Quantencomputern noch um einiges schneller gehen |
||
07.01.2004, 17:16 | Gockel | Auf diesen Beitrag antworten » |
Mit Quantencomputern wäre das so schnell, dass es sogar polynomiell ist. Das hieße für Quantencomputer gilt: NP=P |
|
Verwandte Themen
Die Beliebtesten » |
Die Größten » |
|
Die Neuesten » |
|