CIRCUITS FOR MODULAR ARITHMETIC BASED ON THE COMPLEMENTATION OF CONTINUED FRACTIONS

摘要

Verfahren zur Durchführung der modularen Multiplikation RN[ab] von ganzen Zahlen bezüglich eines Modulus N und der modularen Multiplikation RN(X)[a(x)b(x)] von Polynomen bezüglich eines Moduluspolynoms N = N(x), wobei die ganzen Zahlen a < N, b < N, und N bezüglich einer Radix p dargestellt sind, während die Polynome a = a(x) mit Grad(a(x)) < Grad(N(x)), b = b(x) mit Grad(b(x)) < Grad(N(x)) und N(x) bezüglich Potenzen der freien Variablen x und mit Koeffizienten aus einem ganzzahligen Restklassenring ZM dargestellt sind, umfassend die Schritte: - Berechnung eines ergänzten Produktkettenbruchs c = (ab+jN)/t durch Ergänzungen von einzelnen Zählern eines als Kettenbruch dargestellten Produktbruchs (ab)/t, wobei im ersten Fall der Berechnung mit ganzen Zahlen, c und j ebenfalls ganze Zahlen sind sowie t = p?, während im zweiten Fall der Berechnung mit Polynomen, c = c(x) und j = j(x) ebenfalls Polynome mit Koeffizienten aus ZM sind sowie t = t(x) =x? und wobei in beiden Fällen K eine ganze Zahl größer oder gleich der Länge ?p(a) des im Kettenbruch zerlegten Operanden a ist - Berechnung eines zweiten ergänzten Produktkettenbruchs r = (cd+kN)/t aus dem vorab berechneten modularen Rest d = RN[t2] und dem Ergebnis c der im oben genannten Schritt durchgeführten Rechnung, wobei im ersten Fall r, k und d ganze Zahlen sind und im zweiten Fall r = r(x) = RN(x)[a(x)b(x)], k = k(x) und d = d(x) Polynome mit Koeffizienten aus ZM sind.