Modular Exponentiation C++

Shade Of Mine

http://stackoverflow.com/questions/6659414/efficient-128-bit-addition-using-carry-flag

Klar ists Compilerabhaengig aber dafuer fuer jeden Compiler eigentlich relativ trivial zu machen...

knivil

google fuer gcc, nein ist nicht portabel:

__uint128_t a;

cooky451

Nutze leider VS, die haben glaube ich kein uint128.
Shade Of Mine: Also ich sehe da jetzt keine add-with-carry instruction, gucke ich nicht richtig? Sicher, das jmp ist weg, cmp macht er trotzdem unnötigerweise.

knivil

Es gibt mehr als eine Antwort. Alternativ kann auch eine der vielen Bibliotheken benutzt werden.

Generell wuerde mich eine Bibliothek interessieren, die Integer<128> oder Integer<256> als Template abstrahiert aehnlich wie std::bitset

Oooch, man findet so einiges: http://stackoverflow.com/questions/9145644/visual-c-x64-add-with-carry

volkard

knivil schrieb:

Generell wuerde mich eine Bibliothek interessieren, die Integer<128> oder Integer<256> als Template abstrahiert aehnlich wie std::bitset

Jo, die wäre fein. Zweierkomplementdarstellung und + und - macht man mit Schleifen und * per Karatsuba rekursiv. Dividieren traue ich mich nicht.

cooky451

knivil: Ja, arbitrary_integer<128/256/512/1024..> wäre cool. Aber nur, wenn das dann auch auf Machine-Words basiert und das Carry-Bit benutzt, sonst bringt mir das nichts.

knivil

Der erste Schritt bei Kryptographie sind eben BigIntegers.

cooky451

Nun ja, eher bei asymmetrischer Verschlüsselung und speziell bei RSA. Die meisten Block-Cipher inlusive AES (und damit auch (fast?) alle Hash-Funktionen und PRNGs) brauchen sowas nicht.

knivil

Vielleicht interessiert es dich: http://locklessinc.com/articles/256bit_arithmetic/ , kann man wahrscheinlich auch irgendwie mit Standard-C++ beschreiben, um den gleichen Asm-Code zu bekommen. mul128 braucht kein adc .

krümelkacker

cooky451 schrieb:

Hi,

ich suche einen Algorithmus um b^e mod n exakt (mit Integern) auszurechnen. Ich hatte diesen hier verwendet:
T result = 1;
	while (exponent != 0)
	{
		if ((exponent & 1) != 0)
			result = (result * base) % modulus;

		exponent >>= 1;
		base = (base * base);
		base %= modulus;
	}
	return result;
Das Problem dabei ist aber, dass base * base overflowen kann. Gibt es eine effiziente Möglichkeit das (ohne ASM) zu beheben?

Was du implementiert hast ist ja hier eine Variante des Square-and-Multiply-Algorithmus. So etwas ähnliches gibt es auch für die Multiplikation: Double-and-Add. Du könntest also statt base*base einfach mul(base,base,n) schreiben und mult per Double-and-Add implementieren, wobei du dann beim Verdoppeln auf aufaddieren immer das Ergebnis modulo n reduzierst.

cooky451 schrieb:

Hi,

ich suche einen Algorithmus um b^e mod n exakt (mit Integern) auszurechnen. Ich hatte diesen hier verwendet:
T result = 1;
	while (exponent != 0)
	{
		if ((exponent & 1) != 0)
			result = (result * base) % modulus;

		exponent >>= 1;
		base = (base * base);
		base %= modulus;
	}
	return result;
Das Problem dabei ist aber, dass base * base overflowen kann. Gibt es eine effiziente Möglichkeit das (ohne ASM) zu beheben?

Nimm dies: http://philzimmermann.com/EN/bnlib/index.html