mersenneforum.org  

Go Back   mersenneforum.org > Extra Stuff > Miscellaneous Math

Reply
 
Thread Tools
Old 2017-06-24, 00:41   #133
Batalov
 
Batalov's Avatar
 
"Serge"
Mar 2008
Phi(4,2^7658614+1)/2

2·4,787 Posts
Default

Quote:
Originally Posted by mahbel View Post
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.
Batalov is offline   Reply With Quote
Old 2017-06-24, 00:57   #134
CRGreathouse
 
CRGreathouse's Avatar
 
Aug 2006

3·1,993 Posts
Default

Quote:
Originally Posted by mahbel View Post
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
CRGreathouse is offline   Reply With Quote
Old 2017-06-24, 01:00   #135
CRGreathouse
 
CRGreathouse's Avatar
 
Aug 2006

3·1,993 Posts
Default

Quote:
Originally Posted by a1call View Post
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).
CRGreathouse is offline   Reply With Quote
Old 2017-06-24, 12:39   #136
Dr Sardonicus
 
Dr Sardonicus's Avatar
 
Feb 2017
Nowhere

3×1,669 Posts
Default

Quote:
Originally Posted by mahbel View Post
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.
Dr Sardonicus is offline   Reply With Quote
Old 2017-06-24, 12:55   #137
mahbel
 
"mahfoud belhadj"
Feb 2017
Kitchener, Ontario

22·3·5 Posts
Default

Quote:
Originally Posted by CRGreathouse View Post
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.

https://math.stackexchange.com/quest...that-add-up-to

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.
mahbel is offline   Reply With Quote
Old 2017-06-24, 13:19   #138
Dr Sardonicus
 
Dr Sardonicus's Avatar
 
Feb 2017
Nowhere

500710 Posts
Default

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

203008 Posts
Default

Quote:
Originally Posted by Dr Sardonicus View Post
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
science_man_88 is offline   Reply With Quote
Old 2017-06-24, 13:46   #140
Dr Sardonicus
 
Dr Sardonicus's Avatar
 
Feb 2017
Nowhere

3·1,669 Posts
Default

Quote:
Originally Posted by mahbel View Post
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.
Dr Sardonicus is offline   Reply With Quote
Old 2017-06-24, 13:59   #141
mahbel
 
"mahfoud belhadj"
Feb 2017
Kitchener, Ontario

22×3×5 Posts
Default

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

26×131 Posts
Default

Quote:
Originally Posted by mahbel View Post
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
science_man_88 is offline   Reply With Quote
Old 2017-06-24, 18:57   #143
Batalov
 
Batalov's Avatar
 
"Serge"
Mar 2008
Phi(4,2^7658614+1)/2

2×4,787 Posts
Default

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


Tue Oct 26 21:08:06 UTC 2021 up 95 days, 15:37, 0 users, load averages: 0.96, 1.32, 1.35

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.