Finding out which prime factors a integer is made up by

  • Thread starter ull
  • Start date
  • #1
ull
6
0

Main Question or Discussion Point

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:

Answers and Replies

  • #2
34,467
10,586
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 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.

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.
 
  • #3
ull
6
0
Is the faster ways of finding prime factors less reliable? If so, in what sense?
 
  • #4
210
10
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:
  • Like
Likes 1 person
  • #5
34,467
10,586
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.
 
  • Like
Likes 1 person
  • #6
ull
6
0
You can stop earlier: at the square root of the last number you got.
If the square root of the last number isnt an prime number (quadrat/"perfect square") then the last number must be a prime?
 
  • #7
806
23
If the square root of the last number isnt 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?
 
  • Like
Likes 1 person
  • #8
648
18
  • #9
34,467
10,586
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.
 
  • Like
Likes 1 person
  • #10
648
18
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!
 

Related Threads on Finding out which prime factors a integer is made up by

Replies
7
Views
545
Replies
2
Views
1K
  • Last Post
Replies
3
Views
689
  • Last Post
Replies
2
Views
2K
  • Last Post
Replies
7
Views
3K
Replies
10
Views
18K
  • Last Post
Replies
20
Views
9K
Replies
3
Views
356
Replies
3
Views
13K
Replies
2
Views
744
Top