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, 00:41   #133
Batalov

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

100101011001002 Posts

Quote:
 Originally Posted by mahbel You just do it yourself. I can tell you that I used the online 4-sq reps calculator for which I provided the link before. ...if I somehow cheated...
So do the decomposition of 5068057921 by your great method using
http://www.mathcelebrity.com/foursqu...quare+Notation
and factor it. Just do it yourself.

Simply because you think that "people think that you are cheating" doesn't mean that you are not cheating.

2017-06-24, 00:57   #134
CRGreathouse

Aug 2006

175B16 Posts

Quote:
 Originally Posted by mahbel There are algorithms that can provide the decomposition of an integer N into a sum two squares which do not require factoring N.
Are these algorithms faster than factorization? That would be a surprise to me, I was not aware of any such algorithm.

I've chosen two random semiprimes such that one is a sum of two squares and the other is not. They both have 120 decimal digits, which is designed to be large enough that they are inconvenient to factor. Can you tell, via this method, which is the sum of two squares?

212516552112132255144219181942145041853904419406206147277341101918011712262187398404745415408630814953685178049763053241

512905543662054235449961761129912643539514261930778780575803129094809217414988287315500794889688083726470478732454337581

2017-06-24, 01:00   #135
CRGreathouse

Aug 2006

3·1,993 Posts

Quote:
 Originally Posted by a1call Expanding Fermat's factorization method: a+b | a^n + b^n For all positive odd integers n. Similarly, all positive even integers n, yield imaginary integer factors. However, while true it has little practical value for large semi primes, due to "exponential" growth of powers.
If mahbel could demonstrate a factoring method along those lines, perhaps based on a geometric version of rectangle decomposition, I would certainly consider it a success (even though it only works on a narrow set of numbers). I've seen at least one published paper on a factorization method for a special class of numbers (as far as I know it had only curio value, but it was interesting).

2017-06-24, 12:39   #136
Dr Sardonicus

Feb 2017
Nowhere

22×32×139 Posts

Quote:
 Originally Posted by mahbel How I found them was described before in one of my post. You take a 4-sq rep (a,b,c,d) and you combine the elements a,b,c,d, in this case the non-squares. a+b, a+c, a+d, b+c, b+d, a+b+c, a+b+d, b+c+d and you calculate the gcd of these combinations. There is a really simple way to see if I somehow cheated and invented these combinations that sum up to a factor.
There is a simple way: Show your work. You have to find the 4-square reps before you can use them. For me, at any rate, finding 4-square reps is a lot harder than trial division. Especially for numbers less than 10,000. If you ran a script to find the reps, post it. Especially if the output shows it finding a factor.

Besides, I have said myself that your "method" is likely to stumble across factors less than 100. You haven't tried your "method" on any numbers large enough to be of interest WRT whether your "new factoring method" has any merit.

2017-06-24, 12:55   #137
mahbel

Feb 2017
Kitchener, Ontario

22·3·5 Posts

Quote:
 Originally Posted by CRGreathouse Are these algorithms faster than factorization? That would be a surprise to me, I was not aware of any such algorithm. I've chosen two random semiprimes such that one is a sum of two squares and the other is not. They both have 120 decimal digits, which is designed to be large enough that they are inconvenient to factor. Can you tell, via this method, which is the sum of two squares? 212516552112132255144219181942145041853904419406206147277341101918011712262187398404745415408630814953685178049763053241 512905543662054235449961761129912643539514261930778780575803129094809217414988287315500794889688083726470478732454337581
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.

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.

2017-06-24, 13:19   #138
Dr Sardonicus

Feb 2017
Nowhere

22×32×139 Posts

Quote:
 Originally Posted by mahbel The algorithm is described here. https://math.stackexchange.com/quest...that-add-up-to
Consulting this august source, we find:
Quote:
 The condition for a solution is that: (2*k + 6)^2−8*(k^2 + 4*k+5 - N) = s^2
