Results 1 to 6 of 6

Math Help - Worst case for prime factorisation

  1. #1
    Junior Member
    Joined
    Jul 2008
    Posts
    28

    Worst case for prime factorisation

    Many places tell me that n=pq with p,q distinct and near to the square root of n is the worst case in terms or arithmetic operations needed to factorise n completely. Why is this?
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Super Member Bacterius's Avatar
    Joined
    Nov 2009
    From
    Wellington
    Posts
    927
    There are lots of methods. Here are some :

    - Trial division : try to divide n by a number between 2 and \sqrt{n}. It is always a worst case since any number can be picked.

    - Fermat's factorization algorithm : note that if you set n = pq with p = (a - b) and q = (a + b), then it becomes n = (a - b)(a + b) or n = a^2 - b^2. It becomes clear that the nearer a prime factor is from the square root of n, the easier the algorithm becomes. However, if a prime factor is very small, then this algorithm is possibly the worst ever.

    - Linear sieve : start from p = 2, and try divisions by increasing p by 1 each time. The worst case will be if p = \sqrt{n}. That must be your point.

    There are lots of better methods, like the quadratic sieve or general number field sieve, but I'm not really good at explaining them so I will let Wikipedia do it

    The worst case for factoring semiprimes in terms of arithmetic complexity really depends on the method used.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Junior Member
    Joined
    Jul 2008
    Posts
    28
    Quote Originally Posted by Bacterius View Post
    There are lots of methods. Here are some :

    - Trial division : try to divide n by a number between 2 and \sqrt{n}. It is always a worst case since any number can be picked.

    - Fermat's factorization algorithm : note that if you set n = pq with p = (a - b) and q = (a + b), then it becomes n = (a - b)(a + b) or n = a^2 - b^2. It becomes clear that the nearer a prime factor is from the square root of n, the easier the algorithm becomes. However, if a prime factor is very small, then this algorithm is possibly the worst ever.

    - Linear sieve : start from p = 2, and try divisions by increasing p by 1 each time. The worst case will be if p = \sqrt{n}. That must be your point.

    There are lots of better methods, like the quadratic sieve or general number field sieve, but I'm not really good at explaining them so I will let Wikipedia do it

    The worst case for factoring semiprimes in terms of arithmetic complexity really depends on the method used.
    I was sure I'd put it in there - sorry about that. The method being used is trial division.

    So you're saying n=pg with pq close together is the worst case since if you pick numbers randomly to try, you're unlikely to get within that ball park which will give you the right answer?

    But then, why does this take longer than n=pqr for instance?
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Super Member Bacterius's Avatar
    Joined
    Nov 2009
    From
    Wellington
    Posts
    927
    No, in trial division, the worst case is any number, since you are equally likely to pick the right number.

    It takes longer than n = pqr because in n = pq, there are two prime factors only, and in n = pqr, there are three, so you have a bit more chance of finding the right number.

    -----------------------

    In trial division, you are looking for q = \frac{n}{p}, with p < q. It is necessary that p < \sqrt{n}, thus.
    Basically, you just pick random numbers between 2 and \sqrt{n}, until you fall on a number that divides n. At this moment, you know you found p, and you can find q easily.
    Last edited by Bacterius; December 15th 2009 at 03:42 AM.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Super Member

    Joined
    May 2006
    From
    Lexington, MA (USA)
    Posts
    11,811
    Thanks
    701
    Hello, phillips101!

    Many places tell me that n=pq with p,q distinct primes and near to \sqrt{n}
    is the worst case in terms of arithmetic operations needed to factor n completely.
    Why is this?

    If the two prime factors are both near to \sqrt{n},
    . . then the two factors are almost equal.
    This makes our search much longer.


    I'll illustrate with an example.


    Find the factors of 2,108,303.

    So we divide by consecutive primes to look for factors.

    We divide by 2, 3, 5, 7, 11, 13, 17, 19, ... and none "come out even".

    So we keep trying: 991, 997, 1009, 1013, 1019, 1021, 1031 . . . nope!

    By now I'd suspect that the number is prime, but we keep going:
    . . divide by 1033, 1039, 1049, 1061, ... 1447 . . . still no luck!


    Then we find that: . 2,\!108,\!303 \div 1451 \:=\:1453

    . . That is: . 2,\!108,\!303 \;=\;1451\cdot 1453 . . . There!


    We found the factors, but it took us 230 divisions to find it.

    Follow Math Help Forum on Facebook and Google+

  6. #6
    Super Member Bacterius's Avatar
    Joined
    Nov 2009
    From
    Wellington
    Posts
    927
    It really depends on the method used. For example, if I used Soroban's number on the Fermat method, it would have taken only one operation
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. sorting of unordered elements - worst case scenario
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: January 7th 2012, 08:24 AM
  2. gaussian prime factorisation
    Posted in the Number Theory Forum
    Replies: 4
    Last Post: October 6th 2011, 09:38 PM
  3. Need help understanding prime factorisation
    Posted in the Number Theory Forum
    Replies: 3
    Last Post: February 20th 2011, 12:38 PM
  4. prime factorisation
    Posted in the Algebra Forum
    Replies: 3
    Last Post: September 6th 2009, 06:06 AM
  5. Unique Prime factorisation
    Posted in the Number Theory Forum
    Replies: 0
    Last Post: October 12th 2008, 03:08 PM

Search Tags


/mathhelpforum @mathhelpforum