Silverman & Wagstaff on Joint Distribution of Ultimate and Penultimate Prime Factors

[wblipp]

This thread pulls together discussions that have been buried on several different threads.

Silverman and Wagstaff's paper "A Practical Analysis of Elliptical Curve Factoring," Mathematics of Computation, Vol. 61, No. 203, (July 1993), p 445-462 has an expression for the asymptotic distribution of the largest and second largest prime factors of a number. I think there is a typographical error in this expression.


This message has a jpeg of the expression in the pdf version of the paper.

This message a jpeg of my guess for the correct expression.

This message has my rationale for my expression.

[wblipp]

Originally Posted by Bob Silverman

I have just double checked the paper again and my notes. The expression
appears to be correct. Note that what we call alpha is actually the
reciprocal of what Knuth uses. Could this be a source of confusion?

Perhaps the confusion is mine. I am certainly not infallible. But Sam Wagstaff
checked the paper carefully as well...

Let's take a simple case where we know the answer. Consider the second largest prime is less then than x^1/2 and the largest prime factor is less than x^2/3.

Since the second largest prime can NEVER exceed x^1/2, we know this is the same as the single condition that the largest prime factor is less than x^2/3. And we know that this is rho(1.5). And we know that this is 1-ln(1.5) = 0.595.

For using the expression in the paper, we have alpha = 2 and beta = 1.333.

Over these ranges we know rho analytically as 1 or 1-ln(t), so it's easy to evaluate both expressions.

The expression in the paper evaluates to 0.496. The expression in my guess evaluates to 0.595.

[R.D. Silverman]

Originally Posted by wblipp

Let's take a simple case where we know the answer. Consider the second largest prime is less then than x^1/2 and the largest prime factor is less than x^2/3.

Since the second largest prime can NEVER exceed x^1/2, we know this is the same as the single condition that the largest prime factor is less than x^2/3. And we know that this is rho(1.5). And we know that this is 1-ln(1.5) = 0.595.

For using the expression in the paper, we have alpha = 2 and beta = 1.333.

Over these ranges we know rho analytically as 1 or 1-ln(t), so it's easy to evaluate both expressions.

The expression in the paper evaluates to 0.496. The expression in my guess evaluates to 0.595.

The probability that the second largest is less than x^1/B is not
independent of the probability that the largest is less than x^1/A.
The distribution of the second largest factor depends on the size of the
largest one... If the largest is near x^2/3 then the second
largest must be less than x^1/3..... You have to consider the
joint pdf and they are not independent. Might this be the source of the
problem? You can't just compute the probability that (say) the largest
is less than x^k and the probability that the second largest is less than
x^j and conclude that the probability that the largest is less than x^k
AND that the second largest is less than x^j is the product of the two...

Dan Bernstein has code that will do these computations. Perhaps you
might want to compare what his code yields with yours...

I am NOT saying that you are wrong. I could very well be in error.
But others have read this paper as well without finding what might be
this problem...

[wblipp]

Originally Posted by Bob Silverman

You can't just compute the probability that (say) the largestis less than x^k and the probability that the second largest is less than x^j and conclude that the probability that the largest is less than x^k
AND that the second largest is less than x^j is the product of the two...

Of course you can't.

And I didn't.

What I said is that we have two descriptions for the same set.

The Rho Description - This is the set of numbers whose largest prime factor is less than x^2/3.

The Mu Description - This is the set of numbers that satisfy both
1. The largest prime factor is less than x^2/3

AND

2. The second largest prime factor is less than x^1/2.


Note we are talking about joint distributions, not joint densities, so we cannot make infereneces based on assuming the largest factor is near x^2/3.

I claim these two sets are identical, and hence their probabilities should be the same. If you think I've made an error, please demonstrate a number that belongs to one set and not the other.

William

[R.D. Silverman]

Originally Posted by wblipp

Of course you can't.

And I didn't.

What I said is that we have two descriptions for the same set.

The Rho Description - This is the set of numbers whose largest prime factor is less than x^2/3.

The Mu Description - This is the set of numbers that satisfy both
1. The largest prime factor is less than x^2/3

AND

2. The second largest prime factor is less than x^1/2.


Note we are talking about joint distributions, not joint densities, so we cannot make infereneces based on assuming the largest factor is near x^2/3.

I claim these two sets are identical, and hence their probabilities should be the same. If you think I've made an error, please demonstrate a number that belongs to one set and not the other.

William

If you want to consider the possibility that the second largest factor may
be as large as x^(1/2), then the largest MUST be less than x^(1/2), not
x^(2/3).

The product of the two numbers must be <= N, thus if you want
the largest less than x^A and the second largest less than x^B, then
A+B must be less than 1. In your instance 2/3 + 1/2 > 1. --> impossible.

[wblipp]

Originally Posted by Bob Silverman

If you want to consider the possibility that the second largest factor maybe as large as x^(1/2), then the largest MUST be less than x^(1/2), not x^(2/3).

That would be right if we were talking about densities, but it's wrong when talking about distributions.

The definition does not require that the second largest factor be NEAR x^1/2, only that it be LESS than x^1/2. 343=7³ is an example of a number that fits in both sets even though neither factor is near the boundaries. 217=7*31 is an example of number that fits in both sets with the largest factor near x^2/3.

Perhaps a more dramatic example of the erroneous results given by the formula in the pdf will help.

