Translate

Tuesday, January 01, 2013

Another approach?

My latest mathematical ideas can be related to integer factorization, which can be simply seen as solving a binary quadratic Diophantine equation.

And my finding of the rules for x2 - Dy2 = 1 actually are relevant in one way, though a more general equation may be even more important.

First off, I found that the size of the fundamental solution is only really large compared to D, when D is a prime or twice a prime, and neither D+1, D-1, D+2 nor D-2 is a square. And if D-1 has small primes as factors, and also if 4 itself is a factor.

Well if you just let D equal T, an odd composite target to be factored, guess what? You know it's not a prime or twice a prime, and the likelihood that T-1, T+1, T-2, or T+2 is a square is small as you get to larger T.

So remarkably, you may factor with (x-1)(x+1) = Ty2 where you can use my modular solution to generate x modulo N, for as large an N as you wish!

With x2 - Ty2 = 1:

Find a non-zero integer N for which a residue m exists where, m2 = T mod N, and r, any residue modulo N for which r-1 mod N exists then:

2x = r + r-1 mod N and 2my = r - r-1 mod N

If N is on the order of the size of T, then you may just get a solution, theoretically, as I haven't bothered to check! Just musing about things that occurred to me.

Weirdly enough though, the size of solutions for x and y could be a LOT smaller than one might think from looking at big solutions to what mathematicians commonly call "Pell's Equation" and the modular solutions allow one to easily try the idea out with even a very large composite T.

Also, knowing the rules, the fundamental solution will tend to factor T, remarkably enough, as it won't be -1 or 1 mod T.

Which can be shown, as is traditional, by showing a factorization of 15.

42 - 15(1)2 = 1, and (4-1)(4+1) = 15

Isn't it fascinating how much more you know when you have the rules?

However, it might be better to go more general and use: x2 - Ty2 = C2

Now the fundamental solution rules above no longer apply unless C2 = 1, and now you can factor with:

(x-C)(x+C) = Ty2

And then the modular solution for x2 - Ty2 = C2 is:

Find a non-zero integer N for which a residue m exists where, m2 = T mod N, and r, any residue modulo N for which C2r-1 mod N exists then:

2x = r + C2r-1 mod N and 2my = r - C2r-1 mod N

Finding N is actually easy, as for instance, N = m2 - T, would work, where you just pick m.

You'd also pick C, of course, and I kind of wonder what values might work best!

You see, it's guaranteed that solutions may factor T if it's a composite, but not at all clear to me how often such solutions would occur, or what choices would provide them.

And maybe I'm grasping for something! I found these modular solutions and think they should be important.

But who knows?

However, they do allow endlessly generating solutions for x and y mod N, where you can make N as large as you wish.

So some speculation. Maybe I should check these things. I do wonder how well they work!

And this approach may not work well at all. I don't know. But it is a fairly obvious way that might factor so worth mentioning. Also it gives me a chance to note that the fundamental solution to what mathematicians call "Pell's Equation" will tend to factor D. I find that curious.


James Harris
Post a Comment