The base of the logarithm in AKS algorithms - Page 3

R.D. Silverman · 2011-04-30, 12:46

Quote:

Originally Posted by imwithid

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.

Forgive me for trying to impose or expect some minimal standards of
scholarship. Part of the problem with education in the U.S. is that teachers
do not demand excellence or diligence from students.

I do demand diligence. I expect that students should be willing to put
in the necessary background study and preparation before discussing
a subject. (esp. a technical one such as mathematics)

fivemack · 2011-04-30, 16:23

You may demand diligence if you want, but the atmosphere in this forum is such that you're unlikely to get it - much more likely to get rewarding results in that direction at Terence Tao or Tim Gowers' forums, http://polymathprojects.org/ or even MathOverflow. And the style in which you demand it isn't one whereby you're likely to get it.

Continuing in an ornery fashion to demand things - even praiseworthy things - which you haven't got the last eighteen times rapidly shades into incivility.

cheesehead · 2011-04-30, 20:02

Quote:

Originally Posted by R.D. Silverman

Forgive me for trying to impose or expect some minimal standards of scholarship. Part of the problem with education in the U.S. is that teachers do not demand excellence or diligence from students.

(* sigh *) Once again:

This is not one of your classrooms, Mr. Silverman. Your imposition and/or expectation of minimal standards is inappropriate here.

CRGreathouse · 2011-04-30, 21:07

Quote:

Originally Posted by cheesehead

This is not one of your classrooms

FWIW I think he's in industry, not academia.

cheesehead · 2011-05-01, 05:10

Quote:

Originally Posted by CRGreathouse

FWIW I think he's in industry, not academia.

1) He used the terms "standards of scholarship", "education", "teachers" and "students".

2) I was once an instructor in the Training Department of a computer vendor. I worked in a "classroom", in addition to my personal cubicle elsewhere. :-)

CRGreathouse · 2011-05-01, 16:23

No disagreement, just bringing up a potentially relevant point.

cheesehead · 2011-05-02, 18:16

Quote:

Originally Posted by cheesehead

2) I was once an instructor in the Training Department of a computer vendor. I worked in a "classroom", in addition to my personal cubicle elsewhere. :-)

However, that terminology might have been biased: all the other instructors were former school teachers.

Maybeso · 2011-06-04, 09:53

To get back to the question ... here's a very non-technical description of another consequence of fiddling with r.

Yes, reducing the minimum required r will reduce how may values of a you think you have to try. But it also reduces the width of your coefficient vector.

AKS calculates the nth row of Pascals triangle, but wraps the n terms into r terms with the modulo. This would be okay if, for n = p*q, only term p and term q were non-zero modulo n. But every p-th term = k*q, and every q-th term = j*p. And in a crude sense you're stacking n/r terms into each term, and with the wrong a you'll get h*p*q == 0 mod n. Yes, I know mathematically this is gibberish, probably in several ways at the same time.

I tried it with n = mersenne numbers, starting with a big r. So steps 1 and 3 are very fast. It worked perfectly on my entire test range, but as I reduced r the larger n gave false primality more often. (Related among other things to r mod p and q mod r.) So sometimes a slightly smaller r would work again, but the overall failure rate went up.

R.D. Silverman · 2011-06-04, 10:58

Quote:

Originally Posted by Maybeso

To get back to the question ... here's a very non-technical description of another consequence of fiddling with r.

Yes, reducing the minimum required r will reduce how may values of a you think you have to try. But it also reduces the width of your coefficient vector.

AKS calculates the nth row of Pascals triangle, but wraps the n terms into r terms with the modulo. This would be okay if, for n = p*q, only term p and term q were non-zero modulo n. But every p-th term = k*q, and every q-th term = j*p. And in a crude sense you're stacking n/r terms into each term, and with the wrong a you'll get h*p*q == 0 mod n. Yes, I know mathematically this is gibberish, probably in several ways at the same time.

It is. So I ask: what compels you to post it? Especially since you
recognize that it is gibberish?

cheesehead · 2011-06-04, 16:43

Quote:

Originally Posted by R.D. Silverman

It is. So I ask: what compels you to post it? Especially since you recognize that it is gibberish?

