20100525, 23:50  #1 
May 2010
Prime hunting commission.
2^{4}·3·5·7 Posts 
A (very) weak factoring method.
I stumbled upon a rather inefficient but effective way to factor an integer, using GCDs. Here's it: (It's basically trial division, but using GCDs.)
Suppose you have a probable prime (For the sake of being quick, I shall use an obvious composite.) I'll use.. 77. Step 1: Choose an even integer. Try 38. gcd(77, 38) = ? 77 mod 38 = 1 38 * 2 + 1 = 77 = gcd(38, 1) = 1. Therefore gcd(77, 38) = 1. Step 2: Choose number divisible by three. Repeat. gcd(77, 39) = ? 77 mod 39 = 38 39 * 1 + 38 = 77 = gcd(39, 38) = 1 Therefore gcd(77, 39) = 1. Step 3: Skip 5, number obviously not a factor of 5. Step 4: Choose number divisible by 7. gcd(77, 56) = ? 77 mod 56 = 21 56 * 1 + 21 = 77 = gcd(56, 21) 56 mod 21 = 14 21 * 2 + 14 = 56 = gcd(21, 14) 21 mod 14 = 7 14 * 1 + 7 = 21 = gcd(14, 7) 14 mod 7 = 0 7 * 2 = 14 End result is divisible by 7. Therefore, gcd(77, 56) = 7 77's factor found: 7. 77/7 = 11. Hopefully the members don't decide to do the following: (To make a lame pun.) Last fiddled with by 3.14159 on 20100525 at 23:58 
20100526, 00:08  #2 
May 2010
Prime hunting commission.
2^{4}×3×5×7 Posts 
Another function it has.
Example: Factoring 127. Step 1: Again, choose an even integer. gcd(127, 88) 127 mod 88 = 39. 88 * 1 + 39 = 127 = gcd(88, 39) 88 mod 39 = 10 39 * 2 + 10 = 88 = gcd(39, 10) 39 mod 10 = 9 10 * 3 + 9 = 39 = gcd(10, 9) 10 mod 9 = 1 9 * 1 + 1 = 10 = gcd(9, 1) = 1 gcd(127, 88) = 1 Step 2: Choose integer divisible by 3. gcd(127, 69) 127 mod 69 = 58 69 * 1 + 58 = 127 = gcd(69, 58) 69 mod 58 = 11 58 * 1 + 11 = 69 = gcd(58, 11) 11 = prime number. Therefore gcd(58, 11) = 1 gcd(127, 69) = 1. Step 3: Skip 5, 127 is obviously not divisible by 5. Step 4: Choose integer divisible by 7. gcd(127, 84) = 127 mod 84 84 * 1 + 43 = 127 = gcd(84, 43) 43 = prime number. Therefore gcd(84, 43) = 1 Therefore gcd(127, 84) = 1 Step 5: Choose integer divisible by 11. gcd(127, 99) 127 mod 99 = 28 99 * 1 + 28 = 127 = gcd(99, 28) 99 mod 28 = 15. 28 * 3 + 15 = 99 = gcd(28, 15) 28 mod 15 = 13 15 * 1 + 13 = 28 = gcd(15, 13) 13 = prime number. Therefore gcd(15, 13) = 1 Therefore gcd(127, 99) = 1 No factor able to be found for 127. 127 is prime. QED. A question that will likely arise: Why skip 5, when I could have also skipped 2 and 3? 5 scares me. Last fiddled with by 3.14159 on 20100526 at 00:17 
20100526, 00:22  #3 
Account Deleted
"Tim Sorbera"
Aug 2006
San Antonio, TX USA
11·389 Posts 
I'm glad you at least realize it's basically trial division. For comparison, I'll find 77's factorization using basic trial division (skipping even numbers):
77/3 is not whole. (as calculated by hand, a computer, or this simple trick) 77/5 is not whole. (as is easily seen by it ending in 7 instead of 0 or 5) 77/7=11, so 77=7*11. 7 is prime since it was the first odd number to divide 77, and 11 is trivially prime. Therefore we have found the prime factorization of 77: 7*11. Quite a bit easier, eh? The only advantage your method has is that it can check for several factors at once. e.g. when you do gcd(77,39), you're not only checking for divisibility by 3, but also by 13 (3*13=39). Or, if you had tried gcd(77, 7#), you'd find if 2 through 7 are factors, in getting their product with at most one power (in this case just find that 7 is a factor): gcd(77,210)= gcd(77,56)= gcd(21,56)= gcd(21,14)= gcd(7,14)= 7 It is not remarkable that you can prove primality by calculating that those several gcd's are 1. It's simply a roundabout trial division. Sure it's fast for 127, (so is normal trial division) but try that for, say, a 60 digit number. Actually, I'll give you a hint: don't, you won't be able to in your lifetime (just like normal trial division...but even slower). You could prove 127 is prime, considering 13^2 is larger than 127, by showing that gcd(127,13#) is 1. (if the number N we're testing is composite, this gcd will return a factor; it will be N itself, which is still a factor, if all prime factors of N are below 14 and not raised to a power above 1) gcd(127,30030)= gcd(127,58)= gcd(11,58)= gcd(11,3)= gcd(2,3)= gcd(2,1)= 1 I think this is faster than dividing, but it takes much more memory (to test a 7 bit number we need to deal with a 15 bit one, and know all primes up to the square root of the number to prove prime, which becomes impractical after a few digits). Last fiddled with by TimSorbet on 20100526 at 00:33 
20100526, 00:29  #4 
May 2010
Prime hunting commission.
2^{4}×3×5×7 Posts 
"The only advantage your method has is that it can check for several factors at once. e.g. when you do gcd(77,39), you're not only checking for divisibility by 3, but also by 13 "
Sadly, I did not notice that. Hey, that beings an idea! I just test it for sqrt(n)#, omitting the decimal in the sqrt. And.. Isn't 7# = 510510? 2*3*5*7*11*13*17 = First 7 primes = 7# = 510510? Primorial = Wordplay on factorial. Factorial = The products of the first n positive integers. 
20100526, 00:31  #5 
May 2010
Prime hunting commission.
2^{4}×3×5×7 Posts 
"I think this is faster than dividing, but it takes much more memory (to test a 7 bit number we need to deal with a 15 bit one, and know all primes up to the square root of the number to prove prime, which becomes impractical after a few digits)."
Dude, no. Consider the massive amount of steps you would need for each individual prime out of.. The amount of primes preceding the prime number 39589473005437955949718714361898237409951, (There are about 10^18 or 10^19 preceding 10^23, if I'm not mistaken) whenever you were faced with let's say.. a c120 whose smallest prime factor was 39589473005437955949718714361898237409951. The amount of steps and time needed would be perhaps several orders of magnitude higher than trial division. Last fiddled with by 3.14159 on 20100526 at 00:33 
20100526, 00:39  #6 
May 2010
Prime hunting commission.
2^{4}×3×5×7 Posts 
And it would be hopeless trying to look for the product of the first 10^55 or so primes. O_O
Last fiddled with by 3.14159 on 20100526 at 00:40 
20100526, 00:52  #7  
Account Deleted
"Tim Sorbera"
Aug 2006
San Antonio, TX USA
11×389 Posts 
Quote:
To find a 41 digit factor with either method, you'd need to search all primes up to about 10^41 (assuming we're trying to find that 41 digit factor in the c120, not proving the discovered 41 digit factor is prime...which is half as impossible). There are about 1.07*10^39 primes below 10^41. For normal trial division, you'd never have to work with numbers larger than 10^41, but you'd have to do c120/p for 1.07*10^39 primes. With the GCD method, you'd need to do gcd(c120,(1.07*10^39)#). So first you have to find the 1.07*10^39 primes below 10^41. And then you'd have to be able to hold them all in memory at once, and do a gcd on that. Good luck. Last fiddled with by TimSorbet on 20100526 at 00:55 

20100526, 01:18  #8 
May 2010
Prime hunting commission.
2^{4}·3·5·7 Posts 
Hmm, you are correct, to an extent: Let's say I wanted to factor 69871 (107 * 653), using the GCD. I would just use 2*3*5*7*...*263, since sqrt(69871) is closest to 263 (263^2 = 69169). So in this case, the gcd would be (263, (number of primes less than or equal to 263)#)
Last fiddled with by 3.14159 on 20100526 at 01:33 
20100526, 01:43  #9 
May 2010
Prime hunting commission.
2^{4}×3×5×7 Posts 
As for the amount of primes below 39589473005437955949718714361898237409951, it's approximately 428089723375425820660149427320848300794. (Based on x/(ln(x)1) )

20100526, 02:34  #10  
Account Deleted
"Tim Sorbera"
Aug 2006
San Antonio, TX USA
1000010110111_{2} Posts 
Quote:
There's a shorthand for that: pi(263). That's pi the prime counting function, not related to pi the number. You need to do the gcd of 69871 and 263#, not of 263 and (pi(263))#. x# (primorial of x) denotes the product of all primes less than or equal to x, so you want 263#, not (pi(263))# 

20100526, 03:12  #11 
May 2010
Prime hunting commission.
2^{4}·3·5·7 Posts 
Primorial: Product of the first n primes. 5# = 2*3*5*7*11 = 2310.
263# would in fact be 2*3*5*7*11*...*1669. 
Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
Help with series convergence in Fermat method of factoring  EdH  Other Mathematical Topics  52  20210129 21:17 
A stupid factoring method  JM Montolio A  Miscellaneous Math  11  20180228 11:29 
Factoring "weak" RSA moduli  Nooby  Factoring  30  20170808 13:04 
Another factoring method rides the bus  3.14159  Factoring  233  20110515 18:50 
Is this a feasible factoring method?  1260  Miscellaneous Math  46  20100531 17:37 