Finding out which prime factors a integer is made up by

[ull]

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 divide 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

 

[mfb]

Now the prime number 3 is ruled out as a possible prime factor of 8750
4375/5 = 875

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

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?

You can stop earlier: at the square root of the last number you got. Suppose x is divisible by y where y²>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.

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

Yes it will. It is a very slow, but reliable way to find all prime factors.

 

[ull]

Is the faster ways of finding prime factors less reliable? If so, in what sense?

 

[Boorglar]

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

 

[mfb]

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.

 

[ull]

You can stop earlier: at the square root of the last number you got.

If the square root of the last number isn't an prime number (quadrat/"perfect square") then the last number must be a prime?

 

[Number Nine]

If the square root of the last number isn't an prime number (quadrat/"perfect square") then the last number must be a prime?

What would happen if $p$ had no proper prime divisors less than $\sqrt{p}$? What would its factorization look like?

 

[mesa]

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.

Even faster than that,
http://www.alpertron.com.ar/ECM.HTM

 

[mfb]

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.

 

[mesa]

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.

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!