2 ms·

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

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
    I'm sorry, I can't follow this argument at all. Suppose I give you a moderate sized number like 163123711. What are your choices of a and c? How do you proceed using the "Factorisation with Rectangles" method? Don't pick magic numbers, don't roll everything into one, I'd like to see a complete step-by-step example. So with vanilla Fermat we say: a = ceil(sqrt(N)) = 12772 b2 = a^2 - N = 273 <- Not a square Add 1 to a. a = 12773 b2 = a^2 - N = 25818 <- Not a square Add 1 to a. a = 12774 b2 = a^2 - N = 51365 <- Not a square And so on. So, how does your algorithm proceed?
    - marcookker 5y ago
      Say we want to factor 163123711, N=163123711. Before we start the algorithm, we have to choose a number to start our algorithm with. A good pick for the first number that we want to start our algorithm with, is a number that is higher than N and has many different factor pairs, of which the difference of the factor pair is lower N. For example 6469693230 has 512 factor pairs, of which 489 pairs that are lower than N(https://www.calculatorsoup.com/calculators/math/factors.php https://www.calculatorsoup.com/calculators/math/factors.php). 79534 × 81345 = 6469693230 79373 × 81510 = 6469693230 ... This means that 6469693230 contains 489 possible combinations for c. (a+c)x(a): (79534+1811) x 79534 = 6469693230 (79373+2137) x 79373 = 6469693230 ... First we write down all the c's possible. c = 1811 c = 2137 ... After this we start the algorithm with our first number "6469693230": 6469693230 % 163123711 = 107868501 Now because we know that 1x107868501 = 107868501, we know the c of the number we left with, 107868501-1 = 107868500. c = 107868500 Does 107868500 match the c's we had written down? (a+c) x a - (b+c) x b (79534+1811) x 79534 - (1+107868500) x 1; c is not the same (1811 is not 107868500). (79534+2137) x 79534 - (1+107868500) x 1; c is not the same (2137 is not 107868500). ... Not at all? We try a different number than 6469693230 If it matches, you can calculate the factors. If you try it with 6469693230, you have a chance of 489/163123711 = around 1 in 333587 chance that you can factor it.
      - ColinWright 5y ago
        I'm rapidly running out of time to spend on this. I'm sure you think you're being clear, but I really can't follow much of what you're saying. Let me show you. > N=163123711. Right, so that's my example. > choose a number higher than N and has many different factor pairs, of which the difference of the factor pair is lower N. So basically you pick a number S > N which is smooth (has lots of small factors) Then you appear to find lots of solutions: (a+c)a = S Specifically you require c<N. Example: 79534 × 81345 = 6469693230 -> (79534+1811) x 79534 = 6469693230 So 1811 is a candidate for c. OK. > First we write down all the c's possible. So you write down every c such that there is an a with (a+c)a=S, and because of your choice of S there will be many such values. > After this we start the algorithm with our first number "6469693230": 6469693230 % 163123711 = 107868501 What? > Now because we know that 1x107868501 = 107868501, we know the c of the number we left with, 107868501-1 = 107868500. > c = 107868500 > Does 107868500 match the c's we had written down? What? > (a+c) x a - (b+c) x b > (79534+1811) x 79534 - (1+107868500) x 1; c is not the same (1811 is not 107868500). > (79534+2137) x 79534 - (1+107868500) x 1; c is not the same (2137 is not 107868500). What? You haven't actually explained your algorithm. I've got as far as: I have a collection of candidate values for c. You haven't explained then what you're actually doing. But now I really have run out of time. If you write this up properly somewhere and point at it I'll try to come back to it, but no promises.

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
  I'm sorry, I can't follow this argument at all. Suppose I give you a moderate sized number like 163123711. What are your choices of a and c? How do you proceed using the "Factorisation with Rectangles" method? Don't pick magic numbers, don't roll everything into one, I'd like to see a complete step-by-step example. So with vanilla Fermat we say: a = ceil(sqrt(N)) = 12772 b2 = a^2 - N = 273 <- Not a square Add 1 to a. a = 12773 b2 = a^2 - N = 25818 <- Not a square Add 1 to a. a = 12774 b2 = a^2 - N = 51365 <- Not a square And so on. So, how does your algorithm proceed?
  - marcookker 5y ago
    Say we want to factor 163123711, N=163123711. Before we start the algorithm, we have to choose a number to start our algorithm with. A good pick for the first number that we want to start our algorithm with, is a number that is higher than N and has many different factor pairs, of which the difference of the factor pair is lower N. For example 6469693230 has 512 factor pairs, of which 489 pairs that are lower than N(https://www.calculatorsoup.com/calculators/math/factors.php https://www.calculatorsoup.com/calculators/math/factors.php). 79534 × 81345 = 6469693230 79373 × 81510 = 6469693230 ... This means that 6469693230 contains 489 possible combinations for c. (a+c)x(a): (79534+1811) x 79534 = 6469693230 (79373+2137) x 79373 = 6469693230 ... First we write down all the c's possible. c = 1811 c = 2137 ... After this we start the algorithm with our first number "6469693230": 6469693230 % 163123711 = 107868501 Now because we know that 1x107868501 = 107868501, we know the c of the number we left with, 107868501-1 = 107868500. c = 107868500 Does 107868500 match the c's we had written down? (a+c) x a - (b+c) x b (79534+1811) x 79534 - (1+107868500) x 1; c is not the same (1811 is not 107868500). (79534+2137) x 79534 - (1+107868500) x 1; c is not the same (2137 is not 107868500). ... Not at all? We try a different number than 6469693230 If it matches, you can calculate the factors. If you try it with 6469693230, you have a chance of 489/163123711 = around 1 in 333587 chance that you can factor it.
    - ColinWright 5y ago
      I'm rapidly running out of time to spend on this. I'm sure you think you're being clear, but I really can't follow much of what you're saying. Let me show you. > N=163123711. Right, so that's my example. > choose a number higher than N and has many different factor pairs, of which the difference of the factor pair is lower N. So basically you pick a number S > N which is smooth (has lots of small factors) Then you appear to find lots of solutions: (a+c)a = S Specifically you require c<N. Example: 79534 × 81345 = 6469693230 -> (79534+1811) x 79534 = 6469693230 So 1811 is a candidate for c. OK. > First we write down all the c's possible. So you write down every c such that there is an a with (a+c)a=S, and because of your choice of S there will be many such values. > After this we start the algorithm with our first number "6469693230": 6469693230 % 163123711 = 107868501 What? > Now because we know that 1x107868501 = 107868501, we know the c of the number we left with, 107868501-1 = 107868500. > c = 107868500 > Does 107868500 match the c's we had written down? What? > (a+c) x a - (b+c) x b > (79534+1811) x 79534 - (1+107868500) x 1; c is not the same (1811 is not 107868500). > (79534+2137) x 79534 - (1+107868500) x 1; c is not the same (2137 is not 107868500). What? You haven't actually explained your algorithm. I've got as far as: I have a collection of candidate values for c. You haven't explained then what you're actually doing. But now I really have run out of time. If you write this up properly somewhere and point at it I'll try to come back to it, but no promises.