A heuristic irreducibility test for univariate polynomials. (English) Zbl 0748.12010
Let \(f(x)\) be a polynomial: if \(f(a)\), for an \(a\) sufficiently far from the zeros of \(f\), is prime then \(f\) is irreducible. It is shown how to choose \(a\), and how large values of \(f(a)\) may be avoided by a change of variable. Timings are given for comparison with the Berlekamp-Hensel procedure as implemented in MACSYMA, MAPLE, and REDUCE.
The possibility of factorizing \(f\) by factorizing \(f(a)\) is discussed. If \(f\) has many factors then choosing the right combination of factors of \(f(a)\) can be difficult.
The possibility of factorizing \(f\) by factorizing \(f(a)\) is discussed. If \(f\) has many factors then choosing the right combination of factors of \(f(a)\) can be difficult.
Reviewer: H.J.Godwin (Egham)
MSC:
| 12Y05 | Computational aspects of field theory and polynomials (MSC2010) |
| 11Y05 | Factorization |
| 11C08 | Polynomials in number theory |
| 11Y11 | Primality |
| 68W30 | Symbolic computation and algebraic computation |
References:
| [1] | Adleman, L. M.; Odlyzko, A. M., Irreducibility testing and factorization of polynomials, Maths. Comput, 41, 699-709 (1983) · Zbl 0527.12002 |
| [2] | Berlekamp, E. R., Factoring polynomials over finite fields, Bell System Technical Journal, 46, 1853-1859 (1967) · Zbl 0166.04901 |
| [3] | Berlekamp, E. R., Factoring polynomials over large finite fields, Maths. Comput, 24, 713-715 (1970) · Zbl 0247.12014 |
| [4] | Brown, W. S.; Graham, R. L., An irreducibility criterion for polynomials over the integers, Am. math. Mon, 76, 1055-1059 (1969) · Zbl 0179.34602 |
| [5] | Cantor, D. G.; Zassenhaus, H., A new algorithm for factoring polynomials over a finite field, Maths. Comput, 36, 587-592 (1981) · Zbl 0493.12024 |
| [6] | Char, B. W.; Geddes, K. O.; Gentleman, W. M.; Gonnet, G. H., The design of Maple: a compact, portable, and powerful computer algebra system, (Proceedings of Eurocal ’83. Proceedings of Eurocal ’83, Lecture Notes in Computer Science, 162 (1983)), 101-115 |
| [7] | Char, B. W.; Geddes, K. O.; Gonnet, G. H., GCDHEU: heuristic polynomial GCD algorithm based on integer GCD computation, (Proceedings of Eurosam ’84. Proceedings of Eurosam ’84, Lecture Notes in Computer Science, 174 (1984)), 285-296 · Zbl 0584.68057 |
| [8] | Hearn, A. C., (REDUCE User’s Manual (1983), The Rand Corporation: The Rand Corporation Santa Monica, CA 90406) |
| [9] | Kaltofen, E.; Musser, D. R.; Saunders, D. B., A generalized class of polynomials that are hard to factor, SIAM J. Comput, 473-483 (1983) · Zbl 0529.68018 |
| [10] | Kaltofen, E., On the complexity of finding short vectors in integer lattices, (Proceedings of Eurocal ’83. Proceedings of Eurocal ’83, Lecture Notes in Computer Science, 162 (1983)), 236-244 · Zbl 0546.68022 |
| [11] | Kannan, R.; Lenstra, A. K.; Lovaśz, L., Polynomial factorization and nonrandonmess of bits of algebraic and some transcendental numbers, (Proceedings of the Sixteenth Annual ACM Symposium on Theory of Computing (1984)), 191-200 |
| [12] | Knuth, D. E., (The Art of Computer Programming Vol. 2: Seminumerical Algorithms (1981), Addison-Wesley: Addison-Wesley Reading, Massachusetts), 420-441 · Zbl 0477.65002 |
| [13] | Lenstra, A. K.; Lenstra, H. W.; Lovasz, L., Factoring polynomials with rational coefficients, Math. Ann, 261, 515-534 (1982) · Zbl 0488.12001 |
| [14] | Miller, G., Riemann’s hypotheses, and test for primality, J. Comput. Syst. Sci, 13, 300-317 (1976) · Zbl 0349.68025 |
| [15] | Mignotte, N., An inequality about factors of polynomials, Maths. Comput, 28, 1153-1157 (1974) · Zbl 0299.12101 |
| [16] | Moses, J., Macsyma: The 5th Year, (Proceedings of the Eurosam ’74 Conference (1974)) |
| [17] | Musser, D., On the efficiency of a polynomial irreducibility test, JACM, 25, 271-282 (1978) · Zbl 0372.68014 |
| [18] | Rabin, M. O., Probabilistic algorithm for testing primality, J. Number Theory, 12, 128-138 (1980) · Zbl 0426.10006 |
| [19] | Schonhage, S., Factorization of univariate polynomials by diophantine approximation and an improved basis reduction algorithm, (Proceedings ICALP ’84 SLNCS, 172 (1984)), 436-447 · Zbl 0569.68030 |
| [20] | Shaw, A. M.; Traub, J. F., On the number of multiplications for evaluation of a polynomial and some of its derivatives, JACM, 21, 161-167 (1974) · Zbl 0271.68040 |
| [21] | Solovay, R.; Strassen, V., A fast Monte-Carlo test for primality, SIAM J. Comput, 6, 84-85 (1977) · Zbl 0345.10002 |
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.
