Die Mathe-Redaktion - 19.06.2018 10:55 - Registrieren/Login
Auswahl
ListenpunktHome
ListenpunktAktuell und Interessant ai
ListenpunktArtikelübersicht/-suche
ListenpunktAlle Links / Mathe-Links
ListenpunktFach- & Sachbücher
ListenpunktMitglieder / Karte
ListenpunktRegistrieren/Login
ListenpunktArbeitsgruppen
ListenpunktSchwätz / Top 15
ListenpunktWerde Mathe-Millionär!
ListenpunktAnmeldung MPCT Juli
ListenpunktFormeleditor fedgeo
Aktion im Forum
Suche
Stichwortsuche in Artikeln und Links von Matheplanet
Suchen im Forum
Suchtipps

Bücher
Englische Bücher
Software
Suchbegriffe:
Mathematik bei amazon
Naturwissenschaft & Technik
In Partnerschaft mit Amazon.de
Kontakt
Mail an Matroid
[Keine Übungsaufgaben!]
Impressum

Bitte beachten Sie unsere Nutzungsbedingungen, die Distanzierung, unsere Datenschutzerklärung und
die Forumregeln.

Sie können Mitglied werden. Mitglieder können den Matheplanet-Newsletter bestellen, der etwa alle 2 Monate erscheint.

Der Newsletter Okt. 2017

Für Mitglieder
Mathematisch für Anfänger
Wer ist Online
Aktuell sind 597 Gäste und 22 Mitglieder online.

Sie können Mitglied werden:
Klick hier.

Über Matheplanet
 
Zum letzten Themenfilter: Themenfilter:
Matroids Matheplanet Forum Index
Moderiert von Wauzi
Mathematik » Zahlentheorie » Primzahlen lösen und dann?
Druckversion
Druckversion
Antworten
Antworten
Autor
Universität/Hochschule Primzahlen lösen und dann?
monarch87
Aktiv Letzter Besuch: im letzten Quartal
Dabei seit: 27.10.2010
Mitteilungen: 409
Aus:
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Themenstart: 2018-02-25


Wer garantiert mir, dass mir, wenn ich die Lösung für Primzahlenbestimmung poste, sie keiner klaut?

Grüße m0n4rch87 razz



  Profil  Quote  Link auf diesen Beitrag Link
dietmar0609
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 29.06.2007
Mitteilungen: 2592
Aus: Oldenburg , Deutschland
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.1, eingetragen 2018-02-25


ist es das Sieb des Eratosthenes ???

Wenn nicht, beschreib mal was deine "Primzahlbestimmung" kann ....

Ausserdem klaut hier keiner was .....

Gruss Dietmar



  Profil  Quote  Link auf diesen Beitrag Link
viertel
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 04.03.2003
Mitteilungen: 26348
Aus: Hessen
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.2, eingetragen 2018-02-25


Nunja, da das Forum öffentlich einsehbar ist, kann also jeder, auch ohne Anmeldung, kiebitzen — und stibitzen.

@monarch87
Schreibe deine Idee zunächst per PM an ein Mitglied/Senior deines Vertrauens.


-----------------
Bild



  Profil  Quote  Link auf diesen Beitrag Link
Regmorus
Wenig Aktiv Letzter Besuch: vor mehr als 3 Monaten
Dabei seit: 09.01.2018
Mitteilungen: 50
Aus:
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.3, eingetragen 2018-02-25


Du veranlasst besser die Löschung dieses Threads und versteckst dich im Wald, wobei du zuvor jegliche Infos von dir aus dem Netz entfernst.
Ich hoffe, es ist noch nicht zu spät... Sag niemandem etwas vom Bildungsgesetz, sonst bringst du den Menschen auch in Gefahr. Ach so vergiss nicht Überlebenszeug mitzunehmen, es wird wahrscheinlich einige Jahre dauern. Ich hoffe, du liest es rechtzeitig, viel Glück!

EDIT: viertel und Dietmar sind involviert, das ist wohl klar  mad Sie wollen sicher gehen...



  Profil  Quote  Link auf diesen Beitrag Link
Wirkungsquantum
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 10.03.2015
Mitteilungen: 442
Aus:
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.4, eingetragen 2018-02-25

\(\begingroup\)
Hallo Regmorus,
ich glaube monarch87 Intention war nicht eine mögliche Entdeckung geheim zu halten, sondern das die Entdeckung dann von jemand anderes als Eigenverdienst "geklaut" werden kann, wenn er sie direkt öffentlich raus posaunen würde.

