Division und Vergleiche in Hardware

Dieses Thema gehört eigentlich nicht nach dsie, betrifft aber viele Bereiche und somit ist es wahrscheinlich schwierig, DIE passende Gruppe dafür zu finden, jedoch passt de.sci.electronics eher als dsie.

F'up nach dse

Und mir fällt ein Papier einer IEEE-Konferenz (mittlerweile zwei Ewigkeiten her) dazu ein:

Gruß, Mario

"Christof Kluß" schrieb im Newsbeitrag news: snipped-for-privacy@individual.net...

Hallo Christof,

In jedem Mikroprozessor ist ein Hardware-Vergleicher eingebaut, die ALU. Die macht nicht nur A+B oder A-B, sondern sie hat Ausgänge für . Wo sonst kämen die Flags her auf die man Abfragen machen kann wie wenn A>B dann springe nach xyz?

Abfrage auf Gleichheit ist einfach A-B und dann z.B. mit einem OR-Gatter alle Bits des Ergebnises auf 0 vergleichen.

Vielelicht solltest du den Begriff ineffizient genauer spezifizieren.

Parallele Division ist in der Tat schwierig. Deshalb wird das meistens Bit für Bit sequentiell gemacht. Dazwischen gibt es Mischformen die mit Tabellen zu guten Schätzwerten kommen die dann mit wenigen Iterationen zu genauen Ergebnissen führen.

Gruß Helmut

Christof Klu=DF schrieb:

Hallo,

f=FCr ein gen=FCgend kleines n ist das einfach, man programmiert es in ei= n=20 Eprom, f=FCr ein n bis 6 geht das so noch. F=FCr n > 16 wird man an iterativen Methoden nicht vorbei kommen.

Um welches n geht es denn nun?

Bye

Helmut Sennewald schrieb:

Hallo,

wobei ein schneller Addierer f=FCr gro=DFe Wortl=E4ngen so einfach auch w= ieder=20 nicht ist wenn Ripple Carry =FCber die ganze Breite nicht mehr geht.

Bye

Hallo Uwe,

erstmal Danke für eure Antworten.

Uwe Hercksen wrote:

Also konkret geht es um einen Vergleich von Algorithmen für die Modularmultiplikation, die z.B. für RSA benötigt wird, wo dann n im Bereich von 512-2048 Bit liegt.

Nun möchte man also XY mod M berechnen, dazu gibt es z.B. folgende Möglichkeiten

1) klassische Methode, also P = X*Y berechnen und dann den Rest der Division P / M berechnen.

Nachteile: P ist 2n-Bit lang, aber wie sieht hier der Algorithmus konkret aus. Was gibt es noch für Nachteile?

2) Verschränkte Modularmultiplikation P := 0 for i = n-1 to 0 P = 2*P + x_i*Y if (P >= M) then P := P - M if (P >= M) then P := P - M

Nachteile: Vergleiche, die nicht parallel ausgeführt werden können. Für die Vergleiche sind nichtredundaten Addierer nötig? Also der größte Nachteil bei Vergleichen scheint die Laufzeit zu sein.

3) Montgomery Modularmultiplikation (berechnet X*Y*2^-n mod M) P := 0 for i = 0 to n-1 P := P + x_i*Y if (p_0 = 1) P := P + M P := P / 2 if (P >= M) then P := P - M

Hier wird nur am Ende ein Vergleich gebraucht. Außerdem kann man redundanten Addierer benutzen usw.

Nachteile: Vor- und Nachberechnung nötigt

Also im Grunde bräuchte ich mehr Argumente was an dem einen Algorithmus so viel schlechter als am anderen ist. Man könnte da jetzt sicher konkret die Area/Time Komplexität ausrechnen, aber es geht mir eher ums Grundverständnis.

Gruß, Christof

Hallo Christof,

Probier mal Google mit folgendem Text.

division 1024 bit

Da gibt es seitenweise Treffer mit obigem Suchtext.

Gruß Helmut

"Christof Kluß" schrieb im Newsbeitrag news: snipped-for-privacy@individual.net...

Christof Klu=DF schrieb:

Hallo,

bei so grossen n bedeutet das einen f=FCrchterlichen Aufwand f=FCr eine=20 reine Hardwarel=F6sung. Bitserielle Verfahren kommen ja wohl nicht in=20 Frage, aber auch damit w=E4re eine Division sehr aufwendig, aber auch=20 =E4usserst langsam.

Bye