 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-24, 19:30 #144 mahbel   "mahfoud belhadj" Feb 2017 Kitchener, Ontario 6010 Posts tiling an 11x11 square with squares from the 4-sq rep (10,4,2,1) I made the tiling of an 11x11 square. I started with the 4-sq rep (10,4,2,1). Now using combinations of non-squares, we can find a factor by adding 2 terms 10+1=11. In this picture, it will be shown that one can tile the whole 11x11 square with squares derived from the 4-sq rep (10,4,2,1). One has to remember that 11=5+5+1, 3+3+1+1+1+1+1=11, 5+4+2=11 and 5+4+2=11 and 2+2+2+2+3=11. So 10+1=11 becomes in the final picture 5+5+1=11. Attached Thumbnails   2017-06-24, 19:52   #145
CRGreathouse

Aug 2006

3×1,993 Posts Quote:
 Originally Posted by mahbel I don't know if the algorithm is faster than factorization. I only know that such an algorithm exists. It is based on solving quadratic equations and finding values of a parameter k that makes the discriminant a perfect square. I suppose for some numbers, solutions can be found quickly and for some other numbers not so quickly. The algorithm is described here. https://math.stackexchange.com/quest...that-add-up-to
Ah. This requires solving a diophantine quadratic, in particular the hyperbolic case. I think of solving diophantine equations as hard; I guess you could look into this particular case and see if it's easier than the general one. There are known algorithms, and I know PARI/GP implements fast versions of those algorithms (but they're not very user-friendly).

Quote:
 Originally Posted by mahbel To answer your second question, there is no quick way to tell if a number does not admit a representation as a sum of two squares. To find out, one has to check every value of the parameter k in the discriminant until we run out of values to check before we can say the number does not admit a representation as a sum of two squares. And this may take a long time, maybe even longer than factorization.
Right, if you do it this way it would take a long time, definitely longer than factorization. When I suggested factorization it was because it was a good/fast approach.    2017-06-24, 19:54   #146
CRGreathouse

Aug 2006

3×1,993 Posts Quote:
 Originally Posted by mahbel The answer Will Jagy gave in the thread on the statckexchange site proved that writing 2N as a sum of two squares is equivalent to writing N as a sum of two squares. And he is one of the most knowledgeable mathematician I know. He called it a bijection between the two methods.
Yes, and you can understand that claim in light of the factorization characterization I gave.    2017-06-24, 19:55   #147
CRGreathouse

Aug 2006

597910 Posts Quote:
 Originally Posted by mahbel I made the tiling of an 11x11 square. I started with the 4-sq rep (10,4,2,1). Now using combinations of non-squares, we can find a factor by adding 2 terms 10+1=11. In this picture, it will be shown that one can tile the whole 11x11 square with squares derived from the 4-sq rep (10,4,2,1). One has to remember that 11=5+5+1, 3+3+1+1+1+1+1=11, 5+4+2=11 and 5+4+2=11 and 2+2+2+2+3=11. So 10+1=11 becomes in the final picture 5+5+1=11.
That's very pretty. I'm not at all sure how I would use this for factorization, though.    2017-06-24, 20:07   #148
Batalov

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

2×4,787 Posts Quote:
 Originally Posted by mahbel I made the tiling of an 11x11 square. I started with the 4-sq rep (10,4,2,1). Now using combinations of non-squares, we can find a factor by adding 2 terms 10+1=11. In this picture, it will be shown that one can tile the whole 11x11 square with squares derived from the 4-sq rep (10,4,2,1). One has to remember that 11=5+5+1, 3+3+1+1+1+1+1=11, 5+4+2=11 and 5+4+2=11 and 2+2+2+2+3=11. So 10+1=11 becomes in the final picture 5+5+1=11.
Brilliant! And here is my picture for 13^2=10^2+7^2+4^2+2^2.
In fact it works for any set of squares. We will just cut them all into 1x1 pieces.
One simply has to remember that 7=1+1+1+1+1+1+1, 4=1+1+1+1, and 2=1+1.
Elementary, Watson!
Attached Thumbnails   2017-06-24, 20:12   #149
science_man_88

"Forget I exist"
Jul 2009
Dumbassville

20C016 Posts Quote:
 Originally Posted by CRGreathouse That's very pretty. I'm not at all sure how I would use this for factorization, though. I somewhat understand, after all I linked to the numberphile video. But, I also get the point, that factoring a number with known factors, allows you to plan ahead. This allows you to make sure you use squares that fit such that their side lengths add to a known factor. The problem is, in a general factorization, baring any knowledge of the type of side length we will be dealing with ( aka factor types like 2kp+1 for mersennes), we can't say which sums will give us a factor so we must try basically all of them. edit: Also the problem of n^2 = n^2*1^2 shows up like Batalov talked about.

