The limit of a factoring algorithm

[Eus]

Hi Ho!

It is easy to observe that to get all factors of an integer n, one does not need to try whether a divides n for 1 < a < n.

But, rather using the following observation:
Suppose n is 24, then
24 / 1 = 24
24 / 2 = 12
24 / 3 = 8
24 / 4 = 6
-------------(!)
24 / 6 = 4
24 / 8 = 3
24 / 12 = 2
24 / 24 = 1

Notice that after (!), the divisor and the result of each probing step are just the swap of the divisor and the result of each probing step before (!). With other words, (!) acts as a mirror. Therefore, to find all factors of an integer n, one only needs to record both the divisor and the result of each probing step until the first swap happens, or until the values of the divisor and the result are the same such as when n = 49.

We know that, to test whether an integer number n is prime or not, one only needs to try to divide n by an integer from 2 until square root of n. Is it possible to predict before hand at what n-th factor the mirroring will occur?

Thanks.

Regards,
Eus

 

[Gib Z]

The mirror occurs at half way >.< Whilst the square root occurs earlier, which is why we use that observation instead.

 

[Hurkyl]

Eus: if you can factor your number as

N = A \times B (with A \leq B)

then it is well known that A \leq \sqrt{N} \leq B.

 

[CRGreathouse]

Suppose you can check divisibility in 10 ns. Then factoring a number by checking sequential numbers takes

10 digits:
1 minute (N/2)
1 ms (sqrt(N))

16 digits:
1.5 years (N/2)
1 second (sqrt(N))

20 digits:
15 millennia (N/2)
2 minutes (sqrt(N))

Of course good factoring methods are much better. Pari, which isn't really all that fast in general, factored the random 20-digit semiprime 42731646881968660727 in 156 ms. For larger numbers the difference is more pronounced: for 30 digits, the sqrt method would take 4 months while Pari took 516 ms (for 9981479919456039576778843766369589135143).

 

[Eus]

Hi Ho!

Thank you for all of the replies, especially, CRGreathouse for giving me information on PARI/GP.

What I can conclude is that there is no quick way to determine the number of factors that an integer number has.

If suppose there is a function f(n) that can give us the number of factors of an integer number n, then we know that the mirroring will occur after we get the (\left\lceil\frac{f(n)}{2}\right\rceil)-th factor.

But, there is no such a function, right?


Eus

 

[Gib Z]

Of course there is such a function, you just defined it.

 

[CRGreathouse]

If suppose there is a function f(n) that can give us the number of factors of an integer number n, then we know that the mirroring will occur after we get the (\left\lceil\frac{f(n)}{2}\right\rceil)-th factor.

Suppose N=n_1^{a_1}\cdot n_2^{a_2}\cdots n_k^{a_k}.

Then \omega(n)=k, \Omega(n)=a_1+a_2+\cdots+a_k, and \sigma_0(n)=(a_1+1)(a_2+1)\cdots(a_k+1). There are three standard functions that count factors: distinct prime factors, indistinct prime factors, and total factors.

The mirroring point you're looking for happens at the square root. Notice that in your example, \sqrt{24}\approx4.9 and the mirror is between 4 and 6.

 

[Xevarion]

The OP wants a way to compute the exact number (in the case of 24, it would be 4) beyond which you don't need to check anything.

I would be surprised if this was easy to do. I'd expect it would be faster to just bite the bullet and go on up to the square root.

 

[CRGreathouse]

The OP wants a way to compute the exact number (in the case of 24, it would be 4) beyond which you don't need to check anything.

I would be surprised if this was easy to do. I'd expect it would be faster to just bite the bullet and go on up to the square root.

You can take L = the lcm of the factors you find so far, and then you only need to check up to floor(sqrt(N / L)). Of course when you look at the process as factoring rather than finding divisors this is obvious.

 

[Eus]

Suppose N=n_1^{a_1}\cdot n_2^{a_2}\cdots n_k^{a_k}.

Then \omega(n)=k, \Omega(n)=a_1+a_2+\cdots+a_k, and \sigma_0(n)=(a_1+1)(a_2+1)\cdots(a_k+1). There are three standard functions that count factors: distinct prime factors, indistinct prime factors, and total factors.

The mirroring point you're looking for happens at the square root. Notice that in your example, \sqrt{24}\approx4.9 and the mirror is between 4 and 6.

Thank you very much for pointing out that the mirroring will happen approximately after finding the (\sqrt{n})-th factor. This way I can determine the worst running time of such an algorithm and the memory space needed to contain all of factors of an integer number n.

Moreover, you also mentioned three interesting functions.
If N=24 then 24=2^{3}\cdot 3^{1}. So, \omega(24)=4, \Omega(24)=4, and \sigma_0(24)=8.
The number of indistinct prime factors is 4. How do you define indistinct prime factors?
Do you mean that they are 4, 6, 8, 12 for N=12?

I don't get what you mean below. Isn't that \sqrt{N} is all that counts? I would be glad if you could explain further.

You can take L = the lcm of the factors you find so far, and then you only need to check up to floor(sqrt(N / L)).

Thank you very much.

Regards,
Eus

 

[CRGreathouse]

How do you define indistinct prime factors?
Do you mean that they are 4, 6, 8, 12 for N=12?

4, 6, 8, and 12 are all composite (none are prime), so I don't call them indistinct prime factors. Consider the prime factors of 12 = 2 x 2 x 3. It has three prime factors, (2, 2, 3), but only two distinct prime factors, {2, 3}. So \omega(12)=2 but \Omega(12)=3.

\omega(1024) = 1, \Omega(1024) = 10 since 1024 = 2^10.

 

[CRGreathouse]

Thank you very much for pointing out that the mirroring will happen approximately after finding the (\sqrt{n})-th factor. This way I can determine the worst running time of such an algorithm and the memory space needed to contain all of factors of an integer number n.

The mirror is at sqrt(n), not the sqrt(n)th factor. You can always stop factoring at the square root of the number you're on; all divisors above sqrt(n) can be found by dividing n by the smaller divisors.

This is easy to see: if k > sqrt(n), and h > sqrt(n), then k * h > sqrt(n) * sqrt(n) = n and so h * k is not a factor of n.