Ответ 1
Код 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 [количество решений, размер модуля в битах]), если я не сделал ошибку. Таким образом, это быстро, если не существует много фиксированных точек. В этом случае, кажется, только один.