14813Re: [PrimeNumbers] the start of AKS-algorithm?
- May 1, 2004-----BEGIN PGP SIGNED MESSAGE-----
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.
> 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.
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.2.4 (GNU/Linux)
-----END PGP SIGNATURE-----
- << Previous post in topic Next post in topic >>