Browse Groups

• 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
Message 1 of 5 , May 1, 2004
View Source
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]
• ... Hash: SHA1 ... 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. ... Let s
Message 1 of 5 , May 1, 2004
View Source
-----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-----
• ... 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
Message 1 of 5 , May 1, 2004
View Source
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

>
> > 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/
>
>
>
>
>
>
>
>
• ... Hash: SHA1 ... Asymptotically, perhaps. However, there are faster methods in practice. For instance, to detect whether an integer is a square, one can
Message 1 of 5 , May 1, 2004
View Source
-----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-----
• ... Correct as far as it goes, though yuou can optimize by only testing primeth roots because if you ve already tested for a p-th root and the test failed, you
Message 1 of 5 , May 2, 2004
View Source
> 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?

Correct as far as it goes, though yuou can optimize by only
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
> if N is 'm' digits long?

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

Paul
Your message has been successfully submitted and would be delivered to recipients shortly.
• Changes have not been saved
Press OK to abandon changes or Cancel to continue editing
• Your browser is not supported
Kindly note that Groups does not support 7.0 or earlier versions of Internet Explorer. We recommend upgrading to the latest Internet Explorer, Google Chrome, or Firefox. If you are using IE 9 or later, make sure you turn off Compatibility View.