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 » Undergraduate
Factoring idea
Post new topic   Reply to topic Page 1 of 1 [5 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 2:10 am    Post subject: Factoring idea Reply with quote

After years of effort with lots of failures I noticed something
remarkably simple, and this time the math is all worked out, and there
are few places for errors to hide.

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.

But how do you find all 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.

If you're skeptical you may consider the question of finding k when you
already have the factorization of T.


James Harris
Back to top
jstevh@msn.com
science forum Guru


Joined: 21 Jan 2006
Posts: 951

PostPosted: Thu Jul 06, 2006 5:53 am    Post subject: Re: Factoring idea Reply with quote

jstevh@msn.com wrote:
Quote:
After years of effort with lots of failures I noticed something
remarkably simple, and this time the math is all worked out, and there
are few places for errors to hide.

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.

But how do you find all 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!!!

Tell me more!

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.

If you're skeptical you may consider the question of finding k when you
already have the factorization of T.


Unfortunately, my opinion is that most of you could not become real
mathematicians, and there are too many people already who need to be
cleared out who have pretended for too long.

The speed here is slow to make a point.

And part of that point is that while sure, a lot of you might be
material for math teachers or math scholars, few if any of you can
actually be a mathematician.

It takes more than some degree at some school.

You have to be someone at least a little like me, or the people who
came before me on whose shoulders I stand and in whose memory I will
act as needed.

And for most of you that means you will never be mathematicians.


James Harris
Back to top
Ben Young
science forum beginner


Joined: 15 Jun 2006
Posts: 9

PostPosted: Thu Jul 06, 2006 1:50 pm    Post subject: Re: Factoring idea Reply with quote

you are not a mathematician, nor could you tell one were it right in front of you
Back to top
Frederick Williams
science forum addict


Joined: 19 Nov 2005
Posts: 97

PostPosted: Fri Jul 07, 2006 1:25 am    Post subject: Re: Factoring idea Reply with quote

jstevh@msn.com wrote:
Quote:

...

Unfortunately, my opinion is that most of you could not become real
mathematicians, ....

And part of that point is that while sure, a lot of you might be
material for math teachers or math scholars, few if any of you can
actually be a mathematician.


Fairy snuff: this is alt.math.undergrad, it's not "for" mathematicians,
it's for undergraduate students of mathematics. Why not post the fruits
of your research in sci.math.research <giggle>?

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


Joined: 24 Mar 2005
Posts: 239

PostPosted: Fri Jul 07, 2006 7:07 am    Post subject: Re: Factoring idea Reply with quote

"Ben Young" <djfray@gmail.com> wrote in message
news:17646181.1152193874282.JavaMail.jakarta@nitrogen.mathforum.org...
Quote:
you are not a mathematician, nor could you tell one were it right in front
of you


rather harsh assessment?
Back to top
Google

Back to top
Display posts from previous:   
Post new topic   Reply to topic Page 1 of 1 [5 Posts] View previous topic :: View next topic
The time now is Sat Oct 22, 2011 1:07 pm | All times are GMT
Forum index » Science and Technology » Math » Undergraduate
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.0487s ][ Queries: 16 (0.0023s) ][ GZIP on - Debug on ]