Re: factoring using geomerty?

From: Bruce Palmer (bpalmer201_at_optonline.net)
Date: 09/29/03 

Date: Sun, 28 Sep 2003 23:46:37 GMT

sqrt(i) wrote:

> does anyone know if a method using geometry has been used, or could be
> developed to factor numbers into their primes factors?
> Does anyone have an idea where to start? and what kind of geometry will be
> most useful to the purpose of factoring?

Here's how to visualize one way to do it:

Imagine 2 squares, one smaller than the other and inside the other with both of
their bottom-left corners coinciding at (x,y) = (0,0). Take the number you want
to factor and multiply it by 4. Now, attempt to set the lengths of the sides of
the squares such that the area _between_ the inner square and the outer square
is equal to 4 * N, where N is the number you want to factor.

Geometrically this area is s1^2 minus s2^2 (s1 is the length of the side of the
larger square and s2 is the smaller), so you've got s1^2 - s2^ = 4N. If you can
do this with both s1 and s2 _being_integers_ then you have factored the number
because, assuming the factors are p and q (with p being the larger of the two),
s1 = p + q and s2 = p - q.

Example: Factor N = 35. The larger square has a side length of 12 and the
smaller square has a side length of 2. The difference in their areas is 12^2 -
2^2 = 144 - 4 = 140. Note that 140 = 4 * N. So we have p - q = 2 and p + q =
12. Add them together to get 2p = 14. Thus, p = 7 and q must therefore = 5.
The factors of 35 are 5 and 7.

This is probably a simplistic way of talking about quadratic residues, I'm not
sure. Finding squares that fulfill the necessary condition is easy. Finding
squares with integer-size side lengths is not.

 From what I understand - admittedly not a lot - elliptic curves are a useful
mathematical construct for factoring, but their usefulness comes more from the
amenability of their equations to being manipulated rather than any
visualization excercises.

Relevant Pages

  • Re: JSH: Finally useful theory?
    ... Likewise even if you present a factoring approach that just looks promising ... the implications are HUGE: ... You'll see for yourself that the gcd is ... pick any x and y whatsoever that are squares of integers (pick ...
    (sci.math)
  • Surrogate factoring, correcting sign problems
    ... really don't like an answer for some reason. ... That is, you can find integer Ax from the relation for Az, by factoring ... I talked about algorithms that just checked Ax to see if it has ... It turns out that you can use the Ax to do the difference of squares or ...
    (sci.crypt)
  • Difference of squares, SF
    ... Using a difference of squares you can sometimes factor a target ... After months of discussing surrogate factoring I've yet to hear anyone ... problem so there must be a reason that you wouldn't factor M. ...
    (sci.crypt)
  • Re: Difference of squares ,SF Theorem
    ... > of squares. ... > Surrogate Factoring Theorem: ... mathematics" and explain why each only gives trivial factors. ... ] But they DO disagree and they disagree quite boldly. ...
    (sci.crypt)
  • Re: Difference of squares ,SF Theorem
    ... > difference of squares, potentially non-trivial, like the SF Theorem ... In fact, factoring T j^2 as ... and the mathematics just does not show any preference for ... The chance that n is divisible by both p and q is 1/. ...
    (sci.crypt)