Optimierung: Addition und Shifting



  • Hallo!
    da ich mich mit Kryptografie beschäftige, stoße ich relativ schnell an Performance-Probleme (momentan dauert es ca. 30 Sekunden eine zufällige 512-bit-Primzahl zu finden). Gleich vorweg, ich nutze Karatsuba-Multiplikation und Barrett-Reduktion für Modulo und Square&Multiply für ModExp-Berechnungen, die Algorithmen sind also vorerst kein Optimierungsgrund.
    Besonders Addition und Shifting sind mein Augenmerk, die Addition sieht in etwa so aus:

    // bigint besteht aus Arrays, also werden Arrayelemente per Übertrag addiert
    // AtomType ist ein vorzeichenloser Integertyp
    void bigint::add(AtomType summand) {
        AtomType carry = 0;
        for(std::size_t n = 0; n < ATOM_SIZE; ++n) {
           AtomType result = storage[n] + summand.storage[n] + carry;
           // prüfen, ob die Summe einen Overflow ausgelöst hat
           if(result <= storage[n] && summand.storage[n] != 0 || result <= summand.storage[n] && storage[n] != 0)
              carry = 1;
           else carry = 0;
           storage[n] = result;
    }
    

    Ich vermute stark, dass die Bedingung für den Overflow zu kompliziert ist und würde diese gerne vereinfachen. Wie kann ich den unsigned-Overflow feststellen?



  • Hast Du Deine Algorithmen durch einen Profiler gejagt und die Addition ist das Bottleneck?
    So ziemlich jede CPU hat ja die arithmetischen Operationen mit Carry übertrag. Könntest Du hier also verwenden (x86: adc = add with carry). Dann musst Du nicht selber das Carry-Flag mitschleppen und testen. Macht die Sache natürlich plattformabhängig.



  • Ich habe das manuell überprüft und schon einiges an Performance wettgemacht. Die Bottleneck-Hierachie sieht so aus (Pfeile bedeuten "besteht aus"):

    Miller-Rabin-Test --> 1 mal Modexp (99% der Rechenzeit gehen dafür drauf)
    --> viele Barrett-Reduktionen und Karatsuba-Multiplikationen (pro Schleifendurchlauf je eine, wobei Barrett-Reduktionen doppelt zu lange dauern wie Karatsuba-Multiplikationen) --> 
    2 Karatsuba-Multiplikationen im Barrett deuten stark darauf hin, dass Karatsuba die meiste Zeit im Barrett benötigt --> 
    Karatsuba besteht aus vielen vielen Additionen/Bitshifting (wird rekursiv aufgerufen).
    

    Also ist das tiefste Bottleneck Karatsuba, aber so schlecht ist der Algo nicht, eher seine Implementierung. Daher suche ich hier weiter.



  • Jop, das wäre in Assembler sogar einfacher zu implementieren als in C++, ganz zu schweigen von performanter. 😞 Daher wirst du da auch wenig Land sehen gegen die ganzen Assembler-Bibliotheken.



  • Jede Java-Cryptlib ist noch schneller. Ich glaube, die Implementierung ist sicherlich noch nicht so gut, dass nur noch Assembler aushelfen könnte.



  • Aber ohne Assembler musst du solange mit Deinem Code rumspielen, bis der Compiler von selbst auf die Idee kommt, Add-With-Carry zu benutzen. Da gehst Du echt effizienter mit Deiner begrenzten Zeit um, wenn Du gleich die "optimale" Lösung hinschreibst.



  • Welche Java-Bibliotheken meinst du denn? Und bist du dir auch sicher, dass die hinterher nicht einfach native-calls machen?
    PS: Du machst da etwas rekursiv? Das solltest du vielleicht zu erst mal fixen. 😉



  • Wird

    if(result <= storage[n] && summand.storage[n] != 0 || result <= summand.storage[n] && storage[n] != 0)
              carry = 1;
    

    nicht einfach zu

    if(result < storage[n])
              carry = 1;
    

    ?

    Ansonsten würde ich mir eine Funktion addWithCarry oder so bauen, die den Assemblerbefehl mappt, mit #ifdef für msvc und gcc auf x86 und #else mit if(<). Aber keine Schleifen oder sowas in asm machen, sondern immer nur mal einen einzigen Befehl.


  • Mod

    carry = carry ? result <= storage[n] : result < storage[n];
    


  • volkard: Das geht leider nicht, weil das Carry-Bit mit addiert wird. Nur bei der ersten Addition würde es funktionieren. Und das mit dem Assembler-Befehl mappen ist auch nicht so leicht, weil man sich ja sicher sein muss, was der letzte Arithmetische Befehl war. Letztlich hat man eigentlich nur die Chance das passend zur Schlüsselgröße direkt in Assembler zu implementieren, das sieht dann mehr oder weniger so aus:

    add
    adc
    adc
    adc
    ...
    

    Was, wie man sicher auf einen Blick erkennen kann, relativ effizient ist. Schade dass C++ da keinen eingebauten Mechanismus für hat, der Compilern erlaubt solchen Code aus Templates zu generieren. Na ja, vielleicht für C++17. 🤡



  • Assembler ist für mich nicht wirklich eine Option. Dadurch, dass ich den Code möglichst plattformunabhängig brauche (und es für Visual Studio z.B. nicht mal mehr Inline-Assembler für x64 gibt (ja, der Code soll auch im 64-bit Modus laufen)) und er für int32, int64, int16 etc. Basistypen laufen sollte.

    Campers Vorschlag ist sehr gut, er hat die Modulare Exponentiation um gute 10% beschleunigt. Vermutlich kann ich jetzt aber nicht mehr aus der Addition herauskratzen.

    In der Tat ist der Karatsuba-Algorithmus rekursiv. Den aber mithilfe von std::stack iterativ zu implementieren ist nicht gerade einfach und ich bin mir nicht sicher, ob das am Ende wirklich schneller ist (gleichwohl die Komplexität wohl besser sein sollte). Ich werde es mal probieren.

    Wie sieht es mit Bitshifting aus? Mein aktueller Algorithmus für Left-Shift sieht so ähnlich aus wie

    ... shift_left_(int n) { ...
    // shifting over bitsize is undefined behaviour --> catch this case
    if(n >= ATOM_BITSIZE) {
    	// carrys full 0s are filled at the right
    	const AtomType carrys = n / ATOM_BITSIZE;
    	// move the important bytes left to make place for 0s
    	storage_type temp;
    	std::fill(temp.begin(), temp.end(), 0);
    	std::copy(storage_.begin(), storage_.end() - carrys, temp.begin() + carrys); // swap direction for big endian
    	storage_.swap(temp);
    	shift_left_(n % ATOM_BITSIZE); // now try an simple shift
    }
    else {
    	AtomType carry = 0, next_carry = 0;
    	for(int i = 0; i < N; ++i) { // swap direction for big endian
    		// range_mask sets a bitmask with 1s at bits ATOM_BITSIZE - n to ATOM_BITSIZE
    		carry = (storage_[i] & range_mask<AtomType>(ATOM_BITSITE - n)) >> (ATOM_BITSIZE - n);
    		((storage_[i] <<= n) |= next_carry);
    		next_carry = carry;
    	}
    }
    

    Ich finde den ersten Fall verdächtig, wo ich Nullen auffüllen muss, falls die Shiftgröße größer ist als ein Basistyp.



  • Ich weiss nicht ob das schneller ist, aber für unsigned gilt:

    carry_neu = (carry_alt & a^b) | (a&b);
    

    wobei a und b jeweils die obersten bits der beiden Summanden sind.

    Also:

    carry = (carry & (storage[n]>>sizeof(storage_type-1))^(summand.storage[n]>>sizeof(storage_type-1))) | 
    ((storage[n]>>sizeof(storage_type-1))&(summand.storage[n]>>sizeof(storage_type-1)));
    


  • Alternativ

    carry = ~(~carry&(a^b));
    


  • Carry Fisher: Das könnte in der Tat schneller sein. (Wenn's stimmen würde..)
    Jodocus: Also mal ganz naiv, shift würde ich einfach so implementieren:

    if (n >= sizeof data_ * 8)
    {
    	memset(data_, 0, sizeof data_);
    }
    else
    {
    	if (n >= sizeof(base_type) * 8)
    	{
    		auto n0 = n / (sizeof(base_type) * 8);
    		n = n % (sizeof(base_type) * 8);
    
    		size_t i = N;
    		while (i-- != n0)
    		{
    			data_[i] = data_[i - n0];
    		}
    		data_[i] = 0;
    		while (i-- != 0)
    		{
    			data_[i] = 0;
    		}
    	}
    	if (n != 0)
    	{
    		base_type carry = 0;
    		for (size_t i = 0; i != N; ++i)
    		{
    			data_[i] = data_[i] << (n) | carry;
    			carry = data_[i] >> (sizeof(base_type) * 8 - n);
    		}
    	}
    }
    

    Allerdings braucht man da auch eine Sonderbehandlung für Werte die >= sizeof carry * 8 sind.



  • @Carry Fisher: Bist du sicher, dass das erste stimmt? Für mich sieht das so aus, als ob das nur für 1-bit-Zahlen gilt. (Beispiel a = 0, b = 1, carry = 1)
    Und bei deinem zweiten Posting wird das neue carry 1, wenn a=0, b=0 und carry=0...


  • Mod

    Carry Fisher schrieb:

    Ich weiss nicht ob das schneller ist, aber für unsigned gilt:

    carry_neu = (carry_alt & a^b) | (a&b);
    

    wobei a und b jeweils die obersten bits der beiden Summanden sind.

    Das kann ich nicht nachvollziehen.

    mit carry_alt == 0, x == AtomType_max, y == 1
    sollte x + y + carry_alt liefern:
    sum == 0, carry_neu == 1

    Edit: da war jemand schneller.



  • wxSkip schrieb:

    Carry Fisher: Bist du sicher, dass das erste stimmt? Für mich sieht das so aus, als ob das nur für 1-bit-Zahlen gilt. (Beispiel a = 0, b = 1, carry = 1)
    Und bei deinem zweiten Posting wird das neue carry 1, wenn a=0, b=0 und carry=0...

    Vor Fehlern ist natürlich niemand gefeit 😉 Mal schaun. Die zweite Anmerkung von Dir ist leicht zu beantworten:

    0 XOR 0 = 0 -> 0 AND 0 = 0 -> NOT 0 = 1 -> NOT 1 = 0
    Ich hätte noch eine Klammer mehr spendieren müssen :

    carry = ~(~(carry&(a^b)))
    

    Ich habe mir einen Tabelle auf gestellt und dann die boolschen Gleichungen dafür aufgeschrieben, mit a, b, c als Eingangsdaten, x als Ergebnis und c' als neuem Carry

    a  1 0 1 0 1 1
    b  0 1 0 1 1 1
    c  0 0 1 1 0 1
    
    x  1 1 0 0 0 1
    
    c' 0 0 1 1 1 1
    

    Und da ist auch schon der Fehler: Ich habe nicht alle acht möglichen Fälle betrachtet.

    Also nochmal:

    a  0 1 0 1 0 1 0 1
    b  0 0 1 1 0 0 1 1
    c  0 0 0 0 1 1 1 1
    
    x  0 1 1 0 1 0 0 1
    
    c' 0 0 0 1 0 1 1 1
    

    c' = ab OR (a XOR b)c (Der erste Post von mir, also richtig)

    Der zweite Post von mir war aber falsch, weil nicht alle Fälle betrachtet wurden. Und Deine Anmerkung, dass das nur für eine Stelle gilt ist insofern richtig, als dass noch betrachtet werden muss, wie das Carry durch mehrere Stellen durchläuft. c ist in diesem Fall nämlich nicht das ursprüngliche carry, sondern das aus der Addition des bits n-2. Hmm, da muss ich noch mal nachdenken,aber ich halte den Ansatz für vielversprechend...


Log in to reply