Matroids Matheplanet Forum Index
Moderiert von Wauzi
Teilbarkeit » Kongruenzen » Letzte Stellen sehr großer Zahlen auf Richtigkeit überprüfen
Autor
Universität/Hochschule Letzte Stellen sehr großer Zahlen auf Richtigkeit überprüfen
hyperG
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 03.02.2017
Mitteilungen: 1677
  Themenstart: 2022-01-28

In einem anderen Beitrag hatte ich ja gezeigt, wie man die letzte Stelle sehr großer Bell-Zahlen überprüfen kann. Sobald ich aber mehr als die eine letzte überprüfen will, wird es kompliziert. Bei GroßeZahl Mod (10^n) sieht man sofort, dass man damit die letzten n Stellen bekommt. Wie sieht es aber mit n=Primzahl \sourceon nameDerSprache GroßeZahl Mod (Primzahl) = Konstante kurz: G mod p = K \sourceoff aus? Zunächst dachte ich an " eine neben 10^n" also z.B. p=101, aber wenn K =5, dann bekommt man lauter unterschiedliche "mögliche letzte Stellen": 101106,101207,101308,101409,101510,... die Mod 101 eine 5 ergeben. Frage: gibt es besonders günstige Kombinationen aus Primzahl und Konst., um sofort Aussagen zu den letzten n Dezimalstellen tätigen zu können? Ziel ist möglich großes n (viele richtige Stellen zu finden). Natürlich könnte man mehrere Kombinationen aus {p,K} sammeln, um dann Rückschlüsse auf die letzten Ziffern zu ziehen -> kann beliebig kompliziert werden... Ich suche aber eine sehr einfache... Und dabei muss G beliebig sein! Also keine Sonderfälle aus G,p,K sondern nur Sonderfälle aus {p,K}. Grüße


   Profil
Nuramon
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 23.01.2008
Mitteilungen: 3529
  Beitrag No.1, eingetragen 2022-01-28

