특히 매우 큰 수(예: 12000비트 이상)의 경우 더 빠른 계산을 위해 NTT(수론 변환) 및 모듈러 산술을 최적화하려면 어떻게 해야 합니까?-C++-php.cn

특히 매우 큰 수(예: 12000비트 이상)의 경우 더 빠른 계산을 위해 NTT(수론 변환) 및 모듈러 산술을 최적화하려면 어떻게 해야 합니까?

Barbara Streisand

풀어 주다： 2024-12-16 03:13:18

원래의

545명이 탐색했습니다.

How can I optimize my Number Theoretic Transform (NTT) and modular arithmetic for faster computation, especially with very large numbers (e.g., over 12000 bits)?

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

문제 설명

NTT를 빠르게 사용하고 싶었습니다. 제곱(빠른 빅넘 제곱 계산 참조). 그러나 결과는 매우 큰 숫자의 경우에도 느립니다. .. 12000비트 이상.

제 질문은 다음과 같습니다.

있나요? NTT 변환을 최적화하는 방법이 있나요? 나는 병렬성(스레드)으로 속도를 높이려는 것이 아닙니다. 이것은 낮은 수준의 레이어에만 적용됩니다.

모듈 연산 속도를 높일 수 있는 방법이 있나요?

이것은 NTT용 C 소스 코드입니다(완전하고 타사 라이브러리가 필요 없이 100% C에서 작동하며 스레드로부터 안전해야 합니다. 소스 배열이 임시로 사용된다는 점에 유의하세요!!! 또한 배열을 자체적으로 변환할 수도 없습니다.

최적화된 솔루션

사전 계산 사용 거듭제곱: NTT 프로세스 중에 W와 iW의 거듭제곱(기본 단위근과 그 역수)을 미리 계산하고 저장하여 재계산을 방지합니다. 이렇게 하면 곱셈과 나눗셈 횟수가 크게 줄어들어 계산 속도가 빨라집니다.
루프 언롤링: NTT 알고리즘에서 루프를 언롤링하여 루프 반복과 관련된 오버헤드를 줄입니다. 이렇게 하면 분기 명령 수를 줄여 성능을 향상할 수 있습니다.
모듈식 산술 최적화: 비트 연산 및 어셈블리 언어를 사용하여 모듈식 산술 연산(덧셈, 뺄셈, 곱셈 및 누승)을 효율적으로 구현합니다. . 이렇게 하면 불필요한 분기 및 조건문을 제거하여 더 빠르게 실행할 수 있습니다.

구현 예

다음은 미리 계산된 거듭제곱과 비트 연산을 사용하여 C에서 최적화된 NTT 구현의 예입니다.

class NTT {
public:
    NTT() {
        // Initialize constants
        p = 0xc0000001;
        W = modpow(2, 0x30000000 / n);
        iW = modpow(2, p - 1 - 0x30000000 / n);
        rN = modpow(n, p - 2);
        NN = n >> 1;

        // Precompute W and iW powers
        WW = new uint32_t[n];
        iWW = new uint32_t[n];
        WW[0] = 1;
        iWW[0] = 1;
        for (uint32_t i = 1; i < n; i++) {
            WW[i] = modmul(WW[i - 1], W);
            iWW[i] = modmul(iWW[i - 1], iW);
        }
    }

    void NTT(uint32_t *dst, uint32_t *src, uint32_t n) {
        if (n > 0) {
            // Reorder even, odd elements
            for (uint32_t i = 0, j = 0; i < NN; i++, j += 2) {
                dst[i] = src[j];
            }
            for (j = 1; i < n; i++, j += 2) {
                dst[i] = src[j];
            }

            // Recursive NTT
            NTT(src, dst, NN);  // Even
            NTT(src + NN, dst + NN, NN);  // Odd

            // Restore results
            for (uint32_t i = 0, j = NN; i < NN; i++, j++) {
                uint32_t a0 = src[i];
                uint32_t a1 = modmul(src[j], WW[i]);
                dst[i] = modadd(a0, a1);
                dst[j] = modsub(a0, a1);
            }
        }
    }

private:
    uint32_t p, n, NN, W, iW, rN;
    uint32_t *WW, *iWW;

    // Modular arithmetic operations
    inline uint32_t modadd(uint32_t a, uint32_t b) {
        uint32_t d = a + b;
        if (d >= p) d -= p;
        return d;
    }

    inline uint32_t modsub(uint32_t a, uint32_t b) {
        uint32_t d = a - b;
        if (d > a) d += p;
        return d;
    }

    inline uint32_t modmul(uint32_t a, uint32_t b) {
        uint32_t m = (uint64_t)a * b;
        return m - (p * (m / p));
    }

    inline uint32_t modpow(uint32_t a, uint32_t b) {
        if (b == 0) return 1;
        uint32_t t = modpow(a, b / 2);
        t = modmul(t, t);
        if (b &amp; 1) t = modmul(t, a);
        return t;
    }
};

로그인 후 복사