신속한 곱셈과 뺄셈을 기본으로 모듈화

Question

int (32 비트)의 벡터에 스칼라 모듈 p (p는 소수 (2^32) -5)를 곱한 다음 빼기 코드를 최적화해야합니다. 다른 벡터로부터의 벡터 p.

public static void multiplyAndSubtract(long fragmentCoefficient, long[] equationToSubtractFrom, long[] equationToSubtract) { 
    for (int i = 0; i < equationToSubtractFrom.length; i++) { 
     equationToSubtractFrom[i] = modP(equationToSubtractFrom[i] - multiplyModP(fragmentCoefficient, equationToSubtract[i])); 
    } 
} 

자바 부호없는 정수를 지원하지 않기 때문에 내가 갈망을 사용하고 있지만 (모든 숫자가 0 < = X < 될 것으로 예상 할 수 있도록 두 벡터 모드 페이지입니다

코드는 다음과 같습니다 2^32) -5

최적의 아이디어? mod p 연산은 대부분의 실행 시간을 차지하므로,이를 최적화하는 한 가지 방법은 곱셈 후에 modP를 수행하지 않고 빼기 후에 만 ​​수행 할 수 있습니다. 어떻게하는지에 대한 아이디어가 있습니까?

Answer 1

2^32 = 5 (mod p)라는 사실을 사용하여 계산 속도를 높이고 분할을 피할 수 있습니다.

곱셈 및 뺄셈 후 결과를 낮은 (x % 2^32) 및 hi (x/2^32) 부분으로 나눕니다. 그런 다음 hi 부분에 5를 곱하고 낮은 부분과 합칩니다. 그런 다음이 절차를 한 번 더 반복하십시오. 결과가 p보다 큰 경우 p를 빼십시오. 부정적인 결과가 나오면 p를 추가하십시오.

편집 : 조합 된 곱셈과 뺄셈이 오버플로 할 수 있으므로 곱셈의 결과는 또한 모듈로 p로 가져와야합니다. 그러나 위의 절차 중 한 단계만으로도 충분합니다. 단지 나누어서 5를 곱한 다음 추가하십시오.

Answer 2

e - (f * e mod p) mod p = (e-e f) mod p 

Wolfram Alpha을 참조하십시오.

방법 1 : 불가 곱셈

Answer 3

나는 부서 또는 계수를 사용하지 않고이 작업을 수행하는 두 가지 방법을 알고. (see this paper)

여기서 기본적인 아이디어는 p의 역수를 미리 계산하고 근사하여 정수 곱셈을 사용하여 정수 나누기를 수행하는 것입니다. 그렇다면 곱셈하여 모듈러스를 얻을 수 있습니다. 이것은 구현하기 쉬운 접근법입니다.

방법 2 : (난 보통 사용하는 것), 부동 소수점을 사용하는 것입니다. 숫자를 부동 소수점으로 변환하고 사전 계산 된 역수 인 p을 곱하십시오. 그런 다음 정수로 다시 변환합니다. 이 접근법은 올바르게 진행되기가 더 어려울 수 있지만 제 경험에 따르면 제대로 수행되면 빠릅니다.

여기의 두 가지 접근법은 정수 또는 부동 소수점 중 하나의 역수를 사전 계산하는 것 외에 다른 부분을 포함하지 않습니다.

이러한 방법 중 하나가 %의 직접 사용보다 빠르지 여부는 구현 방법에 따라 달라집니다. 그래서 어느 쪽이 더 빠를 것이라고 보장 할 수는 없습니다.