Deciding squarefree numbers

Jushi · 2006-03-29, 19:57

I was wondering if there exists an algorithm which can decide whether a given number N is squarefree (i.e. N is not the multiple of a square). Obviously, factoring N gives the answer, but can it be done faster?

There is only one thing I can think of: when doing trial division, you only need to trial divide up to N^(1/3), as opposed to N^(1/2). This is because a number N with no factors less than N^(1/3) can have at most 2 factors. So, if N is not a square (this is easily checked), it is squarefree.

ColdFury · 2006-03-29, 21:05

There's no known polynomial-time algorithm.

Jushi · 2006-03-30, 10:53

And is there any algorithm known which is faster than factoring?

R.D. Silverman · 2006-03-30, 12:50

Quote:

Originally Posted by Jushi

And is there any algorithm known which is faster than factoring?

In function rings, yes. In number rings, no.

Jushi · 2006-03-30, 13:56

Quote:

Originally Posted by R.D. Silverman

In function rings, yes. In number rings, no.

Thanks. Unfortunately, this is the answer that I expected.

2006-03-29, 19:57	#1
Jushi Sep 2005 UGent 111100₂ Posts	Deciding squarefree numbers I was wondering if there exists an algorithm which can decide whether a given number N is squarefree (i.e. N is not the multiple of a square). Obviously, factoring N gives the answer, but can it be done faster? There is only one thing I can think of: when doing trial division, you only need to trial divide up to N^(1/3), as opposed to N^(1/2). This is because a number N with no factors less than N^(1/3) can have at most 2 factors. So, if N is not a square (this is easily checked), it is squarefree.

Similar Threads
Thread	Thread Starter	Forum	Replies	Last Post
Carmichael numbers and Devaraj numbers	devarajkandadai	Number Theory Discussion Group	0	2017-07-09 05:07
What's the algorithm for deciding in which base to express the post count?	jasong	Forum Feedback	9	2016-11-08 02:22
Need help deciding between Athlon II X4 620 and i5	garo	Hardware	164	2010-01-30 18:59
6 digit numbers and the mersenne numbers	henryzz	Math	2	2008-04-29 02:05
LLT numbers, linkd with Mersenne and Fermat numbers	T.Rex	Math	4	2005-05-07 08:25

2006-03-29, 21:05	#2
ColdFury Aug 2002 101000000₂ Posts	There's no known polynomial-time algorithm.

2006-03-30, 10:53	#3
Jushi Sep 2005 UGent 60₁₀ Posts	And is there any algorithm known which is faster than factoring?