Comment pouvons-nous optimiser la transformation NTT et l'arithmétique modulaire pour une mise au carré Bignum plus rapide ?

Arithmétique modulaire et optimisations NTT (DFT à champs finis)

Problème :

Dans un projet impliquant la quadrature utilisant le bignum rapide , la mise en œuvre avec NTT est lente, même pour les grands nombres (12000 bits ou plus).

Question :

1. Existe-t-il un moyen d'optimiser la transformation NTT ?
2. Existe-t-il un moyen d'accélérer la transformation modulaire arithmétique ?

Solution :

Transformation NTT optimisée

Séparer la fonction NTT_fast en deux fonctions, l'une avec WW[] et l'autre avec iWW[], conduit à un paramètre de moins dans les appels récursifs. Cela permet une légère amélioration des performances.

Arithmétique modulaire optimisée

Le code d'origine utilisait une série de contrôles de branchement et de sécurité, qui peuvent être éliminés en utilisant des petites astuces et en réorganisant la boucle principale. Le code d'assemblage de modmul a également été modifié pour plus d'efficacité.

Nouveau code

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;          
        };  
    }
    // ...
};

Conclusion

Ces optimisations entraînent une accélération de 1,35x de la transformée NTT et l'arithmétique modulaire. Le code est fourni en C et en assembleur en ligne.

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!