Author 
Message 
jstevh@msn.com science forum Guru
Joined: 21 Jan 2006
Posts: 951

Posted: Wed Jul 05, 2006 12:34 am Post subject:
New factoring idea



Was doodling, playing around with some simple equations and noticed
that with
x^2  a^2 = S + T
and
x^2  b^2 = S  k*T
I could subtract the second from the first to get
b^2  a^2 = (k+1)*T
which is, of course, a factorization of (k+1)*T:
(b  a)*(b+a) = (k+1)*T
with integers for S and T, where T is the target composite to factor,
so you have to pick this other integer S, and factor S+T.
Really simple so of course I'm thinking it's not new, but looking over
at the Wikipedia:
http://en.wikipedia.org/wiki/Factoring
It's new!!!
But how do you find the variables?
Well, if you pick S, and have a T you want to factor, then using
f_1*f_2 = S+T
it must be true that
a = (f_1  f_2)/2
And
x=(f_1 + f_2)/2
so, you need the sum of factors of (Sk*T)/4 to equal the sum of the
factors of (S+T)/4, so I introduce j, where
S  k*T = (f_1 + f_2  j)*j
and now you solve for k, to get
k = (S  (f_1 + f_2  j)*j)/T
so you also have
S  (f_1 + f_2  j)*j = 0 mod T
so
j^2  (f_1 + f_2)*j + S = 0 mod T
and completing the square gives
j^2  (f_1 + f_2)*j + (f_1 + f_2)^2/4 = ((f_1 + f_2)^2/4  S) mod T
so
(2*j  (f_1 + f_2))^2 = ((f_1 + f_2)^2  4*S) mod T
so you have the quadratic residue of ((f_1 + f_2)^2  4*S) modulo T, to
find j, which is kind of neat, while it's also set what the quadratic
residue is, so there's no search involved.
The main residue is a trivial result that gives k=1, but you have an
infinity of others found by adding or subtracting T.
And then you can find b, from
b^2 = x^2  S + kT
and you have the factorization:
(ba)*(b+a) = (k1)*T.
It is possible to generalize further using
j = z/y
and then the congruence equation becomes
(2*z  (f_1 + f_2)y)^2 = ((f_1 + f_2)^2*y^2  4*S*y^2) mod T.
And just like that a bit of amateur mathematical research showing what
I hope is a new way to factor.
James Harris 

Back to top 


Frederick Williams science forum addict
Joined: 19 Nov 2005
Posts: 97

Posted: Wed Jul 05, 2006 1:52 am Post subject:
Re: New factoring idea



jstevh@msn.com wrote:
Meaning what? That because it isn't mentioned in Wikipedia, it must be
new?

Remove "antispam" and ".invalid" for email address. 

Back to top 


fishfry science forum Guru Wannabe
Joined: 29 Apr 2005
Posts: 299

Posted: Wed Jul 05, 2006 2:07 am Post subject:
Re: New factoring idea



In article <1152059690.013132.23960@l70g2000cwa.googlegroups.com>,
jstevh@msn.com wrote:
Right. If it's not on Wiki, nobody ever thought of it before.
James, why not spend the time learning some math? 

Back to top 


Ulrich Diez science forum beginner
Joined: 01 Nov 2005
Posts: 9

Posted: Wed Jul 05, 2006 4:49 pm Post subject:
Re: New factoring idea



