Jede natürliche Zahl m ist darstellbar als m = h*2^k +1

09.01.2023, 15:38

Malcang

Auf diesen Beitrag antworten »

Jede natürliche Zahl m ist darstellbar als m = h*2^k +1

Hallo zusammen,

ich schaue mir für meine Masterarbeit den Algorithmus von Bosma an. Nun geht es los mit

Zitat:

Jede natürliche Zahl $\begin{eqnarray*} m \end{eqnarray*}$ ist darstellbar als $\begin{eqnarray*} m = h\cdot 2^k \pm 1. \end{eqnarray*}$

mit $\begin{eqnarray*} h \end{eqnarray*}$ ungerade.
Dies wollte ich nun beweisen und effizient implementieren.

Zuerst der Beweis:
Gerade beim Aufschreiben meiner Idee stelle ich fest, dass dies doch sofort aus der eindeutigen Primfaktorzerlegung folgt.

Trotzdem möchte ich gerne meine Idee vorstellen.
Dabei zeige ich zuerst, dass die Darstellung eindeutig ist.
Nehme also an, es existieren zwei Darstellungen $\begin{eqnarray*} m\mp 1 = h_1\cdot 2^{k_1} = h_2\cdot 2^{k_2} \end{eqnarray*}$ . Es ist also $\begin{eqnarray*} h_1 = h_2\cdot 2^{k_2-k_1} \end{eqnarray*}$ . Falls nun $\begin{eqnarray*} k_2<k_1 \end{eqnarray*}$ , so folgt $\begin{eqnarray*} h_1 = h_2\cdot 2^{<0} \end{eqnarray*}$ und damit ist $\begin{eqnarray*} h_2 \end{eqnarray*}$ gerade.
Falls $\begin{eqnarray*} k_2>k_1 \end{eqnarray*}$ , so folgt $\begin{eqnarray*} h_1 = h_2\cdot 2^{>0} \end{eqnarray*}$ und damit wäre $\begin{eqnarray*} h_1 \end{eqnarray*}$ gerade.
Also ist $\begin{eqnarray*} k_1 = k_2 \end{eqnarray*}$ und es folgt $\begin{eqnarray*} h_1 = h_2 \end{eqnarray*}$ .

Ist dies so ok? Die Schreibweise $\begin{eqnarray*} 2^{>0} \end{eqnarray*}$ würde ich anpassen, aber gerade möchte ich gerne meinen Gedankengang vorstellen.

Nun frage ich mich noch, wie ich das vernünftig implementiere (in meinem Fall in Python).
Ich würde bei Eingabe $\begin{eqnarray*} m \end{eqnarray*}$ dann erstmal $\begin{eqnarray*} m := m\mp 1 \end{eqnarray*}$ bilden und dann

code:
1: 2: 3: 4: 5: 6:	k=0 while m != 1 m = m // 2 k = k + 1 h = m // 2^k return [h, k]

machen.
Geht das besser?

Danke für's Lesen smile

smile

09.01.2023, 15:48

IfindU

Auf diesen Beitrag antworten »

RE: Jede natürliche Zahl m ist darstellbar als m = h*2^k +1
Wie würdest du denn $\begin{eqnarray*} m = 6 \end{eqnarray*}$ darstellen? Wenigstens im Paper steht $\begin{eqnarray*} h = 1, \ldots, 2^k \end{eqnarray*}$ mit $\begin{eqnarray*} h \end{eqnarray*}$ ungerade.

Ohne Voraussetzung würde ich einfach $\begin{eqnarray*} k = 0 \end{eqnarray*}$ und $\begin{eqnarray*} h = m \mp 1 \end{eqnarray*}$ nehmen.

Edit: Für $\begin{eqnarray*} k \geq 1 \end{eqnarray*}$ ist $\begin{eqnarray*} m = h\cdot 2^k \pm 1 \end{eqnarray*}$ immer ungerade.

09.01.2023, 15:54

Malcang

Auf diesen Beitrag antworten »

Danke IFindU. $\begin{eqnarray*} h \end{eqnarray*}$ ungerade hatte ich hier nicht hingeschrieben. Sorry an alle Helfer, ich ergänze es oben. Dann ist $\begin{eqnarray*} 6 = 3\cdot 2^1 \end{eqnarray*}$ .

Zu deinem Edit:
Aber ich gehe ja davon aus, dass ich $\begin{eqnarray*} m \end{eqnarray*}$ gegeben habe.
Sei beispielsweise $\begin{eqnarray*} m = 21 = 20+1 = 5\cdot 2^4 + 1 \end{eqnarray*}$ und auch $\begin{eqnarray*} m=21 = 22-1 = 11\cdot 2^1-1 \end{eqnarray*}$ .

09.01.2023, 15:57

IfindU

Auf diesen Beitrag antworten »

Hi, siehe noch meine Anmerkung zur Ungeradheit von $\begin{eqnarray*} m \end{eqnarray*}$ . Ist es denn gefordert, dass alle Zahlen so eine Darstellung besitzen, oder dient der Test für spezielle Zahlen von der Form?

