Fastest Primality Tests

[philmoore]

Originally Posted by flouran

Isn't the Miller-Rabin primality test faster than L-L? L-L has a run-time bit-complexity of for n bits. Miller-Rabin, on the other hand, according to http://en.wikipedia.org/wiki/Miller-...primality_test, has a bit-complexity (or arithmetic complexity? correct me if I'm wrong) "using modular exponentiation by repeated squaring, the running time of this algorithm is O(k × log3 n), where k is the number of different values of a we test; thus this is an efficient, polynomial-time algorithm. FFT-based multiplication can push the running time down to O(k × log2 n log log n log log log n) = Õ(k × log2 n)". Isn't Miller-Rabin way faster, and in fact, almost as fast as Shor's algorithm which has a run-time bit-complexity of ?

For the L-L complexity cited at the beginning of the post, n is the exponent of the Mersenne number. For the Miller-Rabin complexity cited from Wikipedia, n is the number itself. Thus both tests have essentially the same complexity, except that the Miller-Rabin test is done k times as opposed to once. On the other hand, if one assumes the Generalized Riemann Hypothesis, making the Miller-Rabin test determinate requires 2(log n)^2 bases, so it is essentially of order degree 4 + epsilon in the number of digits; L-L is degree 2 + epsilon.

[ewmayer]

Originally Posted by ewmayer

"I've run out of pseudointellectual musings on primality testing..."

"...so let me try some pseudointellectual musings on the internet-as-linear-algebra-problem:"

Originally Posted by flouran

Besides, Google is the epitome of cross-referencing (it is a matrix of eigenvalue 2.7 billion if not more). LOL. But I'll check it out. thanks.

LOL, indeed - you wouldn't perchance be contemplating a liberal-arts major, would you, "my ill-conditioned friend"?

[Fluoran rushes off to check the Wikipedia page on "eigenvalue" and prepares his huffy "I was only joking ... it was, like, a metaphor or something, not a homonym as you seem to think, ewmayer" riposte.]

[henryzz]

Originally Posted by R.D. Silverman

Then go read a BOOK (not Wikipaedia which is a very innacurate and
unreliable source)

Riesel's book is excellent. So is Crandall & Pomerance.

Or else, ask me.....

i something on wikipedia is incorrect then correct it
also would you count mersennewiki as a bad source
http://www.mersennewiki.org/index.ph...primality_test

[flouran]

Originally Posted by R.D. Silverman

Gibberish.

Read Paul Garret's "Cryptographic Primitives", and you'll see that I am right in saying, "Monte-Carlo algorithm can either be yes-biased or no-biased, and thus 50% of its answers are certain." In fact, I'll be more exact, read pg. 8 Section 2.2 entitled, "Probabilistic Algorithms".

[ewmayer]

Now take a look at this 'ere parrot - lovely plumage. Although I prefer the Norwegian Blue meself, strictly personal-wise speakin'...

[cheesehead]

Originally Posted by flouran

It's a waste of time, and with all due respect, shut up.

If you'd actually googled "Norwegian Blue parrot:", you'd have found that one of the first links was to your beloved Wikipedia: http://en.wikipedia.org/wiki/Dead_Parrot. If you think Wikipedia is so good as a reference, why didn't you at least try a Wikipedia search (at left margin on http://en.wikipedia.org/wiki/Main_Page), which comes up with the Dead_Parrot article as its first result?

Wikipedia is NOT a reliable reference source; anyone can edit it. Despite the measures taken to make it easy to revert erroneous edits, it's just never as reliable as a professional source can be. Indeed, Wikipedia's own article on "Reliability of Wikipedia" (http://en.wikipedia.org/wiki/Reliability_of_Wikipedia) is currently headed by a warning that that very article needs improvement.

I usually cite Wikipedia only for convenience, and only when I think the content I reference there is accurate according to my _independent_ knowlege. I don't use or cite it as a reliable reference to support an argument (other than an argument about Wikipedia) -- for those purposes, I find more-professional references, as should you.

[Orgasmic Troll]

Originally Posted by flouran

Furthermore, it's hilarious that you think I'm a guy; I guess male chauvinism hasn't left the mathematics community yet.

I assumed you're a guy because I've never known a woman to be such an argumentative ass without any substantive knowledge behind it.

You must be loads of fun at all the parties you don't get invited to.

[davieddy]

Originally Posted by xilman

You should get out more ...

And come to think of it, are there any female
members of Mersenneforum, active or otherwise?

There should be a Sophie Germaine out there somewhere.

David (male).

[davieddy]

Originally Posted by flouran

LOL, Germaine primes and AKS.

I was primeraly thinking of Gauss's famous response on discovering
that his correspondent (with a male pseudonym) was female.

[CRGreathouse]

Originally Posted by flouran

Also, to determine whether or not the bit-complexity of one algorithm requires more or less operations than the bit-complexity of another algorithm, can I just plug in large number into the bit-complexity formula of each and see which outputs the largest number (meaning it requires the most operations)?

No, because you don't know what the constant terms are. Further, you don't know what the underlying complexity is if you have only an O(---) runtime. An O(n^3) algorithm may in fact take quadratic time, but that fact remains unproved.

Now if you have an algorithm that takes Theta(n^5) and another that takes Theta(n^4) you know that there is some N such that for all n > N, the second algorithm is faster (though the first may be faster for all practical cases, if N is large enough). If you have two algorithms that take time O(n^5) and O(n^4) you can't actually say anything about their run times, not even for large enough n.

[flouran]

I have posted this on every thread that I have started (there are only 2):
As a New Years resolution, I wanted to apologize for my past behavior on this forum. I have been irrational, childish, and rude in my postings, and after reading some of my posts I have decided that this sort of behavior is absolutely unacceptable and should not be tolerated. I have decided to put an end to this behavior before it can further progress, and I sincerely apologize to anyone (or everyone for that matter) whom I have offended, frustrated, and/or angered throughout my membership here. I promise that it will not happen again, and although many members here can make me angry at times (and I can make them angry too), my rude responses to them are not a means to an end. I hope that in this New Year, that we will treat each other better (and hopefully the economy will heal as well).

Have a blessed New Year,