Was ist die Perle von x Element N ungerade?

Question

Aufgabe:

Was ist die Perle von x Element N ungerade mit x>2?

Problem/Ansatz:

Definition 1: x teilt (2^k) - 1 <=> k ist Element der Ketten von x.

Definition 2: Die Perle von x ist das Minimum der Ketten von x.

Wer findet den schnellsten Algorithmus um für große x die Perle von x zu bestimmen? (x > 10²⁵⁰)

Teilerfolg: Welche unterschiedlichen Ansätze gibt es, um die Perle von x zu bestimmen?

Comments

Definition 1: $x \mid 2^k-1 \Leftrightarrow k \in \text{"Ketten von x"}$

muss es nicht 'Kette' (also Singular) heißen? Wenn Nein - was wäre dann eine 'Kette'?

---

Die Zahl 47 teilt alle 2^(k*23) - 1.

Somit sind alle Vielfachen von 23 Elemente der Ketten von x=47.

Die Perle von x ist 23, das Minimum aller Ketten von x.

Der Plural Ketten von x ist richtig.

---

Der Plural Ketten von x ist richtig.

Ok - und was ist dann eine Kette?

---

... ist eine Kette eine Restklasse modulo $x$?

---

2⁴⁶ -1 ist eine Kette von 47, denn 47 teilt 2⁴⁶ -1. Das ist die Definition des Begriffs Kette in Definition 1. Eine Kette von x ist ein Element der Ketten von x.

Die Definition von Perle findet sich in Definition 2.

---

Das gesuchte Verfahren bildet den ersten Schritt zu einer schnelleren Faktorisierung großer Zahlen.

Es gelten folgende Sätze, die leicht zu beweisen sind:

Satz1: Ist P eine Primzahl >2, dann ist P-1 eine Kette von P.

Satz2: Die Perle einer Primzahl P teilt immer P-1

Satz3: Sei Z=2^P - 1 mit Z nicht prim, P Element der Primzahlen, dann existiert ein x=2*k*P +1 mit x teilt Z, k Element N.

Satz4: Die Perle von Pⁿ = (Perle von P) * P^(n-1) für P Element der Primzahlen, n Element N.

Satz5: Die Perle einer jeden ungeraden ganzen Zahl > 1 lässt sich aus den Perlen ihrer Primfaktorpotenzen bilden.

Bsp: gesucht ist ein x mit x teilt 2¹¹ -1:

Da 11 eine Primzahl ist muss x = 2*k*11 +1 sein.

Bereits k=1 liefert uns die Teiler 23 =2*1*11+1 & 89 = 2*4*11+1.

Analog x teilt 2²³ - 1 liefert 2²³ .1 = (2*1*23 +1)  * (2*3880*23 +1).

Nachträglicher Satz:

Jede Perle von x Teilt natürlich jede Kette von x, daher die gewählten Namen Kette und Perle.

---

Zu Nachträglicher Satz:

Es gibt nur eine Perle von x, es muss daher heißen:

Die Perle von x teilt jede Kette von x ...

Answer 1

Hallo,

Weise $x$ einer Variablen $a$ zu und $k$ den Wert $0$. Und dann in einer Schleife:

Falls $a=0$ ist, enthält $k$ das Ergebnis. Ist $a$ gerade, so addiere $x$ zu $a$. Subtrahiere $1$ und dividiere das Ergebnis durch $2$. Inkrementiere $k$ und gehe zum Anfang der Schleife.

Formal könnte das so aussehen:$$a_0 := x \\ a_{i+1}=\begin{cases}k := i &\text{für }a_{i}=0\\\frac{1}{2}(a_{i}-1)&\text{für } 2\nmid a_{i}\\\frac{1}{2}(a_{i}+x-1) &\text{für } 2|a_i \land a_i \gt 0\end{cases}$$

ob das der schnellste Algorithmus ist, kann ich nicht sagen. Jedenfalls enthält er pro Schritt nur Additionen, Subtraktionen und eine Division durch 2. Das alles kann ein handelsüblicher Rechenknecht ziemlich fix. Die mittlere Anzahl der Schritte ist $x/2$.

Potential für eine Optimierung sehe ich noch indem man mehrere Schritte von ungeraden $a$ zu einem zusammen fast. Da die Werte in einem Computer im Binärsystem vorliegen, könnte man auch $a$ nach rechts schiften, so dass alle links stehenden 1'en verschwinden und $k$ anschließend um die Anzahl der geschiften 1'en inkrementieren. Zum Beispiel:$$a_{i} = 101001111_2 \implies a_{i+4} = 10100_2, \space k := k + 4$$

Gruß Werner

Comments

Ganz gut Werner, das beschreibt auch meinen ersten Algorithmus.

Du hast das Prinzip genau erfasst.

Um die Einsen zu überspringen nahm ich damals einen kürzeren Weg und ich blieb im Dezimalsystem, aber Du hast völlig recht, das Fundament dieses Problems spielt sich im Binärcode ab.

Für die großen Zahlen konnte ich UDFs schreiben.

Findest Du noch eine schnellere Variante?

---

Das gesuchte Verfahren bildet den ersten Schritt zu einer schnelleren Faktorisierung großer Zahlen.

Es gelten folgende Sätze, die leicht zu beweisen sind:

Satz1: Ist P eine Primzahl >2, dann ist P-1 eine Kette von P.
Satz2: Die Perle einer Primzahl P teilt immer P-1
Satz3: Sei Z=2^P - 1 mit Z nicht prim, P Element der Primzahlen, dann existiert ein x=2*k*P +1 mit x teilt Z, k Element N.
Satz4: Die Perle von Pⁿ = (Perle von P) * P^(n-1) für P Element der Primzahlen, n Element N.
Satz5: Die Perle einer jeden ungeraden ganzen Zahl > 1 lässt sich aus den Perlen ihrer Primfaktorpotenzen bilden.


Bsp: gesucht ist ein x mit x teilt 2¹¹ -1:
Da 11 eine Primzahl ist muss x = 2*k*11 +1 sein.
Bereits k=1 liefert uns die Teiler 23 =2*1*11+1 & 89 = 2*4*11+1.

Analog x teilt 2²³ - 1 liefert 2²³ .1 = (2*1*23 +1)  * (2*3880*23 +1).