James Harris wrote:
....
Quote:  x^2  a^2 = S + T
and
x^2  b^2 = S  k*T
subtract the second from the first to get
b^2  a^2 = (k+1)*T
which is ... a factorization of (k+1)*T:
.... 
Let's number the equations:
I) x^2  a^2 = S + T
II) x^2  b^2 = S  k*T
I)II) > III) b^2  a^2 = (k+1)*T
....
Quote:  But how do you find the variables?
Well, if you pick S, and have a T you want to factor, then using
f_1*f_2 = S+T
it must be true that
a = (f_1  f_2)/2
And
x=(f_1 + f_2)/2
.... 
If I got it right, you want an integerfactorization
of T.
(a and x will only be integers as long as f_1 and f_2
are of same parity.)
So you chose S more or less arbitrarily in a way so that
the right side (S+T) of equation I can easily be written
as product of two integerfactors of same parity/as difference
of two squares for obtaining integer values for a and x.
This means that while dealing with equation I, you choose/
calculate integervalues for a, x, S and T.
After having chosen/calculated these values, you need to
solve II for integer b and k.
Why do you think that such integer b and k exist at
all for any more or less arbitrarily chosen S?
If a,b,x,S,T are not all integer  what makes you think
that you can easily obtain an integerfactorization of T
from your equationsystem?
Or looking at it from the other side:
How to find S so that
 both S+T can easily be factorized
 and there are allinteger x,a and b that will solve
your equationsystem ?
Ulrich 

Back to top 


Proginoskes science forum Guru
Joined: 29 Apr 2005
Posts: 2593

Posted: Wed Jul 05, 2006 10:34 pm Post subject:
Re: New factoring idea



Frederick Williams wrote:
Quote:  jstevh@msn.com wrote:
... I'm thinking it's not new, but looking over
at the Wikipedia:
http://en.wikipedia.org/wiki/Factoring
It's new!!!
Meaning what? That because it isn't mentioned in Wikipedia, it must be
new?

It must be, according to JSH's logic.
 Christopher Heckman 

Back to top 


Proginoskes science forum Guru
Joined: 29 Apr 2005
Posts: 2593

Posted: Wed Jul 05, 2006 10:42 pm Post subject:
Re: New factoring idea



jstevh@msn.com wrote:
Quote:  Was doodling, playing around with some simple equations
[ Derivation snipped ]
Really simple so of course I'm thinking it's not new, but looking over
at the Wikipedia:
http://en.wikipedia.org/wiki/Factoring
It's new!!!
[...]

In all seriousness, James, the dead ends of research are NOT published
(in general). So just because this approach isn't mentioned, doesn't
mean that no one thought of it.
For instance, the Four Color Theorem, which states that in any map, you
can color the regions with four colors such that no two adjacent
regions get the same color. It is not too difficult to show that you
cannot have five countries, all adjacent to each other. A COMMON
mistake, which is probably made every 6 months or so, is that this is
the same as the 4CT. However, it is not; and you will not find this
fact at Wikipedia, or even at MathWorld.
In fact, someone may have been able to prove that that particular
approach cannot work. But since it's something that doesn't work, it
wouldn't have been publishable, and no mention would have been made in
Wikipedia.
 Christopher Heckman 

Back to top 


jstevh@msn.com science forum Guru
Joined: 21 Jan 2006
Posts: 951

Posted: Thu Jul 06, 2006 12:00 am Post subject:
Re: New factoring idea



Ulrich Diez wrote:
Quote:  James Harris wrote:
...
x^2  a^2 = S + T
and
x^2  b^2 = S  k*T
subtract the second from the first to get
b^2  a^2 = (k+1)*T
which is ... a factorization of (k+1)*T:
...
Let's number the equations:
I) x^2  a^2 = S + T
II) x^2  b^2 = S  k*T
I)II) > III) b^2  a^2 = (k+1)*T
...
But how do you find the variables?
Well, if you pick S, and have a T you want to factor, then using
f_1*f_2 = S+T
it must be true that
a = (f_1  f_2)/2
And
x=(f_1 + f_2)/2
...
If I got it right, you want an integerfactorization
of T.
(a and x will only be integers as long as f_1 and f_2
are of same parity.)

