Bignum-Division

02/08/2010 - 13:02 von Markus Wichmann | Report spam
Hi all,

ich suche nach einem Algorithmus zur ganzzahligen Division _großer_
Zahlen. Oder anders:

Zu berechnen ist dasjenige Paar (n, r) mit

n*b + r = a (a, b gegeben)

sodass r >= 0 minimal ist.

Es kann angenommen werden, dass a >= b > 0.

(Falls a < b, ist die Lösung einfach (0, a))

Sei m die Verarbeitungsgröße der CPU, l_a die Lànge von a und l_b die
von b. Dann lassen sich a und b mithilfe der Zahlenfolgen (a_i) und
(b_i) wie folgt darstellen:

a = sum(i = 0 .. l_a, m^i * a_i)

b analog.

Dabei gelte stets: a_i < m, b_i < m

Okay, einen simplen Algorithmus habe ich ja schon parat:

r := a
n := 0

while (r >= b) {
n++;
r -= b;
}

Schön einfach, sicherlich. Aber hinter "r -= b" verbirgt sich eine
Bignum-Subtraktion, also mehrere Subtraktionen hintereinander. Und "n++"
ist eine Bignum-Addition (im schlimmsten Fall müsste ich ein Carry durch
alle Blöcke durchschleifen). Mal von der Speicherverwaltung ganz
abgesehen (Wie groß wird n am Ende? Reicht m? m^2? m^4?).

Gut, wir wissen ja schon vorher:

l_n = l_a - l_b
l_r = l_b

r kann nicht größer als b werden, also kann es in genauso vielen Blöcken
gespeichert werden wie b. Und da die Lànge eines Produktes gleich der
Summe der Làngen der Faktoren ist, muss die Lànge eines Faktors wohl die
Differenz aus der Lànge des Produktes und der Lànge des anderen Faktors
sein.

Gut, es liegt nahe, auch die Zahlenfolgen (n_i) und (r_i) zu definieren,
analog zu (a_i), oben.

Berechnen kann ich mit der CPU auf jeden Fall die Matritzen N und R mit

n_ij * b_i + r_ij = a_j

Aber wie komme ich von da weiter?

(Es wàre schön, wenn nicht jedes Element der Matritzen benötigt wurde,
Division ist nàmlich teuer).

Hintergrund ist die kürzlich hier gepostete Frage, wie sicher selbst
kleine RSA-Schlüssel heutzutage noch sind. (Um einen RSA-Modulus zu
faktorisieren, muss man ja mehrere Probedivisionen machen. Wenn es dafür
keinen schnelleren Algorithmus gibt, als den oben geschriebenen, dann
dürfte das auch bei 256 Bit im Modulus immer noch ewig dauern.)

Tschö,
Markus
 

Lesen sie die antworten

#1 mock
02/08/2010 - 17:04 | Warnen spam
On 2 Aug., 13:02, Markus Wichmann wrote:
Hi all,

ich suche nach einem Algorithmus zur ganzzahligen Division _großer_
Zahlen. Oder anders:

Zu berechnen ist dasjenige Paar (n, r) mit

n*b + r = a (a, b gegeben)

sodass r >= 0 minimal ist.



Die Frage scheint mir falsch formuliert zu sein. Bei gegebenen a und b
ist das minimale r = a mod b.

Ähnliche fragen