Inversa de A * X MOD (2 ^ N) -1

Question

Dada uma função y = f (A, X):

unsigned long F(unsigned long A, unsigned long x) {
    return  ((unsigned long long)A*X)%4294967295;
}

Como eu iria encontrar a função inversa x = g (A, y) tal que x = g (A, f (A, x)) para todos os valores de 'x'?

Se f () não pode ser invertida para todos os valores de 'x', o que é o mais próximo de uma inversa?

(F é um PRNG obsoleto, e eu estou tentando entender como se inverte tal função).

• Atualizado
  Se A é relativamente primos de (2 ^ N) -1, então g (A, Y) é apenas f (A-1, y).
  Se A não é relativamente primos, então o intervalo de y é limitada ... Does g () ainda existir se restringe a essa faixa?

Answer 1

Você precisa calcular o inverso de A mod ((2^N) - 1), mas você nem sempre pode ter uma inversa dado o seu módulo. Consulte isso em Wolfram Alpha .

Note que

A = 12343 tem um inverso (A ^ -1 = 876879007 modificação 4294967295)

mas 12345 não tem um inverso.

Assim, se A é relativamente primos com (2 ^ n) -1, então você pode facilmente criar uma função inversa usando o Extensão Algoritmo de Euclides onde

g(A,y) = F(A^-1, y),

caso contrário, você está sem sorte.

Atualizar : Em resposta à sua pergunta atualizado, você ainda não pode obter um inversa único no intervalo restrito. Mesmo se você usar solução de força bruta do CookieOfFortune, você vai ter problemas como

G(12345, F(12345, 4294967294)) == 286331152 != 4294967294.

Answer 2

Você precisa do Extensão euclidiana algoritmo . Isto dá-lhe R e S tal que

gcd(A,2^N-1) = R * A + S * (2^N-1).

Se o gcd é 1, então R é o inverso multiplicativo de A. Em seguida, a função inversa é

g(A,y) = R*y mod (2^N-1).

Ok, aqui é uma actualização para o caso em que a G = Gcd (A, 2 ^ N-1) não é 1. Nesse caso

R*y mod (2^N-1) = R*A*x mod (2^N-1) = G*x mod (2^N-1).

Se y foi calculado pela função f, em seguida, y é divisível por G. Daí que pode dividir a equação acima por G e obter um módulo equação (2 ^ N-1) / L. Assim, o conjunto de soluções é

  x = R*y/G + k*(2^N-1)/G, where k is an arbitrary integer.

Answer 3

A solução é dada aqui ( http://en.wikipedia.org/wiki/Linear_congruence_theorem ), e inclui uma demonstração de como o algoritmo de Euclides estendido é usado para encontrar as soluções.

A função módulo, em geral, não tem um inverso função , mas às vezes você pode encontrar um conjunto de de x que mapeiam para o y dado.

Answer 4

Accipitridae, Glenn, e Jeff Moser tem a resposta entre eles, mas vale a pena explicar um pouco mais porque não cada número tem uma inversa sob mod 4294967295. A razão é que 4294967295 não é um número primo; é o produto de cinco factores : 3 x 5 x 17 x 257 x 65537. Um número x tem um inverso mutiplicative sob mod m se e somente se x e m são coprime , portanto, qualquer número que é um múltiplo desses fatores não podem ter uma inversa em sua função.

É por isso que o módulo escolhido para tais PRNGs é geralmente prime.

Answer 5

Eh ... aqui está um que vai funcionar:

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