\(\begingroup\)\(\renewcommand{\Re}{\operatorname{Re}} \renewcommand{\Im}{\operatorname{Im}} \newcommand{\End}{\operatorname{End}} \newcommand{\id}{\operatorname{id}} \newcommand{\GL}{\operatorname{GL}} \newcommand{\im}{\operatorname{im}} \newcommand{\sgn}{\operatorname{sgn}} \newcommand{\d}{{\rm d}} \newcommand{\rg}{\operatorname{rg}} \newcommand{\spur}{\operatorname{spur}} \newcommand{\Hom}{\operatorname{Hom}} \newcommand{\tr}{\operatorname{tr}} \newcommand{\opn}{\operatorname} \newcommand\ceil[1]{\left\lceil #1 \right\rceil} \newcommand\floor[1]{\left\lfloor #1 \right\rfloor}\) Hallo, wenn $p$ eine zu $10$ teilerfremde Primzahl ist, dann gibt es nach dem chinesischen Restsatz für alle $K,L,m,n\in \IN$ eine Zahl $G\in \IZ$ mit $G\equiv K \pmod {p^m}$ und $G\equiv L \pmod {10^n}$. Man kann also aus dem Rest von $G$ modulo $p^m$ keine Rückschlüsse auf die letzten $n$ Dezimalstellen von $G$ ziehen.\(\endgroup\)


   Profil
DavidM
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 11.06.2012
Mitteilungen: 396
  Beitrag No.2, eingetragen 2022-01-28

Hallo hyperG, wenn ich dich richtig verstehe, dann funktioniert das, was du willst, nicht. Wenn $p$ eine beliebige Primzahl außer 2 und 5 ist und $K$ irgendeine natürliche Zahl kleiner als $p$, dann gibt es zu jeder beliebigen Folge von $n$ letzten Ziffern immer eine Zahl $G$, sodass der Rest von $G$ modulo $p$ gerade $K$ ist und $G$ diese Folge von letzten Ziffern hat. Das gilt für alle $n$, $K$ und $p$ (außer, wie gesagt, $p=2$ und $p=5$). Letztlich ist das einfach eine Folgerung aus dem chinesischen Restsatz. Gruß, David [Die Antwort wurde vor Beitrag No.1 begonnen.]


   Profil
pzktupel
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 02.09.2017
Mitteilungen: 2180
Wohnort: Thüringen
  Beitrag No.3, eingetragen 2022-01-28

Äh, da fällt mir vielleicht was dazu ein. Man könnte den ganzen String zum Bsp. in 7er Blöcke von rechts nach links splitten und die addieren. Die Summe macht man dann MOD 239 oder MOD 4649, die Primfaktoren von 9999999 oder eben 1111111. Also 98174891741 MOD 239 = 146 9817+4891741=4901558 4901558 MOD 239 = 146 Selbige mit 4649 -> 1512 Einen anderen Check sehe ich jetzt mit Primzahlen nicht. Merke, das passt nicht zum Problem...🤔 Als spielerei vielleicht noch... 98174891741 , schneide 2 Stellen ab: 98+1748917 = MOD 239 = 13 13*100-146 von oben =1154 1154 MOD 239=198 239-198=41 waren beide letzten Stellen.


   Profil
hyperG
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 03.02.2017
Mitteilungen: 1677
  Beitrag No.4, vom Themenstarter, eingetragen 2022-01-28

\quoteon(2022-01-28 17:28 - Nuramon in Beitrag No. 1) ... keine Rückschlüsse auf die letzten $n$ Dezimalstellen von $G$ ziehen. \quoteoff Ja, das mit 1 Primzahl nur die letzte Stelle, jedoch nicht mehr, das hatte ich ja schon geschrieben. Mir geht es aber um Kombinationen {p,K} also p1=10^17-3 p2=10^17+3 Wenn man dann das Modulo-Ergebnis nochmals Modulo 10^4 nimmt, bekommt man doch mehr Informationen: https://matheplanet.com/matheplanet/nuke/html/uploads/b/47407_Modulo_vorletzteStellen.png Also etwa in der Art: Wenn das Modulo-Ergebnis nochmals Modulo 10^4 bei 10^17-3 genau 6 und bei p2=10^17+3 dann 0 ist, müssten die letzten 3 Stellen von G "003" lauten... Nachsatz: also "führende Nullen" + "Mittelwert der beiden Modulo 10^4 Ergebnisse", wobei die "10^nochmaligeMod" kleiner als das aktuelle p sein muss... und das erste Ergebnis (vorletzte Spalte) größer als letzte Spalte sein muss. [Die Antwort wurde nach Beitrag No.1 begonnen.]


   Profil
Nuramon
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 23.01.2008
Mitteilungen: 3529
  Beitrag No.5, eingetragen 2022-01-28

\(\begingroup\)\(\renewcommand{\Re}{\operatorname{Re}} \renewcommand{\Im}{\operatorname{Im}} \newcommand{\End}{\operatorname{End}} \newcommand{\id}{\operatorname{id}} \newcommand{\GL}{\operatorname{GL}} \newcommand{\im}{\operatorname{im}} \newcommand{\sgn}{\operatorname{sgn}} \newcommand{\d}{{\rm d}} \newcommand{\rg}{\operatorname{rg}} \newcommand{\spur}{\operatorname{spur}} \newcommand{\Hom}{\operatorname{Hom}} \newcommand{\tr}{\operatorname{tr}} \newcommand{\opn}{\operatorname} \newcommand\ceil[1]{\left\lceil #1 \right\rceil} \newcommand\floor[1]{\left\lfloor #1 \right\rfloor}\) Wenn man von einer Zahl $G$ nur die Reste $r_i := mod(G, p_i)$ für $i=1,...,m$ und Primzahlen $p_1,\ldots, p_m \notin\{2,5\}$ kennt, dann kann man keine Aussage über die Dezimalziffern von $G$ treffen (wegen des chinesischen Restsatzes). Wenn man von $G$ sogar nur die Reste $r_i':= mod(r_i, 10^4)$ kennt, dann weiß man ja sogar noch weniger über $G$, also kann man mit diesen iterierten Resten erst recht keine Aussage treffen.\(\endgroup\)


   Profil
hyperG
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 03.02.2017
Mitteilungen: 1677
  Beitrag No.6, vom Themenstarter, eingetragen 2022-01-28

Es sah zunächst bis 31stellig so gut aus: https://matheplanet.com/matheplanet/nuke/html/uploads/b/47407_Modulo_vorletzteStellen2.png Aber später kommen die befürchteten "unbestimmten Fälle"... Würde ein weiterer p3 helfen, um Sonderfälle zu finden? Oder welche Randbedingungen muss man noch herausfiltern (was ich mit "?" ausgeben würde)?


   Profil
hyperG
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 03.02.2017
Mitteilungen: 1677
  Beitrag No.7, vom Themenstarter, eingetragen 2022-01-28

Dass mit p={2 oder 5} bei nur 1 letzten Stelle sehe ich nun ein. Wenn G nun in Hexadezimalform vorliegt, müsste man doch mehr herausbekommen, denn mod 13 entspricht mod 0D die letzte Hex-Stelle von G kann dann nur zw. 0...0C liegen... zwar keine "vollen 2 Dezimalstellen", aber doch etwas mehr Info beim Vergleich zweier großen G1 & G2.


   Profil
pzktupel
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 02.09.2017
Mitteilungen: 2180
Wohnort: Thüringen
  Beitrag No.8, eingetragen 2022-01-28

Sowas brauchbar ? N=123456789 M=(N MOD 99999)-1234 = 56789 ? oder N=279837124191341 MOD 9999999999 - 27983 = 7124191341


   Profil
hyperG
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 03.02.2017
Mitteilungen: 1677
  Beitrag No.9, vom Themenstarter, eingetragen 2022-01-28

\quoteon(2022-01-28 19:39 - pzktupel in Beitrag No. 8) Sowas brauchbar ? ... M=(N MOD 99999)... ... MOD 9999999999 ... \quoteoff Nein, da weder 99999 noch 9999999999 Primzahlen sind. Leider scheint die Idee mit anderer Basis natürlich nichts zu bringen, da die Modulo-Funktion unabhängig von der Basis funktioniert. Bei String-Funktionen ist das was anderes. Ich dachte nur, weil die BBP-Algorithmen für Pi ja auch nur mit Basis 2^n funktionieren...wo man dann einzelne Stellen "dieser anderen Basis" herauspicken kann.


   Profil
hyperG hat die Antworten auf ihre/seine Frage gesehen.

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-2022 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]