Last fiddled with by science_man_88 on 2017-06-24 at 20:30   2017-06-24, 20:34   #150
mahbel

Feb 2017
Kitchener, Ontario

22·3·5 Posts Quote:
 Originally Posted by CRGreathouse That's very pretty. I'm not at all sure how I would use this for factorization, though. It is simply a confirmation that using combinations of non-squares (a,b,c,d) to get a factor is justified.

In the original 4-sq rep used, (10,4,2,1), by just adding 10+1=11, we get a factor. But of course we cannot tile with this rep as is. But if we expand 10^2=(5,5,5,5) and 4^2+2^2=3^3+3^2+1+1, then we would be able to tile the whole square. Each side will give the same factor.   2017-06-24, 20:46   #151
mahbel

Feb 2017
Kitchener, Ontario

748 Posts Quote:
 Originally Posted by CRGreathouse Yes, and you can understand that claim in light of the factorization characterization I gave. Yes.   2017-06-24, 21:16   #152
a1call

"Rashid Naimi"
Oct 2015
Remote to Here/There

215210 Posts Quote:
 Originally Posted by mahbel I made the tiling of an 11x11 square. I started with the 4-sq rep (10,4,2,1). Now using combinations of non-squares, we can find a factor by adding 2 terms 10+1=11. In this picture, it will be shown that one can tile the whole 11x11 square with squares derived from the 4-sq rep (10,4,2,1). One has to remember that 11=5+5+1, 3+3+1+1+1+1+1=11, 5+4+2=11 and 5+4+2=11 and 2+2+2+2+3=11. So 10+1=11 becomes in the final picture 5+5+1=11.
I actually do see a geometric algorithm in there.
Here is my 2 cents, FWIW.
It has absolutely nothing to do with 4 squares and there is no justification to start from 5.
I just applied the geometric tiling algorithm and started with 2x6^2
I ended up tiling a 14x13 rectangle.
I think if one starts from N/2 rounded down and works its way down to N/sqrt(N), then he will find a deterministic factor if any. I also think it will be very very slow.
But if I am missing something, it won't be the first time. Last fiddled with by a1call on 2017-06-24 at 21:20   2017-06-24, 21:43   #153
CRGreathouse

Aug 2006

3·1,993 Posts Quote:
 Originally Posted by a1call I actually do see a geometric algorithm in there. Here is my 2 cents, FWIW. It has absolutely nothing to do with 4 squares and there is no justification to start from 5. I just applied the geometric tiling algorithm and started with 2x6^2 I ended up tiling a 14x13 rectangle. I think if one starts from N/2 rounded down and works its way down to N/sqrt(N), then he will find a deterministic factor if any. I also think it will be very very slow. But if I am missing something, it won't be the first time. If you allow using as many 1x1 squares as you need, this is just a variant of trial division. If not, it's not clear to me that you will find a factorization even if there is one -- maybe there is a factorization but no associated tiling. But I wasn't thinking of something this brute force when I suggested looking at it geometrically. I know that there are parameterized tilings and conceivably these could give factorizations for an appropriate class of integers. Maybe they would be very very thin, and so not useful, or maybe only somewhat thin and so useful at least as a curiosity. If they were fully general, of course, you'd get a normal factorization method.   2017-06-24, 21:49   #154
Dr Sardonicus

Feb 2017
Nowhere

116178 Posts Quote:
 Originally Posted by axn Before we proceed further, what is the theoretical justification that it has to be squares?
Here's another question: What's the theoretical justification for requiring that the four squares add up exactly to N? The reason I ask is, I thought of a way to speed up the process of using 4-tuples (a, b, c, d) to find factors of N: simply drop the requirement that

a^2 + b^2 + c^2 + d^2 = N exactly.

As long as a^2 + b^2 + c^2 + d^2 is close to N, go ahead and form the sums of some or all of a, b, c, d, a^2, b^2, c^2, and d^2, and take the gcd with N. (There are 127 nonempty sums.)

I hypothesize that, there being so many possibilities, the chances are good that any factor of N under 100 will show up fairly quickly. I tried this idea with N = 1457 = 31*47, and the results were better than I expected. Even though a^2 + b^2 + c^2 + d^2 never hit N right on the nose, I still got at least one of the 15 sums of a, b, c, and d alone having a common factor with N in 6 of 8 tries.

If anyone would care to have a go at my examples N = 77, 1457, 3901, 4661, 6557, 7597, 8549, and 9869 using this approach, have at them!

I cheerfully proclaim that this approach really is nothing more than blazing away with a scattergun, in hopes that some of the buckshot will hit. The advantage over the OP's idea is, reloading is a whole lot quicker
;-)   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 20:56.

Tue Oct 26 20:56:52 UTC 2021 up 95 days, 15:25, 0 users, load averages: 1.31, 1.18, 1.24