Wie finden Sie die Fixpunkte einer einfachen Mod-Funktion elegant?

Question

Hier ist eine Funktion, die in C ausgedrückt ist:

uint32_t f(uint32_t x) { 
    return (x * 0x156)^0xfca802c7; 
} 

Dann kam ich auf eine Herausforderung: Wie alle seine Fixpunkte zu finden?

Ich weiß, dass wir jeden uint32_t Wert testen können, dieses Problem zu lösen, aber ich will noch wissen, ob es eine andere Möglichkeit ist, die mehr elegant ist - vor allem, wenn uint32_tuint64_t werden und (0x156, 0xfca802c7) ein beliebige Wertepaar.

Answer 1

Python-Code:

def f(x, n): 
    return ((x*0x156)^0xfca802c7) % n 


solns = [1] # The one solution modulo 2, see text for explanation 
n = 1 
while n < 2**32: 
    prev_n = n 
    n = n * 2 
    lifted_solns = [] 
    for soln in solns: 
     if f(soln, n) == soln: 
      lifted_solns.append(soln) 
     if f(soln + prev_n, n) == soln + prev_n: 
      lifted_solns.append(soln + prev_n) 
    solns = lifted_solns 

for soln in solns: 
    print soln, "evaluates to ", f(soln, 2**32) 

Ausgang: 150129329 ausgewertet 150129329

Idee hinter dem Algorithmus: Wir versuchen x XOR 0xfca802c7 = x*0x156 modulo n, wo in unserem Fall n=2^32 zu finden. Ich habe es so geschrieben, weil die rechte Seite eine einfache modulare Multiplikation ist, die sich gut mit der linken Seite verhält.

Die Haupteigenschaft, die wir verwenden werden, ist, dass eine Lösung zu x XOR 0xfca802c7 = x*0x156 modulo 2^(i+1) zu einer Lösung zu x XOR 0xfca802c7 = x*0x156 modulo 2^i reduziert. Eine andere Art zu sagen ist, dass eine Lösung zu x XOR 0xfca802c7 = x*0x156 modulo 2^i übersetzt zu einer oder zwei Lösungen modulo 2^(i+1): diese Möglichkeiten sind entweder x und/oder x+2^i (wenn wir genauer sein wollen, betrachten wir nur ganze Zahlen zwischen 0, ... , Modulgröße - 1, wenn wir "Lösung" sagen).

Wir können dies leicht für i=1 lösen: x XOR 0xfca802c7 = x*0x156 modulo 2^1 ist die gleiche wie x XOR 1 = x*0 mod 2, was bedeutet, x=1 die einzige Lösung ist. Von dort wissen wir, dass nur 1 und 3 die möglichen Lösungen sind modulo 2^2 = 4. Wir haben also nur zwei zu versuchen. Es stellt sich heraus, dass nur einer funktioniert. Das ist unsere aktuelle Lösung modulo 4. Wir können diese Lösung dann auf die Möglichkeiten modulo 8 heben. Und so weiter. Irgendwann bekommen wir alle solche Lösungen.

Bemerkung1: Dieser Code findet alle Lösungen. In diesem Fall gibt es nur einen, aber für allgemeinere Parameter kann es mehr als einen geben.

Bemerkung2: Die Laufzeit ist O (max [Anzahl der Lösungen, Modulgröße in Bits]), vorausgesetzt, ich habe keinen Fehler gemacht. Es ist also schnell, es sei denn, es gibt viele, viele Fixpunkte. In diesem Fall scheint es nur einen zu geben.

Answer 2

des Z3 solver Lassen Sie verwenden:

(declare-const x (_ BitVec 32)) 
(assert (= x (bvxor (bvmul x #x00000156) #xfca802c7))) 
(check-sat) 
(get-model) 

Das Ergebnis ist '#x08f2cab1' = 150129329.

Answer 3

Da Eingangsbits an Position n nur Ausgangsbits an Positionen beeinflussen ≥ n Sie wissen, dass Sie eine Lösung durch die Wahl des ersten Bits finden, dann das zweite Bit usw.

Hier ist, wie Sie es in C lösen könnte ++ für 64-Bit-Integer (natürlich funktioniert es auch mit 32-Bit-Integer):

#include <cstdint> 
#include <cstdio> 

uint64_t f(uint64_t x) { 
    return (x * 0x7ef93a76ULL)^0x3550e08f8a9c89c7ULL; 
} 

static void search(uint64_t x, uint64_t bit) 
{ 
    if (bit == 0) 
    { 
     printf("Fixed point: 0x%llx\n", (long long unsigned)x); 
     return; 
    } 

    if (f(x + bit) & bit) search(x + bit, bit << 1); 
    if ((f(x) & bit) == 0) search(x, bit << 1); 
} 

int main() 
{ 
    search(0x0, 1); 
} 

Mit dieser Ausgabe:

Fixed point: 0xb9642f1d99863811