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

Question

Etant donnée une fonction y = f (A, X):

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

Comment je trouver la fonction inverse x = g (A, y) de telle sorte que x = g (a, f (a, x)) pour toutes les valeurs de 'x'?

Si f () n'est pas inversible pour toutes les valeurs de « x », ce qui est le plus proche de l'inverse?

(F est un PRNG obsolète, et je suis en train de comprendre comment on intervertit une telle fonction).

• Mise à jour
  Si A est premier avec (2 ^ N) -1, alors g (A, Y) est juste f (A-1, y).
  Si A n'est pas premiers entre eux, alors la plage y est limitée ... Est-ce que g () existent encore si limité à cette plage?

Answer 1

Vous devez calculer l'inverse de A mod ((2^N) - 1), mais vous pourriez avoir pas toujours l'inverse étant donné votre module. Voir ceci sur Wolfram Alpha .

Notez que

A = 12343 a un inverse (A ^ -1 mod = 876879007 4294967295)

mais ne pas 12345 l'inverse.

Ainsi, si A est premier avec (2 ^ n) -1, vous pouvez facilement créer une fonction inverse en utilisant algorithme d'Euclide étendu où

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

sinon vous êtes hors de la chance.

UPDATE : En réponse à votre question mise à jour, vous ne pouvez toujours pas obtenir un inverse unique dans la gamme restreinte. Même si vous utilisez une solution de force brute de CookieOfFortune, vous aurez des problèmes tels que

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

Answer 2

Vous avez besoin algorithme d'Euclide étendu . Cela vous donne R et S tel que

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

Si le GCD est alors R 1 est l'inverse multiplicatif de A. Ensuite, la fonction inverse est

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

Ok, voici un update dans le cas où G = PGCD (A, 2 ^ N-1) ne soit pas 1. Dans ce cas,

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

Si y a été calculée par la fonction f alors y est divisible par G. En conséquence, on peut diviser l'équation ci-dessus par G et obtenir un modulo de l'équation (2 ^ N-1) / G. Ainsi, l'ensemble des solutions est

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

Answer 3

La solution est donnée (

Accipitridés, Glenn et Jeff Moser ont la réponse entre eux, mais il vaut la peine d'expliquer un peu plus pourquoi pas chaque numéro a une inverse sous mod 4294967295. La raison est que 4294967295 est pas un nombre premier; elle est le produit de cinq facteurs : 3 x 5 x 17 x 257 x 65537. Un certain nombre x a une inverse multiplicatif sous mod m si et seulement si x et m coprime , donc un nombre qui est un multiple de ces facteurs ne peut pas avoir un inverse dans votre fonction.

Ceci est la raison pour laquelle le module choisi pour ces PRNGs est généralement le premier.

Eh ... voici un qui fonctionne:

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

Answer 4

Answer 5

Answer 6

Answer 7

Answer 8

Accipitridés, Glenn et Jeff Moser ont la réponse entre eux, mais il vaut la peine d'expliquer un peu plus pourquoi pas chaque numéro a une inverse sous mod 4294967295. La raison est que 4294967295 est pas un nombre premier; elle est le produit de

Answer 9

Eh ... voici un qui fonctionne:

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