4 ms·

Integer factorization with rectangles, cubes and cuboids

2 points by marcookker 5y ago

marcookker 5y ago
When analysing fermat's integer factorization method, I found 3 new factorization methods, with rectangles, cubes and cuboids.
- ColinWright 5y ago
  Clickable: https://en.wikipedia.org/wiki/Fermat%27s_factorization_method#Factorization_with_rectangles https://en.wikipedia.org/wiki/Fermat%27s_factorization_metho... https://en.wikipedia.org/wiki/Fermat%27s_factorization_method#Factorization_with_cubes https://en.wikipedia.org/wiki/Fermat%27s_factorization_metho... https://en.wikipedia.org/wiki/Fermat%27s_factorization_method#Factorization_with_cuboids https://en.wikipedia.org/wiki/Fermat%27s_factorization_metho... However, it's not enough to just tell us that these are identities, to be useful you need to suggest ways of finding expressions of the form given in the LHS. It's easy with Fermat's method ... take a=ceil(sqrt(N)) and see if a^2-N is a square. If so, you're done. If not, add one to a and try again (there are significant improvements to be had by sieving and modular arguments). It's trivial to adapt this to the difference of cubes method, but that's much less likely to find a factorisation[0]. But how do I find expressions of the form (a+c)a-(b+c)b=N ?? In particular, how do I step through the pairs (a,c)? Similarly with the cuboids expression. Perhaps this is promising, but it needs some further insight beyond the expressions. [0] Citation needed
  - marcookker 5y ago
    Okay, I am not sure if this answers your question, but I discover the methods the following way: imagine 5*5 - 2*2: 00000 00000 00000 000 000 Now imagine (5+1)*5 - (2+1)*2: 000000 000000 000000 000 000 Now imagine (5+2)*5 - (2+2)*2: 0000000 0000000 0000000 000 000 The 3d version works the same, but than you must imagine a rubix cube(with 3*3*3 blocks), where 1 block is missing in the corner. Than you cut the part with the missing block(which are 3*3 - 1*1 blocks), and put it on top. This does not fit, because you have 2 blocks left over. These leftover blocks you cut again, after that you turn it around and put it on top of the complete block again. After that you can just roll the entire structure like a mat and you have a rectangle of 2*13. The cuboid version works like the cube version.
    - ColinWright 5y ago
      That doesn't help, and I wonder if it's because I didn't explain my question well enough. Suppose I have a number N and I want to try using the "Difference of Rectangles" method to factor it. So I want to find integers a, b, and c that satisfy this: (a+c)a-(b+c)b=N I'm going to assume that, as with standard Fermat factoring, I will choose values for a and c, compute (a+c)a-N, and then try to solve for b. If I succeed then I'm done. But how do I choose my initial values of a and c? And if I then can't solve for b, how do I choose my next values of a and c? I don't need visualisations, I know the algebra and can form my own pictures of what's going on. I need to know how the algorithm chooses a and c, and then how it proceeds when b doesn't exist.
    - marcookker 5y ago
      If you want to factorize 1649 for example, and we want to use c=1. What you do is you squareroot it first. The squareroot of 1649 is around 41. than you do (41+1)*41 = 73 MOD 1649. After that you find the factors of 73, 1 * 73= 73. Than you see that the difference of the numbers is 73-1 = 72. Let's look at the identity: (41+1)*41 - (1+72)*(1). Nope, 72 is not 1, so we don't have a match. Now we do (42+1)*42= 157 MOD 1649. Factorize number 157, 1 * 157 = 157. The difference of the numbers is 157-1 = 156. Again look at the identity: (42+1)*42 - (1+156)*(1). Nope, 156 is not 1, so we don't have a match. You keep doing this until you found a value of c and a where it is 1. After a time you get at 65: (65+1)*65 = 992 MOD 1649 992 = 31*32 32 - 31 = 1, we have a match! (65+1)*65 - (31+1) * 31 = (65-31) * (31+65+1) Now you want to find the factors of 1649, you do GCD(1649,(65-31)) = 17 GCD(1649, (31+65+1)) = 97 17*97 = 1649
      - ColinWright 5y ago
        But why should c=1 be the right value? Don't you want to be changing c as it goes? If not, why not? If so, then how do you change it? And then ... why should this method be any more successful than vanilla Fermat factoring?
        marcookker 5y ago
        Imagine you start a number that has many possible c's, for example 2*3*5*7*11*13*17*19*23*29*31*37*41*43*47*53*59*61*67*71 = 557940830126698960967415390 after that you do 557940830126698960967415390 MOD 1649. The number you are left with, has a bigger chance to have a c in it, that also is in 557940830126698960967415390.
ColinWright 5y ago
We've had a long exchange, but I still can't work out what your algorithm is in detail ... there are no contact details in your profile, so I'll just have to leave it with you to get in touch with me. See here: https://news.ycombinator.com/item?id=28978463 https://news.ycombinator.com/item?id=28978463

