mersenneforum.org  

Go Back   mersenneforum.org > Extra Stuff > Miscellaneous Math

Reply
 
Thread Tools
Old 2010-05-25, 23:50   #1
3.14159
 
3.14159's Avatar
 
May 2010
Prime hunting commission.

24·3·5·7 Posts
Default 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
3.14159 is offline   Reply With Quote
Old 2010-05-26, 00:08   #2
3.14159
 
3.14159's Avatar
 
May 2010
Prime hunting commission.

24×3×5×7 Posts
Default

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
3.14159 is offline   Reply With Quote
Old 2010-05-26, 00:22   #3
Mini-Geek
Account Deleted
 
Mini-Geek's Avatar
 
"Tim Sorbera"
Aug 2006
San Antonio, TX USA

22×11×97 Posts
Default

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 Mini-Geek on 2010-05-26 at 00:33
Mini-Geek is offline   Reply With Quote
Old 2010-05-26, 00:29   #4
3.14159
 
3.14159's Avatar
 
May 2010
Prime hunting commission.

24×3×5×7 Posts
Default

"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 is offline   Reply With Quote
Old 2010-05-26, 00:31   #5
3.14159
 
3.14159's Avatar
 
May 2010
Prime hunting commission.

24×3×5×7 Posts
Default

"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
3.14159 is offline   Reply With Quote
Old 2010-05-26, 00:39   #6
3.14159
 
3.14159's Avatar
 
May 2010
Prime hunting commission.

110100100002 Posts
Default

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
3.14159 is offline   Reply With Quote
Old 2010-05-26, 00:52   #7
Mini-Geek
Account Deleted
 
Mini-Geek's Avatar
 
"Tim Sorbera"
Aug 2006
San Antonio, TX USA

22×11×97 Posts
Default

Quote:
Originally Posted by 3.14159 View Post
"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.

Last fiddled with by Mini-Geek on 2010-05-26 at 00:55
Mini-Geek is offline   Reply With Quote
Old 2010-05-26, 01:18   #8
3.14159
 
3.14159's Avatar
 
May 2010
Prime hunting commission.

69016 Posts
Default

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 2010-05-26 at 01:33
3.14159 is offline   Reply With Quote
Old 2010-05-26, 01:43   #9
3.14159
 
3.14159's Avatar
 
May 2010
Prime hunting commission.

24·3·5·7 Posts
Default

As for the amount of primes below 39589473005437955949718714361898237409951, it's approximately 428089723375425820660149427320848300794. (Based on x/(ln(x)-1) )
3.14159 is offline   Reply With Quote
Old 2010-05-26, 02:34   #10
Mini-Geek
Account Deleted
 
Mini-Geek's Avatar
 
"Tim Sorbera"
Aug 2006
San Antonio, TX USA

22×11×97 Posts
Default

Quote:
Originally Posted by 3.14159 View Post
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 View Post
(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 View Post
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))#
Mini-Geek is offline   Reply With Quote
Old 2010-05-26, 03:12   #11
3.14159
 
3.14159's Avatar
 
May 2010
Prime hunting commission.

24×3×5×7 Posts
Default

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.
3.14159 is offline   Reply With Quote
Reply

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

All times are UTC. The time now is 07:20.


Tue Oct 19 07:20:55 UTC 2021 up 88 days, 1:49, 0 users, load averages: 1.34, 0.99, 1.04

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2021, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.