Инверсия A * X MOD (2 ^ N) -1 - PullRequest
Новая
       16

Инверсия A * X MOD (2 ^ N) -1

2 голосов
/ 21 мая 2009

Дана функция 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 () все еще существует, если ограничен этим диапазоном?

Ответы [ 5 ]

8 голосов
/ 21 мая 2009

Вам нужен Расширенный евклидов алгоритм . Это дает вам 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.
6 голосов
/ 21 мая 2009

Решение дано здесь (http://en.wikipedia.org/wiki/Linear_congruence_theorem), и включает демонстрацию того, как расширенный евклидов алгоритм применяет для поиска решений.

Функция модуля в общем случае не имеет обратной функции , но иногда вы можете найти набор х, которые соответствуют данному y.

3 голосов
/ 21 мая 2009

У Accipitridae, Glenn и Jeff Moser есть ответ между ними, но стоит пояснить немного больше, почему не у каждого числа есть обратное в моде 4294967295. Причина в том, что 4294967295 не является простым числом; это произведение пяти факторов : 3 x 5 x 17 x 257 x 65537. Число x имеет обратное сглаживание при mod m , если и только если x и m являются взаимно простыми , поэтому любое число, кратное этим факторам, не может иметь обратное значение в вашей функции.

Вот почему модуль, выбранный для таких PRNG, обычно прост.

2 голосов
/ 21 мая 2009

Вам необходимо вычислить обратное значение 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.

2 голосов
/ 21 мая 2009

Эх ... вот тот, который будет работать: 

unsigned long G(unsigned long A, unsigned long y)
{
    for(unsigned int i = 0; i < 4294967295; i++)
    {
        if(y == F(A, i)) return i);
    }
}
...