Wie können wir die NTT-Transformation und die modulare Arithmetik für eine schnellere Bignum-Quadrierung optimieren?

Modulare Arithmetik und NTT-Optimierungen (Finite Field DFT)

Problem:

In einem Projekt, das Quadrieren mit schnellem Bignum beinhaltet , die Implementierung mit NTT ist langsam, selbst für große Zahlen (12000 Bits bzw mehr).

Frage:

1. Gibt es eine Möglichkeit, die NTT-Transformation zu optimieren?
2. Gibt es eine Möglichkeit, modular zu beschleunigen Arithmetik?

Lösung:

Optimierte NTT-Transformation

Aufteilung der NTT_fast-Funktion in zwei Funktionen, eine mit WW[] und die andere mit iWW[] führt bei Rekursionsaufrufen zu einem Parameter weniger. Dies sorgt für eine kleine Leistungsverbesserung.

Optimierte modulare Arithmetik

Der ursprüngliche Code verwendete eine Reihe von Verzweigungen und Sicherheitsprüfungen, die durch den Einsatz von Bittricks und die Neuanordnung der Hauptschleife eliminiert werden können. Der Assembler-Code für Modmul wurde ebenfalls aus Effizienzgründen geändert.

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

Fazit

Diese Optimierungen führen zu einer 1,35-fachen Beschleunigung von die NTT-Transformation und modulare Arithmetik. Der Code wird in C und Inline-Assembly bereitgestellt.

Das obige ist der detaillierte Inhalt vonWie können wir die NTT-Transformation und die modulare Arithmetik für eine schnellere Bignum-Quadrierung optimieren?. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!