2 points by marcookker 5y ago

When analysing fermat's integer factorization method, I found 3 new factorization methods, with rectangles, cubes and cuboids.

ColinWright 5y ago
Clickable: https://en.wikipedia.org/wiki/Fermat%27s_factorization_method#Factorization_with_rectangles https://en.wikipedia.org/wiki/Fermat%27s_factorization_metho... https://en.wikipedia.org/wiki/Fermat%27s_factorization_method#Factorization_with_cubes https://en.wikipedia.org/wiki/Fermat%27s_factorization_metho... https://en.wikipedia.org/wiki/Fermat%27s_factorization_method#Factorization_with_cuboids https://en.wikipedia.org/wiki/Fermat%27s_factorization_metho... However, it's not enough to just tell us that these are identities, to be useful you need to suggest ways of finding expressions of the form given in the LHS. It's easy with Fermat's method ... take a=ceil(sqrt(N)) and see if a^2-N is a square. If so, you're done. If not, add one to a and try again (there are significant improvements to be had by sieving and modular arguments). It's trivial to adapt this to the difference of cubes method, but that's much less likely to find a factorisation[0]. But how do I find expressions of the form (a+c)a-(b+c)b=N ?? In particular, how do I step through the pairs (a,c)? Similarly with the cuboids expression. Perhaps this is promising, but it needs some further insight beyond the expressions. [0] Citation needed
- marcookker 5y ago
  Okay, I am not sure if this answers your question, but I discover the methods the following way: imagine 5*5 - 2*2: 00000 00000 00000 000 000 Now imagine (5+1)*5 - (2+1)*2: 000000 000000 000000 000 000 Now imagine (5+2)*5 - (2+2)*2: 0000000 0000000 0000000 000 000 The 3d version works the same, but than you must imagine a rubix cube(with 3*3*3 blocks), where 1 block is missing in the corner. Than you cut the part with the missing block(which are 3*3 - 1*1 blocks), and put it on top. This does not fit, because you have 2 blocks left over. These leftover blocks you cut again, after that you turn it around and put it on top of the complete block again. After that you can just roll the entire structure like a mat and you have a rectangle of 2*13. The cuboid version works like the cube version.
  - ColinWright 5y ago
    That doesn't help, and I wonder if it's because I didn't explain my question well enough. Suppose I have a number N and I want to try using the "Difference of Rectangles" method to factor it. So I want to find integers a, b, and c that satisfy this: (a+c)a-(b+c)b=N I'm going to assume that, as with standard Fermat factoring, I will choose values for a and c, compute (a+c)a-N, and then try to solve for b. If I succeed then I'm done. But how do I choose my initial values of a and c? And if I then can't solve for b, how do I choose my next values of a and c? I don't need visualisations, I know the algebra and can form my own pictures of what's going on. I need to know how the algorithm chooses a and c, and then how it proceeds when b doesn't exist.
  - marcookker 5y ago
    If you want to factorize 1649 for example, and we want to use c=1. What you do is you squareroot it first. The squareroot of 1649 is around 41. than you do (41+1)*41 = 73 MOD 1649. After that you find the factors of 73, 1 * 73= 73. Than you see that the difference of the numbers is 73-1 = 72. Let's look at the identity: (41+1)*41 - (1+72)*(1). Nope, 72 is not 1, so we don't have a match. Now we do (42+1)*42= 157 MOD 1649. Factorize number 157, 1 * 157 = 157. The difference of the numbers is 157-1 = 156. Again look at the identity: (42+1)*42 - (1+156)*(1). Nope, 156 is not 1, so we don't have a match. You keep doing this until you found a value of c and a where it is 1. After a time you get at 65: (65+1)*65 = 992 MOD 1649 992 = 31*32 32 - 31 = 1, we have a match! (65+1)*65 - (31+1) * 31 = (65-31) * (31+65+1) Now you want to find the factors of 1649, you do GCD(1649,(65-31)) = 17 GCD(1649, (31+65+1)) = 97 17*97 = 1649
    - ColinWright 5y ago
      But why should c=1 be the right value? Don't you want to be changing c as it goes? If not, why not? If so, then how do you change it? And then ... why should this method be any more successful than vanilla Fermat factoring?
      - marcookker 5y ago
        Imagine you start a number that has many possible c's, for example 2*3*5*7*11*13*17*19*23*29*31*37*41*43*47*53*59*61*67*71 = 557940830126698960967415390 after that you do 557940830126698960967415390 MOD 1649. The number you are left with, has a bigger chance to have a c in it, that also is in 557940830126698960967415390.

ColinWright 5y ago

We've had a long exchange, but I still can't work out what your algorithm is in detail ... there are no contact details in your profile, so I'll just have to leave it with you to get in touch with me. See here: https://news.ycombinator.com/item?id=28978463 https://news.ycombinator.com/item?id=28978463