starke Pseudoprimzahlen < Zahlentheorie < Algebra+Zahlentheo. < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 14:28 Sa 23.08.2014 | | Autor: | Falke88 |
| Aufgabe | n = [mm] d*2^s+1
[/mm]
n-1 = [mm] d*2^s
[/mm]
[mm] \bruch{n-1}{2^s} [/mm] = d |
Wie berechne ich "s" in der obrigen Formel. Ferner interessiert mich eher welche Bezeichnungen für d & s vorliegen.
Bei "n" ist es klar das von einer zusammengesetzten, natürlichen Zahl die Rede ist.
Jedoch verwirrt mich "d" und "s" - Ich finde nicht heraus um was für Zahlen es sich dort handelt.
Quelle der Formel:
http://de.wikibooks.org/wiki/Pseudoprimzahlen:_Starke_Pseudoprimzahlen
Ich habe diese Frage in keinem Forum auf anderen Internetseiten gestellt
|
|
| |
|
Hallo,
> n = [mm]d*2^s+1[/mm]
> n-1 = [mm]d*2^s[/mm]
> [mm]\bruch{n-1}{2^s}[/mm] = d
> Wie berechne ich "s" in der obrigen Formel.
Na, die letze Gleichung ist äquivalent zu [mm]2^s=\frac{n-1}{d}[/mm] für [mm]d\neq 0[/mm]
Nun auf beiden Seiten der Gleichung den dualen Logarithmus [mm]\log_2(\cdot{})[/mm] loslassen ...
> Ferner
> interessiert mich eher welche Bezeichnungen für d & s
> vorliegen.
>
> Bei "n" ist es klar das von einer zusammengesetzten,
> natürlichen Zahl die Rede ist.
>
> Jedoch verwirrt mich "d" und "s" - Ich finde nicht heraus
> um was für Zahlen es sich dort handelt.
[mm]n[/mm] ist eine ungerade zusammengesetzte Zahl, [mm]d[/mm] ist eine ungerade Zahl. Das [mm]s[/mm] ist eine Potenz von 2.
siehe bei wikipedia
Die Darstellung [mm]n=d\cdot{}2^s+1[/mm] von n als ungerade zusammengesetzte Zahl ist doch vorgegeben bzw. für n gefordert ...
>
> Quelle der Formel:
>
> http://de.wikibooks.org/wiki/Pseudoprimzahlen:_Starke_Pseudoprimzahlen
Schaue doch mal hier rein:
http://matheplanet.com/default3.html?call=article.php?sid=611&ref=http%3A%2F%2Fwww.google.de%2Furl%3Fsa%3Dt%26rct%3Dj%26q%3D%26esrc%3Ds%26source%3Dweb%26cd%3D4%26ved%3D0CDoQFjAD
>
> Ich habe diese Frage in keinem Forum auf anderen
> Internetseiten gestellt
Gruß
schachuzipus
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 10:26 So 24.08.2014 | | Autor: | Falke88 |
| Aufgabe | 781 zur Basis 5
n = 781 d = 195 <- (Produkt aus Primfaktorzerlegung minus [mm] 2^{s})
[/mm]
[mm] 5^{195} \equiv [/mm] mod 781
1541 zur Basis 5
n = 1541 d = 385
[mm] 5^{385} \equiv [/mm] 1540 mod 1541
25 zur Basis 7
n = 25 d = 3
[mm] 7^{3} \equiv [/mm] 18 mod 25
[mm] 7^{6} \equiv [/mm] 24 mod 25
305 zur Basis 11
n = 305 d = 19
[mm] 11^{19} \equiv [/mm] 111 mod 305
[mm] 11^{38} \equiv [/mm] 121 mod 305
[mm] 11^{76} \equiv [/mm] 1 mod 305 |
Guten Tag nochmal!
Ich bräuchte da wohl doch noch den einen oder anderen Anstoß um das Thema richtig zu verstehen.
zu (781 zur Basis 5)
Hier ist die Erfüllung der ersten Bedingung für eine starke Pseudoprimzahl gegeben da [mm] a^{d} \equiv [/mm] 1 mod n
zu (1541 zur Basis 5)
Hier wirds unverständlich. Laut Wiki Artikel http://de.wikibooks.org/wiki/Pseudoprimzahlen:_Starke_Pseudoprimzahlen
ist 1541 damit eine bewiesene Pseudoprimzahl zur Basis 5.
Jedoch liegt doch hier Kongruenz zu 1540 und nicht zu 1 wie die Bedingung [mm] a^{d} \equiv [/mm] 1 mod n es doch fordert. Wieso wird im Artikel denn trotzdem davon gesprochen das es eine starke PseudoPrim ist?
zu (25 zur Basis 7)
Hier erstmal ein Problem (für mich) zur Berechnung von "d". In den zwei oberen Beispielen habe ich die Primfaktorzerlegung angewandt und die 2er Potenzen entfernt und das Produkt der restlichen Faktoren multipliziert. So war es auch vorgegeben bei der Berechnung bei 781 zur Basis 5.
Hat mit 1541 auch funktioniert.
Jedoch endet die Faktorisierung bei 25 = [mm] 5^{2}. [/mm] Somit gibt es nicht zu entfernen und diese Regelung funktioniert daher nicht. Um auf d = 3 zu gelangen habe ich dann die umgestellte Formel welche oben im Thread angegeben ist angewandt. Diesmal musste ich ein wenig nach ^{s} suchen. Bei [mm] 2^{3} [/mm] also s = 3 hat es dann funktioniert - das Ergebnis ist nun d = 3. Ob das nun Zufall ist oder der Lösungsweg falls die Zerlegungsmethode nicht anschlägt weiss ich leider nicht. Da bitte ich um Aufklärung.
Nun Frage ich mich jedoch wieso man zur Basis 7 in diesem Fall spricht. Wie erkenne ich auf welcher Basis ich die zu prüfende Zahl n denn nun prüfen soll.
Vielleicht habe ich diesen Punkt bei den c.a. 20 offenen Fenstern zum Thema übersehen.
Und was mich auch hier wieder stört ist das [mm] 7^{6} \equiv [/mm] 24 mod 25 eine starke Primzahl sein soll. Die Bedingung [mm] a^{d} \equiv [/mm] 1 mod n trifft hier für mich wieder nicht zu und somit ist die Aussage aus meiner laienhaften Sicht falsch.
zu (305 zur Basis 11)
Laut Artikel ist diese Zahl keine starke Pseudoprimzahl zur Basis 11. Wobei gerade hier ich das Gegenteil vermutet hätte. Auf "d" kam ich hier wieder durch die umgestellte Formel und Brute Forcing auf Ebene von "s" bis ich zur Lösung d = 19 kam.
Ich weiss das ich viel Mist hier abliefer - Jedoch reicht mein Bildungsabschluss nur zur mittleren Reife wesshalb ich nicht sehr viel Fachwissen in der Mathematik habe. Nichts desto Trotz bin ich jetzt sehr interessiert an Mathematik in Verbindung mit Programmiersprachen. Daher brauche ich für einen schnellen Algorithmus diese Mathekenntnisse.
PS: Ab wann beginnt das Thema von Pseudoprimzahlen in Matheunterrichten? Abitur? Studium?
|
|
|
| |
|
Hallo,
> 781 zur Basis 5
>
> n = 781 d = 195 <- (Produkt aus Primfaktorzerlegung minus
> [mm]2^{s})[/mm]
> [mm]5^{195} \equiv[/mm] mod 781
>
> 1541 zur Basis 5
>
> n = 1541 d = 385
> [mm]5^{385} \equiv[/mm] 1540 mod 1541
>
> 25 zur Basis 7
>
> n = 25 d = 3
> [mm]7^{3} \equiv[/mm] 18 mod 25
> [mm]7^{6} \equiv[/mm] 24 mod 25
>
> 305 zur Basis 11
>
> n = 305 d = 19
> [mm]11^{19} \equiv[/mm] 111 mod 305
> [mm]11^{38} \equiv[/mm] 121 mod 305
> [mm]11^{76} \equiv[/mm] 1 mod 305
> Guten Tag nochmal!
>
> Ich bräuchte da wohl doch noch den einen oder anderen
> Anstoß um das Thema richtig zu verstehen.
>
> zu (781 zur Basis 5)
> Hier ist die Erfüllung der ersten Bedingung für eine
> starke Pseudoprimzahl gegeben da [mm]a^{d} \equiv[/mm] 1 mod n
>
> zu (1541 zur Basis 5)
> Hier wirds unverständlich. Laut Wiki Artikel
> http://de.wikibooks.org/wiki/Pseudoprimzahlen:_Starke_Pseudoprimzahlen
>
> ist 1541 damit eine bewiesene Pseudoprimzahl zur Basis 5.
> Jedoch liegt doch hier Kongruenz zu 1540 und nicht zu 1
> wie die Bedingung [mm]a^{d} \equiv[/mm] 1 mod n es doch fordert.
> Wieso wird im Artikel denn trotzdem davon gesprochen das es
> eine starke PseudoPrim ist?
Weil die zweite Bedingung mit r=0 erfüllt ist.
> zu (25 zur Basis 7)
> Hier erstmal ein Problem (für mich) zur Berechnung von
> "d". In den zwei oberen Beispielen habe ich die
> Primfaktorzerlegung angewandt und die 2er Potenzen entfernt
> und das Produkt der restlichen Faktoren multipliziert. So
> war es auch vorgegeben bei der Berechnung bei 781 zur Basis
> 5.
> Hat mit 1541 auch funktioniert.
> Jedoch endet die Faktorisierung bei 25 = [mm]5^{2}.[/mm] Somit gibt
> es nicht zu entfernen und diese Regelung funktioniert daher
> nicht.
Du musst es halt auch wieder so machen wie vorher und nicht anders.
Du fakorisiert (n-1) nicht n.
Also 780 nicht 781,
1540 nicht 1540,
24 nicht 25.
> Um auf d = 3 zu gelangen habe ich dann die
> umgestellte Formel welche oben im Thread angegeben ist
> angewandt. Diesmal musste ich ein wenig nach ^{s} suchen.
> Bei [mm]2^{3}[/mm] also s = 3 hat es dann funktioniert - das
> Ergebnis ist nun d = 3. Ob das nun Zufall ist oder der
> Lösungsweg falls die Zerlegungsmethode nicht anschlägt
> weiss ich leider nicht. Da bitte ich um Aufklärung.
>
> Nun Frage ich mich jedoch wieso man zur Basis 7 in diesem
> Fall spricht. Wie erkenne ich auf welcher Basis ich die zu
> prüfende Zahl n denn nun prüfen soll.
> Vielleicht habe ich diesen Punkt bei den c.a. 20 offenen
> Fenstern zum Thema übersehen.
Ob eine Zahl pseudoprim zu einer Basis a ist erkennst du daran ob die Bedingung erfüllt ist, die es nachzurechnen gilt.
> Und was mich auch hier wieder stört ist das [mm]7^{6} \equiv[/mm]
> 24 mod 25 eine starke Primzahl sein soll. Die Bedingung
> [mm]a^{d} \equiv[/mm] 1 mod n trifft hier für mich wieder nicht zu
> und somit ist die Aussage aus meiner laienhaften Sicht
> falsch.
Auch hier ist wieder die zweite Bedingung erfüllt.
> zu (305 zur Basis 11)
>
> Laut Artikel ist diese Zahl keine starke Pseudoprimzahl zur
> Basis 11. Wobei gerade hier ich das Gegenteil vermutet
> hätte. Auf "d" kam ich hier wieder durch die umgestellte
> Formel und Brute Forcing auf Ebene von "s" bis ich zur
> Lösung d = 19 kam.
304=2*152=4*76=8*38=16*19.
Wieso machst du hier Brute-force?
Was soll brute-force hier überhaupt sein?
Das ist eine Primfaktorzerlegung, wie man sie i.d.R. in der 5.Klasse lernt.
Hast du zu diesem Absatz eine Frage oder ist das eine reine Mitteilung?
>
>
> Ich weiss das ich viel Mist hier abliefer - Jedoch reicht
> mein Bildungsabschluss nur zur mittleren Reife wesshalb ich
> nicht sehr viel Fachwissen in der Mathematik habe. Nichts
> desto Trotz bin ich jetzt sehr interessiert an Mathematik
> in Verbindung mit Programmiersprachen. Daher brauche ich
> für einen schnellen Algorithmus diese Mathekenntnisse.
Dein Wissenstand wär sinnvoll in deinem Profil, dass es für jeden nachvollziehbar ist.
> PS: Ab wann beginnt das Thema von Pseudoprimzahlen in
> Matheunterrichten? Abitur? Studium?
Nie. Im Studium evtl. in Vorlesungen zur Kryptographie.
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 12:03 So 24.08.2014 | | Autor: | Falke88 |
Heya!
Ohman danke für den Deutschuss. Habe das -1 total außer Acht gelassen.
Das mit dem Wissensstand im Profil werde ich nachtragen.
Zum Bruteforcing - Ich meine damit alle Faktormöglichkeiten durchgehen für [mm] 2^x [/mm] da ich sonst keinen Weg fand. Dass hat sich aber nach der Klärung eben auch wieder erledigt.
Weil die zweite Bedingung mit r=0 erfüllt ist.
Hm wenn r = 0 ist für mich [mm] a^{d} [/mm] und [mm] a^{d*2^{r}} [/mm] doch gleich? Bei beiden kommt in dem Fall [mm] 5^{385} [/mm] heraus welches [mm] \equiv [/mm] 1540 mod 1541 hat.
Es muss aber doch [mm] a^{d} \equiv [/mm] 1 oder [mm] a^{d*2^{r}} \equiv [/mm] -1
Und nicht 1540.
Aus meiner Sicht ist das demnach nicht so ganz plausibel.
Es sei denn es ist [mm] a^{d} \equiv [/mm] 1 oder [mm] a^{d*2^{r}} \equiv [/mm] n-1 <<< gemeint. Dann passt die zweite Bedingung natürlich
gruß Charlie
|
|
|
| |
|
> Heya!
>
> Ohman danke für den Deutschuss. Habe das -1 total außer
> Acht gelassen.
> Das mit dem Wissensstand im Profil werde ich nachtragen.
> Zum Bruteforcing - Ich meine damit alle
> Faktormöglichkeiten durchgehen für [mm]2^x[/mm] da ich sonst
> keinen Weg fand. Dass hat sich aber nach der Klärung eben
> auch wieder erledigt.
>
> Weil die zweite Bedingung mit r=0 erfüllt ist.
>
> Hm wenn r = 0 ist für mich [mm]a^{d}[/mm] und [mm]a^{d*2^{r}}[/mm] doch
> gleich?
Richtig.
> Bei beiden kommt in dem Fall [mm]5^{385}[/mm] heraus welches
> [mm]\equiv[/mm] 1540 mod 1541 hat.
>
> Es muss aber doch [mm]a^{d} \equiv[/mm] 1 oder [mm]a^{d*2^{r}} \equiv[/mm]
> -1
>
> Und nicht 1540.
Es ist $ 1540 [mm] \equiv [/mm] -1 [mm] \mod [/mm] 1541$
> Aus meiner Sicht ist das demnach nicht so ganz plausibel.
>
> Es sei denn es ist [mm]a^{d} \equiv[/mm] 1 oder [mm]a^{d*2^{r}} \equiv[/mm]
> n-1 <<< gemeint. Dann passt die zweite Bedingung
> natürlich
>
>
> gruß Charlie
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 13:52 So 24.08.2014 | | Autor: | Falke88 |
Es ist $ 1540 [mm] \equiv [/mm] -1 [mm] \mod [/mm] 1541 $
@MaslanyFanclub
Also soweit ich weiss ist das nicht Kongruent ?
1540 mod 1541 = 1540
-1 mod 1541 = -1
1540 != -1
Hast du dich verschrieben?
Bei dem Beispiel [mm] 5^{195} \equiv [/mm] 1 mod 781
[mm] 5^{195} [/mm] mod 781 = 1
1 mod 781 = 1
1 = 1
Das ist für mich Kongruent
|
|
|
| |
|
Fehlt dir was auf wo du das mod schreibt und wo ich und die wikibooks Seite mod schreiben?
a mod b ist ein Rechenoperation, da a den Rest bei der Division durch b zuweist.
Es geht hier aber um das Rechnen in Restklassenringen:
https://de.wikipedia.org/wiki/Kongruenz_%28Zahlentheorie%29
Also nein, ich hab mich diese mal nicht verschrieben.
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 14:30 So 24.08.2014 | | Autor: | Falke88 |
Hm gut ich verstehe den Unterschied schon.
Wollte Dir auch nichts vorwerfen, ich nenne halt direkt meine Sichtweise wobei einem auffällt das ich ziemlich verwirrt im Moment bin.
Vorhin gab es noch nen Aha Effekt nur jetzt stehe ich wieder bei 0.
Ich finde einfach nicht die Verbindung von [mm] a^{d} \equiv [/mm] 1 oder [mm] a^{d*2^{r}} \equiv [/mm] -1
zu den anderen Beispielen wie [mm] 5^{385} \equiv [/mm] 1540 mod 1541.
Das einzige Beispiel was für mich verständlich ist wäre [mm] 5^{195} \equiv [/mm] 1 mod 781 - da hier die "1" wie in den Bedingungen gefordert vorhanden ist.
Bitte nehmt mir das Unverständnis nicht übel - Ihr kennt das ja, wenn man es mal versteht ist es unverständlich wenn jemand es nicht versteht ;)
Versucht doch bitte für weniger Auffassungsbegabte wie mir dieses Sachverhalt so simpel wie möglich zu erklären - für ein detailliertes Beispiel wäre ich sehr dankbar!
|
|
|
| |
|
> Hm gut ich verstehe den Unterschied schon.
Für mich sieht es so aus, dass dem nicht so ist.
Insbesondere scheinst du nicht sonderlich mit der von mir verlinkten modulo-Rechnung vertraut zu sein. Das ist aber eine grundlegende Technik/Begriffsbildung der Zahlentheorie und es wäre daher sehr sinnvoll sich damit zu beschäftigen wenn man Zahlenthorie betreiben will.
> Wollte Dir auch nichts vorwerfen, ich nenne halt direkt
> meine Sichtweise wobei einem auffällt das ich ziemlich
> verwirrt im Moment bin.
>
> Vorhin gab es noch nen Aha Effekt nur jetzt stehe ich
> wieder bei 0.
>
> Ich finde einfach nicht die Verbindung von [mm]a^{d} \equiv[/mm] 1
> oder [mm]a^{d*2^{r}} \equiv[/mm] -1
> zu den anderen Beispielen wie [mm]5^{385} \equiv[/mm] 1540 mod
> 1541.
>
> Das einzige Beispiel was für mich verständlich ist wäre
> [mm]5^{195} \equiv[/mm] 1 mod 781 - da hier die "1" wie in den
> Bedingungen gefordert vorhanden ist.
>
> Bitte nehmt mir das Unverständnis nicht übel - Ihr kennt
> das ja, wenn man es mal versteht ist es unverständlich
> wenn jemand es nicht versteht ;)
Ich nehme niemandem Unverständnis übel und wohl auch sonst niemand hier.
Wobei ich allerdings hier nicht sehe was das Unverständnis eigentlich sein soll. Das was du schreibst ist sehr vage.
Versuche bitte für Dich rauszufinden an welche Stelle du genau hängst.
Das formulieren der richtigen Fragen ist der wichtigste Schritt zur Antwort.
> Versucht doch bitte für weniger Auffassungsbegabte wie mir
> dieses Sachverhalt so simpel wie möglich zu erklären -
> für ein detailliertes Beispiel wäre ich sehr dankbar!
Das wiederrum ist eine Einstellung die ich gar nicht mag. Das ist genauso wie "ich war noch nie gut in Mathe, meine Eltern auch nicht". Du schaffst dir damit eine billige psychologische Ausrede wenn du was nicht schaffst, wenn nicht sogar gleich eine selbsterfüllende Prophezeiung.
Du willst das doch verstehen oder? Dann musst du auch was dafür tun. Und es fällt einem nicht alles nach 5 Sekunden zu manchmal muss man auch länger drübernachdenken.
Wenn's einfach wär, wär's Fußball.
Um zum Punkt zurückzukommen:
Welcher Sachverhalt? Ein Beispiel wofür? Wer doch grade über ein Beispiel, also ein Beispiel für ein Beispiel?
Und zum Schluß: Manche Sachverhalte kann man schlicht nicht simpel erklären, weil sie es nicht sind.
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 12:55 So 24.08.2014 | | Autor: | Diophant |
Hallo,
> PS: Ab wann beginnt das Thema von Pseudoprimzahlen in
> Matheunterrichten? Abitur? Studium?
In der Schule wird das zumindest in Deutschland nicht behandelt, zumindest nicht planmäßig. Überhaupt spielt ja die Zahlentheorie im Schulunterrricht (leider) so gut wie keine Rolle.
Gruß, Diophant
|
|
|
|
