mersenneforum.org  

Go Back   mersenneforum.org > Great Internet Mersenne Prime Search > Math

Reply
 
Thread Tools
Old 2004-09-01, 15:43   #1
wblipp
 
wblipp's Avatar
 
"William"
May 2003
New Haven

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

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 is offline   Reply With Quote
Old 2004-09-01, 15:44   #2
wblipp
 
wblipp's Avatar
 
"William"
May 2003
New Haven

23×103 Posts
Default A Numerical Example with Known Results

Quote:
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 x1/2 and the largest prime factor is less than x2/3.

Since the second largest prime can NEVER exceed x1/2, we know this is the same as the single condition that the largest prime factor is less than x2/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.
wblipp is offline   Reply With Quote
Old 2004-09-01, 16:56   #3
R.D. Silverman
 
R.D. Silverman's Avatar
 
Nov 2003

22·5·373 Posts
Thumbs up

Quote:
Originally Posted by wblipp
Let's take a simple case where we know the answer. Consider the second largest prime is less then than x1/2 and the largest prime factor is less than x2/3.

Since the second largest prime can NEVER exceed x1/2, we know this is the same as the single condition that the largest prime factor is less than x2/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 x1/B is not
independent of the probability that the largest is less than x1/A.
The distribution of the second largest factor depends on the size of the
largest one... If the largest is near x2/3 then the second
largest must be less than x1/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...
R.D. Silverman is offline   Reply With Quote
Old 2004-09-01, 17:20   #4
wblipp
 
wblipp's Avatar
 
"William"
May 2003
New Haven

23·103 Posts
Default

Quote:
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 x2/3.

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

AND

2. The second largest prime factor is less than x1/2.


Note we are talking about joint distributions, not joint densities, so we cannot make infereneces based on assuming the largest factor is near x2/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
wblipp is offline   Reply With Quote
Old 2004-09-01, 18:10   #5
R.D. Silverman
 
R.D. Silverman's Avatar
 
Nov 2003

22×5×373 Posts
Default

Quote:
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 x2/3.

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

AND

2. The second largest prime factor is less than x1/2.


Note we are talking about joint distributions, not joint densities, so we cannot make infereneces based on assuming the largest factor is near x2/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.
R.D. Silverman is offline   Reply With Quote
Old 2004-09-01, 18:39   #6
wblipp
 
wblipp's Avatar
 
"William"
May 2003
New Haven

1001010000012 Posts
Default

Quote:
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 x1/2, only that it be LESS than x1/2. 343=73 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 x2/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 x1/2 and the largest prime is less than x49/50. Again, we know this is the same set as the set for largest prime factor is less than x49/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.
wblipp is offline   Reply With Quote
Old 2004-09-01, 19:19   #7
R.D. Silverman
 
R.D. Silverman's Avatar
 
Nov 2003

22×5×373 Posts
Default

Quote:
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 x1/2, only that it be LESS than x1/2. 343=73 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 x2/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 x1/2 and the largest prime is less than x49/50. Again, we know this is the same set as the set for largest prime factor is less than x49/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.
R.D. Silverman is offline   Reply With Quote
Old 2004-09-01, 20:12   #8
wblipp
 
wblipp's Avatar
 
"William"
May 2003
New Haven

23×103 Posts
Default

Quote:
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 x49/50 and whose second largest factor is less than x1/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 x49/50 and second largest factor less than x1/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.

Quote:
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
Quote:
Originally Posted by Silverman & Wagstaff, p446 &amp View Post
We designate by u(a,b) the probability that x has it's largest prime factor less than x1/a and it's second largest prime factor less than xb/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?
wblipp is offline   Reply With Quote
Old 2004-09-02, 13:04   #9
R.D. Silverman
 
R.D. Silverman's Avatar
 
Nov 2003

22×5×373 Posts
Thumbs up

Quote:
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
R.D. Silverman is offline   Reply With Quote
Old 2004-09-03, 04:31   #10
wblipp
 
wblipp's Avatar
 
"William"
May 2003
New Haven

236910 Posts
Default

Quote:
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 x1/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 xgamma/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 xgamma/alpha, which is

ln(x)/alpha*xgamma/alpha

Not all of these numbers are prime, though. The fraction that is prime is 1/ln(xgamma/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 x1/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:
Attached Thumbnails
Click image for larger version

Name:	MuDerive.jpg
Views:	550
Size:	16.3 KB
ID:	303  

Last fiddled with by wblipp on 2004-09-03 at 04:33
wblipp is offline   Reply With Quote
Old 2004-09-12, 03:21   #11
wblipp
 
wblipp's Avatar
 
"William"
May 2003
New Haven

23×103 Posts
Default

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
wblipp is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Distribution of Mersenne Factors tapion64 Miscellaneous Math 21 2014-04-18 21:02
Known factors distribution graphs James Heinrich Data 21 2013-09-26 19:54
The ultimate prime test ? Carl Fischbach Miscellaneous Math 33 2009-09-11 20:49
strange factors distribution?? pegaso56 Information & Answers 19 2009-06-29 15:04
Distribution of Mersenne prime factors mod 6 alpertron Math 0 2006-06-23 20:07

All times are UTC. The time now is 00:19.


Wed Dec 8 00:19:00 UTC 2021 up 137 days, 18:47, 0 users, load averages: 1.75, 2.14, 2.25

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2021, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.