09.01.2023, 15:59

HAL 9000

Auf diesen Beitrag antworten »

Zitat:

Original von Malcang
Dabei zeige ich zuerst, dass die Darstellung eindeutig ist.

Allem Anschein nach hast du "vergessen" zu erwähnen, unter welchen Zusatzbedingungen an $\begin{eqnarray*} h,k \end{eqnarray*}$ diese Eindeutigkeit hier gelten soll. Ich nehme an, dass $\begin{eqnarray*} h \end{eqnarray*}$ ungerade sein soll, außerdem kann sich die Eindeutigkeit nur auf die "+"-Varianten untereinander bzw. die "-" Varianten untereinander beziehen, denn es ist etwa

$\begin{eqnarray*} 5 = 1\cdot 2^2 + 1 = 3\cdot 2^1-1 \end{eqnarray*}$ ,

also mit zwei $\begin{eqnarray*} (h,k) \end{eqnarray*}$ -Paaren: $\begin{eqnarray*} (1,2) \end{eqnarray*}$ für "+" und $\begin{eqnarray*} (3,1) \end{eqnarray*}$ für "-".

Und ja klar, die Eindeutigkeit folgt dann aus der Eindeutigkeit der Primfaktorzerlegung von $\begin{eqnarray*} m-1 \end{eqnarray*}$ bzw. $\begin{eqnarray*} m+1 \end{eqnarray*}$ .

Den Rest habe ich mir noch gar nicht angeschaut - ich wollte erstmal in dieser Frage Klarheit herstellen.

EDIT: Upps, da war ich etwas langsam. Ist ja viel passiert in 10 Minuten.

09.01.2023, 16:03

Malcang

Auf diesen Beitrag antworten »

@IfindU: Das Paper sagt, es geht mit allen ganzen Zahlen. Es wird zwar im weiteren Verlauf $\begin{eqnarray*} 3|h \end{eqnarray*}$ vorausgesetzt, aber ich wollte gerne die möglichst allgemeine Form zeigen.

@HAL 9000: Danke für die wichtigen Hinweise. $\begin{eqnarray*} h \end{eqnarray*}$ wird in der Tat als ungerade angenommen, das habe ich nun im Eingangspost ergänzt.
Auch den zweiten Hinweis kann ich nachvollziehen. Ich würde den Beweis dann wie oben führen, nur eben zweimal separat. Einmal für +, einmal für -

Anzeige

09.01.2023, 16:11

HAL 9000

Auf diesen Beitrag antworten »

Dein Python-Code ist rätselhaft. Mir würde eher sowas vorschweben:

code:
1: 2: 3: 4: 5: 6:	h = m-1 # oder m+1, je nachdem k = 0 while ((h & 1) == 0): k = k+1 h = h // 2 return [h,k]

Ist allerdings immer noch unsauber: Ruft man das mit m=1 auf, gerät man in eine unendliche Schleife ... das sollte man besser durch Überprüfung abfangen.

09.01.2023, 16:11

Malcang

Auf diesen Beitrag antworten »

Zitat:

Original von IfindU
Hi, siehe noch meine Anmerkung zur Ungeradheit von $\begin{eqnarray*} m \end{eqnarray*}$ . Ist es denn gefordert, dass alle Zahlen so eine Darstellung besitzen, oder dient der Test für spezielle Zahlen von der Form?

Oh, das hatte ich falsch gesehen.
Sei $\begin{eqnarray*} m=20 \end{eqnarray*}$ gegeben. Dann ist $\begin{eqnarray*} h = m-1 = 19, k=0. \end{eqnarray*}$

Zitat:

Original von HAL 9000
Dein Python-Code ist rätselhaft. Mir würde eher sowas vorschweben:

code:
1: 2: 3: 4: 5: 6:	h = m-1 # oder m+1, je nachdem k = 0 while ((h & 1) == 0): k = k+1 h = h // 2 return [h,k]

Ist allerdings immer noch unsauber: Ruft man das mit m=1 auf, gerät man in eine unendliche Schleife ... das sollte man besser durch Überprüfung abfangen.

h & 1 ist ein bitweises AND, ja? Ich nehme an hiermit wird überprüft, ob das letzte Bit eine 0 ist? Ich schaue es mir gerade in der Python-Doku einmal an.
Ja, ich würde Speziallfälle vorher abfangen. Mir ging es vor allem um die Zeile
h = h // 2
Eine ganzzahlige Division ist zeitintensiv, oder?
Ich hatte die Hoffnung, dass ich $\begin{eqnarray*} k \end{eqnarray*}$ möglicherweise etwas geschickter bestimmen könnte. Das ist aber immer mein Gedanke bevor ich den Rechner eine Brute-Force-Rechnung durchführen lasse.

Edit: HAL, zu deiner Anmerkung

Zitat:

Original von HAL 9000
Dein Python-Code ist rätselhaft. Mir würde eher sowas vorschweben:

Natürlich, danke sehr. Ich prüfe ja nicht ob h 1 ergibt, sondern ob es ungerade ist. Ich korrigiere das aber oben nicht, um den Lesefluss hier zu erhalten.

09.01.2023, 16:18

IfindU

Auf diesen Beitrag antworten »

Zitat:

Original von Malcang
[quote]Original von IfindU
Hi, siehe noch meine Anmerkung zur Ungeradheit von $\begin{eqnarray*} m \end{eqnarray*}$ . Ist es denn gefordert, dass alle Zahlen so eine Darstellung besitzen, oder dient der Test für spezielle Zahlen von der Form?

Oh, das hatte ich falsch gesehen.
Sei $\begin{eqnarray*} m=20 \end{eqnarray*}$ gegeben. Dann ist $\begin{eqnarray*} h = m-1 = 19, k=0. \end{eqnarray*}$
Da wäre die Frage, ob man $\begin{eqnarray*} h \end{eqnarray*}$ noch eingrenzt wie es im Paper zu sehen ist oder sehr flexibel ist. Aber ohne die Voraussetzung gilt es, ja.

09.01.2023, 16:20

HAL 9000

Auf diesen Beitrag antworten »

Zitat:

Original von Malcang
h & 1 ist ein bitweises AND, ja?

So ist es.

Zitat:

Original von Malcang
Mir ging es vor allem um die Zeile
h = h // 2
Eine ganzzahlige Division ist zeitintensiv, oder?

Na wenn du diesbezügliche Sorgen hast, dann verwende stattdessen h = h >> 1 .

Bei C/C++ wäre ich mir sicher, dass der Compiler die Division sowieso automatisch in einen Shift übersetzt. Bei Python als Interpretersprache kann das natürlich anders aussehen.

09.01.2023, 16:22

Malcang

Auf diesen Beitrag antworten »

Zitat:

Original von IfindU
Da wäre die Frage, ob man $\begin{eqnarray*} h \end{eqnarray*}$ noch eingrenzt wie es im Paper zu sehen ist oder sehr flexibel ist. Aber ohne die Voraussetzung gilt es, ja.

Im weiteren Verlauf werde ich das sicher machen. Gerne wollte ich aber am Anfang der Arbeit schonmal klarstellen, dass es diese eindeutige Darstellung gibt. Mir ist aber auch gerade nicht unmittelbar klar, warum $\begin{eqnarray*} h<2^k \end{eqnarray*}$ gelten soll verwirrt

verwirrt

Zitat:

Original von HAL 9000

Na wenn du diesbezügliche Sorgen hast, dann verwende stattdessen h = h >> 1 .

Ich werde mir anschauen, was das macht. Danke smile

smile

09.01.2023, 16:27

IfindU

Auf diesen Beitrag antworten »

Zitat:

Original von Malcang

Zitat:

Original von IfindU
Da wäre die Frage, ob man $\begin{eqnarray*} h \end{eqnarray*}$ noch eingrenzt wie es im Paper zu sehen ist oder sehr flexibel ist. Aber ohne die Voraussetzung gilt es, ja.

Im weiteren Verlauf werde ich das sicher machen. Gerne wollte ich aber am Anfang der Arbeit schonmal klarstellen, dass es diese eindeutige Darstellung gibt. Mir ist aber auch gerade nicht unmittelbar klar, warum $\begin{eqnarray*} h<2^k \end{eqnarray*}$ gelten soll verwirrt

verwirrt

Es gilt auch nicht, wie man an $\begin{eqnarray*} m=6 \end{eqnarray*}$ sieht. Wenn $\begin{eqnarray*} k=0 \end{eqnarray*}$ ist, $\begin{eqnarray*} h=1 \end{eqnarray*}$ oder es gibt gar kein $\begin{eqnarray*} h \end{eqnarray*}$ , je nachdem ob Ungleichung strkt ist, und bei $\begin{eqnarray*} k > 0 \end{eqnarray*}$ ist $\begin{eqnarray*} h 2^k \pm 1 \end{eqnarray*}$ ungerade und damit kann man $\begin{eqnarray*} m \end{eqnarray*}$ nicht so darstellen.

09.01.2023, 16:29

HAL 9000

Auf diesen Beitrag antworten »

Zitat:

Original von Malcang
Mir ist aber auch gerade nicht unmittelbar klar, warum $\begin{eqnarray*} h<2^k \end{eqnarray*}$ gelten soll verwirrt

verwirrt

Aus den (eindeutigen) Darstellungen $\begin{eqnarray*} m=h\cdot 2^k+1 \end{eqnarray*}$ bzw. $\begin{eqnarray*} m=h\cdot 2^k-1 \end{eqnarray*}$ folgt mitnichten $\begin{eqnarray*} h<2^k \end{eqnarray*}$ . Es scheint sich um eine Zusatzvoraussetzung (dann an $\begin{eqnarray*} m \end{eqnarray*}$ ) zu handeln, die vermutlich wichtig ist für den weiteren Fortgang der Überlegungen im Paper.