Grüße,
h


-----------------
$h=6,626⋅10^{-34} Js$
\(\endgroup\)


  Profil  Quote  Link auf diesen Beitrag Link
Red_
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 28.09.2016
Mitteilungen: 445
Aus: Erde
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.5, eingetragen 2018-02-25


Wie wäre es, wenn du deine Lösung perfekt aufschreibst und dann auf ArXiv veröffentlichst?
So hat es Grigori Perelman damals gemacht :D
Falls du Erfolg hast, kannst du dein Paper ja einer Fachschrift vorlegen und diese veröffentlichen es vielleicht (wobei es in diesem Fall sicher veröffentlicht werden würde).




  Profil  Quote  Link auf diesen Beitrag Link
Slash
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 23.03.2005
Mitteilungen: 6667
Aus: New York
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.6, eingetragen 2018-02-25


Lade dein Paper/Idee auf irgendeinen Server (privat, onlinspeicher, etc.). Für arXiv benötigst du einen Hochschulaccount(Student sein reicht aber nicht) oder Fürsprecher. Einen Fürsprecher kannst du aber nur gewinnen, wenn du ihm dein Paper vorlegst. Hätte arXiv nicht so strenge Kontrollen, würde es schnell das Niveau von viXra erreichen. Fachzeitschriften ist es aber egal, ob du dein Paper zuvor auf arXiv oder deiner Homepage oder gar nicht veröffentlich hast. Dort zählt allein die Qualität deiner Arbeit.

Aber auch ohne dass du uns hier deine Idee erläuterst, können wir sie testen. Kannst du beliebig große Primzahlen generieren oder beliebig große Zahlen schnell auf Primalität testen?



  Profil  Quote  Link auf diesen Beitrag Link
Regmorus
Wenig Aktiv Letzter Besuch: vor mehr als 3 Monaten
Dabei seit: 09.01.2018
Mitteilungen: 50
Aus:
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.7, eingetragen 2018-02-25


Hallo Wirkungsquantum,

es war eigentlich Anspielung auf Geheimdienste, nicht wirklich was ernst gemeintes  biggrin

Ich bezweifle, dass der TS gemeint hatte, er habe bereits etwas gefunden, eher ist das als eine rhetorisch-theoretische Frage zu interpretieren, scheint es mir.



  Profil  Quote  Link auf diesen Beitrag Link
monarch87
Aktiv Letzter Besuch: im letzten Quartal
Dabei seit: 27.10.2010
Mitteilungen: 409
Aus:
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.8, vom Themenstarter, eingetragen 2018-03-08


"Dividing Numbers By 9er Series Is Maybe The Fastest Algorithm To Detect Prime Numbers Or Find The Composition"


www.facebook.com/groups/512316765497242/permalink/1732101383518768/



  Profil  Quote  Link auf diesen Beitrag Link
MartinN
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 05.08.2016
Mitteilungen: 884
Aus: Bayern
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.9, eingetragen 2018-03-08

\(\begingroup\)
Ich versteh nicht ganz, wie du auf "fastest algorithm" kommst...
Welcher Algorithmus denn?

An sich (wenn ich es richtig verstehe) überprüfst du, ob für deine Zahl \(n \in \IN\) gilt: \(\gcd(n;10^k-1) = 1 \forall k \in [1;10^{\lceil \log(n) \rceil}-1]\) oder so...

Aber da musst du auch mega viele Zahlen überprüfen :D (sogar mehr als n)
Oder wie kann man den größten gemeinsamen Teiler (gcd) einer Zahl n und einer Zahl bestehend aus nur 9en schnell ermitteln?

Und wenn das immer 1 ist, dann sei n eine Primzahl? (das müsste man ja auch beweisen)
\(\endgroup\)


  Profil  Quote  Link auf diesen Beitrag Link
dietmar0609
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 29.06.2007
Mitteilungen: 2592
Aus: Oldenburg , Deutschland
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.10, eingetragen 2018-03-08


Dein Facebook Beitrag hat mich nicht auf Anhieb überzeugt. Wäre nett, wenn du uns hier im Forum deine Primzahlzerlegung von 203 nochmal näher erläutern könntest.

Gruss Dietmar  

[Die Antwort wurde nach Beitrag No.8 begonnen.]



  Profil  Quote  Link auf diesen Beitrag Link
Nichtaristoteles
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 20.01.2018
Mitteilungen: 99
Aus:
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.11, eingetragen 2018-03-08


