Вопрос

Задана функция 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);
    }
}
Лицензировано под: CC-BY-SA с атрибуция
Не связан с StackOverflow
scroll top