 mersenneforum.org The new strong (extended) factoring method using the 4-square representation of an integer.
 Register FAQ Search Today's Posts Mark Forums Read  2017-06-20, 00:56   #89
Dr Sardonicus

Feb 2017
Nowhere

10100000011012 Posts Quote:
 Originally Posted by CRGreathouse Actually I think you're the only one who has used real math in this thread so far, in your analysis (post #72) of the failure of the original algorithm. I just used cheap heuristics and decent algorithms.
I think my response in post #40 here has more mathematics. Your numerical work was nice. I still smile when I think of the OP's method going head-to-head with choosing random numbers up to sqrt(N) -- and losing by orders of magnitude.

Of course, I must concede, the OP's method stands an excellent chance of finding factors -- provided they're less than 100! The fact that trial division will almost certainly find all such factors much more quickly, in no way detracts from this. As to factors of any size, I refer the reader to my remarks in post #40, linked to above. I will add that, forming all combinations of a^2, b^2, c^2, d^2, a, b, c, and d, with coefficients from the set {-1, 0, 1}, will give 6561 numbers (not necessarily all different) for each 4-tuple (a, b, c, d), so the number of possibilities is multiplied by less than 10,000 -- far less than the factor of a trillion I allowed for in my analysis.

I find it ironic that the OP demands others "say it with math," when he has already stated he doesn't understand the math. I did a bit of math with the question partly to satisfy my own curiosity, and partly to test the OP's receptiveness. At this point, my inclination to mathify further on the subject is tempered by the wisdom of the Good Book, particularly Matthew 7:6.

I approve of the change to the subject name for this thread. I found the adjective "strong" an inapt modifier of "problem" in the thread from whence the new name of this thread originated. It is at least applicable to the term "method," even if the description of the method under discussion as "strong" is of dubious accuracy.   2017-06-20, 15:15   #90
Dr Sardonicus

Feb 2017
Nowhere

3·29·59 Posts Quote:
 Originally Posted by CRGreathouse But don't worry, if we find a number this can't factor we can just move to a double-extended test where include combinations like a + b^2 + d. I think that would require 72 tests in total. And if that doesn't work we can always use a triple-extended test which allows nonbinary coefficients, or cubes, or something.
I am not an expert on the subject of scatterguns, but it would be prudent to consider the possibility that blazing away with one repeatedly might cause it to overheat.

Going through the thread, the only numbers I could find for which the OP produced factors, are 91 and 77. As it turns out, both have 7 as a factor. Also as it turns out, numbers this small are quickly factored by a simple difference-of-squares method. Such methods were favored by, e.g. Fermat. For example, adding squares to 77 gives

77 + 1 = 78 (not a square), 77 + 4 = 81 = 9^2, and the factors are 9 - 2 = 7 and 9 + 2 = 11. Alternatively,

sqrtint(77) = 8; 9^2 - 77 = 4, again giving the factors 9 - 2 = 7 and 9 + 2 = 11.

Similarly, 91 + 1 = 92 (not square), 91 + 4 = 95 (not square), 91 + 9 = 10^2, giving the factors 10 - 3 = 7 and 10 + 3 = 13. Alternatively,

sqrtint(91) = 9; 10^2 - 91 = 9 = 3^2, giving the factors 10 - 3 = 7 and 10 + 3 = 13.

I invite the OP to try his method on N = 19673. One of the difference-of-squares methods gives the factors in fewer than ten tries.

Now mind, I am not advocating the simple-minded difference-of-squares methods exemplified above as general factoring methods. They're far too slow. However, I would be remiss if I did not point out that the best methods known today for factoring large numbers with no "small" factors, are avatars of the difference-of-squares method. The basic idea behind them is to find two squares which are congruent (mod N), both of which are "smooth," i.e. all (or perhaps all but one or two of) their prime factors are less than a fairly small pre-set bound B. Regarding the number field sieve, I refer the interested reader to Murphy's thesis and Bai's thesis.   2017-06-21, 06:54   #91
Nick

Dec 2012
The Netherlands

33368 Posts Quote:
 Originally Posted by Dr Sardonicus Regarding the number field sieve, I refer the interested reader to Murphy's thesis and Bai's thesis.
