Faith E. Fich
Abstract
Modular integer exponentiation (given a, e, and m, compute ae mod m) is a fundamental problem in algebraic complexity for which no efficient parallel algorithm is known. Two closely related problems are modular polynomial exponentiation (given a(x), e, and m(x), compute (a(x))e mod m(x)) and polynomial exponentiation (given a(x), e. and t, compute the coefficient of xt in (a(x))e). It is shown that these latter two problems are in NC2 when a(x) and m(x) are polynomials over a finite field whose characteristic is polynomial in the input size.
- 1 ALT, H. Comparison of arithmetic functions with respect to boolean circuit depth. In Proceedings of the 16th Annual ACM Symposium on Theory of Computing (Washington D.C., Apr. 30-May 2). ACM, New York, 1984, pp. 466-470. Google Scholar
- 2 ANGLUIN, D. Lecture notes on the complexity of some problems in number theory. Tech. Rep. 243. Yale Univ., New Haven, Conn., Aug. 1982.Google Scholar
- 3 BEAME, P. W., COOK, S. A., AND HOOVER, H. J. Log depth circuits for division and related problems. SIAM J. Comput. 15, 4 (Nov. 1986), 994-1003. Google Scholar
- 4 BERLEKAMP, E. R. Factoring polynomials over large finite fields. Math. Comput. 24 (1970), 713-735.Google Scholar
- 5 COOK, S. A. A taxonomy of problems with fast parallel algorithms. Inf. Control 64 (1985), 2-22. Google Scholar
- 6 CULn<, K., AND SALOMAA, A. Ambiguity and decision problems concerning number systems. In Automata, Languages, and Programming, J. Diaz, Ed., vol. 154. In Lecture Notes in Computer Science, Springer-Verlag, New York, 1983, pp. 137-146. Google Scholar
- 7 EBERLY, W. Very fast parallel matrix and polynomial arithmetic. In Proceedings of the 25th Annual IEEE Symposium on Foundations of Computer Science (Singer Island, Fla., Oct. 24-26). IEEE, New York, 1984, pp. 21-30.Google Scholar
- 8 GAREY, M. R., AND JOHNSON, D. S. Computersandlntractability, A GuidetotheTheory of NP-Completeness. Freeman, San Francisco, 1979. Google Scholar
- 9 KARr', R. M. Reducibility among combinatorial problems. In Complexity of Computer Computations, R. E. Miller and J. W. Thatcher, Eds. Plenum Press, New York, 1972, pp. 85-103.Google Scholar
- 10 KUCK, D. J. The Structure of Computers and Computation. vol. 1. Wiley, New York, 1978. Google Scholar
- 11 LmSON, J. D. Elements of Algebra and Algebraic Computing. Addison-Wesley, Reading, Mass., 1981.Google Scholar
- 12 MmLER, G. Riemann's hypothesis and tests for primality. J. Comput.Syst.Sci. 13 (Dec. 1976), 300--317.Google Scholar
- 13 RA}3~r, M. O. Digitalized signatures and public-key functions as intractable as factorization. Tech. Rep. M1T/LCS/TR-212. Massachusetts Institute of Technology, Cambridge, Mass., Jan. 1979. Google Scholar
- 14 RAI3n,~, M. O. Probabilistic algorithm for testing primality. J. Numb. Theory 12 (1980), 128- 138.Google Scholar
- 15 RWEST, R. L., SHAMm, A., AND ADLEMAN, L. A method for obtaining digital signatures and public-key cryptosystems. Commun. ACM 21, 2 (Feb. 1978), 120-126. Google Scholar
- 16 VON ZUR GATrmN, J. Computing powers in parallel. SlAM J. Comput. 16, 5 (Oct. 1987), 930-945. Google Scholar
- 17 YON zurt GATrmN, J. Parallel algorithms for algebraic problems. SlAM J. Comput. 13 (Nov. 1984), 802-824. Google Scholar
- 18 WALLACE, C. A suggestion for a fast multiplier. IEEE Trans. Elec. Comput. EC-13 (1964), 14--17.Google Scholar
Index Terms
- The parallel complexity of exponentiating polynomials over finite fields
Recommendations
Reversed Dickson polynomials over finite fields
Reversed Dickson polynomials over finite fields are obtained from Dickson polynomials D"n(x,a) over finite fields by reversing the roles of the indeterminate x and the parameter a. We study reversed Dickson polynomials with emphasis on their ...
Power sums of polynomials over finite fields and applications
In this brief expository survey, we explain some results and conjectures on various aspects of the study of the sums of integral powers of monic polynomials of a given degree over a finite field. The aspects include non-vanishing criteria, formulas and ...
Explicit factorizations of cyclotomic polynomials over finite fields
Let q be a prime power and let $${\mathbb {F}}_q$$Fq be a finite field with q elements. This paper discusses the explicit factorizations of cyclotomic polynomials over $$\mathbb {F}_q$$Fq. Previously, it has been shown that to obtain the factorizations ...
Reviews
Hale F. Trotter
This paper considers the complexity of parallel computation for modular polynomial exponentiation and polynomial exponentiation: that is, given polynomials a( x) and m( x) over a finite field F, and positive integers e and t, compute a( x) e mod m( x) and m( x) and the coefficient of x t in a( x) e, respectively. The input size of a problem is defined as the maximum of the degrees of a( x) and the number of bits in e. Fitch and Tompa present algorithms for both problems that show them to be in the complexity class NC 2 when the characteristic of F is polynomial in the input size. Note that the restriction on F refers to its characteristic, not its order. Both algorithms use the relation a( x) q = a( x q), where q is the order of F, and break the computation up into pieces corresponding to the digits in the base q representation of e. Raising to the qth power in the modular algorithm is then equivalent to matrix multiplication (as in Berlekamp's factorization algorithm), and operations on different rows can be done in parallel. For the second problem, a( x) e becomes a product of sparse polynomials with rather special structure, and the authors show that the coefficient of x t can be found by a combinatorial calculation that admits parallel computation. The authors provide some background discussion, including a comparison of these results with those for related problems. I recommend the paper to those interested in the subject.
Access critical reviews of Computing literature here
Become a reviewer for Computing Reviews.
Comments