Basic factoring algorithm?

jstevh_at_msn.com
Date: 12/12/04 

Date: 12 Dec 2004 06:44:13 -0800

Yesterday, I made a post mentioning this basic factoring idea I had a
couple of days ago. Now I'm going to step it out into an algorithm.
To see the derivation of the formulas that follow see my previous
thread.

The base equation is

yx^2 + Ax - k = T

where T is the target, and A is picked.

y = n + T, where n is given by

n = (2k +/- sqrt((2k + T)^2 + A^2 - T^2))

where you use the factors of A^2 - T^2 to determine k, so that n will
be an integer.

That's done simply enough as if you have factors 4f_1 f_2 = A^2 - T^2,
and

2k + T = f_1 - f_2

then

(2k+T)^2 + A^2 - T^2 = f_1^2 - 2f_1 f_2 + f_2^2 + 4f_1 f_2

so

(2k+T)^2 + A^2 - T^2 = f_1^2 + 2f_1 f_2 + f_2^2 = (f_1 + f_2)^2

and you have simply enough that

n = (2k +/- (f_1 + f_2)).

Here to minimize that value of A^2 - T^2 you can just let

A = floor(sqrt(T)) or A = floor(sqrt(T)) + 1

where the first gives a negative number and the second a positive one.

Now you have y and k, so you can go back to

yx^2 + Ax - k = T

and substitute those values in, which allows you to solve for x, and x
will be rational, but it will be fraction. Now you also need to factor
the left side, to get the factors of T.

One way is to introduce z, where

yz^2 + Az - k = 0, and solve for z.

It will come out rational and a fraction, and you make sure that the
numerators and denominators of its solutions are coprime, so you have

z_1 = -b_1/a_1, and z_2 = -b_2/a_2

and that gives

(a_1 x + b_1)(a_2 x + b_2) = yx^2 + Ax - k

so now you have all the values you need.

To finish you just substitute in the value of x, from earlier as you
have

(a_1 x + b_1)(a_2 x + b_2) = T

and simplify, and you will necessarily have factors of T, but I don't
know if they'll be trivial or not. If T is prime, of course, you'll
get T(1), or (-T)(-1) or something like that, but at this point,
mathematically I don't see why you wouldn't get non-trivial factors of
T if it's not prime.

But I've STILL not tested this idea, only worked it out theoretically
and now given the algorithm. Talking it out helps me. Hopefully if
there's some flaw in it, I'll see it sooner than later, versus
investing a lot of time and effort in an idea that doesn't work. For
me talking it out is part of a process that usually has ended in
failure. But hey, it's also an engaging process for me, which I enjoy,
so I keep at it!

James Harris

Relevant Pages

  • Simple factoring algorithm?
    ... Now I'm going to step it out into an algorithm. ... It will come out rational and a fraction, and you make sure that the ... To finish you just substitute in the value of x, ... But hey, it's also an engaging process for me, which I enjoy, ...
    (sci.crypt)
  • Re: E96 Series Computation
    ... >>>3) multiply remaining fraction by 64 ... >>>absolute closest standard value to arbitrary input R are hopelessly lost ... >>>as noise compared to tolerance. ... >> I guess I don't understand what your algorithm is supposed to do. ...
    (sci.electronics.design)
  • Re: Evolution in HS Anthropology class
    ... algorithm provides a solution is the so-called Halting Problem for ... the fraction 1/7 means one of seven equal parts of the whole. ... 1/5 of the pizza. ... Each student now has seven equal-sized small pieces, ...
    (talk.origins)
  • Re: Evolution in HS Anthropology class
    ...  An algorithm is an effective procedure for solving a problem. ... The concept of "fraction", leaving aside improper fractions for the ... 1/5 of the pizza. ... Each student now has seven equal-sized small pieces, ...
    (talk.origins)
  • Re: GCD in Z[x]_5
    ... Mkajuma wrote: ... One way to do this is to first determine the gcd via Euclid's algorithm: ... substitute r_with its value given by the previous line, ...
    (sci.math)