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

Question

Dada una función y = f (A, X):

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

¿Cómo puedo encontrar la función inversa x = g (A, y) de tal manera que x = g (a, f (a, x)) para todos los valores de 'x'?

Si f () no es invertible para todos los valores de 'x', lo que es el más cercano a la inversa?

(F es un PRNG obsoleta, y yo estoy tratando de entender cómo se invierte tal función).

• Actualización
  Si A es relativamente primo a (2 ^ N) -1, entonces g (A, Y) es sólo f (A-1, y).
  Si A no es relativamente primo, entonces el rango de y está limitada ... Aún existe g () si se restringe a ese rango?

Answer 1

Es necesario para calcular la inversa de A mod ((2^N) - 1), pero no siempre se puede tener una inversa dada su módulo. Ver esto en Wolfram Alpha .

Tenga en cuenta que

A = 12343 tiene una inversa (A ^ -1 = 876879007 mod 4294967295)

12345, pero no tiene una inversa.

Por lo tanto, si A es relativamente primos con (2 ^ n) -1, entonces usted puede crear fácilmente una función inversa utilizando la extendido de Euclides Algoritmo donde

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

de lo contrario estás fuera de suerte.

Actualizar : En respuesta a su pregunta actualizado, todavía no se puede obtener una inversa única en el rango restringido. Incluso si utiliza la fuerza bruta solución de CookieOfFortune, tendrá problemas como

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

Answer 2

Es necesario el extendido de Euclides algoritmo . Esto le da R y S tal que

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

Si el gcd es 1, entonces R es la inversa multiplicativa de A. A continuación, la función inversa es

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

Ok, aquí es un actualización para el caso en que el G = mcd (a, 2 ^ N-1) no es 1. En ese caso

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

Si y se calculó por la función f entonces y es divisible por G. Por lo tanto podemos dividir la ecuación anterior por G y obtener un modulo ecuación (2 ^ N-1) / G. Así, el conjunto de soluciones es

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

Answer 3

La solución se da aquí ( http://en.wikipedia.org/wiki/Linear_congruence_theorem ), e incluye una demostración de cómo se utiliza el algoritmo de Euclides extendido para encontrar las soluciones.

La función de módulo en general no tiene una inversa función , pero a veces se puede encontrar un conjunto de las x que se asignan a la Y dado.

Answer 4

Accipítridos, Glenn y Jeff Moser tienen la respuesta entre ellos, pero vale la pena explicar un poco más por qué no cada número tiene una inversa bajo mod 4294967295. La razón es que 4294967295 no es un número primo; que es el producto de cinco factores : 3 x 5 x 17 x 257 x 65537. Un número x tiene un inverso mutiplicative bajo mod m si y sólo si x y m son primos entre sí , por lo que cualquier número que es un múltiplo de esos factores no puede tener una inversa en su función.

Esta es la razón por el módulo elegido para tales PRNG es generalmente mejor momento.

Answer 5

Eh ... aquí es uno que funcione:

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