Let's see here. Simplifying the LHS of the above equation gives

8*N - 4*(k + 1)^2 = s^2, or 8*N = s^2 + 4*(k + 1)^2.

In other words, the condition that there is a solution, is that 8*N be a sum of two squares. And how do we actually find them?

Quote:
 We may have to try few values of k before we hit on the solution.
In other words, trial-and-error.

Last fiddled with by Dr Sardonicus on 2017-06-24 at 13:28

2017-06-24, 13:38   #139
science_man_88

"Forget I exist"
Jul 2009
Dumbassville

26×131 Posts

Quote:
 Originally Posted by Dr Sardonicus 8*N - 4*(k + 1)^2 = s^2, or 8*N = s^2 + 4*(k + 1)^2. In other words, the condition that there is a solution, is that 8*N be a sum of two squares. And how do we actually find them?
This proves that s is even, because in general $2a\neq 2b + 2c+1$ . If s=2*t then s^2= 4(t^2). We can remove the factor of 4 from each side, reducing it to 2N=t^2+(k+1)^2 so the fact that 8N has to be of this form, proves 2N has to a sum of two squares.

Last fiddled with by science_man_88 on 2017-06-24 at 13:42

2017-06-24, 13:46   #140
Dr Sardonicus

Feb 2017
Nowhere

22×32×139 Posts

Quote:
 Originally Posted by mahbel Now, if you want to impose limitations on how one can go about combining 4 different numbers in different ways, then please post your do's and dont's.
Again, it is incumbent on you, the claimant, to prove that your method does work, rather than for others to prove it doesn't.

I think that others have already shown that your "method" is extremely unlikely to work in a reasonable amount of time with numbers of any size. The fact that you have steadfastly refused to apply your method to challenge numbers of any size lends credence to this assessment.

Besides, in your above demand, you appear to be admitting that your method is only guaranteed to work if you are allowed to combine the 4 numbers without limitation -- which, as far as I can tell, could include substituting a, b, c, and d into any polynomial in 4 variables with integer coefficients. If you're saying that that's what it would take to guarantee that your "method" would produce a factor, then it is as I previously described it: blazing away with a scattergun, desperately hoping that some of the buckshot will hit.

2017-06-24, 13:59   #141
mahbel

Feb 2017
Kitchener, Ontario

22·3·5 Posts

Quote:
 Originally Posted by science_man_88 This proves that s is even, because in general $2a\neq 2b + 2c+1$ . If s=2*t then s^2= 4(t^2). We can remove the factor of 4 from each side, reducing it to 2N=t^2+(k+1)^2 so the fact that 8N has to be of this form, proves 2N has to a sum of two squares.
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.

2017-06-24, 14:38   #142
science_man_88

"Forget I exist"
Jul 2009
Dumbassville

26×131 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.
I applied even =sum of two numbers of same parity , but my result also can follow from what I stated earlier. That because 8 is not square-free ( 8=(2^2*2) ) that we can also delete that square factor from the squares that sum to it in this case. applying even =sum of two numbers of same parity again ( as well as the fact that a power has the same parity as it's base) we see that k+1 has the same parity as t. Unless we know one though I don't think we can easily find the other.

Last fiddled with by science_man_88 on 2017-06-24 at 15:08

2017-06-24, 18:57   #143
Batalov

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

957210 Posts

Quote:
 Originally Posted by mahbel The algorithm is described here. https://math.stackexchange.com/questions/1972771/is-this-the-general-solution-of-finding-the-two-original-squares-that-add-up-to
is-this-the-general-solution-of-finding...
Doesn't it sound like a question, rather than an answer? Why yes! It is a question, and the answer is 'No.'
There is no algorithm in that thread. Try again.

 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 05:22.

Mon Oct 25 05:22:01 UTC 2021 up 93 days, 23:51, 0 users, load averages: 1.52, 1.25, 1.12