문제

함수 y = f (a, x)가 주어지면 :

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

'x'의 모든 값에 대해 x = g (a, f (a, x))를 위해 역 함수 x = g (a, y)를 어떻게 찾을 수 있습니까?

F ()가 'X'의 모든 값에 대해 전환 할 수 없다면 역에 가장 가까운 것은 무엇입니까?

(F는 쓸모없는 PRNG이며, 그러한 기능을 어떻게 반전시키는 지 이해하려고 노력하고 있습니다).

  • 업데이트되었습니다
    a가 비교적 (2^n) -1로 프라임이면 G (a, y)는 단지 f (a-1, y)입니다.
    A가 상대적으로 프라임이 아닌 경우 Y의 범위가 제한됩니다 ... 해당 범위로 제한되면 g ()가 여전히 존재합니까?
도움이 되었습니까?

해결책

반대를 계산해야합니다 A mod ((2^N) - 1), 그러나 모듈러스를 감안할 때 항상 역전이 아닐 수도 있습니다. 보다 이것은 Wolfram Alpha에 있습니다.

주목하십시오

a = 12343은 역입니다 (a^-1 = 876879007 MOD 4294967295)

그러나 12345에는 역전이 없습니다.

따라서 A 인 경우 비교적 주요 (2^n) -1로 확장 된 유클리드 알고리즘 어디

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

그렇지 않으면 운이 좋지 않습니다.

업데이트: 업데이트 된 질문에 대한 응답으로 제한된 범위에서 고유 한 역수를 얻을 수 없습니다. Cookieoffortune의 Brute Force 솔루션을 사용하더라도 다음과 같은 문제가 발생합니다.

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

다른 팁

당신은 필요합니다 확장 된 유클리드 알고리즘. 이것은 당신에게 R과 S를 제공합니다

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

gcd가 1이면 r은 A의 곱하기 역 역입니다. 그러면 역 함수는 다음과 같습니다.

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

좋아요, 여기에 있습니다 업데이트 g = gcd (a, 2^n-1)가 1이 아닌 경우

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

y가 함수 F에 의해 계산 된 경우 y는 G로 나눌 수 있습니다. 따라서 위의 방정식을 g로 나눌 수 있고 방정식 모듈로 (2^n-1)/g를 얻을 수 있습니다. 따라서 솔루션 세트는 다음과 같습니다

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

해결책이 제공됩니다 여기 (http://en.wikipedia.org/wiki/linear_congruence_theorem), 확장 된 유클리드 알고리즘이 솔루션을 찾는 데 사용되는 방법에 대한 데모를 포함합니다.

모듈러스 기능은 일반적으로 역전이 없습니다. 기능, 그러나 때로는 주어진 y에 맵을 맵으로 찾을 수 있습니다.

Accipitridae, Glenn 및 Jeff Moser는 그들 사이에 답을 가지고 있지만, Mod 4294967295에 따라 모든 숫자가 역전을 갖지 않는 이유는 무엇입니까? 4294967295가 소수가 아니기 때문입니다. 그것은의 제품입니다 다섯 가지 요인: 3 x 5 x 17 x 257 x 65537. 숫자 엑스 모드 하에서 반복적 인 역전이 있습니다 경우에만 엑스 그리고 ~이다 Coprime, 그러므로 이러한 요소 중 하나 인 숫자는 기능에 반대를 가질 수 없습니다.

이것이 그러한 PRNG에 대해 선택한 계수가 일반적으로 주요한 이유입니다.

Eh ... 여기에 작동 할 것이 있습니다.

unsigned long G(unsigned long A, unsigned long y)
{
    for(unsigned int i = 0; i < 4294967295; i++)
    {
        if(y == F(A, i)) return i);
    }
}
라이센스 : CC-BY-SA ~와 함께 속성
제휴하지 않습니다 StackOverflow
scroll top