I take it you mean if f_1 and f_2 are both odd or both even, which is
correct.
Quote:  So you chose S more or less arbitrarily in a way so that
the right side (S+T) of equation I can easily be written
as product of two integerfactors of same parity/as difference
of two squares for obtaining integer values for a and x.
This means that while dealing with equation I, you choose/
calculate integervalues for a, x, S and T.
After having chosen/calculated these values, you need to
solve II for integer b and k.
Why do you think that such integer b and k exist at
all for any more or less arbitrarily chosen S?
If a,b,x,S,T are not all integer  what makes you think
that you can easily obtain an integerfactorization of T
from your equationsystem?
Or looking at it from the other side:
How to find S so that
 both S+T can easily be factorized
 and there are allinteger x,a and b that will solve
your equationsystem ?

I step through how in the original post.
You end up with a congruence relationship, solve it, and you're done.
It's weirdly simple.
The gist of it, is that if you have g_1*g_2 = S+T, and f_1*f_2 = S 
k*T, you find values for k such that
g_1 + g_2 = f_1 + f_2
and doing so is just a matter of solving a congruence equation, where
quadratic residues step in, as I show in my original post.
Some remarkable mathematics that you have to keep staring at to believe
it, as it just looks too simple, even to me.
How could it be so simple, and yet not be already known?
James Harris 

Back to top 


jstevh@msn.com science forum Guru
Joined: 21 Jan 2006
Posts: 951

Posted: Thu Jul 06, 2006 5:50 am Post subject:
Re: New factoring idea



jstevh@msn.com wrote:
Quote:  Was doodling, playing around with some simple equations and noticed
that with
x^2  a^2 = S + T
and
x^2  b^2 = S  k*T
I could subtract the second from the first to get
b^2  a^2 = (k+1)*T
which is, of course, a factorization of (k+1)*T:
(b  a)*(b+a) = (k+1)*T
with integers for S and T, where T is the target composite to factor,
so you have to pick this other integer S, and factor S+T.
Really simple so of course I'm thinking it's not new, but looking over
at the Wikipedia:
http://en.wikipedia.org/wiki/Factoring
It's new!!!
But how do you find the variables?
Well, if you pick S, and have a T you want to factor, then using
f_1*f_2 = S+T
it must be true that
a = (f_1  f_2)/2
And
x=(f_1 + f_2)/2
so, you need the sum of factors of (Sk*T)/4 to equal the sum of the
factors of (S+T)/4, so I introduce j, where
S  k*T = (f_1 + f_2  j)*j
and now you solve for k, to get
k = (S  (f_1 + f_2  j)*j)/T
so you also have
S  (f_1 + f_2  j)*j = 0 mod T
so
j^2  (f_1 + f_2)*j + S = 0 mod T
and completing the square gives
j^2  (f_1 + f_2)*j + (f_1 + f_2)^2/4 = ((f_1 + f_2)^2/4  S) mod T
so
(2*j  (f_1 + f_2))^2 = ((f_1 + f_2)^2  4*S) mod T
so you have the quadratic residue of ((f_1 + f_2)^2  4*S) modulo T, to
find j, which is kind of neat, while it's also set what the quadratic
residue is, so there's no search involved.
The main residue is a trivial result that gives k=1, but you have an
infinity of others found by adding or subtracting T.

It was pointed out to me that these are also trivial, so I figured out
a way around that by turning the problem around a bit:
One approach is to find some quadratic residue r, where
(f_1 + f_2)^2  4*S = r + n*T
where n is a natural number, as then solving for f_1 gives
f_11 = (sqrt(4*S + r + n*T) +/ sqrt(r + (n1)*T))/2
so you can arbitrarily pick some integer w, square it, and get the
quadratic residue modulo T, which is then your r, so now you have
w^2 = r + (n1)*T
so you can easily solve for n, and then you pick S so that the second
square root is an integer.
So now you have
2*j  (f_1 + f_2) = w
is a solution.
Neat!!! I like solving problems!!!
Now you can get k.
Quote:  And then you can find b, from
b^2 = x^2  S + kT
and you have the factorization:
(ba)*(b+a) = (k1)*T.
It is possible to generalize further using
j = z/y
and then the congruence equation becomes
(2*z  (f_1 + f_2)y)^2 = ((f_1 + f_2)^2*y^2  4*S*y^2) mod T.
And just like that a bit of amateur mathematical research showing what
I hope is a new way to factor.

