- Group...

If I wanted to prove that some number N is not equal to the form a^b, then wouldn't I have to start by finding the square root, the third root, the fifth root, and every odd-number root ... and not stop until the result was either integral or less than 2?

What would be the maximal order of this type of calculation if N is 'm' digits long?

Bill Bouris, Aurora, IL USA

---------------------------------

Do you Yahoo!?

Win a $20,000 Career Makeover at Yahoo! HotJobs

[Non-text portions of this message have been removed] - -----BEGIN PGP SIGNED MESSAGE-----

Hash: SHA1

On Saturday 01 May 2004 09:46, you wrote:

> Group...

>

> If I wanted to prove that some number N is not equal to the form a^b, then

> wouldn't I have to start by finding the square root, the third root, the

> fifth root, and every odd-number root ... and not stop until the result was

> either integral or less than 2?

Sure, that's a possibility. Not the fastest either, but since you're using

AKS, you don't care the least about speed after all.

> What would be the maximal order of this type of calculation if N is 'm'

> digits long?

Let's call this largest power k. Then we know that N^(1/k) < 2, and we also

know that N ~ 10^m. Thus (10^m)^(1/k) < 2, or 10^(m/k) < 2. Now take

logarithms to base 10 on both sides, you get m/k < 0.3. Thus m < 0.3k, or k >

m/0.3, or finally, k > 3.3m.

Décio

-----BEGIN PGP SIGNATURE-----

Version: GnuPG v1.2.4 (GNU/Linux)

iD8DBQFAk8UoFXvAfvngkOIRApPlAJ9dmZZVwIuhJ1s0wZ0+ww3cUgmvjgCdGRtB

JTgY0kJULWDT+ZlIcyb0w1E=

=bk9N

-----END PGP SIGNATURE----- - On Sat, 1 May 2004, Décio Luiz Gazzoni Filho wrote:
> On Saturday 01 May 2004 09:46, you wrote:

I do believe that the proposed method is the fastest known (except that

> > If I wanted to prove that some number N is not equal to the form a^b, then

> > wouldn't I have to start by finding the square root, the third root, the

> > fifth root, and every odd-number root ... and not stop until the result was

> > either integral or less than 2?

>

> Sure, that's a possibility. Not the fastest either, but since you're using

> AKS, you don't care the least about speed after all.

you only need to check roots of prime order of course). But I am willing

to see arguments otherwise. See "Detecting perfect powers in essentially

linear time" by Daniel Bernstein at http://cr.yp.to/papers/powers-ams.pdf

>

> > What would be the maximal order of this type of calculation if N is 'm'

> > digits long?

>

> Let's call this largest power k. Then we know that N^(1/k) < 2, and we also

> know that N ~ 10^m. Thus (10^m)^(1/k) < 2, or 10^(m/k) < 2. Now take

> logarithms to base 10 on both sides, you get m/k < 0.3. Thus m < 0.3k, or k >

> m/0.3, or finally, k > 3.3m.

>

> Décio

> -----BEGIN PGP SIGNATURE-----

> Version: GnuPG v1.2.4 (GNU/Linux)

>

> iD8DBQFAk8UoFXvAfvngkOIRApPlAJ9dmZZVwIuhJ1s0wZ0+ww3cUgmvjgCdGRtB

> JTgY0kJULWDT+ZlIcyb0w1E=

> =bk9N

> -----END PGP SIGNATURE-----

>

>

>

> Unsubscribe by an email to: primenumbers-unsubscribe@yahoogroups.com

> The Prime Pages : http://www.primepages.org/

>

>

> Yahoo! Groups Links

>

>

>

>

>

> - -----BEGIN PGP SIGNED MESSAGE-----

Hash: SHA1

On Saturday 01 May 2004 12:54, you wrote:

> On Sat, 1 May 2004, Décio Luiz Gazzoni Filho wrote:

> > On Saturday 01 May 2004 09:46, you wrote:

> > > If I wanted to prove that some number N is not equal to the form a^b,

> > > then wouldn't I have to start by finding the square root, the third

> > > root, the fifth root, and every odd-number root ... and not stop until

> > > the result was either integral or less than 2?

> >

> > Sure, that's a possibility. Not the fastest either, but since you're

> > using AKS, you don't care the least about speed after all.

>

> I do believe that the proposed method is the fastest known (except that

> you only need to check roots of prime order of course). But I am willing

> to see arguments otherwise. See "Detecting perfect powers in essentially

> linear time" by Daniel Bernstein at http://cr.yp.to/papers/powers-ams.pdf

Asymptotically, perhaps. However, there are faster methods in practice. For

instance, to detect whether an integer is a square, one can check whether the

residue class it lies in, modulo a few primes, is a quadratic residue modulo

that prime. I believe the same can be done for arbitrary powers n, so long as

n | phi(p) for a given prime p, so that there are elements of order n in

Z/pZ.

Décio

-----BEGIN PGP SIGNATURE-----

Version: GnuPG v1.2.4 (GNU/Linux)

iD8DBQFAlAKPFXvAfvngkOIRAn3oAJ49hes5o3TmUfJ7qhGkKmwPV7H2XgCfRHRs

WJip9rI9hPyDr9+/qgSukqg=

=Xp3u

-----END PGP SIGNATURE----- > If I wanted to prove that some number N is not equal to the

Correct as far as it goes, though yuou can optimize by only

> form a^b, then wouldn't I have to start by finding the square

> root, the third root, the fifth root, and every odd-number

> root ... and not stop until the result was either integral or

> less than 2?

testing primeth roots because if you've already tested for

a p-th root and the test failed, you already know that it

isn't a pq-th root.

> What would be the maximal order of this type of calculation

m *log(10)/log(2).

> if N is 'm' digits long?

Paul