A low complexity probabilistic test for integer multiplication. (English) Zbl 1196.68104
Summary: A probabilistic test for the equality \(a=bc\) for given \(n\)-bit integers \(a,b,c\) is designed within complexity \(n(\log \log n)\exp \{O(\log ^{*}n)\}\).
MSC:
| 68Q25 | Analysis of algorithms and problem complexity |
| 68Q87 | Probability in computer science (algorithm analysis, random structures, phase transitions, etc.) |
References:
| [1] | Aho, A.; Hopcroft, J.; Ullman, J., Design and Analysis of Computer Algorithms (1974), Addison-Wesley · Zbl 0326.68005 |
| [2] | M. Blum, S. Kannan, Designing programs that check their work, in: Proc. ACM Symp. Th. Comput. 1989, pp. 86-97; M. Blum, S. Kannan, Designing programs that check their work, in: Proc. ACM Symp. Th. Comput. 1989, pp. 86-97 · Zbl 0886.68046 |
| [3] | Freivalds, R., Fast probabilistic algorithms, (Proc. Symp. Math. Found. Comput. Sci. (1979), Springer), 57-69 · Zbl 0408.68035 |
| [4] | M. Fürer, Faster integer multiplication, in: Proc. ACM Symp. Th. Comput. 2007, pp 57-66; M. Fürer, Faster integer multiplication, in: Proc. ACM Symp. Th. Comput. 2007, pp 57-66 · Zbl 1179.68198 |
| [5] | Ivić, A.; Tenenbaum, G., Local densities over integers free of large prime factors, Quart. J. Math. (Oxford) (2), 37, 401-417 (1986) · Zbl 0604.10024 |
| [6] | Schönhage, A.; Strassen, V., Schnelle Multiplikation grosser Zahlen, Computing, 7, 281-292 (1971) · Zbl 0223.68007 |
| [7] | Tenenbaum, G., Introduction à la théorie analytique et probabiliste des nombres; Collection Échelles (2008), Berlin: Berlin Paris |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
