Thursday, May 20, 2004
Thoughts on factoring
[sarcasm] Anybody who's anybody these days thinks about factoring [/sarcasm]. It's a beautiful thing, really, to be able to factor very large integers in polynomial time. Anyway, we're not there yet. I think therefore it's o.k. to be a bit creative when approaching the problem. Here's my approach. The first, and most important question in my opinion, is what would an algorithm or equation that factored large numbers do? That seems simple up front - well, factor the number of course. But there's the rub. You don't know (unless you're factoring RSA numbers or someone tells you, or you construct the number yourself) how many factors a number _has_ before you start. So, in my opinion a successful factoring algorithm or equation would do two things. First, it would output the number of factors in the number (my personal view is that this would include multiple instances of the same factor, so that 16 has four factors (2 * 2 * 2 * 2)). Second, it would produce all the factors in one interation. That, to me, is what the equation or algorithm would do. To summarize -- output Bigomega (the upper-case Greek letter that signifies "primes counted with multiplicity") and output all the factors, without using a recursive loop to find successive factors.
Quantum computing provides interesting possibilities as far as these "requirements" are concerned. In fact, one of the two main algorithms discovered so far for quantum computers is a factoring algorithm. However this algorithm finds one factor at a time -- http://en.wikipedia.org/wiki/Shor%27s_algorithm by computing the "period" of the function A^r Mod N, where a is a pseudo-random number less than n. I've noticed some similarities between some of the math I'm working on and some of the math used in quantum computing [er, that's because they use the same kinds of math - ed]
Where does that leave me? High and dry, first off (I haven't even begun to find anything yet). It may be that an equation or algorithm with these output requirements doesn't exist, that I'm following a cold trail. Nevertheless, it's what I have to work with so I'm pursuing it. Over the next few days I'll post the stuff I've been doing. I should, of course, put a warning here -- WARNING: I don't have a degree in math although I studied a fair amount of it in college. My basic math skills are somewhere south of "suck", so don't take any math I present here as either a.) accurate, or b.) representative of the rest of mathematics. There are huge numbers of people out there whose skills far surpass mine. I just do this because, for me, it's fun and I really don't know if it might be useful or not. In the event any of it is, I'd like my "work" to be out there for other folks to use. Besides, someone out there might be able to offer useful corrections, although I suspect anyone with the skills to do so has better things to do.
Quantum computing provides interesting possibilities as far as these "requirements" are concerned. In fact, one of the two main algorithms discovered so far for quantum computers is a factoring algorithm. However this algorithm finds one factor at a time -- http://en.wikipedia.org/wiki/Shor%27s_algorithm by computing the "period" of the function A^r Mod N, where a is a pseudo-random number less than n. I've noticed some similarities between some of the math I'm working on and some of the math used in quantum computing [er, that's because they use the same kinds of math - ed]
Where does that leave me? High and dry, first off (I haven't even begun to find anything yet). It may be that an equation or algorithm with these output requirements doesn't exist, that I'm following a cold trail. Nevertheless, it's what I have to work with so I'm pursuing it. Over the next few days I'll post the stuff I've been doing. I should, of course, put a warning here -- WARNING: I don't have a degree in math although I studied a fair amount of it in college. My basic math skills are somewhere south of "suck", so don't take any math I present here as either a.) accurate, or b.) representative of the rest of mathematics. There are huge numbers of people out there whose skills far surpass mine. I just do this because, for me, it's fun and I really don't know if it might be useful or not. In the event any of it is, I'd like my "work" to be out there for other folks to use. Besides, someone out there might be able to offer useful corrections, although I suspect anyone with the skills to do so has better things to do.
