Thursday, January 31, 2008

 

JSH: Weird, but simple math

Sorry I get a bit maudlin and over the top when I realize that there was this simple thing that somehow escaped everyone including myself for so long and part of me reacts very badly.

A lot of today I was wondering to myself how could solutions for factors modulo N actually be of any value and it still seems weird but it's just a weird math answer.

There are two key equations for existence with what I call the factoring congruences:

2ax = k mod N

and

z = x + k

so you can substitute out k and figure out an existence equation for when 'a' exists, dependent on x and z, where, of course:

x^2 = y^2 mod N

and

z^2 = y^2 mod T.

And that just gives a probability if you assume that any particular quadratic residue—as it is about a quadratic residue—is going to happen with equal probability.

With N prime that probability is about 75% that you will get this answer, but it seems so counterintuitive.

But regardless of how weird it may feel if it works then this idea can be used to not only factor but to solve the factoring problem.

Take a series of primes. Get an answer for each singly and then in pairs, and compare. Easy. There is just a probability that it will work. For the math it's just some simple answers. For humanity, who knows?

I'll look it over more carefully tomorrow, but for now it looks like it's it. I'll call it just for caution's sake and maybe later I can say that it's wrong and can just laugh it off as just another mistake.

Such a stupid little answer if it's right. Kind of disappointing.

But with trivial algebra it's hard to find it wrong. I'd say that it's solid at this point.

Kind of sucks though. All the fun is in the chase.





<< Home

This page is powered by Blogger. Isn't yours?