09.01.2023, 16:35

Malcang

Auf diesen Beitrag antworten »

Zuerstmal bedanke ich mich bei euch beiden für die Aufklärungen bisher. Das hat mir schon viel gebracht. Danke sehr!

Nun zu euren beiden letzten Antworten:
Im Paper sagt der Autor ja

Zitat:

Throughout this paper, h will denote an odd positive integer. We shall
consider the question of obtaining primality criteria for $\begin{eqnarray*} n_k = h \cdot 2^k \pm1 \end{eqnarray*}$ for all $\begin{eqnarray*} k \end{eqnarray*}$ such that $\begin{eqnarray*} 2^k>h \end{eqnarray*}$ .

Die Eingabe $\begin{eqnarray*} n \end{eqnarray*}$ wird in Abhängigkeit von $\begin{eqnarray*} k \end{eqnarray*}$ dargestellt? Ich finde das verwirrend.
Es geht ja um Primzahltests, also ist die Eingabe $\begin{eqnarray*} n_k \end{eqnarray*}$ ohnehin ungerade. Dann ist $\begin{eqnarray*} n_k \mp 1 \end{eqnarray*}$ gerade. Mit $\begin{eqnarray*} h \end{eqnarray*}$ ungerade sind doch dann $\begin{eqnarray*} h \end{eqnarray*}$ und $\begin{eqnarray*} k \end{eqnarray*}$ eindeutig bestimmt.

09.01.2023, 16:44

HAL 9000

Auf diesen Beitrag antworten »

Zum ersten: Ich hatte meine letzte Antwort editiert, damit deutlicher herauskommt, was ich meine.

Zitat:

Throughout this paper, h will denote an odd positive integer. We shall
consider the question of obtaining primality criteria for $\begin{eqnarray*} n_k = h \cdot 2^k \pm1 \end{eqnarray*}$ for all $\begin{eqnarray*} k \end{eqnarray*}$ such that $\begin{eqnarray*} 2^k>h \end{eqnarray*}$ .

Das bedeutet eben nichts weiter, als dass dieses Primzahlkriterium eben nicht für alle ungeraden $\begin{eqnarray*} m \end{eqnarray*}$ taugt, sondern nur für solche mit einer Darstellung $\begin{eqnarray*} m=h\cdot 2^k\pm 1 \end{eqnarray*}$ mit $\begin{eqnarray*} 2^k>h \end{eqnarray*}$ .

09.01.2023, 16:49

Malcang

Auf diesen Beitrag antworten »

Ah ok, danke sehr. Das bringt nun Licht ins Dunkle.
Und natürlich, das folgt mitnichten. Das zeigt ja alleine das Beispiel $\begin{eqnarray*} m = 97\cdot 2 +1 \end{eqnarray*}$ . Jetzt sehe ich das Finger1

Finger1

Ich war wirklich fixiert auf diesen Gedanken, dass in der eindeutigen Darstellung $\begin{eqnarray*} h\cdot 2^k \pm 1 \end{eqnarray*}$ doch sicherlich $\begin{eqnarray*} h<2^k \end{eqnarray*}$ gilt Hammer

Hammer

09.01.2023, 17:06

Malcang

Auf diesen Beitrag antworten »

Das folgende Skript spuckt mir also die möglichen Werte aus, für die der Test funktioniert.

code:
1: 2: 3: 4: 5: 6: 7: 8:	k = input() h = 1 exp = 2*int(k) while (h < exp): print(h exp + 1) print(h * exp - 1) h += 1

Richtig?

09.01.2023, 17:12

HAL 9000

Auf diesen Beitrag antworten »

h +=2 würde ich meinen. Der Rest dürfte stimmen, wobei ein Informatiker wohl eher exp = 1 << k schreiben würde, auch wenn es hier auf die Geschwindigkeit sicher nicht ankommen dürfte. Augenzwinkern

Augenzwinkern

09.01.2023, 17:15

Malcang

Auf diesen Beitrag antworten »

Zitat:

Original von HAL 9000
h +=2 würde ich meinen.

Gedacht und nicht geschrieben. Ach man... unglücklich

unglücklich

Für heute sollte ich Feierabend machen.

Vielen Dank an euch beide!!

09.01.2023, 17:33

Malcang

Auf diesen Beitrag antworten »

Doch nochmal was Big Laugh

Big Laugh

Im weiteren Verlauf auf der ersten Seite stellt der Autor ja kurz den LL-Test und den Pépin-Test vor. Direkt nach dem LL-Test sagt er

Zitat:

Similar primality criteria exist for n of the form $\begin{eqnarray*} h\cdot 2^k \pm 1 \end{eqnarray*}$ with h not divisible by 3.
For fixed h divisible by 3, however, one has to allow a dependency on k
in the starting values for the exponentiation (or the recursion, as in (1.2))in
the criterion...

Ich verstehe jetzt den Zusammenhang nicht. Welche Abhängigkeit in k fordert er hier zu erlauben?

09.01.2023, 17:58

HAL 9000

Auf diesen Beitrag antworten »

Ich muss mich korrigieren: Auch mit h+=1 listet dein Skript korrekte $\begin{eqnarray*} m \end{eqnarray*}$ -Werte - nur dass die bei geraden $\begin{eqnarray*} h \end{eqnarray*}$ nicht zum Exponenten $\begin{eqnarray*} k \end{eqnarray*}$ gehören, sondern zu irgendeinem Exponenten $\begin{eqnarray*} >k \end{eqnarray*}$ , Beispiel:

$\begin{eqnarray*} 14\cdot 2^4 \pm 1 \end{eqnarray*}$ liefert auch korrekt $\begin{eqnarray*} m \end{eqnarray*}$ -Werte, denn das ist gleichbedeutend mit $\begin{eqnarray*} 7\cdot 2^5\pm 1 \end{eqnarray*}$ , nur eben zu Exponent 5 statt 4.

D.h., wenn deine Absicht war, diejenigen Zahlen $\begin{eqnarray*} m \end{eqnarray*}$ aufzulisten, die genau (!) zum Exponenten $\begin{eqnarray*} k \end{eqnarray*}$ gehören, dann besser mit h+=2.

-----------------------------------

Was deine Frage betrifft: Du tauchst allmählich tiefer in die Betrachtungen des Papers ein, die ich nicht kenne - ich weiß z.B. nichts mit "starting values for the exponentiation" anzufangen: Was für "Startwerte" ?

09.01.2023, 20:34

Malcang

Auf diesen Beitrag antworten »

Zitat:

Original von HAL 9000
D.h., wenn deine Absicht war, diejenigen Zahlen $\begin{eqnarray*} m \end{eqnarray*}$ aufzulisten, die genau (!) zum Exponenten $\begin{eqnarray*} k \end{eqnarray*}$ gehören, dann besser mit h+=2.

Ja, das war es. Dann werde ich das auch so machen. Den Einwand mit h += 1 habe ich aber nachvollzogen.

Zitat:

Original von HAL 9000
Was deine Frage betrifft: Du tauchst allmählich tiefer in die Betrachtungen des Papers ein, die ich nicht kenne - ich weiß z.B. nichts mit "starting values for the exponentiation" anzufangen: Was für "Startwerte" ?

Das ist es, was ich mich auch fragte. Ich denke, dass er hiermit noch einen Zusammenhang zum LL-Test meint und dort andere Startwerte vergeben werden.

Das ist ganz häufig mein Problem in mathematischen Papern. Mir fehlt da die Stringenz. Ich bin es ja so gewohnt das Mathematik bedeutet "Erst A, dann B, dann C..." und alles baut auf etwas vorherigem auf. Ich selbst versuche auch diesen Stil einzuhalten. Bei Papern wie diesem denke ich mir oft, vor A kommt C und es wird schonmal etwas von F beschrieben. Dann geht man wieder an den Anfang zu A und springt dann nochmal hin und her.
Ich tue mir unheimlich schwer, dem zu folgen wenn dieser rote Faden nicht vorhanden ist - oder ich ihn aus Unerfahrenheit einfach nicht sehe.

10.01.2023, 12:32

IfindU

Auf diesen Beitrag antworten »

Paper musst du etwas anders lesen, wenigsten am Anfang. Am Anfang gibt es Kontext. Hier: Was wird untersucht, und was gibt es für ähnliche Resultate. Was zeichnet das Resultat aus und wo sind große Abweichungen zu Erwartungen.

In meinen Augen ist Abweichung/Einschränkung das, weswegen der Kommentar zum "starting value" gibt. Die Rekursion hier $\begin{eqnarray*} e_0 = -4 \end{eqnarray*}$ und $\begin{eqnarray*} e_{j+1} = e^2_j -2 \end{eqnarray*}$ ist aus numerischer Sicht wunderschön: Es gibt kein $\begin{eqnarray*} k \end{eqnarray*}$ und kein $\begin{eqnarray*} h \end{eqnarray*}$ . D.h. noch bevor du das $\begin{eqnarray*} n \end{eqnarray*}$ auswählst zum Untersuchen, kannst du die Rekursion berechnen und später dann einfach das $\begin{eqnarray*} k-2 \end{eqnarray*}$ -te Folgenglied nehmen, um das Kriterium zu benutzen. Vermutlich gibt es auch im Internet schon bereits vorberechnet die ersten Millionen Folgenglieder, damit man es nicht selbst tun muss.

Jetzt sagt der Autor, dass die ein ähnliches Resultat haben, aber das $\begin{eqnarray*} k,h \end{eqnarray*}$ eine Rolle spielt für die Rekursion. D.h. man kann die Rekursion nicht a priori berechnen, sondern erst wenn das $\begin{eqnarray*} n,k,h \end{eqnarray*}$ feststeht. Eine starke Einschränkung.

Wenn wir jetzt zu Abschnitt 3. Special cases sehen, sehen wir was passiert. Bei $\begin{eqnarray*} h \end{eqnarray*}$ non-divisble by 3 haben wir eine einfache Rekursion, sogar explizite Darstellung $\begin{eqnarray*} 3^{(n-1)/2} \end{eqnarray*}$ , unabhängig von $\begin{eqnarray*} k \end{eqnarray*}$ . Beim nächsten Theorem bekommen wir eine Abhängigkeit von $\begin{eqnarray*} h \end{eqnarray*}$ in die Rekursion. Schon weniger schön.

Beim letzten Absatz vor Abschnitt 4 behandelt er als Beispiel $\begin{eqnarray*} h=3 \end{eqnarray*}$ . Hier ist nun $\begin{eqnarray*} e_0 = -10054 \cdot 2^{3k} \end{eqnarray*}$ und wir bekommen eine Abhängigkeit von $\begin{eqnarray*} k \end{eqnarray*}$ in die Rekursion. Das meinte er am Anfang. Das kannst du nicht verstehen, wenn du noch auf Seite 1 bist.

D.h. wenn du etwas nicht-triviales siehst, gibt es zwei Möglichkeiten: Du übersiehst etwas (die Regel bei Lehrbüchern) oder der Autor spielt auf etwas an, was später relevant wird. Denk dran, die Zielgruppe vom Paper sind nicht Studenten, die versuchen den Stoff zu verstehen, sondern Experten, die jede Menge dazu wissen. Und die interessiert das Resultat und was daran besonders ist--und das steht auf den ersten Seiten. Die Rechtfertigungen kommen später, sind referenziert oder sind "Allgemeinwissen" der Experten. Ist für dich gerade anstrengend, aber stell dich drauf ein, dass viele so schreiben.

10.01.2023, 13:04

Malcang

Auf diesen Beitrag antworten »

Hallo IfindU,

danke für diese ausführliche Antwort.
Ich versuche Paper Punkt für Punkt durchzugehen, was sicherlich mein Problem ist. Das merke ich auch hier, denn soweit wie du bin im Paper noch nicht gekommen. Ich habe dafür einfach zu sehr Bedenken, dass ich auf dem Weg zu Kapitel 3 etwas aus Kapitel 2 nicht verstehe und ich dann nicht weiterkomme. Aber deine Ausführungen waren aufschlussreich für mich. Ich sollte das wohl mehrfach im Kreis lesen Big Laugh

Big Laugh

Außerdem begebe ich mich bei soetwas direkt auch ans Programmieren. Ich habe den Test bereits implementiert gemäß der Sätze 2.1 und 2.2 im Paper. Es funktioniert auch. Und schon stoße ich auf einige für mich interessante Entdeckungen, denen ich direkt nachgehen will.
Das ist einerseits natürlich schön da ich sehe, ich bin auf einem guten Weg. Auf der anderen Seite mag es sein, dass es mich aufhält, da die Fälle in einem späteren Kapitel besprochen werden.

Da es aber nicht schadet, mein Wissen von vornherein zu erweitern, habe ich auch direkt wieder eine Big Laugh

Big Laugh

Ich würde sie allerdings in einen eigenen Thread packen, da es sicher thematisch nicht ausschließlich auf diesen Test abzustellen ist.
Diesen Thread hier würde ich aber gerne in Zukunft wieder aufsuchen, da mir speziell zum genannten Test mit Sicherheit noch jede Menge Fragen kommen werden Big Laugh

Big Laugh

Ich danke euch für eure eifrige Hilfe!

11.01.2023, 15:41

Malcang

Auf diesen Beitrag antworten »

Da bin ich nochmal. Ich habe eine Frage zur Übersetzung und da es um den Bosmatest geht, dachte ich, nutze ich diesen Thread wieder. Sollte man den möglicherweise umbenennen?

Meine Frage bezieht sich auf diesen Abschnitt, auf die Punkte 2.1 und 2.3:
[attach]56654[/attach]

Um Satz 2.1 (bzw. 2.2) anzuwenden benötige ich ja nun ein $\begin{eqnarray*} D \end{eqnarray*}$ , sodass $\begin{eqnarray*} \big(\frac{D}{n}\big)=-1 \end{eqnarray*}$ ist.
Nun geht es darum, dieses Element möglichst vorherzubestimmen. In 2.3 sagt er nun

Zitat:

Determine a finite Set $\begin{eqnarray*} \mathfrak{D} \end{eqnarray*}$ and for every positive Integer $\begin{eqnarray*} k\geq2 \end{eqnarray*}$ an Integer $\begin{eqnarray*} D\in\mathfrak{D} \end{eqnarray*}$ ...

Ich stolpere beim Übersetzen. Sollte es nicht eher heißen

Zitat:

Determine a finite Set $\begin{eqnarray*} \mathfrak{D} \end{eqnarray*}$ , such that for every positive Integer $\begin{eqnarray*} k\geq2 \end{eqnarray*}$ an Integer $\begin{eqnarray*} D\in\mathfrak{D} \end{eqnarray*}$ ...

So wie es im Text steht klingt es für mich, als würde ich die Menge $\begin{eqnarray*} \mathfrak{D} \end{eqnarray*}$ in Abhängigkeit von $\begin{eqnarray*} k \end{eqnarray*}$ wählen.

13.01.2023, 19:32

IfindU

Auf diesen Beitrag antworten »

Für mich klingt auch die Formulierung so, dass $\begin{eqnarray*} \mathfrak D \end{eqnarray*}$ unabhängig von $\begin{eqnarray*} k \end{eqnarray*}$ ist.

"Betimme (erst) eine endliche Menge $\begin{eqnarray*} \mathfrak D \end{eqnarray*}$ und (dann) für jedes $\begin{eqnarray*} k\geq 2 \end{eqnarray*}$ eine Zahl $\begin{eqnarray*} D\in\mathfrak D \end{eqnarray*}$ , so dass... "

Deine Formulierung ist aber dort eindeutiger.

15.01.2023, 20:25

Malcang

Auf diesen Beitrag antworten »

@IfindU: Danke sehr. Ich bin zwar durch mit dem Paper, aber wirklich verdaut hab' ich es noch lange nicht.

02.02.2023, 14:51

Malcang

Auf diesen Beitrag antworten »

Hallo mal wieder,

ich muss nun doch noch mal was zu diesem Paper fragen.
Das Paper schreibt ja folgendes:
[attach]56774[/attach]

In der Literatur finde ich den Satzt von Proth:
[attach]56775[/attach]

Nun verstehe ich nicht genau, warum das Paper noch $\begin{eqnarray*} \left(\frac{D}{n}\right) = -1 \end{eqnarray*}$ (Jacobisymbol) fordert.

Wenn $\begin{eqnarray*} n \end{eqnarray*}$ prim ist, dann existiert ein solches $\begin{eqnarray*} D \end{eqnarray*}$ sowieso und das Jacobi-Symbol fällt dann auch noch mit dem Legendre-Symbol zusammen. Der Term $\begin{eqnarray*} D^{\frac{n-1}{2}} \end{eqnarray*}$ ist dann das Euler-Kriterium.

Für die Rückrichtung kann ich ja nun den Satz von Proth anwenden. Aber dazu brauche ich ja wiederum das Jacobi-Symbol nicht.

Hm, ich stehe da gerade auf dem Schlauch verwirrt

verwirrt

Edit:
Ok, ich glaube ich bin etwas mehr durchgestiegen. Ich brauche aber nun nochmal Hilfe beim Beweis.

Mein Ansatz:
Sei $\begin{eqnarray*} n \end{eqnarray*}$ prim. Nach Voraussetzung ist das Jacobisymbol $\begin{eqnarray*} \left(\frac{D}{n}\right) = -1 \end{eqnarray*}$ und damit fällt dies mit dem Legendresymbol zusammen. Unter Anwedung des Kriteriums von Euler folgt dann $\begin{eqnarray*} D^{\frac{n-1}{2}} \equiv -1 \pmod n \end{eqnarray*}$ .

Aber ich brauche einmal einen Schubs für die Gegenrichtung.

04.02.2023, 09:36

IfindU

Auf diesen Beitrag antworten »

Ist die Gegenrichtung nicht genau der Satz von Proth? Da wird es sicherlich einen schönen Beweis geben Augenzwinkern

Augenzwinkern

05.02.2023, 20:01

Malcang

Auf diesen Beitrag antworten »

Hallo IfindU, sorry für die späte Reaktion meinerseits.

Zitat:

Original von IfindU
Ist die Gegenrichtung nicht genau der Satz von Proth? Da wird es sicherlich einen schönen Beweis geben Augenzwinkern

Augenzwinkern

Aber der Satz von Proth nimmt ja an, dass es ein beliebiges a gibt, dass diese Kongruenz erfüllt.
In dem Test aus dem Paper ist dies aber gerade das Element D, dass die Eigenschaft hat, dass $\begin{eqnarray*} \left(\frac{D}{n}\right) = -1 \end{eqnarray*}$ gilt verwirrt

verwirrt

Ich habe da einen Beweis aufgeschrieben, muss aber noch eine Lücke schließen. Den Beweis würde ich dann gerne hier nochmal vorstellen und freue mich über jede Rückmeldung smile

smile

06.02.2023, 09:37

Malcang

Auf diesen Beitrag antworten »

Guten Morgen,

da bin ich nochmal. Ich habe mich an einem Beweis versucht für die Richtung $\begin{eqnarray*} \Leftarrow \end{eqnarray*}$ von:
[attach]56786[/attach]
Der Fairness halber möchte ich sagen, dass ich mir Tipps bei Stackoverflow geholt habe, die folgende Ausarbeitung stammt aber von mir.

