3 ms·

Imagine you start a number that has many possible c's, for example 235*711131719232931374143475359616771 = 557940830126698960967415390 after

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

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

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