Composites that pass Mathematica's pseudoprime test

[R.D. Silverman]

Originally Posted by Walter Nissen

Another part of the probem is that it seems to be very difficult
to characterize the nature of the probabilty involved in the
"probable" part of "probable prime" .

This is false. We have very good analytic methods that give good estimates
on the probabilities.

Look up "Pomerance and Kim"

[R.D. Silverman]

Originally Posted by ewmayer

The above Wikiarticle omits a crucial aspect of such "deterministic up to a limit" PRP tests; namely for a given set of bases, whether the limit can be determined .

In this sense, a limit can be established. If one assumes GRH, then a result of
Eric Bach shows that there exists a primitive root less than 2 log^2 N,
where N is the candidate.

An estimate by Burgess gives a bound of the form N^alpha for some
value of alpha that I do not recall, but this bound is unconditional.
It does, however, yield a purely exponential test.

[Dubslow]

Originally Posted by ewmayer

The above Wikiarticle omits a crucial aspect of such "deterministic up to a limit" PRP tests; namely for a given set of bases, whether the limit can be determined (or at least bounded below) in a priori fashion. A test which cannot provide such a a priori bound is only "deterministic" in an extremely weak post hoc fashion.

That' why I said "true in practice" and "brute force", but looking back, a priori is the word/phrase I was looking for.






Though RDS has gotten a lot (a whole lot) better, I thought it'd been fun to throw out factually correct troll bait. :P

[CRGreathouse]

Originally Posted by R.D. Silverman

An estimate by Burgess gives a bound of the form N^alpha for some
value of alpha that I do not recall, but this bound is unconditional.
It does, however, yield a purely exponential test.

There's an improved test due to Sorenson that doesn't require GRH and gets better bounds, but it relies on knowledge of sufficiently many pseudosquares. It degrades, I believe, into the Burgess derandomized version of Miller's test if you don't know any.

[Walter Nissen]

Originally Posted by R.D. Silverman

No, the confusion occurs because people use terminology without
actually having read about the algorithms.

Not at all .

A ( presumably high-quality ) predicate function was being offered
to the paying customer = the poster .
Then he read on and discovered he was actually being offered a
sub-standard predicate .
Probably , like anyone , the poster was confused
( and disappointed ) by this .
I don't know the details of PrimeQ , but it bears every mark of
being a compositeness test , which under poorly understood
conditions could fail as a primality test .

---

Originally Posted by R.D. Silverman

??? Are you asking if deterministic tests exist ???? Or do you
really mean "MR test"? If so, the answer is no. If a test is deterministic,
then it isn't MR.

Parsing :

Originally Posted by R.D. Silverman

(2) There are no known composites that pass both a MR and Lucas test
(with D = 5).

seemed to yield the phrase "MR test" .
I don't understand the meaning of this ( whatever it is ) as it relates to
"known composites" .
I'm quite sure ( subject to verification ) that the test referenced by
the poster is probabilistic , leaving open any possible justification
for :

Originally Posted by R.D. Silverman

(2) There are no known composites that pass both a MR and Lucas test
(with D = 5).

---

Originally Posted by R.D. Silverman

This is false. We have very good analytic methods that give good estimates
on the probabilities.

Look up "Pomerance and Kim"

Not at all .

The mere fact of reference to the ( peer-reviewed ? ) literature is
excellent support for the denied claim .