Beweis:
Es sei $\begin{eqnarray*} D^{\frac{n-1}{2}}\equiv -1 \pmod n. \end{eqnarray*}$ Insbesondere ist dann $\begin{eqnarray*} D^{n-1}\equiv D^{h\cdot 2^k}\equiv 1\pmod q \end{eqnarray*}$ .
Ich versuche noch zu verstehen ob hieraus direkt $\begin{eqnarray*} ggT(D, n) = 1 \end{eqnarray*}$ folgt.
Betrachten wir einen möglichen Primteiler $\begin{eqnarray*} q \end{eqnarray*}$ von $\begin{eqnarray*} n \end{eqnarray*}$ . Dann folgt $\begin{eqnarray*} D^{\frac{n-1}{2}}\equiv -1 \pmod q. \end{eqnarray*}$

Nun folgere ich, dass $\begin{eqnarray*} 2^k \end{eqnarray*}$ ein Teiler von $\begin{eqnarray*} q-1 \end{eqnarray*}$ ist.
Denn sei $\begin{eqnarray*} g := ggT(q-1, h\cdot 2^k) \end{eqnarray*}$ . Nach Bézout gibt es ganze Zahlen $\begin{eqnarray*} s,t \end{eqnarray*}$ sodass $\begin{eqnarray*} g = s(q-1) + t(h\cdot 2^k) \end{eqnarray*}$ . Es ist dann $\begin{eqnarray*} D^g \equiv D^{s(q-1) + t(h\cdot 2^k)} \equiv (D^{q-1})^s\cdot (D^{h\cdot 2^k})^t \pmod q. \end{eqnarray*}$
Nach kleinem Fermat ist $\begin{eqnarray*} D^{q-1} \equiv 1 \pmod q \end{eqnarray*}$ und nach Folgerung oben ist $\begin{eqnarray*} D^{h\cdot 2^k}\equiv 1\pmod q \end{eqnarray*}$ . Es ist also $\begin{eqnarray*} D^g\equiv 1 \pmod q. \end{eqnarray*}$
Daher ist $\begin{eqnarray*} g \end{eqnarray*}$ ein Teiler von $\begin{eqnarray*} h\cdot 2^{k} \end{eqnarray*}$ , aber nicht von $\begin{eqnarray*} h\cdot 2^{k-1} \end{eqnarray*}$ . Deshalb ist $\begin{eqnarray*} g = a\cdot 2^k \end{eqnarray*}$ für einen Teiler $\begin{eqnarray*} a \end{eqnarray*}$ von $\begin{eqnarray*} h \end{eqnarray*}$ . Insbesondere ist also $\begin{eqnarray*} 2^k \end{eqnarray*}$ ein Teiler von $\begin{eqnarray*} q-1 \end{eqnarray*}$ und damit $\begin{eqnarray*} 2^k \leq q-1 \Leftrightarrow 2^k+1 \leq q \end{eqnarray*}$ .

Falls $\begin{eqnarray*} n \end{eqnarray*}$ keine Primzahl ist, so ist also $\begin{eqnarray*} n = p\cdot q \geq (2^k+1)^2 = 2^{2k}+2k+1 > 2^k\cdot 2^k + 1 \end{eqnarray*}$ was ein Widerspruch ist zur Voraussetzung $\begin{eqnarray*} h<2^k. \end{eqnarray*}$

Edit:
Ach ja, das Jacobisymbol $\begin{eqnarray*} \left(\frac{D}{n}\right) \end{eqnarray*}$ ist genau dann 0, wenn $\begin{eqnarray*} D \end{eqnarray*}$ und $\begin{eqnarray*} n \end{eqnarray*}$ nicht teilerfremd sind. Damit sollte sich obige Anmerkung erledigt haben.

06.02.2023, 10:24

HAL 9000

Auf diesen Beitrag antworten »

Zitat:

Original von Malcang
Ach ja, das Jacobisymbol $\begin{eqnarray*} \left(\frac{D}{n}\right) \end{eqnarray*}$ ist genau dann 0, wenn $\begin{eqnarray*} D \end{eqnarray*}$ und $\begin{eqnarray*} n \end{eqnarray*}$ teilerfremd sind.

Sollte das nicht eher lauten "... nicht teilerfremd sind" ? verwirrt

verwirrt

06.02.2023, 10:25

Malcang

Auf diesen Beitrag antworten »

Zitat:

Original von HAL 9000

Zitat:

Original von Malcang
Ach ja, das Jacobisymbol $\begin{eqnarray*} \left(\frac{D}{n}\right) \end{eqnarray*}$ ist genau dann 0, wenn $\begin{eqnarray*} D \end{eqnarray*}$ und $\begin{eqnarray*} n \end{eqnarray*}$ teilerfremd sind.

Sollte das nicht eher lauten "... nicht teilerfremd sind" ? verwirrt

verwirrt

Das sollte es. Ich danke dir, HAL!

1

Verwandte Themen

Die Beliebtesten »

Die Größten »

Die Neuesten »