Simple factoring algorithm?

jstevh_at_msn.com
Date: 12/12/04 

Date: 12 Dec 2004 06:39:16 -0800

I made a post a couple of days ago mentioning this basic idea I had a
couple of days ago. Now I'm going to step it out into an algorithm.
To see the derivations go to my previous thread: "Simple factoring,
finally?"

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. Here to minimize that value 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

  • Basic 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.math)
  • 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: OT How to represent a fraction in HEX?
    ... > I wish to take a fraction in DEC say .4 and convert it to a HEX value. ... There is a simple algorithm you can use for conversion of fractions. ...
    (comp.lang.cpp)
  • 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)
  • Re: very basic tip (which you may know already)
    ... and 15 32nds of an inch) to enter fractional values for dimensions ... (substitute what ever whole number and fraction you want). ...
    (comp.cad.solidworks)
Quantcast