20040901, 15:43  #1 
"William"
May 2003
New Haven
100101000011_{2} Posts 
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 445462 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. 
20040901, 15:44  #2  
"William"
May 2003
New Haven
100101000011_{2} Posts 
A Numerical Example with Known Results
Quote:
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 1ln(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 1ln(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. 

20040901, 16:56  #3  
Nov 2003
2^{2}·5·373 Posts 
Quote:
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... 

20040901, 17:20  #4  
"William"
May 2003
New Haven
2,371 Posts 
Quote:
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 

20040901, 18:10  #5  
Nov 2003
7460_{10} Posts 
Quote:
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. 

20040901, 18:39  #6  
"William"
May 2003
New Haven
2,371 Posts 
Quote:
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^{3} 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, 1ln(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. 

20040901, 19:19  #7  
Nov 2003
2^{2}·5·373 Posts 
Quote:
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. 

20040901, 20:12  #8  
"William"
May 2003
New Haven
2,371 Posts 
Quote:
Quote:
Quote:
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? 

20040902, 13:04  #9  
Nov 2003
2^{2}·5·373 Posts 
Quote:
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 

20040903, 04:31  #10  
"William"
May 2003
New Haven
2,371 Posts 
Quote:
Working from the delaydifferential 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 dgamma 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^{(alphagamma)/alpha} that has all of it’s prime factors less than x^{1/alpha}. The count of such numbers is rho(alphagamma)*x^{(alphagamma)/alpha}. These pieces can be combined in a integral and massaged slightly to come up with my guess: Last fiddled with by wblipp on 20040903 at 04:33 

20040912, 03:21  #11 
"William"
May 2003
New Haven
2,371 Posts 
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 
Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
Distribution of Mersenne Factors  tapion64  Miscellaneous Math  21  20140418 21:02 
Known factors distribution graphs  James Heinrich  Data  21  20130926 19:54 
The ultimate prime test ?  Carl Fischbach  Miscellaneous Math  33  20090911 20:49 
strange factors distribution??  pegaso56  Information & Answers  19  20090629 15:04 
Distribution of Mersenne prime factors mod 6  alpertron  Math  0  20060623 20:07 