mathe/informatik S=x^n mod b effektiv berechnen

[jo (Gast)]

Hallo,
für die Programmierung einer digitalen Signatur benötige ich die 
Berechnung

S=x^n mod b
n,b aus N

Da n sehr großwerden kann, möchte ich einen Algorithmus ggfs 
sochastischer Algorithmus verwenden. Fälle Euch da einer ein oder ein 
Stichwort zum Suchen?

MFG

jo

[D. I. (Gast)]

http://de.wikipedia.org/wiki/Diskrete_Exponentialfunktion

http://de.wikipedia.org/wiki/Bin%C3%A4re_Exponentiation

Damit geht das in O(log(n))

[Johann L. (gjlayde)]

n wird nicht größer als b [1], für φ siehe [2]:

$$(x,b)=1 \quad\Rightarrow\quad x^{\varphi(b)} \equiv 1 \quad\Rightarrow\quad x^n \equiv x^{n \text{ mod } \varphi(b)}$$

Da b für kryptographische Zwecke verwendet wird, hat es keine kleinen 
Teiler, daher sind x und b idR teilerfremd. Mit etwas Hirnschmalz geht 
es auch für (x,b)≠1. In diesem Falle faktorisiert man den unliebsamen 
Nullteiler raus und bekommt sogan ein noch kleineres b'.

Zur Berechnung der Potenz braucht man Grundarithmetik, also + und · mod 
b. Addition ist trivial. Multiplikation x·y per Schulmethode (indem man 
die Zahlen zu einem Basis B darstellt, zB B=2^32 oder B=2^31) ist 
machbar, liefert dann aber ein Zwischenergebnis in der Größenordnung b², 
das wieder mod b reduziert werden will.

Stattdessen kann man die Schulmultiplikation auch binär machen (B=2) und 
nach jedem Shift/jeder Addition reduzieren:

$$x+y = (x+y < b)\ ?\ x+y\; :\; x+y-b$$

Dadurch bleiben die Zwischenergebnisse klein und die Reduktion des 
großen Endergebnisses entfällt.

In der Praxis wird man mehrere (Assembler) Implementierungen in einem 
CA-System vorhalten nebst einer Heuristik, welcher Algorithmus der beste 
ist.

Kombination verschiedener Verfahren ist möglich, insbesondere Karatsuba 
[3] ist leicht zu implementieren und gut zu kombinieren.

Schönhage-Strassen [4] ist erst ab mehreren 1000 Dezimalstellen besser, 
was schön verdeutlicht, daß Komplexität nicht alles ist und eine 
kleinere O-Konstanten bei höherer Komplexität bis in große 
Zahlenbereiche hinein durchaus einer besseren Komplexität überlegen sein 
kann.

[1] http://de.wikipedia.org/wiki/Satz_von_Euler
[2] http://de.wikipedia.org/wiki/Phi-Funktion
[3] http://de.wikipedia.org/wiki/Karatsuba-Algorithmus
[4] http://de.wikipedia.org/wiki/Schönhage-Strassen-Algorithmus