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

Question

Da eine Funktion y = f (A, X):

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

Wie würde ich finde die Umkehrfunktion x = g (A, y), so dass x = g (A, f (A, x)) für alle Werte von 'x'?

Wenn f () für alle Werte von ‚x‘ nicht umkehrbar ist, was ist in der Nähe von einem inversen?

(F ist ein veralteter PRNG, und ich versuche zu verstehen, wie man umkehrt, eine solche Funktion).

• Aktualisiert
  Wenn ein relativ prim zu (2 ^ N) -1, dann g (A, Y) ist nur f (A-1, y).
  Wenn A nicht relativ prim ist, dann wird der Bereich von y gezwungen ... Ist g () bestehen immer noch, wenn auf diesen Bereich beschränkt?

Answer 1

Sie müssen die Inverse von A mod ((2^N) - 1) berechnen, aber Sie könnten nicht immer eine inverse Ihr Modul gegeben. Siehe diese auf Wolfram Alpha .

Beachten Sie, dass

A = 12343 hat eine inverse (A ^ -1 = 876.879.007 mod 4294967295)

aber 12345 keine inverse haben.

Wenn also ein teiler mit (2 ^ n) -1, dann Sie können eine inverse Funktion der Erweiterte euklidische Algorithmus wobei

einfach erstellen

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

sonst bist du kein Glück.

UPDATE : Als Antwort auf Ihre Frage aktualisiert, können Sie immer noch keine eindeutige Inverse in dem eingeschränkten Bereich bekommen. Auch wenn Sie CookieOfFortune der Brute-Force-Lösung verwenden, werden Sie Probleme wie haben

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

Answer 2

Sie müssen den Erweiterte euklidischen Algorithmus . Dies gibt Ihnen R und S, so dass

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

Wenn der GCD 1 ist, dann R die multiplikative Inverse von A. Dann wird die inverse Funktion ist

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

Ok, hier ist ein update für den Fall, dass das G = gcd (A, 2 ^ N-1) nicht 1. In diesem Fall ist

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

Wenn y durch die Funktion f berechnet wurde dann ist y teilbar durch G. Daher können wir die obige Gleichung durch G aufzuteilen und um eine Gleichung modulo (2 ^ N-1) / G erhalten. So ist die Menge der Lösungen ist

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

Answer 3

Die Lösung wird gegeben hier (

Accipitridae, Glenn und Jeff Moser haben die Antwort zwischen ihnen, aber es lohnt sich zu erklären, ein wenig mehr, warum nicht jede Zahl eine inverse unter mod hat 4294967295. Der Grund dafür ist, dass 4294967295 keine Primzahl ist; es ist das Produkt der fünf Faktoren : 3 x 5 x 17 x 257 x 65537. Eine Reihe x hat eine mutiplicative inverse unter mod m , wenn und nur wenn x und m sind coprime , so kann eine beliebige Zahl, die ein Vielfaches dieser Faktoren ist nicht eine inverse in Ihrer Funktion haben.

Aus diesem Grund ist das Modul für eine solche PRNGs gewählt ist in der Regel Primzahl ist.

Eh ... hier ist eine, die funktioniert:

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

Accipitridae, Glenn und Jeff Moser haben die Antwort zwischen ihnen, aber es lohnt sich zu erklären, ein wenig mehr, warum nicht jede Zahl eine inverse unter mod hat 4294967295. Der Grund dafür ist, dass 4294967295 keine Primzahl ist; es ist das Produkt der

Answer 9

Eh ... hier ist eine, die funktioniert:

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