Ein Kongruenz-Bitmatch-Problem

Thorsten Reinecke1

Vorbemerkungen

Ich will kurz erläutern, wie ich auf das Bitmatch-Problem gestoßen bin: Der Faktorisierungsalgorithmus von Fermat kann durch Restklassenbetrachtungen beschleunigt werden. Dies war schon Fermat selbst bekannt.

Bei dem Versuch, diese Restklassenbetrachtungen am Telefon anschaulich zu erläutern, habe ich das Bitmatch-Problem formuliert. Es handelt sich um ein eigenständiges, verallgemeinertes Problem, das man völlig losgelöst vom Fermat-Algorithmus betrachten kann.

Derartige Kongruenzprobleme löst man üblicherweise mit Siebverfahren. Eine kurze Internetrecherche hat ergeben, dass bereits ab 1896 diverse Gerätschaften zur Lösung solcher Probleme entwickelt wurden, die allerdings alle darauf basieren, den Suchraum systematisch abzusieben (z.B. die Machine á Congruences von Eugène Olivier Carissan, 1919).

Es ist also sehr wahrscheinlich, dass das Problem in der Literatur unter anderem Namen bereits eingehend untersucht wurde. Für jeden Hinweis, der mir bei einer Komplexitätsabschätzung und/oder Lösung des Problems hilft, wäre ich dankbar. Wer kann mir Literaturverweise für dieses Problem angeben?

Mir jedenfalls ist kein effizienter Algorithmus zur Lösung des nachfolgend geschilderten Bitmatch-Problems bekannt...

Das Bitmatch-Problem

Es seien n Räder R1, R2, R3,..., Rn gegeben. Jedes dieser Räder sei in Sektoren unterteilt. Jeder Sektor ist gefärbt, wobei genau zwei Farben, z.B. schwarz und rot zur Verfügung stehen. Die Anzahl der Sektoren des Rades Ri sei durch si bezeichnet. Die si seien paarweise teilerfremd. Jedes Rad sei so eingefärbt, dass beide Farben auf jedem Rad in etwa gleichhäufig vorkommen.

Die Räder seien durch eine Vorrichtung so miteinander verbunden, dass sie jeweils simultan um ein Feld vorwärts gedreht werden können. Eine vorgegebene Ausgangsstellung der Räder sei markiert.

Aufgabenstellung:

Entwicklung eines Algorithmus, um die nächste (und nicht etwa nur irgendeine!) Stellung zu finden, an der alle Radpositionen rot eingefärbt sind.

Eingabe für den Algorithmus:

Anzahl der Räder; die Färbungsinformation sowie die Ausgangsstellung der Räder.

Ausgabe des Algorithmus:

Lösungsstellung der Räder und/oder Anzahl der notwendigen Schritte, um von der Ausgangsstellung zur Lösungsstellung zu gelangen.

Beispiel

Drei Räder seien hier als Zeichenketten dargestellt. Eine Drehung der Räder entspricht dem Verschieben der Zeichenkette nach links, wobei rausgeschobene Zeichen rechts wieder angehängt werden. Wir betrachten jeweils das erste Zeichen der Zeichenketten. (Dies ist nur eine von vielen möglichen Kodierungen.)

R1= rss R2= ssrrs R3= rsrrsrs (Ausgangsstellung)

R1= ssr R2= srrss R3= srrsrsr(nach 1 Schritt)

R1= srs R2= rrsss R3= rrsrsrs (nach 2 Schritten)

R1= rss R2= rsssrR3= rsrsrsr(nach 3 Schritten)

Alle drei Räder stehen nach drei Schritten auf rot. Je nach Ausgangsstellung und Einfärbung erhalten wir natürlich unterschiedliche Ergebnisse. Je mehr Räder wir verwenden, desto mehr Schritte sind üblicherweise erforderlich, um alle Räder auf die Stellung rot zu bringen. Unter den oben gemachten Bedingungen verdoppelt sich die zu erwartende Schrittzahl in etwa mit jedem neu hinzugefügten Rad.

Wer sich weitere Beispiele am Computer anzeigen lassen möchte, für den steht ein kleines Demonstrationsprogramm in C auf meiner Homepage zur Verfügung.

Lösungsansätze

Ein simpler Ansatz

Es ist klar, dass man durch fortschreitendes Ausprobieren der Stellungen schließlich auf die Lösung kommt. Wenn die Anzahl der Räder klein ist, mag dies eine effiziente Methode sein.

Bereits für n > 50 erscheint diese Vorgehensweise jedoch als unpraktikabel. (Wenn man die Wahrscheinlichkeit, auf einem einzelnen Rad im nächsten Schritt ein rotes Feld zu erwischen, mit 50% kalkuliert und die Einzelwahrscheinlichkeiten als unabhängig annimmt, dann ist die Wahrscheinlichkeit, dass im nachfolgenden Schritt alle Felder rot markiert sind, 2-n. Man kann daher einen Erfolg erst nach etwa 2n-1 Schritten ``erwarten''.)

Hackertricks

Moderne Prozessoren haben eine Registerbreite von 64 (und sogar 128 Bits). Dies bietet genügend Spielraum für eine Parallelverarbeitung der Felder. Mit SSE-Registern lassen sich 128 Felder auf einmal betrachten. Eine komponentenweise Und-Verknüpfung von 128 aufeinandfolgender Positionen der einzelnen Räder (rot=1, schwarz=0) macht den simplen Ansatz 128-mal schneller (benötigt aber entsprechend mehr Platzbedarf)!

Kombinatorische Ansätze

