Inversa di A * X MOD (2 ^ N) -1
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?
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);
}
}