2018-02-25 19:01 - Slash in Beitrag No. 6 schreibt:
Hätte arXiv nicht so strenge Kontrollen

Naja, so streng können die Kontrollen ja auch nicht sein, wenn es Artikel dort gibt, die Wikipedia im Literaturverzeichnis haben.



  Profil  Quote  Link auf diesen Beitrag Link
Bernhard
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 01.10.2005
Mitteilungen: 5878
Aus: Merzhausen, Deutschland
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.12, eingetragen 2018-03-08


Hallo monarch!

Selbst wenn Du tatsächlich einen funktionierenden und effektiven Algorithmus zur Primfaktorzerlegung oder Primzahlgenerierung gefunden hättest, dann wäre immernoch die Frage, ob es aus Sicherheitsgründen oder rein ethischen Gesichtspunkten überhaupt sinnvoll wäre, diesen publik zu machen. Denn damit wären praktisch die ganzen heutigen Methoden zur Datenverschlüsselung unbrauchbar und nichts mehr sicher. Willst Du das wirklich haben? confused

Aber wenn Du das mit Deinem Gewissen verantworten kannst und dementsprechend keine Skrupel hast, diese Methoden zur Nutzung freizugeben, dann solltest Du sie meistbietend an die Geheimdienste versteigern und nicht hier öffentlich machen. cool

Aus diesen Gründen kann man umgekehrt schließen: Wenn Du wirklich hier oder in einem anderen Forum etwas darüber schreiben solltest, dann kann nicht viel dran sein. Und Leute oder Institutionen, die solche Sachen wirklich verwenden könnten und scharf drauf wären, würden sie hier nicht suchen. Insofern ist Deine "Lösung" hier sicher. wink

Viele Grüße, Bernhard


-----------------
"Wichtig ist, daß man nie aufhört zu fragen"
"Weisheit ist nicht das Ergebnis der Schulbildung, sondern des lebenslangen Versuches, sie zu erwerben"
Albert Einstein



  Profil  Quote  Link auf diesen Beitrag Link
StrgAltEntf
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 19.01.2013
Mitteilungen: 4142
Aus: Milchstraße
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.13, eingetragen 2018-03-08


2018-03-08 19:58 - Bernhard in Beitrag No. 12 schreibt:
Aber wenn Du das mit Deinem Gewissen verantworten kannst und dementsprechend keine Skrupel hast, diese Methoden zur nutzung freizugeben, dann solltest Du sie meistbietend an die Geheimdienste versteigern und nicht hier öffentlich machen. cool

Das ist zudem äußerst gefährlich. Geheimdienste haben schon aus nichtigeren Gründen Leute liquidiert. eek



  Profil  Quote  Link auf diesen Beitrag Link
Bernhard
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 01.10.2005
Mitteilungen: 5878
Aus: Merzhausen, Deutschland
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.14, eingetragen 2018-03-08


Hallo StrgAltEntf!

2018-03-08 20:15 - StrgAltEntf in Beitrag No. 13 schreibt:
Das ist zudem äußerst gefährlich. Geheimdienste haben schon aus nichtigeren Gründen Leute liquidiert. eek

Vielleicht ist dieser Thread ja eher als Asylgesuch auf dem Matheplneten gemeint?

Bernhard


-----------------
"Wichtig ist, daß man nie aufhört zu fragen"
"Weisheit ist nicht das Ergebnis der Schulbildung, sondern des lebenslangen Versuches, sie zu erwerben"
Albert Einstein



  Profil  Quote  Link auf diesen Beitrag Link
hyperG
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 03.02.2017
Mitteilungen: 435
Aus:
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.15, eingetragen 2018-03-10


2018-03-08 15:15 - monarch87 in Beitrag No. 8 schreibt:
"Dividing Numbers By 9er Series Is Maybe The Fastest Algorithm To Detect Prime Numbers Or Find The Composition"


www.facebook.com/groups/512316765497242/permalink/1732101383518768/

Also ich werde nicht extra facebook-Mitglied, nur um was lesen zu können.

Kann es sein, dass alles in folgenden Bild enthalten ist:
Quelle des Bildes ?

Hört sich komplizierter an, als gängige Algorithmen.

"...Or Find The Composition"
Na dann zeig mir bitte die Zerlegung von
17969491597941066732916128449573246156367561808012600070888918835531726460341490933493372247868650755230855864199929221814436684722874052065257937495694348389263171152522525654410980819170611742509702440718010364831638288518852689

