Saturday, July 10, 2004

 

Surrogate factoring, update

It's been a while since I mentioned surrogate factoring, and I'll admit that I'm still just trying to figure out basics. I haven't seen evidence of interest in the idea, so I think I'll talk a bit more about why I think there should be a LOT of interest.

A little while back I discovered the factorization:

(jk - Tk + T)(jk + Tk + T) = T^4

and I've emphasized that it's of interest because solving for k, gives

k = (-jT +/- T^2 sqrt(j^2 - T^2 + 1))/(j^2 - T^2)

so that rational k's depend on sqrt(j^2 - T^2 + 1), so if you're trying to factor T, the target, then you can use rational factors of T^2 - 1, the surrogate.

Now then, what about j? Well the easiest thing is just to solve for it to get

j = (-T +/- T sqrt(k^2 + T^2))/k

where now you see that getting a rational k depends on rational factors of T itself.

Another way to think of it is that if you find a rational k with the solution for k using rational factors of T^2 - 1, then necessarily, you are getting solutions dependent on the rational factors of T, as seen by the solution for j.

You see I deliberately went looking for factorizations like

(jk - Tk + T)(jk + Tk + T) = T^4

where the solution for k is warped slightly by the asymmetry, so that it couldn't be defined in a direct manner by the rational factors of T, while j is.

Now then, how does the math pick?

If T were prime, then of course the only positive integer k that you could have with positive integer T is T-1. That's easy.

But if T is composite, say, T = p_1 p_2, then k can equal p_1 - p_2, as well as T - 1.

So how does the math pick between those possibilities?

I don't know.

My original hope was that it would split down the middle.

That is, that half the time you'd get p_1 - p_2, and the other half you'd get T-1, but if I'd found that to be true, I'd have factored the RSA Challenge by now, and wouldn't be making this post!!!

So what gives? What decides which difference of rational factors of T get picked?

One problem is that practically you end up with k's that are fractions, though if someone figured out a way to get integer k's then they'd have a potent solution.

Now then, at this point in time, the reasonable position, unless someone can show otherwise, is that mathematically there may indeed be a way to factor a composite using surrogate factoring a fairly high percentage of the time.

If that is true, then it will affect public key encryption schemes.

I'm just one person. While I'm the only one talking publicly about this, others may be busily working in private, or more than likely, it just sits while I fiddle with it.

But ignoring this idea may be the most dangerous thing that mainstream mathematicians do.

Personally, given the talk about "pure math" I find it extraordinary that I have to even push this idea. You'd think there'd be some curious mathematicians out there, just because.

Maybe I'm missing something. If someone can quickly explain why this idea is no threat, then that'd be appreciated, so that I don't worry anyone else!!!

If no one can, then I think mathematicians may one day have to answer some hard questions about what they really believe and value, versus what they claim is important to them.

Like, what if "pure math" is just an excuse for mathematicians to do nothing important but get paid for it, when they don't even believe in it themselves?

What if it's just a scam?

What if they left the world unprotected, trusting and open for selfish reasons in a story as old as man, and one that often ends tragically?

What if you have no security at all?

I'm painting a dire picture because I want answers. If someone can rule out value to this idea, then I hope they'll do it now. No need for unnecessary panic.





<< Home

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