Average minimum tries for prime factorization

  • #1
3,077
3

Main Question or Discussion Point

On average, at least how many factors must one try dividing a number N by to decompose it into primes?
 

Answers and Replies

  • #2
CRGreathouse
Science Advisor
Homework Helper
2,820
0
On average, at least how many factors must one try dividing a number N by to decompose it into primes?
If you are dividing by sequential primes starting from 2, and you test the cofactor with a primality test after you find each factor, you're asking about the distribution of the second-smallest prime factor of a random integer. In particular, you want the number of primes up to that number.

A good answer would involve the extended Dickman function; see
http://cr.yp.to/bib/1996/bach-semismooth.pdf

An easier answer would involve harmonic numbers, since the 'probability' of finding an n-bit factor in a large number is about 1/n.

An off-the-cuff estimate would be "around n^(1/4) to n^(1/3)".
 
Last edited:
  • #3
CRGreathouse
Science Advisor
Homework Helper
2,820
0
I'm not entirely sure about this, but I hacked together a program to calculate this for you based on the paper cited above. It suggests that the average size (median exponent) of the second-largest prime factor of a random integer N is around N^0.282.
 
  • #4
3,077
3
...you're asking about the distribution of the second-smallest prime factor of a random integer. In particular, you want the number of primes up to that number.
Bravo! - but why the second-smallest in particular? Could you give me an example of this result?

Thanks much for the computation also. I guess it is based on a prime approximation formula.
 
  • #5
CRGreathouse
Science Advisor
Homework Helper
2,820
0
Bravo! - but why the second-smallest in particular? Could you give me an example of this result?
I'm not sure how to explain; it's obvious to me.

Let's say you have n = p * q * ... * r * s. You find the factor s, but n/s is still composite. You find the factor r, but n/ (r * s) is still composite. Then you find a number of other factors, but the cofactor is still composite. Then you find the factor q, and n / (s * r * ... * q) is prime, so you stop factoring. The last prime you had to factor out is the second-smallest.

Thanks much for the computation also. I guess it is based on a prime approximation formula.
It was a very hairy calculation using numerical root-finding, table lookup, a complicated approximation function, and more. It used the extension of Dickman's function from the paper I linked to.

There were so many steps in the process I'm not sure the result is correct! I may have made a mistake along the way. But it seems to be in about the right range, so I'm reasonably sure I have it.
 
  • #6
3,077
3
Your first approximation is really on the cuff. Can you tell how you conceived it?

Thank you for explaining your initial response in more detail. The distribution now seems sensible to me.

You prove yourself to be quite an adept and patient mathematician. The praise here belongs to you.
 
  • #7
CRGreathouse
Science Advisor
Homework Helper
2,820
0
Your first approximation is really on the cuff. Can you tell how you conceived it?
My guess that the second factor was between the fourth and third root, on average, was simply a result of experience with factoring numbers. There was no math involved there.

The n^0.282 approximation was based on the Bach-Peralta asymptotic formula G, which I hope I implemented properly. It's complicated.
 

Related Threads for: Average minimum tries for prime factorization

  • Last Post
Replies
2
Views
4K
  • Last Post
Replies
2
Views
3K
  • Last Post
Replies
7
Views
2K
  • Last Post
Replies
4
Views
4K
  • Last Post
Replies
7
Views
5K
  • Last Post
Replies
9
Views
8K
  • Last Post
Replies
1
Views
3K
  • Last Post
Replies
1
Views
2K
Top