더 빠른 Bignum Squareing을 위해 NTT 변환 및 모듈식 산술을 어떻게 최적화할 수 있습니까?

모듈식 연산 및 NTT(유한 필드 DFT) 최적화

문제:

빠른 빅넘을 사용한 제곱 관련 프로젝트에서 , NTT를 사용한 구현은 큰 수(12000비트 또는 more).

질문:

1. NTT 변환을 최적화하는 방법이 있습니까?
2. 모듈식 속도를 높이는 방법이 있습니까? 산술?

해결책:

최적화된 NTT 변환

NTT_fast 함수를 WW[]를 사용하는 함수와 다른 하나를 사용하는 두 함수로 분리 iWW[]를 사용하면 재귀 호출에서 매개변수가 하나 줄어듭니다. 이는 약간의 성능 향상을 제공합니다.

최적화된 모듈식 연산

원본 코드는 일련의 분기 및 안전 검사를 사용했는데, 이는 비트 트릭을 활용하고 메인 루프를 재배열하여 제거할 수 있습니다. modmul의 어셈블리 코드도 효율성을 위해 수정되었습니다.

새 코드

class fourier_NTT
{
    // ...
    // Modular arithmetics (optimized, but it works only for p >= 0x80000000!!!)
    inline uint32 modadd(uint32 a, uint32 b)
    {
        uint32 d;
        //d = a + b;
        //!if (d < a)
        //    d -= p;
        //!if (d >= p)
        //    d -= p;
         __asm {
            mov eax, a;
            add eax, b
        }
        return d;
    }

    inline uint32 modsub(uint32 a, uint32 b)
    {
        uint32 d;
        //d = a - b;
        //!if (a < b)
        // a - b < 0 when a < b, so no need to check
        //!    d += p;
        __asm {
            mov eax, a;
            sub eax, b
        }
        return d;
    }

    inline uint32 modmul(uint32 a, uint32 b)
    {
        uint32 _a = a;
        uint32 _b = b;   

        __asm
        {
        mov eax, a;
        mul b;
        mov ebx, eax;
        mov eax, 2863311530;
        mov ecx, edx;
        mul edx;
        shld edx, eax, 1;
        mov eax, 3221225473;

        mul edx;
        sub ebx, eax;
        mov eax, 3221225473;
        sbb ecx, edx;
        jc addback;

            neg ecx;
            and ecx, eax;
            sub ebx, ecx;

        sub ebx, eax;
        sbb edx, edx;
        and eax, edx;
            addback:
        add eax, ebx;          
        };  
    }
    // ...
};

결론

이러한 최적화를 통해 1.35배의 속도 향상이 가능합니다. NTT 변환 및 모듈러 산술. 코드는 C 및 인라인 어셈블리로 제공됩니다.

위 내용은 더 빠른 Bignum Squareing을 위해 NTT 변환 및 모듈식 산술을 어떻게 최적화할 수 있습니까?의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!