Probability of n-digit factor?

roger · 2007-05-09, 16:24

I am interested in what the probability of a n-digit factor is in a random x-digit composite.

The reason I ask is, I am trying to factor a C120 and a C160. (For both, I am using Alpertrons ECM applet.) For the C160, I don't have a single factor, and have sieved to (so far) curve 437 (greater than 25 digits, 55% likely greater than 30 digits). So far, the largest factor (not the result, but smaller prime factor) is a P43. P20's, P25's, and P30's are pretty common.

If it matters, it is a home prime sequence, but not one anyone is working on (a 18-digit starting number); and this is just a small hobby, nothing of mathematical importance

Thanks for anyones help!

Roger

R.D. Silverman · 2007-05-09, 16:45

Quote:

Originally Posted by roger

I am interested in what the probability of a n-digit factor is in a random x-digit composite.

I answer this question (and others) in my joint paper with Sam Wagstaff Jr.
A Practical Analysis of the Elliptic Curve Factoring Algorthm.

As n -->oo, the probability that n has a factor between a and a^(1+e)
is e/(e+1). This applies uniformly for a^(1+e) < sqrt(n).

If the factor is greater than sqrt(n), then it must be the largest factor and
its distribution is given by Dickman's rho function. See Knuth, vol. II.

akruppa · 2007-05-09, 17:25

Lets assume your "random" number N is chosen uniformly from large enough interval [1, B] so that we can estimate the probability that a prime p divides it as 1/p. Now you want the probability that there is at least one p in [10^[I]n[/I]-1, 10^[I]n[/I]-1] that divides N. This is messy to compute, lets look at the expected number of such primes instead, $\sum_{p\in P, 10^{n-1} \leq p \leq 10^n-1} 1/p$ . If this expected value is much smaller than 1, it is quite close to the probability. Now $\lim_{k \rightarrow \infty}\sum_{p\in P, p \leq k} 1/p - \log \log(k) = M$ for some constant M, so we can take the sum over the interval as roughly like log log (10^[I]n[/I]) - log log (10^[I]n[/I]-1) = log(n / (n-1)). If n/(n-1) is close to 1, you can approximate log(n / (n-1)) by 1/n, or better 1/(n-0.5).

However, this assumes that N was taken from all the integers not exceeding B. If you have done a PRP test already and it came out negative, you know that N is not any of the primes below B. A prime p divides a prime q iff p=q, so we should remove all the primes from the interval [1, B] except the ones in [10^[I]n[/I]-1, 10^^[I]n[/I]-1]. Since I assume 10^[I]n[/I] << B, we simply remove all of the primes below B instead.

So the set of numbers you chose your random number from has cardinality about B-B/log(B), the set of non-prime numbers not exceeding B that have a prime factor in [10^[I]n[/I]-1, 10^[I]n[/I]-1] has size about B*(log(n /(n-1))) and if you number was chosen uniformly from all the non-primes ≤ B, the probability becomes

log(n / (n-1)) / (1 - 1/log(B))

Everything changes again if you did trial division/ECM/whatever on your number. You can use a Bayesian model to account for unsuccessful factoring attempts. Silverman and Wagstaff "Practical Analysis of the Elliptic Curve Factoring Algorithm" treats this in detail.

Alex

roger · 2007-05-09, 22:51

Wow, information dump!

Thanks for the explanation, Akruppa; both of your posts pointed to Wagstaff/Silverman's paper, so I'll have a look.

Roger

2007-05-09, 16:24	#1
roger Oct 2006 104₁₆ Posts	Probability of n-digit factor? I am interested in what the probability of a n-digit factor is in a random x-digit composite. The reason I ask is, I am trying to factor a C120 and a C160. (For both, I am using Alpertrons ECM applet.) For the C160, I don't have a single factor, and have sieved to (so far) curve 437 (greater than 25 digits, 55% likely greater than 30 digits). So far, the largest factor (not the result, but smaller prime factor) is a P43. P20's, P25's, and P30's are pretty common. If it matters, it is a home prime sequence, but not one anyone is working on (a 18-digit starting number); and this is just a small hobby, nothing of mathematical importance Thanks for anyones help! Roger

2007-05-09, 17:25	#3
akruppa "Nancy" Aug 2002 Alexandria 2,467 Posts	Lets assume your "random" number N is chosen uniformly from large enough interval [1, B] so that we can estimate the probability that a prime p divides it as 1/p. Now you want the probability that there is at least one p in [10^[I]n[/I]-1, 10^[I]n[/I]-1] that divides N. This is messy to compute, lets look at the expected number of such primes instead, $\sum_{p\in P, 10^{n-1} \leq p \leq 10^n-1} 1/p$ . If this expected value is much smaller than 1, it is quite close to the probability. Now $\lim_{k \rightarrow \infty}\sum_{p\in P, p \leq k} 1/p - \log \log(k) = M$ for some constant M, so we can take the sum over the interval as roughly like log log (10^[I]n[/I]) - log log (10^[I]n[/I]-1) = log(n / (n-1)). If n/(n-1) is close to 1, you can approximate log(n / (n-1)) by 1/n, or better 1/(n-0.5). However, this assumes that N was taken from all the integers not exceeding B. If you have done a PRP test already and it came out negative, you know that N is not any of the primes below B. A prime p divides a prime q iff p=q, so we should remove all the primes from the interval [1, B] except the ones in [10^[I]n[/I]-1, 10^^[I]n[/I]-1]. Since I assume 10^[I]n[/I] << B, we simply remove all of the primes below B instead. So the set of numbers you chose your random number from has cardinality about B-B/log(B), the set of non-prime numbers not exceeding B that have a prime factor in [10^[I]n[/I]-1, 10^[I]n[/I]-1] has size about B(log(n /(n-1))) and if you number was chosen uniformly from all the non-primes ≤ B, the probability becomes log(n / (n-1)) / (1 - 1/log(B)) Everything changes again if you did trial division/ECM/whatever on your number. You can use a Bayesian model to account for unsuccessful factoring attempts. Silverman and Wagstaff "Practical Analysis of the Elliptic Curve Factoring Algorithm" treats this in detail. Alex Last fiddled with by akruppa on 2007-05-09 at 23:09 Reason: small clarification*

Similar Threads
Thread	Thread Starter	Forum	Replies	Last Post
Probability of factor (TF)	nuggetprime	Math	2	2011-03-19 22:14
160 digit factor found of 366 digit (PRP-1)	AntonVrba	Factoring	7	2005-12-06 22:02
Probability of finding a factor	JuanTutors	Software	20	2004-09-26 09:47
Probability of finding a factor in TF	eepiccolo	Math	4	2003-06-07 05:56
Probability of finding a factor in DC p-1	Deamiter	Math	4	2002-12-25 06:06

2007-05-09, 22:51	#4
roger Oct 2006 2²×5×13 Posts	Wow, information dump! Thanks for the explanation, Akruppa; both of your posts pointed to Wagstaff/Silverman's paper, so I'll have a look. Roger