Man kann kleinere Räder miteinander kombinieren und daraus neue Räder erzeugen. Vermutlich lässt sich aber nicht vermeiden, dass diese ``Kombinationsräder'' sehr groß werden (Kleinstes gemeinsames Vielfaches der kombinierten si). Die ``Kombinationsräder'' hätten dafür aber auch erheblich weniger rote als schwarze Felder... (Abstandsbetrachtungen zwischen den roten Feldern werden nun sinnvoll!)

Ein zahlentheoretischer Ansatz

Man kann alle denkbaren Lösungspositionen mit dem Chinesischen Restsatz bestimmen und die kleinste Lösung anschließend auswählen. Dieser Ansatz ist jedoch nur dann praktikabel, wenn die Anzahl der roten Felder klein ist. Nach der gegebenen Problemstellung (und bei großem n) ist dies leider nicht der Fall.

Komplexitätstheoretische Fragen

weitere Hinweise

Ein Spezialfall dieses Bitmatch-Problems tritt bei dem Versuch auf, den Fermat-Algorithmus zur Faktorisierung natürlicher Zahlen zu optimieren. Nachfolgend seien die Grundgedanken hierfür skizziert:

Gelte N = p . q; eine Untersuchung der Eigenschaften von p + q ergibt p + q $ \equiv$ $ \Delta$ ( mod t) $ \Rightarrow$ p $ \equiv$ $ {\frac{{\Delta}}{{2}}}$±$ \sqrt{{(\frac{\Delta}{2})^{2}-N}}$  ( mod t). Für alle Teiler t von p + q - $ \Delta$ muss der Term ($ {\frac{{\Delta}}{{2}}}$)2 - N also ein quadratischer Rest modulo t sein. Insbesondere gilt dies für $ \Delta$ = p + q, da die 0 durch alle positiven natürlichen Zahlen ohne Rest teilbar ist. Für ein fixes N können wir daher z.B. eine Färbung der Räder unter Zuhilfenahme des Legendresymbols vornehmen, sofern wir für die si ungerade Primzahlen wählen: Die schwarzen Felder eines Rades Ri (mit $ \Delta$ $ \in$ {0,.., si -1}) besitzen die Eigenschaft $ \left(\vphantom{\frac{(\frac{\Delta}{2}\bmod s_{i})^{2}-N}{s_{i}}}\right.$$ {\frac{{(\frac{\Delta}{2}\bmod s_{i})^{2}-N}}{{s_{i}}}}$$ \left.\vphantom{\frac{(\frac{\Delta}{2}\bmod s_{i})^{2}-N}{s_{i}}}\right)$ = - 1; die übrigen Felder sind rot. Auch eine Startposition der Räder lässt sich vorgeben, z.B. $ \Delta$ = $ \left\lfloor\vphantom{ \sqrt{4N}}\right.$$ \sqrt{{4N}}$$ \left.\vphantom{ \sqrt{4N}}\right\rfloor$.

Folgende Fälle wären interessant:

Falls ein effizienter Algorithmus für das Bitmatch-Problem existiert:

Setze die Anzahl n der Räder so hoch an, dass die Irrtumswahrscheinlichkeit, dass die Lösung des Bitmatch-Problems nicht die Stellung für p + q anzeigt, vernachlässigbar klein ist. Damit wäre ein probabilistischer Faktorisierungsalgorithmus für N gefunden. (Denn der Vorgang lässt sich einerseits sukzessive mit der ``falschen'' Endstellung als neuer Ausgangsstellung wiederholen; andererseits wäre auch eine beliebige Wahl neuer Räder möglich.)

Falls kein effizienter Algorithmus für das Bitmatch-Problem existiert:

Verwende Heuristiken für das Bitmatch-Problem, um sukzessive neue Kandidaten für p + q zu generieren. Hier ist definitiv eine erhebliche Beschleunigung des Fermat-Algorithmus möglich (und wird in diversen Implementierungen auch durchgeführt)! Ein wesentlicher Vorteil liegt darin, dass bis auf einige Initialisierungen und einige seltene Kandidatentests komplett mit herkömmlicher Integer-Arithmetik auf kleinen Restklassen gearbeitet werden kann, sofern die Bitmatch-Heuristik ebenfalls mit herkömmlicher Integer-Arithmetik auskommt.

About this document ...

Ein Kongruenz-Bitmatch-Problem

This document was generated using the LaTeX2HTML translator Version 2002-2-1 (1.70)

Copyright © 1993, 1994, 1995, 1996, Nikos Drakos, Computer Based Learning Unit, University of Leeds.
Copyright © 1997, 1998, 1999, Ross Moore, Mathematics Department, Macquarie University, Sydney.

The command line arguments were:
latex2html -local_icons -transparent -white -antialias -html_version 4.0,math -split 0 -show_section_numbers -up_url /downloads/ -up_title Dokumente/Downloads bitmatch.tex

The translation was initiated by Thorsten Reinecke on 2005-08-07


Footnotes

... Reinecke1
thre@thorstenreinecke.de
...2
Man achte auf die Feinheiten! Die Lösungsstellung kann zwar geraten werden, aber in der Beweisskizze wird nicht verifiziert, ob es sich wirklich um die Lösungsstellung handelt. Es wird lediglich die schwächere Bedingung überprüft, ob eine gültige Kombination vorliegt, die die gegebene Schranke tatsächlich unterschreitet.

Eine Schachtelung von Schranken ist bei Nichtdeterminismus nicht ohne weiteres erlaubt, da man innerhalb der Schachtelung den Fall des nichtdeterministischen Nicht-Akzeptierens per Konstruktion ausschließen muß.

Für den (sehr unwahrscheinlichen) Fall, dass jemand nachweisen könnte, dass das Originalproblem nicht in NP liegt (während das modifizierte in NP liegt), wäre auch P$ \neq$NP nachgewiesen, da man für P=NP die Intervallschachtelung des mozifizierten Problems in P durchführen könnte.

Thorsten Reinecke 2005-08-07