mersenneforum.org  

Go Back   mersenneforum.org > Extra Stuff > Miscellaneous Math

Reply
 
Thread Tools
Old 2017-06-20, 00:56   #89
Dr Sardonicus
 
Dr Sardonicus's Avatar
 
Feb 2017
Nowhere

500710 Posts
Default

Quote:
Originally Posted by CRGreathouse View Post
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.
Dr Sardonicus is offline   Reply With Quote
Old 2017-06-20, 15:15   #90
Dr Sardonicus
 
Dr Sardonicus's Avatar
 
Feb 2017
Nowhere

116178 Posts
Default

Quote:
Originally Posted by CRGreathouse View Post
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.
Dr Sardonicus is offline   Reply With Quote
Old 2017-06-21, 06:54   #91
Nick
 
Nick's Avatar
 
Dec 2012
The Netherlands

175110 Posts
Default

Quote:
Originally Posted by Dr Sardonicus View Post
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.
Nick is online now   Reply With Quote
Old 2017-06-21, 12:33   #92
mahbel
 
"mahfoud belhadj"
Feb 2017
Kitchener, Ontario

22·3·5 Posts
Default

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.
mahbel is offline   Reply With Quote
Old 2017-06-21, 12:41   #93
science_man_88
 
science_man_88's Avatar
 
"Forget I exist"
Jul 2009
Dumbassville

26·131 Posts
Default

so you are trying to do things like:

?
science_man_88 is offline   Reply With Quote
Old 2017-06-21, 13:23   #94
mahbel
 
"mahfoud belhadj"
Feb 2017
Kitchener, Ontario

22×3×5 Posts
Default

Quote:
Originally Posted by science_man_88 View Post
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.
mahbel is offline   Reply With Quote
Old 2017-06-21, 13:30   #95
science_man_88
 
science_man_88's Avatar
 
"Forget I exist"
Jul 2009
Dumbassville

203008 Posts
Default

Quote:
Originally Posted by mahbel View Post
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
science_man_88 is offline   Reply With Quote
Old 2017-06-21, 16:35   #96
Dr Sardonicus
 
Dr Sardonicus's Avatar
 
Feb 2017
Nowhere

116178 Posts
Default

Quote:
Originally Posted by mahbel View Post
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.
Dr Sardonicus is offline   Reply With Quote
Old 2017-06-21, 17:06   #97
CRGreathouse
 
CRGreathouse's Avatar
 
Aug 2006

597910 Posts
Default

Quote:
Originally Posted by Dr Sardonicus View Post
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.
CRGreathouse is offline   Reply With Quote
Old 2017-06-21, 18:42   #98
mahbel
 
"mahfoud belhadj"
Feb 2017
Kitchener, Ontario

3C16 Posts
Default

Quote:
Originally Posted by Dr Sardonicus View Post
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
mahbel is offline   Reply With Quote
Old 2017-06-21, 20:16   #99
Batalov
 
Batalov's Avatar
 
"Serge"
Mar 2008
Phi(4,2^7658614+1)/2

2×4,787 Posts
Default

Quote:
Originally Posted by science_man_88 View Post
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?
Batalov is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
A Sierpinski/Riesel-like problem sweety439 sweety439 1250 2021-10-01 12:53
Another factoring method rides the bus 3.14159 Factoring 233 2011-05-15 18:50
Square numbers and binary representation ET_ Miscellaneous Math 40 2010-06-06 12:55
Is this a feasible factoring method? 1260 Miscellaneous Math 46 2010-05-31 17:37
Representation of integer as sum of squares kpatsak Math 4 2007-10-29 17:53

All times are UTC. The time now is 21:39.


Tue Oct 26 21:39:04 UTC 2021 up 95 days, 16:08, 1 user, load averages: 1.67, 1.78, 1.78

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2021, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.