Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

The limit of a factoring algorithm

  1. Nov 24, 2007 #1

    Eus

    User Avatar

    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
     
  2. jcsd
  3. Nov 24, 2007 #2

    Gib Z

    User Avatar
    Homework Helper

    The mirror occurs at half way >.< Whilst the square root occurs earlier, which is why we use that observation instead.
     
  4. Nov 24, 2007 #3

    Hurkyl

    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    Eus: if you can factor your number as

    [itex]N = A \times B[/itex] (with [itex]A \leq B[/itex])

    then it is well known that [itex]A \leq \sqrt{N} \leq B[/itex].
     
  5. Nov 24, 2007 #4

    CRGreathouse

    User Avatar
    Science Advisor
    Homework Helper

    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).
     
  6. Nov 26, 2007 #5

    Eus

    User Avatar

    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 [tex]f(n)[/tex] that can give us the number of factors of an integer number [tex]n[/tex], then we know that the mirroring will occur after we get the [tex](\left\lceil\frac{f(n)}{2}\right\rceil)[/tex]-th factor.

    But, there is no such a function, right?

    Best regards,
    Eus
     
  7. Nov 26, 2007 #6

    Gib Z

    User Avatar
    Homework Helper

    Of course there is such a function, you just defined it.
     
  8. Nov 26, 2007 #7

    CRGreathouse

    User Avatar
    Science Advisor
    Homework Helper

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

    Then [itex]\omega(n)=k[/itex], [itex]\Omega(n)=a_1+a_2+\cdots+a_k[/itex], and [itex]\sigma_0(n)=(a_1+1)(a_2+1)\cdots(a_k+1)[/itex]. 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, [itex]\sqrt{24}\approx4.9[/itex] and the mirror is between 4 and 6.
     
  9. Nov 26, 2007 #8
    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.
     
  10. Nov 26, 2007 #9

    CRGreathouse

    User Avatar
    Science Advisor
    Homework Helper

    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.
     
  11. Nov 27, 2007 #10

    Eus

    User Avatar

    Thank you very much for pointing out that the mirroring will happen approximately after finding the ([itex]\sqrt{n}[/itex])-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 [itex]n[/itex].

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

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

    Regards,
    Eus
     
    Last edited: Nov 27, 2007
  12. Nov 28, 2007 #11

    CRGreathouse

    User Avatar
    Science Advisor
    Homework Helper

    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 [itex]\omega(12)=2[/itex] but [itex]\Omega(12)=3[/itex].

    [tex]\omega(1024) = 1, \Omega(1024) = 10[/tex] since 1024 = 2^10.
     
  13. Nov 28, 2007 #12

    CRGreathouse

    User Avatar
    Science Advisor
    Homework Helper

    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.
     
    Last edited: Nov 28, 2007
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?



Similar Discussions: The limit of a factoring algorithm
Loading...