Величина, обратная A *X MOD (2^N) -1
Вопрос
Задана функция y = f(A,X):
unsigned long F(unsigned long A, unsigned long x) {
return ((unsigned long long)A*X)%4294967295;
}
Как бы мне найти обратную функцию x = g (A, y) такую, что x = g (A, f (A, x)) для всех значений 'x'?
Если f () не является обратимым для всех значений 'x', то какое значение ближе всего к обратному?
(F - устаревший PRNG, и я пытаюсь понять, как можно инвертировать такую функцию).
- Обновленный
Если A является относительно простым для (2^ N)-1, то g (A, Y) - это просто f (A-1, y).
Если A не является относительно простым числом, то диапазон значений y ограничен...Существует ли все еще g ( ), если она ограничена этим диапазоном?
Решение
Вам нужно вычислить обратное значение A mod ((2^N) - 1)
, но у вас не всегда может быть обратное значение, учитывая ваш модуль.Видишь это на Wolfram Alpha.
Обратите внимание , что
A = 12343 имеет обратное значение (A ^-1 = 876879007 mod 4294967295)
но 12345 не имеет обратного значения.
Таким образом, если A является относительно простой с (2 ^ n)-1, тогда вы можете легко создать обратную функцию, используя Расширенный евклидов Алгоритм где
g(A,y) = F(A^-1, y)
,
в противном случае вам не повезло.
Обновить:В ответ на ваш обновленный вопрос, вы по-прежнему не можете получить уникальное обратное значение в ограниченном диапазоне.Даже если вы используете решение CookieOfFortune методом перебора, у вас возникнут такие проблемы, как
G(12345, F(12345, 4294967294)) == 286331152 != 4294967294
.
Другие советы
Вам нужен Расширенный евклидов алгоритм.Это дает вам R и S такие , что
gcd(A,2^N-1) = R * A + S * (2^N-1).
Если gcd равен 1 , то R является мультипликативной инверсией A.Тогда обратная функция равна
g(A,y) = R*y mod (2^N-1).
Хорошо, вот Обновить для случая, когда G = Gcd(A, 2^N-1) не равно 1.В таком случае
R*y mod (2^N-1) = R*A*x mod (2^N-1) = G*x mod (2^N-1).
Если y было вычислено с помощью функции f , то y делится на G.Следовательно, мы можем разделить приведенное выше уравнение на G и получить уравнение по модулю (2 ^ N-1) / G.Таким образом, набор решений является
x = R*y/G + k*(2^N-1)/G, where k is an arbitrary integer.
Решение дано здесь (http://en.wikipedia.org/wiki/Linear_congruence_theorem), и включает демонстрацию того, как расширенный алгоритм Евклида используется для поиска решений.
Функция модуля в общем случае не имеет обратного функция, но иногда вы можете найти набор x, которые соответствуют заданному y .
У Accipitridae, Гленна и Джеффа Мозера есть общий ответ, но стоит немного подробнее объяснить, почему не каждое число имеет обратное значение в mod 4294967295.Причина в том, что 4294967295 не является простым числом;это продукт пять факторов:3 x 5 x 17 x 257 x 65537.Число x имеет мультипликативную инверсию при mod m тогда и только тогда, когда x и m являются взаимная простота, таким образом, любое число, кратное этим множителям, не может иметь обратного значения в вашей функции.
Вот почему модуль, выбранный для таких PRNGS, обычно является простым.
Эх...вот один из них, который сработает:
unsigned long G(unsigned long A, unsigned long y)
{
for(unsigned int i = 0; i < 4294967295; i++)
{
if(y == F(A, i)) return i);
}
}