NTT 変換とモジュラー演算を最適化して Bignum 二乗法を高速化するにはどうすればよいでしょうか?

剰余演算と NTT (有限体 DFT) 最適化

問題:

高速 bignum を使用した二乗を含むプロジェクト内、NTT での実装は、たとえ大きな数 (12000 ビット) であっても時間がかかります。

質問:

1. NTT 変換を最適化する方法はありますか?
2. 速度を上げる方法はありますか?モジュラー算術?

解決策:

最適化された NTT Transform

NTT_fast 関数を 2 つの関数 (1 つは WW[] で、もう 1 つは関数) に分離します。 iWW[] を使用すると、再帰呼び出しのパラメータが 1 つ減ります。これにより、パフォーマンスが若干向上します。

モジュラー演算の最適化

元のコードでは一連の分岐と安全性チェックが使用されていましたが、ビット トリックを利用してメイン ループを再配置することで削除できます。 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 中国語 Web サイトの他の関連記事を参照してください。