FAQFAQ   SearchSearch   MemberlistMemberlist   UsergroupsUsergroups 
 ProfileProfile   PreferencesPreferences   Log in to check your private messagesLog in to check your private messages   Log inLog in 
Forum index » Science and Technology » Math » Recreational
New factoring idea
Post new topic   Reply to topic Page 1 of 1 [13 Posts] View previous topic :: View next topic
Author Message
jstevh@msn.com
science forum Guru


Joined: 21 Jan 2006
Posts: 951

PostPosted: Wed Jul 05, 2006 12:34 am    Post subject: New factoring idea Reply with 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 (S-k*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:

(b-a)*(b+a) = (k-1)*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

PostPosted: Wed Jul 05, 2006 1:52 am    Post subject: Re: New factoring idea Reply with quote

jstevh@msn.com wrote:
Quote:

... 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?

--
Remove "antispam" and ".invalid" for e-mail address.
Back to top
fishfry
science forum Guru Wannabe


Joined: 29 Apr 2005
Posts: 299

PostPosted: Wed Jul 05, 2006 2:07 am    Post subject: Re: New factoring idea Reply with quote

In article <1152059690.013132.23960@l70g2000cwa.googlegroups.com>,
jstevh@msn.com wrote:


Quote:
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!!!


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

PostPosted: Wed Jul 05, 2006 4:49 pm    Post subject: Re: New factoring idea Reply with quote

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 integer-factorization
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 integer-factors 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 integer-values 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 integer-factorization of T
from your equation-system?
Or looking at it from the other side:
How to find S so that
- both S+T can easily be factorized
- and there are all-integer x,a and b that will solve
your equation-system ?

Ulrich
Back to top
Proginoskes
science forum Guru


Joined: 29 Apr 2005
Posts: 2593

PostPosted: Wed Jul 05, 2006 10:34 pm    Post subject: Re: New factoring idea Reply with quote

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

PostPosted: Wed Jul 05, 2006 10:42 pm    Post subject: Re: New factoring idea Reply with quote

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

PostPosted: Thu Jul 06, 2006 12:00 am    Post subject: Re: New factoring idea Reply with quote

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 integer-factorization
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 integer-factors 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 integer-values 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 integer-factorization of T
from your equation-system?
Or looking at it from the other side:
How to find S so that
- both S+T can easily be factorized
- and there are all-integer x,a and b that will solve
your equation-system ?


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

PostPosted: Thu Jul 06, 2006 5:50 am    Post subject: Re: New factoring idea Reply with quote

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 (S-k*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 + (n-1)*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 + (n-1)*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:

(b-a)*(b+a) = (k-1)*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

PostPosted: Fri Jul 07, 2006 2:59 am    Post subject: Re: New factoring idea Reply with quote

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 e-mail address.
Back to top
Patrick Hamlyn
science forum beginner


Joined: 03 May 2005
Posts: 45

PostPosted: Fri Jul 07, 2006 3:04 am    Post subject: Re: New factoring idea Reply with quote

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

PostPosted: Fri Jul 07, 2006 8:02 am    Post subject: Re: New factoring idea Reply with quote

Please apply your method to non-trivial 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 (S-k*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 + (n-1)*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 + (n-1)*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:

(b-a)*(b+a) = (k-1)*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

PostPosted: Sat Jul 08, 2006 12:10 am    Post subject: Re: New factoring idea Reply with quote

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 re-direct 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 one-line 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

PostPosted: Sat Jul 08, 2006 1:35 am    Post subject: Re: New factoring idea Reply with quote

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 e-mail address.
Back to top
Google

Back to top
Display posts from previous:   
Post new topic   Reply to topic Page 1 of 1 [13 Posts] View previous topic :: View next topic
The time now is Fri Nov 17, 2017 5:25 pm | All times are GMT
Forum index » Science and Technology » Math » Recreational
Jump to:  

Similar Topics
Topic Author Forum Replies Last Post
No new posts Crackpot factoring scheme? Dann Corbit Math 1 Thu Jul 20, 2006 10:56 pm
No new posts Another look at triangle number factoring. Dan11 Math 2 Tue Jul 18, 2006 7:05 pm
No new posts Primality & Factoring Gerry num-analysis 3 Tue Jul 18, 2006 10:45 am
No new posts SF: Definitely a new factoring method jstevh@msn.com Math 36 Tue Jul 18, 2006 1:22 am
No new posts Max Tegmark's Objections Against Hameroff's Microtubule C... Jack Sarfatti Math 2 Mon Jul 17, 2006 4:33 am

Copyright © 2004-2005 DeniX Solutions SRL
Other DeniX Solutions sites: Electronics forum |  Medicine forum |  Unix/Linux blog |  Unix/Linux documentation |  Unix/Linux forums  |  send newsletters
 


Powered by phpBB © 2001, 2005 phpBB Group
[ Time: 0.0335s ][ Queries: 16 (0.0038s) ][ GZIP on - Debug on ]