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

Finding out which prime factors a integer is made up by

  1. Aug 9, 2013 #1

    ull

    User Avatar

    Is this line of thought correct? Please correct me where I´m wrong.

    Will this way of finding prime factors work when A is any integer?

    Is there a proof for this or a proof that is closely related?

    Is there a way to do it that requiers less iterations? It has to be a method that requires no intelligence ;)

    A = any integer
    B = prime number

    If A / B is evenly divisible then B is a prime factor of A

    The first time A is devided by 2, then 3, 5, 7, 11....

    Example:
    2*5*5*5*5*7 = 8750 = A
    8750/2= 4375
    4375/3 is not an integer
    Now the prime number 3 is ruled out as a possible prime factor of 8750
    4375/5 = 875
    875/7 = 125
    125/11 is not an integer
    Now the prime number 11 is ruled out as a possible prime factor of 8750
    125/13 is not an integer
    Now the prime number 13 is ruled out as a possible prime factor of 8750
    ...............
    The ratio is not an integer
    Now the prime number n is ruled out as a possible prime factor of 8750
    ...............
    The next prime, 67, is greater than 125/2. Can you still find the prime factors if you stop deviding before prime number n is greater than the last ratio that was an integer?

    We have found the greatest prime factor that 8750 is made up by and some of the rest but not all of them since the ratio isn´t 1. So far we have found 2,5 and 7

    125/2 is not an integer
    Now the prime number 2 is ruled out as a possible prime factor of 8750
    We have already ruled out 3 and there is no need to devide by it again
    125/5 = 25
    25/7 is not an integer
    Now the prime number 7 is ruled out as a possible prime factor of 8750
    25/5 = 5
    5/5 = 1
    Now we have found all prime factors that 8750 is made up by. They are 2,5,5,5,5 and 7
     
    Last edited: Aug 9, 2013
  2. jcsd
  3. Aug 9, 2013 #2

    mfb

    User Avatar
    2016 Award

    Staff: Mentor

    Don't stop there, keep testing 5:
    875/5=175
    175/5=35
    35/5=7
    Done.

    You can stop earlier: at the square root of the last number you got. Suppose x is divisible by y where y2>x. Call this z: z=x/y. Then z < y and you would have found a smaller factor.

    As an example, you will never have to test if 143 is divisible by 13 (it is): 143/13=11, so 143 is divisible by 11 as well (with 143/11=13), and that prime gets tested first.

    Yes it will. It is a very slow, but reliable way to find all prime factors.
     
  4. Aug 9, 2013 #3

    ull

    User Avatar

    Is the faster ways of finding prime factors less reliable? If so, in what sense?
     
  5. Aug 10, 2013 #4
    All prime factorization algorithms we know of so far are "slow" (in the sense that the time is not bound by a polynomial in the number of bits of the integer). The trial division approach (both up to n and up to sqrt(n) ) are exponential time, because the number of trials increases roughly exponentially in the number of bits of n.

    There are faster (and equally reliable) algorithms, which are much more involved mathematically and I don't know much about them, but even the best so far would take impractical amount of time to factor a 100-digit number. Here's wikipedia articles for more info:
    http://en.wikipedia.org/wiki/Trial_division
    http://en.wikipedia.org/wiki/Fermat's_factorization_method
    http://en.wikipedia.org/wiki/General_number_field_sieve (this one is supposedly the fastest yet)

    Interestingly, Shor has devised an integer factorization algorithm that can run in polynomial time on a quantum computer and will therefore be very fast. Such computers are not yet practical, but when technology becomes more advanced, this might become a threat to security systems based on RSA or similar cryptosystems.
    http://en.wikipedia.org/wiki/Shor's_algorithm
     
    Last edited: Aug 10, 2013
  6. Aug 10, 2013 #5

    mfb

    User Avatar
    2016 Award

    Staff: Mentor

    Elliptic curves are another method.
    You can find prime factors with 20-30 digits within seconds with those methods, where trial divisions (basically the method used in post 1) would need years to millions of years.
     
  7. Aug 10, 2013 #6

    ull

    User Avatar

    If the square root of the last number isnt an prime number (quadrat/"perfect square") then the last number must be a prime?
     
  8. Aug 10, 2013 #7
    What would happen if ##p## had no proper prime divisors less than ##\sqrt{p}##? What would its factorization look like?
     
  9. Aug 10, 2013 #8
    Even faster than that,
    http://www.alpertron.com.ar/ECM.HTM
     
  10. Aug 11, 2013 #9

    mfb

    User Avatar
    2016 Award

    Staff: Mentor

    That's where my time estimate comes from ;).

    If you want to try it yourself, here are some prime numbers with many digits:
    20: 29300536351978728173
    24: 344554212312423565743337
    28: 1310092062024424204347289397
    31: 2013759277103586006682274175401

    344554212312423565743337*2013759277103586006682274175401 (24 digits * 31 digits) gets factorized in 4 seconds.
    1310092062024424204347289397*2013759277103586006682274175401 (28 digits * 31 digits) gets factorized in 11 seconds.
     
  11. Aug 11, 2013 #10
    Hah!

    Finding composites does take longer, primes verification pops up in a fraction of a second for small values like these. It's a great website!
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook




Similar Discussions: Finding out which prime factors a integer is made up by
  1. Primes vs. integers (Replies: 7)

Loading...