DAS würde mich dann sofort überzeugen!!!



  Profil  Quote  Link auf diesen Beitrag Link
ligning
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 07.12.2014
Mitteilungen: 2145
Aus: Berlin
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.16, eingetragen 2018-03-10


2018-03-10 22:30 - hyperG in Beitrag No. 15 schreibt:
Kann es sein, dass alles in folgenden Bild enthalten ist:
Quelle des Bildes ?
Im Prinzip schon, dir entgehen einige Absätze Eso-Geschwurbel.



-----------------
⊗ ⊗ ⊗



  Profil  Quote  Link auf diesen Beitrag Link
stpolster
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 27.03.2014
Mitteilungen: 473
Aus: Chemnitz
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.17, eingetragen 2018-03-10


Der "Satz von Munir Benjamin Bashir Schmidt-Sidique" dürfte bei der Wahl zum skurrilsten Beitrag zur "Entwicklung" der Mathematik 2018 sehr gute Chancen auf Platz 1 haben.  razz

Steffen



  Profil  Quote  Link auf diesen Beitrag Link
Slash
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 23.03.2005
Mitteilungen: 6667
Aus: New York
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.18, eingetragen 2018-03-11


2018-03-10 23:11 - stpolster in Beitrag No. 17 schreibt:
Der "Satz von Munir Benjamin Bashir Schmidt-Sidique" dürfte bei der Wahl zum skurrilsten Beitrag zur "Entwicklung" der Mathematik 2018 sehr gute Chancen auf Platz 1 haben.  razz

Steffen

Gute Chancen auf Platz 1 für den skurrilsten Namen hat er auch. biggrin

Im Übrigen ist es verpönt als Mathematiker selbst Sätze nach sich zu benennen.



  Profil  Quote  Link auf diesen Beitrag Link
hyperG
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 03.02.2017
Mitteilungen: 435
Aus:
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.19, eingetragen 2018-03-12


Lasst uns doch nicht übereinander herziehen, sondern sachlich die Machbarkeit ausloten:

Ich habe jetzt von meiner 230 stelligen Zahl (die bis heute nicht faktorisiert ist) den Kehrwert
1/a auf 50000 Stellen berechnet -> und nun?
Schritt 2 bitte genauer.

Formulierungen mit "Periode von 9nen" kann ich als Praktiker nichts anfangen...



  Profil  Quote  Link auf diesen Beitrag Link
monarch87
Aktiv Letzter Besuch: im letzten Quartal
Dabei seit: 27.10.2010
Mitteilungen: 409
Aus:
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.20, vom Themenstarter, eingetragen 2018-03-21


Teile die Zahl durch die gleiche Anzahl an Neuner

-> Dann schaue wie ihre Periode ist

-> Wenn Periode der 230-Stelligen Zahl beispielsweise
   120 ist, solltest du deine 230 stellige Zahl versuchen durch 120
   Neuner zu teilen, wenn das nicht funktioniert, dann müsstest du deine
   230-Stelligen Zahl durch 230 Neuner teilen-

Wenn beides keinen Teiler ergibt, dann ists wohl eine Primzahl

fed-Code einblenden

Habe mega viel zu tun, aber ich führe es mit Formeleditor diese Woche nochmal ausführlicher. Es lässt sich zeigen, dass eine Zahl, wenn sie ein Composite ist durch eine gewisse Anzahl an Neunerreihen im Divisor

Grüße monarch87, der Metatron-Samadhi  smile



  Profil  Quote  Link auf diesen Beitrag Link
pzktupel
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 02.09.2017
Mitteilungen: 397
Aus: Thüringen,Erfurter Raum
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.21, eingetragen 2018-03-21


Das wird nix, die Idee PLATZT!
Du erzeugst nur ein ggT(N,R(m))
Repunits R(m) haben nie alle Primteiler , sondern nur
der Form 2*k*N+1..oder dem trivialen Fall (10^(p-1)-1)/9 , falls
p das N teilt. Dann ist aber weit über SQRT(N) für die Ermittlung
des Teilers hinausprobiert worden. Dein Bsp mit 16 9er für den Teiler
17 sagt es doch aus. Du kannst nicht 5917 zerlegen, ohne eine 60 oder 96er Neunerkette zu generieren. Mit Sicherheit wird es länger dauern, um eine solche Anzahl an 9er zu bekommen, als Primteiler bis 73 zu testen....
und wir reden hier von Kleinstteilern smile

Gruß



  Profil  Quote  Link auf diesen Beitrag Link
