c = 2^N + -1에 대해 신속하게 (~ * b) mod c를 계산하십시오.

Question

32 비트 정수 수학에서 덧셈과 곱하기의 기본 연산은 내재적으로 mod 2^32로 계산됩니다. 결과는 최하위 순서가됩니다. 가산 또는 곱셈의 비트.

다른 모듈러스로 결과를 계산하려면 다른 언어로 여러 개의 BigInt 클래스를 사용할 수 있습니다. 그리고 값이 a, b, c에 대해 < 2^32이면 중간 값을 64 비트 long int로 계산하고 % 연산자를 사용하여 오른쪽으로 줄일 수 있습니다

하지만 특별한 트릭이 있다고 들었습니다 C가 (2^N) -1 또는 (2^N) +1 형태 일 때 a * b mod C를 효율적으로 계산하기 위해서는 64 비트 수학이나 BigInt 라이브러리를 사용하지 않고 매우 효율적입니다. 임의의 모듈러스 평가 및 중간 곱셈을 포함하는 경우 일반적으로 32 비트 int를 오버플로하는 경우를 적절하게 계산합니다.

이러한 특별한 경우에는 빠른 평가 방법이 있다고 들었지만 실제로 방법에 대한 설명을 찾지 못했습니다. "크 누스에 있지 않니?" "위키피디아 어딘가에 있지 않니?" 나는 들었습니다.

2147483647은 2^31 -1과 같은 소수이므로 a * b mod 2147483647의 곱셈을 수행하는 것은 분명히 난수 생성기에서 일반적인 기술입니다.

전문가에게 물어볼 것입니다. 이 똑똑한 특수한 케이스가 무엇인가요? 어떤 논의도 찾을 수없는 mod 방식으로 곱하면 되나요?

Answer 1

나는 트릭은 다음

당신이 a*b mod 10000-1를 곱하여하는 가정 및

a = 1234 = 12 * 100 + 34 
b = 5432 = 54 * 100 + 32 

(나는 쉽게,하지만 원칙은 유지해야하기 때문에, 기본 10 그것을 할거야) 생각 지금 a*b = 12 * 54 * 10000 + 34 * 54 * 100 + 12 * 32 * 100 + 34 * 32

12 * 54 * 10000 = 648 * 10000 
34 * 54 * 100 = 1836 * 100 
12 * 32 * 100 = 384 * 100 
34 * 32   = 1088 

x * 10000 ≡ x (mod 10000-1) 이후 [1], t

그는 첫 번째와 마지막 조항이 648 + 1088이됩니다. 두 번째와 세 번째 용어는 '트릭'이 들어오는 곳입니다.참고 :

1836 = 18 * 100 + 36 
1836 * 100 ≡ 18 * 10000 + 3600 ≡ 3618 (mod 10000-1). 

이것은 본질적으로 순환 교대입니다. 결과는 648 + 3618 + 8403 + 1088입니다. 또한 모든 경우에 곱해진 숫자는 < 10000 (< 100 및 b < 100)이므로 두 자리 숫자를 함께 사용하면 계산할 수 있습니다 , 그들을 추가하십시오.

바이너리에서는 비슷하게 작동합니다.

a 및 b로 시작하면 둘 다 32 비트입니다. mod 2^31 - 1을 곱하기를 원하지만 16 비트 승수 만 있습니다 (32 비트 제공). 알고리즘은 다음과 같을 것입니다 :

늦었으므로 아마 누산기 부분이 작동하지 않을 것입니다. 나는 원칙적으로 그것이 맞다고 생각합니다. 누군가는 이것을 올바르게하기 위해 이것을 자유롭게 편집 할 수 있습니다.

언롤 드 (Unrolled), 이것은 매우 빠릅니다. PRNG가 사용하는 것입니다. 추측합니다.

[1]: x*10000 ≡ x*(9999+1) ≡ 9999*x + x ≡ x (mod 9999)

Answer 2

빠른 검색 결과는 http://home.pipeline.com/~hbaker1/AB-mod-N.pdf입니다. 불행히도, 너무 간단해서 그냥 단순화 된 수식을 쓰지는 못했지만 어딘가에있을 것입니다.

Answer 3

* b를 p*2^N+q으로 계산한다고 가정 해 보겠습니다. 이를 위해서는 64 비트 계산이 필요하거나 a와 b를 16 비트 파트로 분리하고 32 비트로 계산할 수 있습니다.

a*b mod 2^N-1 = p+q mod 2^N-12^N mod 2^N-1 = 1부터 a*b mod 2^N-1 = p+q mod 2^N-1입니다.

그리고 a*b mod 2^N+1 = -p+q mod 2^N+1은 2^N mod 2^N+1 = -1부터입니다.

두 경우 모두 2^N-1 또는 2^N+1으로 나누지 않습니다.

Answer 4

각 단계마다 모듈러 감소를 수행하는 대신 Montgomery reduction (다른 descriptions이 있음)을 사용하여 모듈러 곱셈 계산 비용을 줄일 수 있습니다. N은 +/- 2의 거듭 제곱의 속성을 사용하지 않습니다.

Answer 5

당신이 찾고있는 ID는 (일반적으로 ± 1 만) N = 2^q + c c는 정수가 주어진, x mod N = (x mod 2^q)- c*floor(x/2^q)입니다. 에서 "특별한 형태의 계수" "소수 : 전산 관점" 리처드 크 랜달과 칼 포머 란스에 의해

당신은 섹션 9.2.3을 읽을 수 있습니다. 이론 외에도 위의 관계를 구현하는 알고리즘에 대한 의사 코드가 포함되어 있습니다.

Answer 6

이 주제에 대해 rather extensive page을 찾았습니다. 문제는 물론 알고리즘과 관련하여 내역의 문제와 해결 방법 및 사람들이 솔루션을 사용하는 방법에 대해서도 논의했습니다.