문제
함수 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);
}
}