
Re: Square free numbers
Posted:
May 13, 2002 3:09 AM


> How to determine if a number is square free without factoring it?
No feasible (polynomial time) algorithm is currently known for recognizing squarefree integers or for computing the squarefree part of an integer. In fact it may be the case that this problem is no easier than the general problem of integer factorization.
The latter problem is important because one of the main tasks of computational algebraic number theory reduces to it (in deterministic polynomial time). Namely the problem of computing the ring of integers of an algebraic number field depends upon the squarefree decomposition of the polynomial discriminant when computing an integral basis, e.g. [2] S.7.3 p.429 or [1] This is due to Chistov [0]. See also Problems 7,8, p.9 in [3], which lists 36 open problems in number theoretic complexity.
Bill Dubuque
[0] A. L. Chistov. The complexity of constructing the ring of integers of a global field. Dokl. Akad. Nauk. SSSR, 306:10631067, 1989. English Translation: Soviet Math. Dokl., 39:597600, 1989. 90g:11170 http://citeseer.nj.nec.com/context/464298/0
[1] Lenstra, H. W., Jr. Algorithms in algebraic number theory. Bull. Amer. Math. Soc. (N.S.) 26 (1992), no. 2, 211244. 93g:11131 http://www.ams.org/bull/pre1996data/1992262/lenstra.pdf http://www.ams.org/bull/pre1996data/1992262/Lenstra
[2] Pohst, M.; Zassenhaus, H. Algorithmic algebraic number theory. Cambridge University Press, Cambridge, 1997.
[3] Adleman, Leonard M.; McCurley, Kevin S. Open problems in numbertheoretic complexity. II. Algorithmic number theory (Ithaca, NY, 1994), 291322, Lecture Notes in Comput. Sci., 877, Springer, Berlin, 1994. 95m:11142 http://citeseer.nj.nec.com/168265.html

