Results 1 to 6 of 6

Math Help - Integer factorization

  1. #1
    Member
    Joined
    Jun 2008
    Posts
    148

    Integer factorization

    Is there a way to determine whether a given integer 'n' is divisible by any of the primes from 2-97, which can be determined faster than calculating gcd(2*3*5...*97, n)? Assume n is not bounded.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Global Moderator

    Joined
    Nov 2005
    From
    New York City
    Posts
    10,616
    Thanks
    10
    Quote Originally Posted by jamix View Post
    Is there a way to determine whether a given integer 'n' is divisible by any of the primes from 2-97, which can be determined faster than calculating gcd(2*3*5...*97, n)? Assume n is not bounded.
    If you are doing a computer program then I think it would be faster to tell the computer to calculate gcd(2,n),gcd(3,n), ... , gcd(97,n) and stop if it reaches a non-unit answer. That will tell you if the number if divisible or is it.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Member
    Joined
    Jun 2008
    Posts
    148
    Good point. That would be faster because it would halt right after we've found one prime factor (and half the time n would be divisible by 2).

    Let me change the question. Determine the largest prime (if any) among 2-97 that divides arbitrary chosen integer n, that can be determined faster (on the average) than calculating the following:

    gcd(97,n), then gcd(89,n), then gcd(83,n) and so forth until prime factor is found.

    Hint: Think about some elementary factoring methods out there. Which method(s) are particularly fast at find smaller prime factors.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Super Member
    Joined
    Jan 2009
    Posts
    591
    Quote Originally Posted by jamix View Post
    Good point. That would be faster because it would halt right after we've found one prime factor (and half the time n would be divisible by 2).

    Let me change the question. Determine the largest prime (if any) among 2-97 that divides arbitrary chosen integer n, that can be determined faster (on the average) than calculating the following:

    gcd(97,n), then gcd(89,n), then gcd(83,n) and so forth until prime factor is found.

    Hint: Think about some elementary factoring methods out there. Which method(s) are particularly fast at find smaller prime factors.
    Starting with the lower primes (2,3,5...) will generally yield a solution faster than starting at the higher end (97,89,83,...)

    If your computer can handle the number then calculate 1 time and use:
    2*3*5*7*11* ... *79*83*89*97
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Member
    Joined
    Jun 2008
    Posts
    148
    It won't be faster. Remember I'm asking for the LARGEST prime factor in the set (2,97). If we start at 2, then we would have to test every single prime in the above set. If we start at 97, we can halt as soon as the first prime factor is found.

    There are 25 primes from 2-97. I say start by calculating gcd(n,37*41*43*47*....97). This is the gcd of n with the largest 12 primes (the bigger half). If this equals 1, then repeat using smaller half of primes 2-31. Otherwise break the primes 37-97 into two half's and repeat this process starting with larger half (ie gcd(n, 71*....*97).
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Super Member
    Joined
    Jan 2009
    Posts
    591
    Quote Originally Posted by jamix View Post
    It won't be faster. Remember I'm asking for the LARGEST prime factor in the set (2,97). If we start at 2, then we would have to test every single prime in the above set. If we start at 97, we can halt as soon as the first prime factor is found.

    There are 25 primes from 2-97. I say start by calculating gcd(n,37*41*43*47*....97). This is the gcd of n with the largest 12 primes (the bigger half). If this equals 1, then repeat using smaller half of primes 2-31. Otherwise break the primes 37-97 into two half's and repeat this process starting with larger half (ie gcd(n, 71*....*97).
    Try this:

    Start at some number, say 987654321.
    Then search increasing (from 2) and decreasing (from 97).
    Do this for a few hundred thousand numbers and see which is faster?
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Integer factorization
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: March 27th 2011, 09:34 AM
  2. Replies: 13
    Last Post: August 3rd 2010, 04:16 AM
  3. [Factorization] Factorization of polynomials
    Posted in the Algebra Forum
    Replies: 9
    Last Post: April 9th 2010, 01:15 AM
  4. Replies: 2
    Last Post: March 4th 2010, 02:49 AM
  5. Raise integer to positive integer power
    Posted in the Algebra Forum
    Replies: 2
    Last Post: May 21st 2009, 01:20 PM

Search Tags


/mathhelpforum @mathhelpforum