... or come to Leiden and talk to Prof. Lenstra himself.   2017-06-21, 12:33 #92 mahbel   "mahfoud belhadj" Feb 2017 Kitchener, Ontario 22×3×5 Posts On a possible justification of using combinations of non-square (a,b,c,d) to find factors. There are two ways to look at using the 4-sq reps, the arithmetic way and the geometric way. The arithmetic way is the one which uses combinations of squares (a^2,b^2,c^2,d^2) and find a factor by evaluating the gcd. The geometric way is similar to tiling of squares or rectangles using 4-sq reps. I will use the example of 3*5=15 to explain what I mean. 15=(3,2,1,1). if we draw a rectangle with sides 3 by 5, we will be able to tile that rectangle exactly with a square 3^2, a square 2^2 and 2 squares of 1^2. This example is one of those perfect examples where the rectangle 3*5 is tiled as stated before. Now if we look at the picture of that rectangle (not provided), we see that 3 is a factor and (3+2) is also a factor. The general case is not always this nice. Even when considering the simple case of 77=7*11, we run into problems. That is we can't fit the 4-sq rep (6,6,2,1) into a rectangle of 7 by 11 ( simply because 6+6>11). But there is a way around that if we expand 6^2 itself into a 4-sq rep and find a way to fit the different squares into the rectangle. I did that for the 4-sq rep (5^2,6^2,4^2) of 77. We can fit 5^2 and 6^2 into a rectangle of 7 by 11. But we will be left with a space, with of course a surface area of 4^2, but which does not have a shape of a 4x4 square. But 4^2 can itself be expanded into 4^2=2^2+2^2+1+1+1+1+1+1+1+1. After all, there is no rule or theorem that says we can't expand a square into a sum of 4 or more than 4 squares. If we do that, we will be able to fit the original 4-sq rep exactly but with the new 10 term rep for 4^2. If we look at the drawing (no picture will be provided), we then can see that the factors are 5+2=7, 5+6=11 and 6+1=7. Can factoring integers be reduced to a tiling of rectangles problem? Well, everyone is free to find an answer for themselves. Last fiddled with by mahbel on 2017-06-21 at 12:38 Reason: correct a spelling.   2017-06-21, 12:41 #93 science_man_88   "Forget I exist" Jul 2009 Dumbassville 26·131 Posts so you are trying to do things like: ?   2017-06-21, 13:23   #94
mahbel

Feb 2017
Kitchener, Ontario

748 Posts Quote:
 Originally Posted by science_man_88 so you are trying to do things like: ?
Not really. Fitting squares into squares looks more complicated to me. Fitting squares into rectangles is what I am trying to do to justify using non-squares (a,b,c,d) to find factors. If one (or more than one) square of the original 4-sq rep cannot be fit into the rectangle, we just expand it into a sum of n squares and try again. There is no rule to tell us what the value of n should be.

In the example provided (77=7*11), the work was done backward so the difficulties were not apparent. But the principle itself is a general one.   2017-06-21, 13:30   #95
science_man_88

"Forget I exist"
Jul 2009
Dumbassville

838410 Posts Quote:
 Originally Posted by mahbel Not really. Fitting squares into squares looks more complicated to me. Fitting squares into rectangles is what I am trying to do to justify using non-squares (a,b,c,d) to find factors. If one (or more than one) square of the original 4-sq rep cannot be fit into the rectangle, we just expand it into a sum of n squares and try again. There is no rule to tell us what the value of n should be. In the example provided (77=7*11), the work was done backward so the difficulties were not apparent. But the principle itself is a general one.
if a shares a factor with n and b c and d together (b+c+d) doesn't then the sum will not share a factor. same with the squares if a doesn't share a factor neither will a^2, if a^2 doesn't share a factor neither can b^2+c^2+d^2 because then the sum a^2+b^2+c^2+d^2 can't share a factor which is ridiculous because that's n. edit: of course I've already shown scaling occurs if you scale by a number divisible by a square ( at least from the multiple that you multiply by the square). yes there is in theory you can sum the squares get a formula for it and check which bounds it can be in between shows that it can be at most such and such a number of squares. the sum of the first n squares is the square pyramidal numbers. edit3: which the OEIS ( online encyclopedia of integer sequences) shows have the formula : n*(n+1)*(2*n+1)/6 for the sum of the squares up to n^2. okay that's for unique squares.

