Вот функция, выраженная в C:
uint32_t f(uint32_t x) {
return (x * 0x156) ^ 0xfca802c7;
}
Затем я столкнулся с проблемой: как найти все свои неподвижные точки?
Я знаю, что мы можем протестировать каждое значение uint32_t для решения этой проблемы, но я все же хочу знать, есть ли еще более элегантный способ - особенно когда uint32_t становится uint64_t и (0x156, 0xfca802c7) является произвольным пара значений.
Код Python:
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)
Выход: 150129329 оценивается до 150129329
Идея за алгоритмом: мы пытаемся найти x XOR 0xfca802c7 = x*0x156 modulo n, где в нашем случае n=2^32. Я написал это так, потому что правая часть - это простое модульное умножение, которое хорошо ведет себя с левой стороны.
Основное свойство, которое мы собираемся использовать, состоит в том, что решение x XOR 0xfca802c7 = x*0x156 modulo 2^(i+1) сводится к решению x XOR 0xfca802c7 = x*0x156 modulo 2^i. Другой способ сказать, что решение x XOR 0xfca802c7 = x*0x156 modulo 2^i переводится в одно или два решения по модулю 2^(i+1): эти возможности либо x, либо /t x+2^i (если мы хотим быть более точными, мы только смотрим при целых числах от 0,..., размер модуля - 1, когда мы говорим "решение" ).
Мы легко можем решить это для i=1: x XOR 0xfca802c7 = x*0x156 modulo 2^1 совпадает с x XOR 1 = x*0 mod 2, что означает, что x=1 является единственным решением. Отсюда мы знаем, что только 1 и 3 являются возможными решениями по модулю 2^2 = 4. Поэтому у нас есть только два, чтобы попробовать. Оказывается, работает только один. Это наше текущее решение по модулю 4. Тогда мы можем поднять это решение на возможности по модулю 8. И так далее. В конце концов мы получаем все такие решения.
Примечание 1: Этот код находит все решения. В этом случае существует только один, но для более общих параметров может быть более одного.
Замечание2: время работы O (max [количество решений, размер модуля в битах]), если я не сделал ошибку. Таким образом, это быстро, если не существует много фиксированных точек. В этом случае, кажется, только один.
Позвольте использовать Z3 решатель:
(declare-const x (_ BitVec 32))
(assert (= x (bvxor (bvmul x #x00000156) #xfca802c7)))
(check-sat)
(get-model)
Результат '#x08f2cab1' = 150129329.
Поскольку входные биты в позиции n влияют только на выходные биты в позициях ≥ n, вы знаете, что вы можете найти решение, выбрав первый бит, затем второй бит и т.д.
Вот как вы могли бы решить его в С++ для 64-битных целых чисел (конечно, он также работает с 32-битными целыми числами):
#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);
}
С этим выходом:
Fixed point: 0xb9642f1d99863811