我们如何优化 NTT 变换和模运算以实现更快的 Bignum 平方？-C++-PHP中文网

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

DDD

发布： 2024-12-19 03:14:13

原创

472 人浏览过

How Can We Optimize NTT Transform and Modular Arithmetic for Faster Bignum Squaring?

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

问题：

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

问题：

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

解法：

优化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中文网其他相关文章！