Last fiddled with by science_man_88 on 2017-06-21 at 13:52   2017-06-21, 16:35   #96
Dr Sardonicus

Feb 2017
Nowhere

120158 Posts Quote:
 Originally Posted by mahbel The geometric way is similar to tiling of squares or rectangles using 4-sq reps. I will use the example of 3*5=15 to explain what I mean. 15=(3,2,1,1). if we draw a rectangle with sides 3 by 5, we will be able to tile that rectangle exactly with a square 3^2, a square 2^2 and 2 squares of 1^2. This example is one of those perfect examples where the rectangle 3*5 is tiled as stated before. Now if we look at the picture of that rectangle (not provided), we see that 3 is a factor and (3+2) is also a factor. The general case is not always this nice. Even when considering the simple case of 77=7*11, we run into problems. That is we can't fit the 4-sq rep (6,6,2,1) into a rectangle of 7 by 11 ( simply because 6+6>11). But there is a way around that if we expand 6^2 itself into a 4-sq rep and find a way to fit the different squares into the rectangle. Can factoring integers be reduced to a tiling of rectangles problem? Well, everyone is free to find an answer for themselves.
I suppose you would consider it unkind of me to point out that, in order to have a rectangle of area N with integer sides all greater than 1 to tile, you need to have already factored N.   2017-06-21, 17:06   #97
CRGreathouse

Aug 2006

10111010110112 Posts Quote:
 Originally Posted by Dr Sardonicus I suppose you would consider it unkind of me to point out that, in order to have a rectangle of area N with integer sides all greater than 1 to tile, you need to have already factored N.
Right. But you might go the other way around, like playing with tangram pieces -- you have squares and you shape them into a rectangle.   2017-06-21, 18:42   #98
mahbel

Feb 2017
Kitchener, Ontario

22·3·5 Posts Quote:
 Originally Posted by Dr Sardonicus I suppose you would consider it unkind of me to point out that, in order to have a rectangle of area N with integer sides all greater than 1 to tile, you need to have already factored N.
No, you don't need to "have already factored N". It was done to justify using combinations of non-squares (a,b,c,d) to get a factor. And just like combinations of squares (a^2,b^2,c^2,d^2), some combinations will provide you with a factor before you get a complete tiling of the rectangle. Remember, a factor is just one side of the rectangle.

in the example I gave about 77=7*11, it was shown using the (5^2,6^2,4^2) rep that some combinations of (a,b,c,d) provided a factor before we had a complete tiling. namely 5+6=11 combination. In fact, I did not provide the complete tiling. It's only if you wanted to tile the whole rectangle that you need to do more work. In this case, you would have had to express 4^2 as a sum of squares in a way that allows the full tiling. But it's not needed.

Last fiddled with by mahbel on 2017-06-21 at 18:51 Reason: added example to explain   2017-06-21, 20:16   #99
Batalov

"Serge"
Mar 2008
Phi(4,2^7658614+1)/2

100101100100012 Posts Quote:
 Originally Posted by science_man_88 so you are trying to do things like: ?
No. If N can be "tiled" with a^2, b^2, c^2 and d^2, then N = a^2+b^2+c^2+d^2, but not the other way around.

11^2 = 10^2+4^2+2^2+1^2. Can you tile 11x11 with these squares?   Thread Tools Show Printable Version Email this Page Similar Threads Thread Thread Starter Forum Replies Last Post sweety439 sweety439 1250 2021-10-01 12:53 3.14159 Factoring 233 2011-05-15 18:50 ET_ Miscellaneous Math 40 2010-06-06 12:55 1260 Miscellaneous Math 46 2010-05-31 17:37 kpatsak Math 4 2007-10-29 17:53

All times are UTC. The time now is 16:50.

Sat Dec 4 16:50:43 UTC 2021 up 134 days, 11:19, 1 user, load averages: 1.49, 1.40, 1.26