Translate

Monday, April 16, 2018

Finding quadratic residues with modular inverse

Am curious about numbers often and find myself trying things. And realized had not yet used one of my innovative ideas in a way that looks possible. So figured may as well try a few things. And doing so public helps my process.

Have focused on x2 - Dy2 = F, as a fundamental equation which controls much of the behavior of integers.

Importantly, realized could solve modularly, as for some integer N, will be true that D is a quadratic residue, such that D = m2 mod N, for some m.

Which means have a useful factorization available:

x2 - Dy2 = x2 - m2y2 = (x-my)(x+my) = F mod N

Where then, for some residue r, x + my = r mod N, and x - my = Fr-1 mod N

And used this direction to find my own way to get the modular inverse, but am thinking could be used to find m, as well. Though why bother? Well, am curious.

Can solve for x, as: 2x = r + Fr-1 mod N, and 2my =  r - Fr-1 mod N

If I simply pick r, then get its modular inverse, and set F, then I have set x.

And with this path can simply set y = 1 mod N, and F = 1 mod N, and then find D, from D = x2 - 1 mod N.

For example, let N = 119, where I like to use composites for these types of experimental musings, as primes can be too particular. This approach does not care though if prime or not, so using a composite covers more territory.

And let's let r = 2 mod 119, for easy. As then also r-1 = 60 mod 119.

So: 2x = 2 + 60 = 62 mod 119, and x = 31 mod 119.

And 2m = 2 - 60 = -58 mod 119, and m = -29 = 90 mod 119

And D = 312 - 1 mod 119 = 8 mod 119

And yeah 902 = 8 mod 119, as required.

Well still ended up squaring x, and definitely does not seem practical to me. Will do one more easy.

So will go up one, and let r = 3 mod 119, again for easy. As then also r-1 = 40 mod 119.

So: 2x = 3 + 40 = 43 mod 119, and x = 43(60) = 81 mod 119.

And 2m = 3 - 40 = -37 mod 119, and m = 60(-37) = 41 mod 119

And D = 812 - 1 mod 119 = 15 mod 119

So of course: 412 = 15 mod 119

And my curiosity is satisfied, for now. Though does not look like did much more than look at examples of the modular factorization. Obviously you can simply square numbers and get residue modulo N, directly without taking this slightly convoluted path.

Of course I set F = 1 mod N, just playing around. But can set to minimize x, or who knows. Just playing around just a bit, so will not speculate much.

Oh, but you could use the BQD Iterator, to get another set of solutions for x, with the same D, if the same r holds. That of course shifts y and F. And then you can solve for m.

Wow that might work. Don't even have to do another square either, as have D. And could be a way to loop through all possible m's for a given D. BUT it could just give the same m, as before. And maybe r does shift when you iterate. Will not try it myself though. Just note it here, for now.

Of course would bring BQD Iterator up, as use it so much. But think is the key controller across integers. That thing is SO wild. Is like this super key to just about anything with integers. Where just have to use your imagination. And that I guess I have.

These kinds of things can be stubs, where later may notice something else which follows. So is worth it to have these initial musings public, as may lead nowhere interesting, but then again, could lead to something else really cool. And how would I know at this point?

Just musing on some math for me is so much of the fun.


James Harris

No comments: