我们如何优化 NTT 变换和模运算以实现更快的 Bignum 平方？

模算术和 NTT（有限域 DFT）优化

问题：

在涉及使用快速 bignum 进行平方的项目中，NTT 的实现速度很慢，即使对于大数（12000 位或更多）。

问题：

1. 有没有办法优化 NTT 变换？
2. 有没有办法加快模块化速度

解法：

优化NTT变换

将NTT_fast函数分成两个函数，一个带有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中文网其他相关文章！