Perhaps Maybeso is trying to learn something via the method of expressing what he thinks he understands (fully knowing that it's imperfect, and not pretending otherwise), then seeing what constructive corrections the more knowledgeable folks may offer.

His goal is to increase his knowledge and understanding. How did you help him do that (keeping in mind that he already knows his understanding is flawed, so telling him that contributes nothing)? Answer: naught, but you did reassert your own mathematics superiority (on the off-chance that we'd forgotten about that).

Have a nice day! :-)

- - -

How're you coming with that petition drive to add participation prerequisites to this Math subforum?

LaurV · 2011-06-11, 15:19

why not use a larger base of logarithm? yeah, why not?

based on the same idea:

laurv's aks algorithm to check if a number is prime:

step1: trial division of n with all numbers smaller then square root of n.
if any factor is found, output "composite"
if no factor is found, output "prime"

but wait! this algorithm is bloody slow! why take square root of n, and not take cubical root of n? why not take $\sqrt{n}$ of a higher order?

well, because in this case maybe you will correctly find some primes having quite small factors, but eventually you will run in a number having just two factors close to $\sqrt{n}$ (like 323=17*19, for which the cubical root is about 7) and your algorithm will say that is prime...

2011-04-30, 16:23	#24
fivemack (loop (#_fork)) Feb 2006 Cambridge, England 7²·131 Posts	You may demand diligence if you want, but the atmosphere in this forum is such that you're unlikely to get it - much more likely to get rewarding results in that direction at Terence Tao or Tim Gowers' forums, http://polymathprojects.org/ or even MathOverflow. And the style in which you demand it isn't one whereby you're likely to get it. Continuing in an ornery fashion to demand things - even praiseworthy things - which you haven't got the last eighteen times rapidly shades into incivility. Last fiddled with by fivemack on 2011-04-30 at 16:25

Similar Threads
Thread	Thread Starter	Forum	Replies	Last Post
Help with discrete logarithm	pinnn	Information & Answers	43	2021-03-18 15:40
multiplication and logarithm	bhelmes	Math	4	2016-10-06 13:33
Discrete logarithm software	Unregistered	Information & Answers	39	2012-04-27 20:08
calculate logarithm base 2 of number very close 1	thehealer	Other Mathematical Topics	9	2011-04-20 14:02
Base-6 speed for prime testing vs. base-2	jasong	Conjectures 'R Us	36	2010-08-03 06:25

2011-05-01, 16:23	#28
CRGreathouse Aug 2006 13533₈ Posts	No disagreement, just bringing up a potentially relevant point.

2011-06-04, 09:53	#30
Maybeso Aug 2002 Portland, OR USA 422₈ Posts	To get back to the question ... here's a very non-technical description of another consequence of fiddling with r. Yes, reducing the minimum required r will reduce how may values of a you think you have to try. But it also reduces the width of your coefficient vector. AKS calculates the nth row of Pascals triangle, but wraps the n terms into r terms with the modulo. This would be okay if, for n = pq, only term p and term q were non-zero modulo n. But every p-th term = kq, and every q-th term = jp. And in a crude sense you're stacking n/r terms into each term, and with the wrong a you'll get hp*q == 0 mod n. Yes, I know mathematically this is gibberish, probably in several ways at the same time. I tried it with n = mersenne numbers, starting with a big r. So steps 1 and 3 are very fast. It worked perfectly on my entire test range, but as I reduced r the larger n gave false primality more often. (Related among other things to r mod p and q mod r.) So sometimes a slightly smaller r would work again, but the overall failure rate went up.

2011-06-11, 15:19	#33
LaurV Romulan Interpreter Jun 2011 Thailand 22613₈ Posts	why not use a larger base of logarithm? yeah, why not? based on the same idea: laurv's aks algorithm to check if a number is prime: step1: trial division of n with all numbers smaller then square root of n. if any factor is found, output "composite" if no factor is found, output "prime" but wait! this algorithm is bloody slow! why take square root of n, and not take cubical root of n? why not take $\sqrt{n}$ of a higher order? well, because in this case maybe you will correctly find some primes having quite small factors, but eventually you will run in a number having just two factors close to $\sqrt{n}$ (like 323=17*19, for which the cubical root is about 7) and your algorithm will say that is prime...