juergen007
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 17.08.2006
Mitteilungen: 2737
Aus: Braunschweig
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.22, eingetragen 2018-03-21


2018-03-21 16:49 - pzktupel in Beitrag No. 21 schreibt:
Das wird nix, die Idee PLATZT!
Du erzeugst nur ein ggT(N,R(m))
Repunits R(m) haben nie alle Primteiler , sondern nur
der Form 2*k*N+1..oder dem trivialen Fall (10^(p-1)-1)/9 , falls
p das N teilt. Dann ist aber weit über SQRT(N) für die Ermittlung
des Teilers hinausprobiert worden. Dein Bsp mit 16 9er für den Teiler
17 sagt es doch aus. Du kannst nicht 5917 zerlegen, ohne 60 und 96 Neunerketten zu generieren.

Gruß

Hatten wir schon unter LinkPrimzahlkonstruktion




  Profil  Quote  Link auf diesen Beitrag Link
hyperG
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 03.02.2017
Mitteilungen: 435
Aus:
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.23, eingetragen 2018-03-22


2018-03-21 16:49 - pzktupel in Beitrag No. 21 schreibt:
Das wird nix, die Idee PLATZT!
Du erzeugst nur ein ggT(N,R(m))
Repunits R(m) ... Mit Sicherheit wird es länger dauern, um eine solche Anzahl an 9er zu bekommen, als Primteiler bis 73 zu testen....
und wir reden hier von Kleinstteilern smile

Gruß

Danke Norman für den logischen ggT-Algorithmus.
Ich gehe ja immer ohne Vorurteil an solche Dinge heran und teste praktisch oder suche weitere Abkürzungen.

Habe ihn mal auf schwer zerlegbare RSA-Zahlen angewendet:
Algorithmus ist bis 12stellige Zahlen noch machbar:
Untersuche 904133512333 Fund nach n=123456 Iterationen mit 123456stelligen Zwischenergebnissen in etwa 2 Sekunden!
ggT(904133512333,(10^123456-1)/9)=123457 also
123457 * 7323469 = 904133512333

ABER Rechenzeit steigt exponentiell an; bei 16stelliger Zahl:
8794406909724391 Fund bei n=12345700 in 13 Stunden!!!!
ggT(8794406909724391, (10^12345700-1)/9)= 12345701
denn 12345701 * 712345691 = 8794406909724391

Mit anderen Worten: der 10er-Exponent ist etwa so groß wie der gesuchte kleinste Faktor!
Selbst mit Tricks wie
- "nur gerade n"
- Start bei der Wurzel der gegebenen Zahl in beide Richtungen
- Parallelisierung
ergeben sich Unmengen an hypergroßen Berechnungen!

@monarch87:
Habe wirklich ohne Vorurteile versucht, etwas positives zu finden.
Bei 263713 schien es auch eine Verbesserung gegenüber "Suche bis zur Wurzel" zu geben:
ggT(263713,(10^(n)-1)/9), nach n=26 Iterationen ggT=859 .
Doch statt Verbesserungen zu anderen Algorithmen, gab es exponentielle Verschlechterung.
Leider Absolut unbrauchbar für Zahlen oberhalb 16 Stellen!

Selbst leichter zerlegbare Carmichael-ähnliche Zahlen, die Seiten wie
Carmichael-Zahl-Faktorisierer
in unter 1 s lösen:
900000000000000032978100000000000302098633
sind für den hier vorgestellten "geheimen ggT-Periode-9-Algorithmus" ungeeignet: 4 Mio Iterationen & keine Abkürzung dabei.



  Profil  Quote  Link auf diesen Beitrag Link
Marcel74
Neu Letzter Besuch: im letzten Quartal
Dabei seit: 23.03.2018
Mitteilungen: 2
Aus:
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.24, eingetragen 2018-03-23


Hallo!

Mein Eindruck ist, dass es sich hier um die Umkehrung des klassischen Teiles der Shor-Faktorisierung handelt.
Diese Faktorisierung ist vom Prinzip her sehr einfach (ähnlich wie Fermat), und lautet: Um eine Zahl

fed-Code einblenden

zu faktorisieren suche zwei Zahlen B und T, so dass

fed-Code einblenden

Wie erhält man daraus die Faktoren von N? Aus obiger Gleichung folgt

fed-Code einblenden

das wiederum kann man schreiben mit

fed-Code einblenden

Man findet so mit einer gewissen Wahrscheinlichkeit durch den ggT die Faktoren von N

