• Multiplikationen von n-stelligen Zahlen.
  • Berechnung von (1+x)1/kmit einer Fehlergrenze von 10 -n.
  • Approximative Faktorisierung eines Polynoms m-ten Grades innerhalb eines Fehlers 10 -n.

    Der Beweis ist konstruktiv und reduziert die approximative Faktorisierung von Polynomen auf die Multiplikation von immens großen Zahlen. 

    Dies macht deutlich, daß die Geschwindigkeit der meisten klassischen numerischen Methoden bei geforderter großer Genauigkeit von der Schnelligkeit der Multiplikationen riesiger Zahlen abhängt. Mit anderen Worten: Die beschriebenen neuen Methoden, die vor 10 bis 15 Jahren noch exotisch anmuteten, sind in der Lage, die Geschwindigkeit von Computerprogrammen in Computeralgebrasystemen und bei numerischen Berechnungen entscheidend zu verbessern.

Literatur

[1] K.-H. Indlekofer, A. Járai, Largest known twin primes, Math. Comp. 65 (1996), no. 213, 427-428.

[2] K.-H. Indlekofer, A. Járai, Largest known twin primes and Sophie Germain primes, Math. Comp. (1998).

[3] R. L. Rivest, A. Shamir, L. M. Adleman, A method for obtaining digital signatures and public-key cryptosystems, Comm. ACM 21 (1978), 120-126.

[4] A. Schönhage, The fundamental theorem of algebra in terms of computational complexity- Preliminary report, Univ. Tübingen, 1982, 1-74.

[5] A. Schönhage, A. F. W. Grotefeld, E. Vetter, Fast Algorithms: A Multitape Turing Machine Implementation, B. I. Wissenschaftsverlag, Mannheim, 1994.

[6] A. Schönhage, V. Strassen, Schnelle Multiplikation großer Zahlen, Computing 7 (1971), 281-292.

linkshome