A (very) weak factoring method.

3.14159 · 2010-05-25, 23:50

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.)

3.14159 · 2010-05-26, 00:08

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.

TimSorbet · 2010-05-26, 00:22

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).

3.14159 · 2010-05-26, 00:29

"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.

3.14159 · 2010-05-26, 00:31

"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.

3.14159 · 2010-05-26, 00:39

And it would be hopeless trying to look for the product of the first 10^55 or so primes. O_O

TimSorbet · 2010-05-26, 00:52

Quote:

Originally Posted by 3.14159

"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.

That prime is 41 digits. That's well out of reach of either standard trial division or your GCD trial division. Note also that I simply said faster than dividing, not faster than any current method of finding such a factor.
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.

3.14159 · 2010-05-26, 01:18

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)#)

3.14159 · 2010-05-26, 01:43

As for the amount of primes below 39589473005437955949718714361898237409951, it's approximately 428089723375425820660149427320848300794. (Based on x/(ln(x)-1) )

TimSorbet · 2010-05-26, 02:34

Quote:

Originally Posted by 3.14159

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).

Well, yeah, nothing there is wrong. Maybe I was saying something wrong earlier (I'll check later), or you misunderstood. But as the square root of the number you're searching grows, the number of primes you have to multiply together, and more importantly the size of their product, grows. This means that for large factorizations or primality checks, you have to have an impossibly large amount of memory, to hold the huge primorial.

Quote:

Originally Posted by 3.14159

(number of primes less than or equal to 263)

There's a shorthand for that: pi(263). That's pi the prime counting function, not related to pi the number.

Quote:

Originally Posted by 3.14159

So in this case, the gcd would be (263, (number of primes less than or equal to 263)#)

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))#

3.14159 · 2010-05-26, 03:12

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.

2010-05-25, 23:50	#1
3.14159 May 2010 Prime hunting commission. 3220₈ 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 2010-05-25 at 23:58

2010-05-26, 00:08	#2
3.14159 May 2010 Prime hunting commission. 2⁴×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 2010-05-26 at 00:17

2010-05-26, 00:22	#3
TimSorbet 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=711. 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: 711. 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 (313=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 2010-05-26 at 00:33*

2010-05-26, 00:31	#5
3.14159 May 2010 Prime hunting commission. 2⁴×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 2010-05-26 at 00:33

2010-05-26, 00:39	#6
3.14159 May 2010 Prime hunting commission. 2⁴·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 2010-05-26 at 00:40

2010-05-26, 00:29	#4
3.14159 May 2010 Prime hunting commission. 2⁴·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? 2357111317 = First 7 primes = 7# = 510510? Primorial = Wordplay on factorial. Factorial = The products of the first n positive integers.

2010-05-26, 01:18	#8
3.14159 May 2010 Prime hunting commission. 2⁴·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 2357...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 2010-05-26 at 01:33*

2010-05-26, 01:43	#9
3.14159 May 2010 Prime hunting commission. 2⁴·3·5·7 Posts	As for the amount of primes below 39589473005437955949718714361898237409951, it's approximately 428089723375425820660149427320848300794. (Based on x/(ln(x)-1) )

2010-05-26, 03:12	#11
3.14159 May 2010 Prime hunting commission. 2⁴×3×5×7 Posts	Primorial: Product of the first n primes. 5# = 235711 = 2310. 263# would in fact be 235711...1669.

Similar Threads
Thread	Thread Starter	Forum	Replies	Last Post
Help with series convergence in Fermat method of factoring	EdH	Other Mathematical Topics	52	2021-01-29 21:17
A stupid factoring method	JM Montolio A	Miscellaneous Math	11	2018-02-28 11:29
Factoring "weak" RSA moduli	Nooby	Factoring	30	2017-08-08 13:04
Another factoring method rides the bus	3.14159	Factoring	233	2011-05-15 18:50
Is this a feasible factoring method?	1260	Miscellaneous Math	46	2010-05-31 17:37