3 ms·

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 proce

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.
- marcookker 5y ago
  "6469693230": 6469693230 % 163123711 = 107868501 "%" is modulo in software it means 6469693230 = 107868501 MOD 163123711. So basicly you find out that 6469693230 - 163123711 * k = 107868501. so you get: (a+c) * a - (b+c) * b = 163123711*k instead of: (a+c) * a - (b+c) * b = 163123711 --------- so back to the formula: (a+c) * a - (b+c) * b = 163123711*k 6469693230 - (b+c) * b = 163123711*k we deduced that 6469693230 = 107868501 MOD 163123711 6469693230 - 107868501 = 163123711*k --------- Okay now we morph 107868501 into (1+c) * 1 (1+107868500) * 1 = 107868501 now we look back at the formula: 6469693230 - (1+107868500) * 1 = 163123711*k does 6469693230 have a factor pair, with the difference is 107868500? (a+107868500) * (a) - (1+107868500) * 1 = 163123711*k? We look at the list we wrote down. If 107868500 is in the list,than (a+107868500) * (a) - (1+107868500) * 1 = 163123711*k holds. If it is not in the list, we have to come up with another number like 6469693230 , with allot of factors, and the the algorithm again.
  - ColinWright 5y ago
    Look, stop. Just, stop. You obviously know what you're doing, but I don't, and your "explanations" aren't helping. You're making me try to decode where everything comes from, and that takes a huge amount of time that I just don't have. I'm trying hard to understand this, but to me, with my currently non-understanding, it just looks like you're pushing stuff around, and it's hard to work out what you're doing. So you need to stop trying to explain it like this, and probably you need to stop trying to explain it here. This is not a good forum to unpick things and explain them fully, and I don't have the time to play guessing games. I do have the time to step through a clear, precise, motivated explanation, but that won't happen here, and it won't happen quickly. Email me, but don't try to tell me everything. You have the knowledge, but if you just dump it at me then I won't know where to start. Let me pull it from you, and I'll construct a document with my understanding of it.
marcookker 5y ago
The normal approach would be the following: a = ceil(sqrt(N)) = 12772 b2 = (12772+1)*(12772) - N = 13045 <- factorize = 5*2609 <- does not fit in (b+1)*(b) b2 = (12773+1)*(12773) - N = 38591 <- factorize = 149*259 <- does not fit in (b+1)*(b) ...
- ColinWright 5y ago
  But why are you just using c=1? Surely you should be using different c's to make this algorithm work. Using c=1 makes your algorithm effectively identical to the vanilla Fermat algorithm. Elsewhere you talk about selecting different possible values of c, but with no reasoning as to why this should work faster, or better, or even at all. And in cases where you choose c=something else, you don't tell us how to compute a and b, and it seems to me that they have multiple solutions, some of which are tantamount to factoring N anyway. So I am none the wiser, and I await a proper, detailed explanation where I can follow, or even implement, the algorithm.

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.
marcookker 5y ago
"6469693230": 6469693230 % 163123711 = 107868501 "%" is modulo in software it means 6469693230 = 107868501 MOD 163123711. So basicly you find out that 6469693230 - 163123711 * k = 107868501. so you get: (a+c) * a - (b+c) * b = 163123711*k instead of: (a+c) * a - (b+c) * b = 163123711 --------- so back to the formula: (a+c) * a - (b+c) * b = 163123711*k 6469693230 - (b+c) * b = 163123711*k we deduced that 6469693230 = 107868501 MOD 163123711 6469693230 - 107868501 = 163123711*k --------- Okay now we morph 107868501 into (1+c) * 1 (1+107868500) * 1 = 107868501 now we look back at the formula: 6469693230 - (1+107868500) * 1 = 163123711*k does 6469693230 have a factor pair, with the difference is 107868500? (a+107868500) * (a) - (1+107868500) * 1 = 163123711*k? We look at the list we wrote down. If 107868500 is in the list,than (a+107868500) * (a) - (1+107868500) * 1 = 163123711*k holds. If it is not in the list, we have to come up with another number like 6469693230 , with allot of factors, and the the algorithm again.
- ColinWright 5y ago
  Look, stop. Just, stop. You obviously know what you're doing, but I don't, and your "explanations" aren't helping. You're making me try to decode where everything comes from, and that takes a huge amount of time that I just don't have. I'm trying hard to understand this, but to me, with my currently non-understanding, it just looks like you're pushing stuff around, and it's hard to work out what you're doing. So you need to stop trying to explain it like this, and probably you need to stop trying to explain it here. This is not a good forum to unpick things and explain them fully, and I don't have the time to play guessing games. I do have the time to step through a clear, precise, motivated explanation, but that won't happen here, and it won't happen quickly. Email me, but don't try to tell me everything. You have the knowledge, but if you just dump it at me then I won't know where to start. Let me pull it from you, and I'll construct a document with my understanding of it.

marcookker 5y ago

The normal approach would be the following: a = ceil(sqrt(N)) = 12772 b2 = (12772+1)*(12772) - N = 13045 <- factorize = 5*2609 <- does not fit in (b+1)*(b) b2 = (12773+1)*(12773) - N = 38591 <- factorize = 149*259 <- does not fit in (b+1)*(b) ...

ColinWright 5y ago
But why are you just using c=1? Surely you should be using different c's to make this algorithm work. Using c=1 makes your algorithm effectively identical to the vanilla Fermat algorithm. Elsewhere you talk about selecting different possible values of c, but with no reasoning as to why this should work faster, or better, or even at all. And in cases where you choose c=something else, you don't tell us how to compute a and b, and it seems to me that they have multiple solutions, some of which are tantamount to factoring N anyway. So I am none the wiser, and I await a proper, detailed explanation where I can follow, or even implement, the algorithm.