Domanda

Data una funzione y = f (A, X):

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

Come faccio a trovare la funzione inversa x = g (A, y) tali che x = g (A, f (A, x)) per tutti i valori di 'x'?

Se f () non è invertibile per tutti i valori di 'x', ciò che è più vicino a un inverso?

(F è un PRNG obsoleta, e sto cercando di capire come si inverte tale funzione).


  • Aggiornato Se A è relativamente primo (2 ^ N) -1, allora g (A, Y) è solo f (A-1, y).
    Se A non è relativamente primi, quindi la gamma di y è vincolato ... Does g () esistono ancora, se limitata a quella gamma?
È stato utile?

Soluzione

È necessario calcolare l'inverso di A mod ((2^N) - 1), ma non si potrebbe sempre avere un inverso dato il vostro modulo. Vedere questo su Wolfram Alpha .

Si noti che

A = 12343 ha inversa (A ^ -1 = 876.879.007 mod 4294967295)

, ma 12345 non ha un inverso.

Così, se A è relativamente primo con (2 ^ n) -1, allora è possibile creare facilmente una funzione inversa utilizzando il estesa euclideo Algoritmo dove

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

altrimenti sei fuori di fortuna.

Aggiorna : In risposta alla tua domanda aggiornato, non è ancora possibile ottenere un inverso unico nel range ristretto. Anche se si utilizza la soluzione di forza bruta di CookieOfFortune, avrete problemi come

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

Altri suggerimenti

È necessario il estesa euclidea algoritmo . Questo vi dà R e S tale che

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

Se il gcd è 1 allora R è l'inverso moltiplicativo di A. Poi la funzione inversa è

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

Ok, ecco un update per il caso in cui G = gcd (A, 2 ^ N-1) non è 1. In questo caso

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

Se y è stata calcolata dalla funzione f, allora y è divisibile per G. Quindi si può dividere l'equazione di cui sopra da G e ricevere un modulo equazione (2 ^ N-1) / G. Così l'insieme delle soluzioni è

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

La soluzione è data qui ( http://en.wikipedia.org/wiki/Linear_congruence_theorem ), e include una dimostrazione di come viene utilizzato l'algoritmo di Euclide esteso per trovare le soluzioni.

La funzione di modulo, in generale, non ha un inverso Funzione , ma a volte è possibile trovare una serie di xe che mappano alla data y.

Accipitridi, Glenn, e Jeff Moser hanno la risposta tra di loro, ma vale la pena spiegare un po 'di più perché non ogni numero ha un inverso sotto mod 4294967295. La ragione è che 4294967295 non è un numero primo; è il prodotto di cinque fattori : 3 x 5 x 17 x 257 x 65537. Un numero x ha un'inversa mutiplicative sotto mod m se e solo se x e m coprimi , in modo che qualsiasi numero che è un multiplo di questi fattori non può avere un inverso nella funzione.

Questo è il motivo per cui il modulo scelto per tali PRNGs è di solito il primo.

Eh ... ecco quello che funziona:

unsigned long G(unsigned long A, unsigned long y)
{
    for(unsigned int i = 0; i < 4294967295; i++)
    {
        if(y == F(A, i)) return i);
    }
}
Autorizzato sotto: CC-BY-SA insieme a attribuzione
Non affiliato a StackOverflow
scroll top