A Followup question on Mlucas...

[R.D. Silverman]

Originally Posted by davieddy

One can and does say exactly that.
The probability that 2^p-1 is prime when no factor
has been found up to x bits is~ x/(gamma*p)
where gamma is Euler's constant

No. We can't.

Once again we have a difficulty with semantics.

For a *given* integer 2^p-1 it is prime
with probability exactly 0 or 1. It is either prime or it isn't.

For a *randomly* chosen value of X in some interval X \in [A, B],
such that X has no prime factors up to k the probability is (as you say)
given by Mertens' theorem *provided* that k is not too large relative to X.

Once q1, q2 > log(X), the probabilities that q1 or q2 might divide X are
NO LONGER INDEPENDENT (because now product of p_i, p_i < log(X)
becomes greater than X) and Merten's theorem becomes innacurate.

[i.e. one can't have all the primes divide X because their product is too
large. They get in each other's way]

One can't prove the PNT by sieve methods because the fundamental lemma
of the sieve gets in the way. Compare the PNT with Mertens' theorem
where the product is taken over all primes up to sqrt(N). You get different
answers because Mertens' theorem is not valid beyond log(N).
[Actually, a weighted version of the sieve can take this to log^r N for
small integer r > 1]

But this is for randomly chosen X and *not* for X of special form such as
2^p-1. We have no proof on the infinitude of Mersenne primes precisely
because we have no theorems saying that numbers of this form have the
same divisibility properties as random integers. We have no proof
that Mersenne numbers behave as random integers do. We can only
state that *heuristically*, for a randomly chosen 2^p-1 [in some
bounded interval] that its divisors behave in a way that lets us apply
Mertens' theorem.

We run into the same problem in the time complexity analysis of NFS.
We *assume* that integers of the form (-b)^n f(-a/b) [for irreducible
polynomial f of degree n] have the same smoothness properties as
random integers of the same size. But their is no PROOF. Which is why
the time complexity estimates for QS and NFS are *heuristics*.

[davieddy]

The card at the bottom of a deck is either the ace of spades or it's not.

If I inspect the top n cards and no ace of spades appears,
the probability of the bottom card being the ace of spades is
1/(52-n).

It seems you wish to dispute something about this assertion.

[R.D. Silverman]

Originally Posted by davieddy

The card at the bottom of a deck is either the ace of spades or it's not.

If I inspect the top n cards and no ace of spades appears,
the probability of the bottom card being the ace of spades is
1/(52-n).

It seems you wish to dispute something about this assertion.

For a card drawn uniformly at random and having 'no special form', YES.

The same does NOT apply to integers of special form (such as Mersenne
Numbers). And you seemingly fail to understand the limitations of
Mertens' theorem and my statement that once you have sieved (or trial
divided) sufficiently many primes, that subsequent sieving or trials results
in the probabilities no longer being independent.

Go read Halberstam & Richert's book on sieve methods. [but be careful,
the book is dense and obtuse; I've kicked it across the room in frustration
more than once].

[davieddy]

The limitations of Merten's theorem are obvious, but you
seem to be implying that it is meaningless to speak of a
probability other than 0 or 1.

[philmoore]

Originally Posted by R.D. Silverman

For ECM [run on a *known* composite] , all one can say after a number of trials is that the probability of there being a factor less than X is some value Z. But this really does not get you closer to the *deterministic* goal of factoring the composite.

But by your previous logic, the probability of there being a factor less than X must be either 0 or 1, i.e., it either exists or does not.

[m_f_h]

Prime95 says things like
"The chances that the exponent you test yields a prime are about 1 in xxxxxxxxx."
This IS a probability, for a GIVEN exponent p.

[R.D. Silverman]

Originally Posted by philmoore

But by your previous logic, the probability of there being a factor less than X must be either 0 or 1, i.e., it either exists or does not.

For a given integer, the probability is indeed 0 or 1.

For a *randomly chosen* integer, drawn uniformly at random from
some interval, then we can say something about the p.d.f for its factors.

Otherwise:

A more accurate statement would be that *ECM* is a random decision
procedure that sometimes makes errors and we can compute the probability
that this *decision procedure* is in error when it declares that, e.g. no factor
less than X exists.

[R.D. Silverman]

Originally Posted by m_f_h

Prime95 says things like
"The chances that the exponent you test yields a prime are about 1 in xxxxxxxxx."
This IS a probability, for a GIVEN exponent p.

(1) The statement assumes that you have randomly chosen a Mersenne
number to test.

(2) It assumes mathematical facts that are not proven; that Mersenne
primes behave as other, uniformly chosen random integers. But we do
not know this to be the case. We know the probability of a uniformly
random chosen integer being prime by the PNT. No such theorem exists
for Mersenne numbers.

[m_f_h]

Originally Posted by R.D. Silverman

(1) The statement assumes that you have randomly chosen a Mersenne number to test.

Well, in some sense any number is a "randomly chosen" number, but whatsoever was the method to choose it, once chosen, any number is either prime or not prime, "without probability", in your logic.
But the statement from Prime95 I refer to IS specific to the selected exponent!
It uses information about its size, previous LL tests if any, previously done factoring etc.
(I wonder why it does not just use the simple binary information which is its primality...)

[cheesehead]

Originally Posted by R.D. Silverman

You are comparing totally different things.

I think you are failing to distinguish between a priori probability and a posteriori probability.

Those you "don't understand" are referring to probability, given only pre-test knowledge: a priori probability. That is, if we expect 1 Mersenne prime in a range of 100,000 exponents, the a priori chance of any specific Mersenne exponent's being that of a prime is 1/100000. Only after we have tested them do we find that, in fact (a posteriori), 3 (for example) of them give Mersenne primes and 99997 denote composites. In that example, the a posteriori probabilities were 1 for three of the exponents, and 0 for 99997 of them.

For LL, the "result" is a statement of the form "If A then B".

This is NOT true for trial division or ECM.

We can cast statements of trial division or ECM results in the "If A then B" form if we want to. They'll be more complicated than the "If A then B" statement of an LL test.

For a given 2^p-1, One can NOT say: "By trial division, 2^p-1 has no factors less than X, therefore the probability that 2^p-1 is primes is Z".

Not for a posteriori probability, that is.

2^p-1 is prime either with probability 0 or 1.

... a posteriori, that is.

All trial division says is: "If 2^p-1 has no factors less than X, then 2^p-1 has no factors less than X": a tautology. One CAN say: "I have trial divided 2^p-1 to X and found no factors, therefore I have done Z% of the work needed to factor 2^p-1 by trial division". [where Z depends on X and p].

But we can also make statements about the a priori probability, based on what we know so far, without complete final knowledge.

E.g., out of all 2^p-1, with p in a given range, and with no factors less than X, and with the experiential knowledge gained from complete tests of other Mersenne numbers or from proven theorems about Mersenne numbers, we can predict that, on average, Z% of such exponents will eventually (after complete testing) turn out to correspond to Mersenne primes. Z is an a priori probability.

But one can say the same of the LL test. One CAN say "I have performed k iterations, therefore I have done k/(p-2) of the work needed tp determine if this number is prime". But this says NOTHING about the "probability" of the number being prime. It simply says one has done some percentage of the required computation.

I agree with what you state about a partially-completed LL test, but that is not the same as having performed trial division on a certain range of potential factors. The latter actually consists of a certain number of complete tests (each of which tested one particular potential factor), so we have information that we didn't have before we started testing.

The concepts do not carry over from one problem to the other.

They can, if you are careful to separate the common concepts from the nonshared concepts.

The LL test is a single test.

Trial division on one potential factor is a single test. Trial division on multiple potential factors consists of multiple tests. Each completed single test adds to our knowledge and enables us to refine our a priori estimate of probability of primality even though we have not yet performed all possible trial divisions (up to the square root).

[cheesehead]

Some of you knowledgable folks have been indulging in the bad habit of attributing lesser intellect to those whom you do not understand.

I suggest that if you "do not understand" someone, you need to remember that you may be part of the problem!

Originally Posted by R.D. Silverman

I'd like to understand the thought process that might lead someone to ask about a PARTIAL computation leading to some kind of conclusion about the ENTIRE computation.

Okay, that's fair -- you want to understand such a person.

I guess that I just don't understand how people think.

Okay, that's fair, too.

What might lead someone who is told "If A then B" to somehow ask "What about C" when the statement says nothing about C??

Perhaps the connection between C and the "If A then B" statement is outside the simplistic logic tunnel you're looking at. Other people are not mechanistically constrained to think only within the particular boundaries on which you happen to be concentrating at the time.

Suppose we had a computation that said: if x^17 = 0 mod N, then N is prime. How could anyone be led to ask about (say) x^8 mod N??

Curiosity?

What might cause someone to believe that the value of x^8 gives useful information about the final conclusion? The computation says x^17, not x^8 mod N gives the answer. Is this a question of READING
comprehension????

It might be a question of your own comprehension of the learning process and other human behavior.

I find quite often that the problems beginners and naiive people have with math is not a lack of mathematical comprehension, but rather of READING comprehension.

... to which finding you may often be led by your own deficiencies rather than theirs.

Originally Posted by Mini-Geek

I think it's one of three things:
reading comprehension problems
wanting "instant gratification", they skipped over the relevant parts to finish reading about it faster
or they just never looked it up at all before asking.

... or perhaps ... a fourth or fifth thing involving your own imperfections rather than theirs, though that may be less convenient for you than the first three.

Originally Posted by m_f_h

I also think it's an "instant gratification" problem

Well, that's convenient, isn't it?

A quick, simple explanation ... gratifying ... almost ... instantly.

Avoids all that tedious analysis of whether "instant gratification" actually has anything to do with a novice's confusion between TF and LL, doesn't it? :-)

You also notice that in the approach of students to mathematics but I believe to other subjects. They know they have to spend a given amount in lessons and/or training sessions, but apart from that, they are not taught to spend hours and hours on understanding a problem.

Right-o.

Why spend time figuring out a reason for a novice's error that is respectful of him/her (and, BTW, is a better fit to the observed facts)? So much easier to chime in with the "instant" answer.

If they cannot do the exam at the end of the course, it's the instructor's fault, not theirs.

If the reason for a novice's confusion isn't immediately obvious, it's the novice's fault, not ...

- - - -

Y'all oughta be ashamed of yerselves.