Re: JSH: Factoring with Pell's Equation

On Jan 20, 8:49 pm, Scott Contini <the_great_cont...@xxxxxxxxx> wrote:
On Jan 21, 12:26 pm, JSH <jst...@xxxxxxxxx> wrote:



The result I noticed previously can also be a factoring result,
intriguingly enough, which deserves its own thread.

Given x^2 - Dy^2 = 1

you have solutions for an ellipse or Pythagorean triples with

(D-1)j^2 + (j+/-1)^2 = (x+y)^2

where  j = ((x+Dy) -/+1)/D, and j can be a fraction.

So if a target composite N to be factored is given by D-1, you have
that finding a non-trivial solution to

x^2 - (N+1)y^2 = 1

will give a difference of squares with the target composite i.e.

Nj^2 + (j+/-1)^2 = (x+y)^2, where j = ((x+(N+1)y) -/+1)/(N+1).

But it's even better, as given one non-trivial solution to a Pell's
Equation you can trivially generate as many more as you like, so you
can continually generate tries at non-trivially factoring N.

So solving Pell's Equation is directly connected to integer
factorization.

James Harris

Factoring by solving the Pell equation is not a new observation.
I think you misunderstand that the study of factoring is about
finding *efficient* algorithms to factor, not about trying to find
new equations that lead to inefficient factoring algorithms.
You really should learn a bit about the analysis of these type
algorithms, and since you are interested in the Pell equation,
you might start by reading this:
  "Solving The Pell Equation"
  H.W. Lenstra, Jr.
 http://www.ams.org/notices/200202/fea-lenstra.pdf
This article emphasizes efficiency, and it is written at a
level that a non-expert in mathematics can appreciate it.

I've read it. And you're deluded.

No one in 2000 years of history on this subject previously found that
Pell's Equation DIRECTLY connects to integer factorization, as if they
had we would not have RSA encryption today.

The result shows that you can solve for (D-1)u^2 + w^2 = v^2, using
solutions to x^2 - Dy^2 = 1, or vice versa.

So setting D-1 equal to a target composite gives you an infinity of
tries at factoring D-1 with

(D-1)u^2 = (w - v)(w + v).

But you can go in EITHER direction--you can solve a Pell's Equation or
variant: x^2 - Dy^2 = C^2, which will work, with a TRIVIAL
factorization of (D-1)u^2, and then generate an infinity of new
solutions to Pell's Equation or the variant, with which to try and NON-
TRIVIALLY factor your target.

Quite simply, it is a trivial solution to the factoring problem that
remarkably enough uses Pell's Equation, which is just the kind of
twist that can only happen in reality. Truth is stranger than
fiction.

Now you can deny trivial algebra all you want, but it won't change the
result. Factoring problem is trivially solved through Pell's
Equation.

Put a fork in it, it's done.


James Harris
.

Relevant Pages

  • Re: JSH: Factoring with Pells Equation
    ... that finding a non-trivial solution to ... I think you misunderstand that the study of factoring is about ... new equations that lead to inefficient factoring algorithms. ... You say nobody in the history of the subject has noticed this ...
    (sci.crypt)
  • Re: JSH: Factoring with Pells Equation
    ... So if a target composite N to be factored is given by D-1, ... Factoring by solving the Pell equation is not a new observation. ... new equations that lead to inefficient factoring algorithms. ...
    (sci.crypt)
  • Re: SF: Generalized SFTs
    ... I don't know if I can describe the feeling, ... He knows darned well too that his previous rounds of "proven correct" factoring algorithms were proved wrong by trying examples, ...
    (sci.math)
  • SF: Back to theory
    ... I see a lot of negative postings about my ideas, ... factoring is getting a lot of bashing, but hey, it's just an idea. ... Basically with the latest surrogate factoring I've been analyzing the ... algorithms, which I'll get to later, require that both j and T be ...
    (sci.math)
  • SF: Back to theory
    ... I see a lot of negative postings about my ideas, ... factoring is getting a lot of bashing, but hey, it's just an idea. ... Basically with the latest surrogate factoring I've been analyzing the ... algorithms, which I'll get to later, require that both j and T be ...
    (sci.crypt)
Loading