What’s the probability the second largest prime is less than x^1/2 and the largest prime is less than x^49/50. Again, we know this is the same set as the set for largest prime factor is less than x^49/50, which is rho(50/49), which is 1 – ln(50/49) = 0.994987.

Over the range in question rho is known to be min(1, 1-ln(t)), so we can easily integrate.

The formula in the paper gives 99.000

My guess gives 0.994987.

Even if I'm wrong, I sure the correct probability is not 99.

[R.D. Silverman]

Originally Posted by wblipp

That would be right if we were talking about densities, but it's wrong when talking about distributions.

The definition does not require that the second largest factor be NEAR x^1/2, only that it be LESS than x^1/2. 343=7³ is an example of a number that fits in both sets even though neither factor is near the boundaries. 217=7*31 is an example of number that fits in both sets with the largest factor near x^2/3.

Perhaps a more dramatic example of the erroneous results given by the formula in the pdf will help.

What’s the probability the second largest prime is less than x^1/2 and the largest prime is less than x^49/50. Again, we know this is the same set as the set for largest prime factor is less than x^49/50, which is rho(50/49), which is 1 – ln(50/49) = 0.994987.

Over the range in question rho is known to be min(1, 1-ln(t)), so we can easily integrate.

The formula in the paper gives 99.000

My guess gives 0.994987.

Even if I'm wrong, I sure the correct probability is not 99.

Huh? If the largest prime factor can be as large as x^.98, then the second
largest can not be taken as large as x^.5. In the case that the largest
IS near x^.98, then the second largest MUST be less than x^.02.

What is wanted is the probability that a large, random integer has
all of its factors less than x^1/B and a single factor between x^1/B and
x^1/A. If you take B = 2, then you can NOT take A = 1+epsilon for
small epsilon. If an integer x has its second largest factor slightly
less than x^1/2, then you can be SURE that its largest is at most a little
bit bigger than x^1/2.

[wblipp]

Originally Posted by Bob Silverman

Huh? If the largest prime factor can be as large as x^.98, then the second largest can not be taken as large as x^.5.

This is so wrong it's hard to take you seriously. Let's take the example of 35. This is a number whose largest factor is less than x^49/50 and whose second largest factor is less than x^1/2. I have just demonstrated that the set of such numbers in non-empty. It seems obvious to me that I CAN take the set of numbers with largest factor less than x^49/50 and second largest factor less than x^1/2 and ask meaningful questions about it's probability. It's true that numbers in the set are not simultaneously near both borders - but that's very different from saying the set is empty.

Originally Posted by Bob Silverman

What is wanted is the probability that a large, random integer has all of its factors less than x^1/B and a single factor between x^1/B and x^1/A.

Maybe this is the error in your paper. This is a far different thing from what the paper says. The paper says

Originally Posted by Silverman & Wagstaff, p446 &amp

We designate by u(a,b) the probability that x has it's largest prime factor less than x^1/a and it's second largest prime factor less than x^b/a a > b > 1.

NOTHING about a minimum size requirement on the largest factor. Nothing that would prohibit 2^N from belonging to the set.

I knew the formula didn't fit the definition, but I had not considered the possibility that the definition was wrong. Are you sure this restatement is really what you intended? If so, I'll go off and study the paper some more.

William

P.S. Do you REALLY mean to change the B/A to 1/B as well as adding the requirement that the largest prime exceed 1/A?

[R.D. Silverman]

Originally Posted by wblipp

This is so wrong it's hard to take you seriously. Let's take the example of 35.
?

Hi,

I agree that there is a definite problem with the formula. I am not
sure whether it is the formula or how alpha & beta were defined.

The derivation of that formula, in its simple form was tedious. It started
from the differential delay equation, involved a substitution t; <- 1/t,
some changes of variables, etc. It is quite possible that I left out some
term.

Bob

[wblipp]

Originally Posted by Bob Silverman

The derivation of that formula, in its simple form was tedious.

I think you’ll rediscover something you knew when writing the paper. I’m pretty sure the tables later in the paper were not calculated using this troublesome formula. It was my inability to match those tables that caused me to look more deeply into the formula.

Working from the delay-differential equations was too tedious for me. I didn’t make any progress until I was inspired by Knuth and Trabb Prado’s description of Dickman’s heuristic derivation. My guess comes from that style of heuristic derivation.

The count of numbers less than x with all factors less than x^1/alpha is rho(alpha)*x. All these numbers are part of the count for mu(alpha, beta).

For the numbers with one large factor, we can count the numbers with a large factor of x^gamma/alpha where gamma ranges from one to beta. In a d-gamma strip the count of large numbers is the derivative with respect to gamma of x^gamma/alpha, which is

ln(x)/alpha*x^gamma/alpha

Not all of these numbers are prime, though. The fraction that is prime is 1/ln(x^gamma/alpha), which is

alpha/(gamma*ln(x))

For each such prime, we get a number in mu for every number less than x^{(alpha-gamma)/alpha} that has all of it’s prime factors less than x^1/alpha. The count of such numbers is

rho(alpha-gamma)*x^{(alpha-gamma)/alpha}.

These pieces can be combined in a integral and massaged slightly to come up with my guess:

[wblipp]

Eureka!

I just found that Richard Brent considered the function mu(alpha, beta) in Some Integer Factorization Algorithms using Elliptical Curves. Formula 3.3 in that paper agrees with my guess.

William