The base of the logarithm in AKS algorithms

[Sairam]

Thanks to everybody who replied. jasonp and cheesehead, thank you for your convincing explanations.
cheesehead...i am not ignoring your suggestions. I just found a copy of the book you suggested in the library.

[R.D. Silverman]

Originally Posted by Batalov

1. AKS test is not a practical test (esp. for 10-digit numbers), is it? /Wiki/
2. By simply changing the base of the log you 'make it faster', but how would you know if it actually remains valid?

It does NOT remain valid.

[science_man_88]

Originally Posted by R.D. Silverman

It does NOT remain valid.

could you ever compensate for it using the conversion posted above.

[R.D. Silverman]

Originally Posted by Sairam

When I change the base from 2 to e in the above algorithm then the computational time taken reduces. I understand the asymptotic notation based on jasonp's reply (thank you), but I was also wondering if we are allowed to change the base like that for computational purposes.

You are NOT allowed to change the base.

For example, the average time taken to test primality for 10 digit numbers increases from 8.9 minutes (natural log) to 1.2 hours (base 2). Terribly sorry if I sound stupid but I don't have much idea about algorithms and their complexities and so would really appreciate a good explanation from someone.

"I don't have much idea about algorithms"

This is easily corrected. Go study. I can recommend some good books.

Allow me to ask:

Why are you bothering with an algorithm that you don't understand?
Go read the original paper.

I can explain why one can't change the base, but you won't understand it.
By your own admission, you lack the math and I can't give a semester
course in group theory here.

You need to take a course in both group theory and number theory (or
self-study equivalent) to understand what is going on. An additional
course in algorithms would not hurt.

Although the following does not explain WHY, the following sentence
explains why changing the logarithm base doesn't work:

You need to prove the congruence is true for SUFFICIENTLY MANY
DIFFERENT values of a. (and they do not have to be sequential;
they are chosen that way for convenience)

Before you ask why, allow me to ask if you know what the multiplicative
group of units of Z/NZ is??

[Sairam]

Honestly, I don't know the answer to the question you posted.

All I know from the paper AKS published is r and a must be chosen carefully since otherwise even some composite numbers satisfy the polynomial congruence relation for some values of a and r and so could be identified as prime. And yes, I thought the values of a have to be sequential for the polynomial test

So is this a forum only for people who know everything? From my perspective, it was a genuine question and which was why I posted it in this forum looking for an answer. I apologize if my ignorance offended some brilliant mathematicians out there.

[CRGreathouse]

Originally Posted by Sairam

I apologize if my ignorance offended some brilliant mathematicians out there.

No, just one. Silverman is like this to everyone, consider it your initiation.

[R.D. Silverman]

Originally Posted by Sairam

Honestly, I don't know the answer to the question you posted.

All I know from the paper AKS published is r and a must be chosen carefully since otherwise even some composite numbers satisfy the polynomial congruence relation for some values of a and r and so could be identified as prime. And yes, I thought the values of a have to be sequential for the polynomial test

So is this a forum only for people who know everything? From my perspective, it was a genuine question and which was why I posted it in this forum looking for an answer. I apologize if my ignorance offended some brilliant mathematicians out there.

Why is it that when I suggest that someone needs to learn some basic
undergrad level math before he/she can understand something, they
respond with "only for people who know everything"?

One does not need to know everything. But one does need to
know the basics. Why do you jump to the extreme??


I was not offended. Where did you get that idea? And my final question
from the earlier post was intended to indicate the kind of mathematics
one needs to know to understand why the number of iterations
can not be changed. If you had answered "yes" to that question, then
we could have had a discussion about how/why one needs to bound the
size of the unit group.

If one is following an algorithm as one follows a cookbook recipe, one
should not be asking the equivalent of "why can't I change the requirement
for 2 cups of flour to just 1 cup"? The answer should be obvious.
If one changes the recipe, the result will not be good.

If the people who invented the algorithm could have made it faster by
reducing the number of iterations don't you think that they would have
done so? If the answer to this is "I was not aware that changing the
logarithm base changed the number of iterations", then a further reply would
be that you are not even ready to take the basic undergrad level courses
one needs because you have not yet mastered high-school level math.

I'm not trying to be mean. I am telling you the reality. This subject has
prerequisites.

[R.D. Silverman]

Originally Posted by CRGreathouse

No, just one. Silverman is like this to everyone, consider it your initiation.

"like this"??? Like what? I told someone that they needed to learn
some basic undergrad math before trying to understand a (moderately)
advanced subject. I even suggested which courses they should take.

What was wrong with what I said?

[xilman]

Originally Posted by R.D. Silverman

"like this"??? Like what? I told someone that they needed to learn
some basic undergrad math before trying to understand a (moderately)
advanced subject. I even suggested which courses they should take.

What was wrong with what I said?

I saw nothing wrong with what you said.

However, as far as you advising a questioner to learn some pre-requisites and giving suggestions as to where they may be found, you are like that to (most) everyone.

IOW, calm down becauwe no-one is accusing you of anything untoward.

Paul

[CRGreathouse]

Originally Posted by R.D. Silverman

What was wrong with what I said?

I didn't say anything was wrong, I just advised Sairam not to take your comments personally. (Most people would otherwise misinterpret what you said.)

[imwithid]

Originally Posted by R.D. Silverman

Why are you bothering with an algorithm that you don't understand?

Perhaps this gets to the root of it. For the sake of argument, it may frustrate you that one who knows nothing. little or insufficiently much about a given subject matter may wish to take it upon themselves to attempt to solve, modify or simply experiment with a given problem. That is their privilege and for the sake of civil discussion there are implicit rules when rightly discounting or critiquing one's ideas.

That one concedes lacking the requisite knowledge, yet is condescended upon by another by assuming one's level of ignorance or skill despite your expectations of this forum is what may lead some to think that you are being "mean" (tantamount to tripping one who is lame, that is, unless one is intentionally being a pest, whereby a general consensus may be informally met). One need not have to explain this to one who knows more/better. This is not an invitation to any flame war. I only mention this as I suspect that it may be more a general sentiment.