Jump to content
  • Advertisement
Sign in to follow this  
Nice Coder

Factorization of massive numbers.

This topic is 5438 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

I have recently discovered a technique for the factorization of giant RSA keys. These keys only have two factors: Q and P. I can exploit this to my advantage. Instead of checking numbers by checking if N % 2 == 0, then N % 3 ==0, ect. I have thought of another way. The way I discovered this is by looking at multiplication, a number at place N does not effect any digit in that number below place N. So, what you would do is get a list of combinations (which are two numbers, as explained later), then with the list of combinations, you do the following: You “grow” them and You cull them. And you keep repeating until you find some combination which, when multiplied together gives the number your factorizing. When growing the list, you add all the numbers from 0-9 in * Front * of the number, eg. If you were growing the combination 12345 * 2345, you would end up with: 012345 * 02345 012345 * 12345 012345 * 22345 012345 * 32345 Ect. 112345 * 02345 112345 * 12345 Ect. When culling, for each combination of numbers, you multiply the two numbers together. You then check: Where P is one number of the combination Where Q is the other number of the combination Where N is the length of P * Q Where X is the number to be factorized. If the lower N-1 digits of X are equal to the N-1 digits of (P * Q) then it passes this test. By using this test, you remove all the combinations which CANNOT be part of the combination which yields the solution because its lower numbers are not correct. This way, you are working out the solution a digit at a time, and much faster then trying a brute force factorization (because you disregard many “blood-lines” of numbers which could not be the answer, while the search would keep searching until it either hits on the answer, or get to sqr(n). I hope this post is readable (and understandable), its very late here. From, Nice coder

Share this post


Link to post
Share on other sites
Advertisement
Guest Anonymous Poster
Fine, now factorize 862753102367816937963267483951819444767 using your method. How many steps do you need?

Share this post


Link to post
Share on other sites
ok, i've been looking at using tables to improve the efficiency of the growing step.
Say you were factorizing 137145781943.

You would look up in a table all the numbers, which when multed end in 3. you then add those into the table (and store the carry)

So now, for each number when growing,
look at digit at N + 1, (where N is last digit that you did).

Get that digit, Subtract your carry from that digit, you would then lookup the table, and then for each digit found you would add it to your list (as per before)

I'm currently making the lists, once i'm finished maybe i'll factorize 137145781943. (onlly 6 iterations needed!)

From,
Nice coder

Share this post


Link to post
Share on other sites
Factorization of 137145781943.

Here are the lists

Multiplication list 1- Possible numbers

0: { 0:0 0:1 0:2 0:3 0:4 0:5 0:6 0:7 0:8 0:9 1:0 2:0 2:5 3:0 4:0 4:5 5:0 5:2 5:4 5:6 5:8 6:0 6:5 7:0 8:0 8:5 9:0 }
1: { 1:1 3:7 7:3 9:9 }
2: { 1:2 2:1 2:6 3:4 4:3 4:8 6:2 6:7 7:6 8:4 8:9 9:8 }
3: { 1:3 3:1 7:9 9:7 }
4: { 1:4 2:2 2:7 3:8 4:1 4:6 6:4 6:9 7:2 8:3 8:8 9:6 }
5: { 1:5 3:5 5:1 5:3 5:5 5:7 5:9 7:5 9:5 }
6: { 1:6 2:3 2:8 3:2 4:4 4:9 6:1 6:6 7:8 8:2 8:7 9:4 }
7: { 1:7 3:9 7:1 9:3 }
8: { 1:8 2:4 2:9 3:6 4:2 4:7 6:3 6:8 7:4 8:1 8:6 9:2 }
9: { 1:9 3:3 7:7 9:1 }





Multiplication list 2- Carries

0 X 0 = 0
0 X 1 = 0
0 X 2 = 0
0 X 3 = 0
0 X 4 = 0
0 X 5 = 0
0 X 6 = 0
0 X 7 = 0
0 X 8 = 0
0 X 9 = 0
1 X 0 = 0
1 X 1 = 0
1 X 2 = 0
1 X 3 = 0
1 X 4 = 0
1 X 5 = 0
1 X 6 = 0
1 X 7 = 0
1 X 8 = 0
1 X 9 = 0
2 X 0 = 0
2 X 1 = 0
2 X 2 = 0
2 X 3 = 0
2 X 4 = 0
2 X 5 = 1
2 X 6 = 1
2 X 7 = 1
2 X 8 = 1
2 X 9 = 1
3 X 0 = 0
3 X 1 = 0
3 X 2 = 0
3 X 3 = 0
3 X 4 = 1
3 X 5 = 1
3 X 6 = 1
3 X 7 = 2
3 X 8 = 2
3 X 9 = 2
4 X 0 = 0
4 X 1 = 0
4 X 2 = 0
4 X 3 = 1
4 X 4 = 1
4 X 5 = 2
4 X 6 = 2
4 X 7 = 2
4 X 8 = 3
4 X 9 = 3
5 X 0 = 0
5 X 1 = 0
5 X 2 = 1
5 X 3 = 1
5 X 4 = 2
5 X 5 = 2
5 X 6 = 3
5 X 7 = 3
5 X 8 = 4
5 X 9 = 4
6 X 0 = 0
6 X 1 = 0
6 X 2 = 1
6 X 3 = 1
6 X 4 = 2
6 X 5 = 3
6 X 6 = 3
6 X 7 = 4
6 X 8 = 4
6 X 9 = 5
7 X 0 = 0
7 X 1 = 0
7 X 2 = 1
7 X 3 = 2
7 X 4 = 2
7 X 5 = 3
7 X 6 = 4
7 X 7 = 4
7 X 8 = 5
7 X 9 = 6
8 X 0 = 0
8 X 1 = 0
8 X 2 = 1
8 X 3 = 2
8 X 4 = 3
8 X 5 = 4
8 X 6 = 4
8 X 7 = 5
8 X 8 = 6
8 X 9 = 7
9 X 0 = 0
9 X 1 = 0
9 X 2 = 1
9 X 3 = 2
9 X 4 = 3
9 X 5 = 4
9 X 6 = 5
9 X 7 = 6
9 X 8 = 7
9 X 9 = 8




The factorisation may take some time... (and be quite big, hand factorization takes quite some time)

From,
Nice coder

Share this post


Link to post
Share on other sites
What's the worst-case storage requirement for your algorithm?
What's the worst-case time requirement for your algorithm?

Share this post


Link to post
Share on other sites
Quote:
Original post by Anonymous Poster
Fine, now factorize 862753102367816937963267483951819444767 using your method. How many steps do you need?


28758436745593897932108916131727 and 3 are the factors found.

Share this post


Link to post
Share on other sites
Guest Anonymous Poster
It amazes me how little credit people give the hundreds of great mathematicians who have put their minds into this kind of problems during the centuries. If it really was that easy, don't you think it would have been done already?


As for the factorization of 137145781943:

Number of 1-digit combinations whose product ends with 3:
2
Number of 2-digit combinations whose product ends with 43:
20
Number of 3-digit combinations whose product ends with 943:
200
Number of 4-digit combinations whose product ends with 1943:
2000
Number of 5-digit combinations whose product ends with 81943:
20000
Number of 6-digit combinations whose product ends with 781943:
200000

As you can see, the number of combinations you need to examine grows with a factor of 10 for every additional digit. This is no better than to simply divide 137145781943 by all numbers ending with 1 or 7 until you find the right one.

Share this post


Link to post
Share on other sites
Guest Anonymous Poster
Quote:
Original post by Nice Coder
28758436745593897932108916131727 and 3 are the factors found.

Nice, the only problem is, 28758436745593897932108916131727 * 3 = 86275310236781693796326748395181, not 862753102367816937963267483951819444767.

Share this post


Link to post
Share on other sites
Quote:
Original post by Nice Coder
... by checking if N % 2 == 0, then N % 3 ==0, ect. I have thought of another way ...


The methods for factorization are infinitely more complex than that. The factors P and Q are chosen as 'random' and giant prime numbers. Roughly so that log(P) and log(Q) are 0.5*log(N). (Additionnaly log(P) and log(Q) must not be too close too.

So for sure you would never have N%3=0 because someone experienced could detect 3 is a factor mentally and your computer would crack the RSA in one micro second since the modulo operator for small ints is linear to the number of bits in N.

True RSA keys can not be broken in one human life span by a single computer with the currently known algos.

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

GameDev.net is your game development community. Create an account for your GameDev Portfolio and participate in the largest developer community in the games industry.

Sign me up!