我們如何優化 NTT 變換和模運算以實現更快的 Bignum 平方？

模算術和NTT（有限域DFT）最佳化

問題：

在涉及使用快速bignum 進行平方的在專案中，NTT 的實現速度很慢，即使對於大數（12000 位元或更多）。

問題：

1. 有沒有辦法優化 NTT 轉換？
2. 有沒有辦法加快模組化速度

解法：

最佳化NTT轉換

將兩個NT個函數，一個有WW[]，另一個有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 和內聯彙編形式提供。

以上是我們如何優化 NTT 變換和模運算以實現更快的 Bignum 平方？的詳細內容。更多資訊請關注PHP中文網其他相關文章！