Search All of the Math Forum:

Views expressed in these public forums are not endorsed by NCTM or The Math Forum.

Notice: We are no longer accepting new posts, but the forums will continue to be readable.

Topic: Square free numbers
Replies: 25   Last Post: May 13, 2002 4:04 PM

 Messages: [ Previous | Next ]
 Bill Dubuque Posts: 444 Registered: 12/4/04
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 square-free 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:1063--1067, 1989.
English Translation: Soviet Math. Dokl., 39:597--600, 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, 211--244. 93g:11131
http://www.ams.org/bull/pre-1996-data/199226-2/lenstra.pdf
http://www.ams.org/bull/pre-1996-data/199226-2/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 number-theoretic complexity. II.
Algorithmic number theory (Ithaca, NY, 1994), 291--322,
Lecture Notes in Comput. Sci., 877, Springer, Berlin, 1994. 95m:11142
http://citeseer.nj.nec.com/168265.html

Date Subject Author
5/8/02 Justin
5/8/02 Phil Carmody
5/8/02 Jean-Luc Cooke
5/8/02 magidin@math.berkeley.edu
5/8/02 Jean-Luc Cooke
5/8/02 Nicol So
5/8/02 Phil Carmody
5/9/02 Phil Carmody
5/8/02 Scott Contini
5/9/02 Phil Carmody
5/8/02 David Hopwood
5/9/02 Phil Carmody
5/9/02 Anton Stiglic
5/9/02 Phil Carmody
5/9/02 Nicol So
5/10/02 Phil Carmody
5/9/02 Anton Stiglic
5/10/02 Phil Carmody
5/10/02 Anton Stiglic
5/9/02 Jean-Luc Cooke
5/10/02 Phil Carmody
5/8/02 Anthony Potts
5/10/02 Joe Number
5/10/02 Bob Marlow
5/13/02 Anthony Potts
5/13/02 Bill Dubuque