Monday, November 23, 2009

 

JSH: Generalizing quadratic residues solution idea

Earlier today I was pondering this weirdly simple idea for solving for quadratic residues I have and realized I should look at the generalization, so I wrote down: f_1 = ak mod p, and f_2 = bk mod p, and quickly realized I had:

k = (a+b)^{-1}(f_1 + f_2) mod p

with T = f_1*f_2 = abk^2 = abq mod p

to solve for k, when k^2 = q mod p.

But it's so weirdly simple and worse ab and a+b are unique!

So to the math when you have k = (a+b)^{-1}(f_1 + f_2) mod p, where f_1*f_2 = abq mod p, then you are TELLING it what 'a' and 'b' are, as that's forced. So the math knows what you're playing with as it's unique!!!

But then again, with p an odd prime, you can have a BUNCH of potential 'a' and 'b' that will work, so conceivably what will happen is that they'll keep kicking out the same k, unless a given choice is blocked for a particular T.

So how can a choice be "blocked" for T? Well, like if ak < p and bk < p, but T does not have k as a factor, then that T is blocked.

But if there are no blockings then this method should give k.

That is so weird. But even weirder if it works well and was missed!!!

One reason it could be missed is that math people learn that congruences are USELESS with factoring as, given say,

product = mn mod p

where m and n are residues modulo p, there are p-1 factorizations: that is, there is a factorization for EVERY nonzero residue!

Math people have it banged into their heads that for that reason residues and factoring don't mix.

But I've found that looking at just the product is wrong!!! You can also get a SUM and that SUM AND PRODUCT ARE UNIQUE.

Such a simple difference and so much history can change. Maybe if Gauss had noticed this thing we'd have never had public key encryption, eh?

IMAGINE how the history of our world would have changed! History turned on a simple miss.





<< Home

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