fed-Code einblenden

___


Man kann das Ganze nun vereinfachen und sich auf B=10 beschränken.
Um N zu faktorisieren lautet dann die Forderung: Suche ein T, so dass

fed-Code einblenden

Dann findet man die Faktoren von N mit

fed-Code einblenden


Um eine praktische Faktorisierung durchzuführen geht man dabei so vor: Die Gleichung

fed-Code einblenden

bedeutet

fed-Code einblenden

Das lässt sich wiederum schreiben mit

fed-Code einblenden

das ergibt

fed-Code einblenden

D.h. es gibt eine Zahl, die aus lauter 9er besteht und die durch N teilbar ist.
(Es lässt sich zeigen, dass es immer eine solche Zahl gibt)



Ich rechne hier mal ein Beispiel vor:

Gegeben sei N = 39. Diese Zahl soll faktorisiert werden. Wir schreiben also eine
endlose Zahl mit 9er hin und dividieren so lange durch N bis sich Rest 0 ergibt:

fed-Code einblenden

Wir stellen also fest, dass die Zahl 999999 durch 39 teilbar ist. Die
Anzahl der 9er ist 6, das bedeutet T = 6. Somit können wir N faktorisieren:

fed-Code einblenden


Statt die Division

fed-Code einblenden

durchzuführen, bietet sich auch der ggT an, womit man oft schneller am Ziel ist, also

fed-Code einblenden



  Profil  Quote  Link auf diesen Beitrag Link
hyperG
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 03.02.2017
Mitteilungen: 435
Aus:
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.25, eingetragen 2018-03-23


Gut Marcel74.

Natürlich funktioniert so ein ggT-Algorithmus mit exponentiell anwachsenden 9er oder 1er.

ABER ein Algorithmus sollte möglichst effizient arbeiten...

Was monarch87 hier jedoch aufzeigt, ist eine Verkomplizierung eines bereits langsamen Alorithmus (alle Teiler durchprobieren),
um Exponential- & ggT-Funktion.
Damit sind - selbst mit schnellster Rechentechnik - nur extrem selten (Sonderfälle) Zahlen mit über 16 Stellen möglich.

Das ist so, als wenn man Pi Nachkommastellen mit Primzahlen berechnet:
natürlich funktioniert das:
Kreiszahl
§3e1 + §3e2
ABER mehr als 30 Nachkommastellen sind damit kaum möglich.




  Profil  Quote  Link auf diesen Beitrag Link
Marcel74
Neu Letzter Besuch: im letzten Quartal
Dabei seit: 23.03.2018
Mitteilungen: 2
Aus:
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.26, eingetragen 2018-03-24


Hallo hyperG,

schon richtig, die beschriebenen Faktorisierungsmethoden sind nicht
wirklich effizient. Das Verdienst von Monarch87 sehe ich darin, etwas
Neues vorgestellt zu haben, was einigen Lesern hier vielleicht wieder
neue Denkanstöße für weitere Forschungen bringt.

Tatsache ist, dass das Faktorisierungs-Problem bis heute nicht gelöst ist,
und die ganzen Methoden von Fermat bis zum Zahlkörpersieb sind schön und
gut, aber sie reichen nicht aus um zum Beispiel die nächsten RSA
anzupacken. Was wir benötigen ist tatsächlich eine neue Methode.

Das von mir beschriebene Faktorisierungs-Verfahren ist in der jetzigen
Form wahrscheinlich noch ineffizienter als Probedividieren, allerdings
denke ich, dass hier noch nicht das letzte Wort gesprochen wurde. (Ich
lebe tatsächlich in dem Glauben, dass da wo viel Schatten ist, auch viel
Licht sein muss. Das heißt: Wenn sich eine Faktorisierungsmethode als
besonders ineffizient erweist, muss es irgendwo eine Verbesserung geben,
welche diese Methode sehr gut werden lässt.)

Danke für den Link zur Kreiszahl und den Primzahlen, ist für mich hochinteressant.




  Profil  Quote  Link auf diesen Beitrag Link
monarch87 hat die Antworten auf ihre/seine Frage gesehen.
Neues Thema [Neues Thema] Antworten [Antworten]    Druckversion [Druckversion]

 


Wechsel in ein anderes Forum:
 Suchen    
 
All logos and trademarks in this site are property of their respective owner. The comments are property of their posters, all the rest © 2001-2018 by Matroids Matheplanet
This web site was made with PHP-Nuke, a web portal system written in PHP. 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]