In a world where you'd think some people care about mathematics.
James Harris 

Back to top 


Frederick Williams science forum addict
Joined: 19 Nov 2005
Posts: 97

Posted: Fri Jul 07, 2006 2:59 am Post subject:
Re: New factoring idea



jstevh@msn.com wrote:
Quote: 
...
And just like that a bit of amateur mathematical research showing what
I hope is a new way to factor.

Assuming that it is new, how about showing that it's _useful_? Try
factoring some big numbers with it.

Remove "antispam" and ".invalid" for email address. 

Back to top 


Patrick Hamlyn science forum beginner
Joined: 03 May 2005
Posts: 45

Posted: Fri Jul 07, 2006 3:04 am Post subject:
Re: New factoring idea



Frederick Williams <Frederick.Williams1@antispamtesco.net.invalid> wrote:
Quote:  jstevh@msn.com wrote:
...
And just like that a bit of amateur mathematical research showing what
I hope is a new way to factor.
Assuming that it is new, how about showing that it's _useful_? Try
factoring some big numbers with it.

Jeeeezzz... don't you remember what happened last time somebody asked that?
Let's not go through that all over again... 

Back to top 


a.khanm@gmail.com science forum beginner
Joined: 02 Jul 2006
Posts: 14

Posted: Fri Jul 07, 2006 8:02 am Post subject:
Re: New factoring idea



Please apply your method to nontrivial cases and post the results
here. I believe that in doing so you will realize the problems with
this method.
jstevh@msn.com wrote:
Quote:  jstevh@msn.com wrote:
Was doodling, playing around with some simple equations and noticed
that with
x^2  a^2 = S + T
and
x^2  b^2 = S  k*T
I could subtract the second from the first to get
b^2  a^2 = (k+1)*T
which is, of course, a factorization of (k+1)*T:
(b  a)*(b+a) = (k+1)*T
with integers for S and T, where T is the target composite to factor,
so you have to pick this other integer S, and factor S+T.
Really simple so of course I'm thinking it's not new, but looking over
at the Wikipedia:
http://en.wikipedia.org/wiki/Factoring
It's new!!!
But how do you find the variables?
Well, if you pick S, and have a T you want to factor, then using
f_1*f_2 = S+T
it must be true that
a = (f_1  f_2)/2
And
x=(f_1 + f_2)/2
so, you need the sum of factors of (Sk*T)/4 to equal the sum of the
factors of (S+T)/4, so I introduce j, where
S  k*T = (f_1 + f_2  j)*j
and now you solve for k, to get
k = (S  (f_1 + f_2  j)*j)/T
so you also have
S  (f_1 + f_2  j)*j = 0 mod T
so
j^2  (f_1 + f_2)*j + S = 0 mod T
and completing the square gives
j^2  (f_1 + f_2)*j + (f_1 + f_2)^2/4 = ((f_1 + f_2)^2/4  S) mod T
so
(2*j  (f_1 + f_2))^2 = ((f_1 + f_2)^2  4*S) mod T
so you have the quadratic residue of ((f_1 + f_2)^2  4*S) modulo T, to
find j, which is kind of neat, while it's also set what the quadratic
residue is, so there's no search involved.
The main residue is a trivial result that gives k=1, but you have an
infinity of others found by adding or subtracting T.
It was pointed out to me that these are also trivial, so I figured out
a way around that by turning the problem around a bit:
One approach is to find some quadratic residue r, where
(f_1 + f_2)^2  4*S = r + n*T
where n is a natural number, as then solving for f_1 gives
f_11 = (sqrt(4*S + r + n*T) +/ sqrt(r + (n1)*T))/2
so you can arbitrarily pick some integer w, square it, and get the
quadratic residue modulo T, which is then your r, so now you have
w^2 = r + (n1)*T
so you can easily solve for n, and then you pick S so that the second
square root is an integer.
So now you have
2*j  (f_1 + f_2) = w
is a solution.
Neat!!! I like solving problems!!!
Now you can get k.
And then you can find b, from
b^2 = x^2  S + kT
and you have the factorization:
(ba)*(b+a) = (k1)*T.
It is possible to generalize further using
j = z/y
and then the congruence equation becomes
(2*z  (f_1 + f_2)y)^2 = ((f_1 + f_2)^2*y^2  4*S*y^2) mod T.
And just like that a bit of amateur mathematical research showing what
I hope is a new way to factor.
In a world where you'd think some people care about mathematics.
James Harris 


Back to top 


jstevh@msn.com science forum Guru
Joined: 21 Jan 2006
Posts: 951

Posted: Sat Jul 08, 2006 12:10 am Post subject:
Re: New factoring idea



Frederick Williams wrote:
Quote:  jstevh@msn.com wrote:
...
And just like that a bit of amateur mathematical research showing what
I hope is a new way to factor.
Assuming that it is new, how about showing that it's _useful_? Try
factoring some big numbers with it.

Well, I'll admit that having had so many failed ideas, and with it
being such a letdown to figure out something doesn't work well, I like
to fully enjoy the part where I focus on it being a new idea, and have
hope that it could be important.
And besides, that's a check of the mathematical community.
If this idea IS an excellent one, what would it mean for it to be
ignored?
Remember this is just one more bit of research for me, like I found my
own prime counting function, and in frustration one day after arguing
with math people who kept fighting its uniqueness and having noticed
that the Wikipedia didn't have a prime counting function article (it
had a redirect to a prime theorem page), I wrote the first prime
counting function for the Wikipedia.
After some iterations and a bit of help from a couple of other people,
I had the page you can see in the history which shows you some of my
OTHER number theory research:
http://en.wikipedia.org/w/index.php?title=Prime_counting_function&oldid=9142249
Now that is a oneline definition for a prime counting function that
not only counts prime numbers it finds prime numbers as it recurses,
unlike any other known.
Mathematicians refuse to fully acknowledge my research and on Usenet,
math people routinely lie about it, and call me names.
I suggest to all of you that it would not change if you had the results
instead of me.
It's a community problem.
Here with the factoring problem, you can see how bad it is.
These math professors are playing political games with mathematics, and
I say, playing with the future of humanity.
Look over my prime counting function in the Wikipedia article I wrote,
and then look back over that factoring idea and ask yourself, can you
be sure that mathematicians ignoring it means it does not work well?
And if you can, try to imagine how I feel, how devastating it is to
make discoveries and face such repudiation and insults when you
accomplished something.
James Harris 

Back to top 


Frederick Williams science forum addict
Joined: 19 Nov 2005
Posts: 97

Posted: Sat Jul 08, 2006 1:35 am Post subject:
Re: New factoring idea



jstevh@msn.com wrote:
Quote: 
Frederick Williams wrote:
jstevh@msn.com wrote:
...
And just like that a bit of amateur mathematical research showing what
I hope is a new way to factor.
Assuming that it is new, how about showing that it's _useful_? Try
factoring some big numbers with it.
Well, I'll admit that having had so many failed ideas, and with it
being such a letdown to figure out something doesn't work well, I like
to fully enjoy the part where I focus on it being a new idea, and have
hope that it could be important.

You mean it being new is more important than it being right? Look
here's something new:
7654854 + 89723648763 = 796596876486.
(Quick proof that it's new: it doesn't appear in Wikipedia.)
It's not right, but according to you it has some value because it's new,
what value exactly?
Quote:  ... look back over that factoring idea and ask yourself, can you
be sure that mathematicians ignoring it means it does not work well?

I think the onus is on you to prove that it works well.

Remove "antispam" and ".invalid" for email address. 

Back to top 


Google


Back to top 



The time now is Sat Jun 24, 2017 8:38 am  All times are GMT

