Crazy Math

...And here's some real math:

http://scholar.lib.vt.edu/theses/available/etd-32298-93111/unrestricted/etd.pdf

This is a very good paper that explains the current state-of-the-art in factoring. There might be other stuff on the horizon, but as far as meat-and-potatos in-use factoring is concerned, the General Number Field Sieve method is it. The paper has a very good introduction section which explains several concepts that I've always wanted to understand -- Factor base, "smooth", etc. It also includes worked examples (although I haven't made it to those yet) and a step-by-step of how the whole thing works. It's a rather long paper, so cuddle up with a pen and paper and play along for a few nights after work for maximum fun. Combined with the video lectures by David Deutsch linked below, these two sources are a good place to go for introductions (if you already have some physics and math under your belt) to the topics of factoring and quantum computing. Anyway, I figure that if I should ever actually come up with something useful for factoring, I should understand how it relates to the current algorithm and be able to explain how it's different. Plus, it's never a bad thing to learn _real_ math and physics!

Here's the first part in a series about my investigations into factoring. As I said earlier, I think that any "algorithm" (I'll use that word to mean both computer programs (classical or quantum) and equations) that successfully factors numbers in polynomial time should output all the factors and simultaneously output Bigomega.

Let's begin by looking at the _function_ Bigomega. It is defined as a function which outputs all of the factors of a number with multiplicity. Bigomega of 1 thru 10 is {1, 1, 1, 2, 1, 2, 1, 3, 2, 2}. Now, let's say we want to know Bigomega of any number x multiplied by 1 thru 10. The answer will be Bigomega{1..10} + Bigomega(x). So, if we were to use the number 3, then Bigomega of our new set (i.e., 3 * {1..10}) is {1, 2, 2, 3, 2, 3, 2, 4, 3, 3}. Note what happens with the number 1. When you multiply any number by 1, you get the same number, thus multiplying by 1 has no effect on Bigomega, so from here on out when speaking about multiplication we'll skip the number 1 (one, though, will become much more interesting in a moment...).

For now, let's formalize this a bit:

I = set of all positive integers
S = some subset {n1...nx} of I
x = member of I

So, Bigomega(S * x) = Bigomega S + Bigomega x, S > 1
For S = 1, Bigomega(S * x) = Bigomega x

Multiplication, then, is pretty straightforward...right? Let's now examine the case of addition. Before getting into sets, we'll start simple. Take, for instance, the case of the number 3. Add 1 to 3 we get 4. Bigomega of 3 = 1, while Bigomega of 4 = 2. Add 1 again, we get 5, and Bigomega of 5 is 1. If we do this on to infinity, we'll end up with Bigomega I, I > 3. Let's make this more interesting. Consider, for a moment, what multiplication really means. If we write "3 * 5", we could just as easily say "add three to itself 5 times", or "add 5 to itself 3 times". In other words, multiplication is just a special case of addition. It's some "unit" x (which is a member of I) added to itself n number of times. So, multiplciation is just "unit addition". Let's consider that for a moment -- "unit addition" creates the same Bigomega output as multiplication. Whether we add 1 to itself some n number of times or 5 to itself some n number of times, the result will be the same - Bigomega(x) + Bigomega(n).

So, if that's the case... Let me introduce a concept I've been playing with that I call "offset". I'm still looking into it, which means I don't understand everything about it. Anyway, it works like this. Say we use a unit of 10. 10 + 10 = 10 * 2 = 20. Bigomega(20) = 3 (because 20 = 2 * 2 * 5). What if, instead of doing 10 + 10, we do 10 + 9, 10 + 9 + 9, etc.? We'll get 10, 19, 28, 37, and so on. In this case, the "offset" is +1. This is so because our series could also be expressed as 1 + 9, 1 + 9 + 9, etc. These "offset" series produce different patterns of output for Bigomega. One of the areas I'm interested in examining is how these sets relate to each other. You may have noticed that for some set created by using 9 as the unit of addition, there are exactly 9 possible offisets which won't repeat themselves. Note that if you extended all 9 sets to infinity and combined them, you'd end up with the set I, I > 9. Now, if you're really paying attention you'll notice something cool here. If we start with, say, 1 + 9, then continue on up to 8 + 9, we'll get every number except multiples of 9. So, we now add in 9 + 9, or offset 0... This system is feeding back on itself, i.e. that last set is simply 9 * I. We _have_ to have a "unit" set if we want to recombine the sets to get I, I > 9. The implications of this are very interesting, namely, that within the set of integers I, the basic pattern Bigomega(I) + Bigomega(x) repeats itself many, many times. Bigomega I _is_ the basic pattern, but it's composed on an infinite number of copies of itself!

I'll go ahead and stop here for now. In the meantime, let me give you something to think about until my next post (whenever that is). What is the smallest possible number with n number of factors? Or, in other words, what's the smallest possible number with 3 factors? with 4? And so on.

[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.

http://www.allsci.com/parallel.html

A cool experiment demonstrating quantum interference that you can do at home.

http://www.quiprocone.org/Protected/DD_lectures.htm

If you've ever wanted to learn about quantum computing, here's a resource. Each lecture is an hour-long video (about 66 megs download size). So far, there are three. Highly recommended.

O.k., some further thoughts: Say we have a simple oscillator, a NOT gate which feeds back on itself. We set the system into "motion", and sample values immediately before the NOT gate, at some time T, and immediately after the gate, at some time T + dT, where dT is the time necessary to traverse the gate. If the system is clocked with a crystal or some other means, then dT is always the same to within some margin of error. What if we made dT random and isolated the system? If we sampled values before and after the gate, we'd still get the same "weight" for 1 and 0 (50% each). However, if dT is random and we have no way of measuring it, then we don't know if, at a particular instant, we'll measure a 1 or a 0. I wonder how similar this situation would be to the state of "superposition", the quantum state where the probability of finding the value of some variable in a system to be a or b is, essentially, the only valid description of the "state" of the system. For example, if an electron is provided exactly one-half of the energy to jump from energy level a to energy level b, then the probability of finding that electron in either energy level is 50%. And that's as specific as we can be about the state of the electron with respect to it's location in one of the two energy levels. That is, of course, until we measure which state the electron inhabits, or the system gains or loses energy. So, is the NOT gate system with random dT in a state of "superposition"? My assignment to myself today is to try and figure out if that's the case.

Along the lines with the first post below, I had another idea -- this one's easier to play with. The idea is to construct harmonic logic systems that oscillate between two or more logical states. You can take, for instance, the output of a NOT gate and feed it back into itself. If you feed it a 0, it spits out a 1, which then goes back through and becomes a 0, etc. Anyway, when you extend the idea to include classical "oscillator" behaviour (and, perhaps, quantum system behaviour) things could get interesting (i.e., how does the concept of "resonance" apply to a system of logic gates?). More fun is to be had if we include reversible logic, and maybe even mix the two. This one is a bit easier to play with than the quantum stuff I mentioned in the post below; the concepts of classical and reversible logic are much more accessible than those of classical and quantum wave dynamics. Anyway, more food for thought.

Hi, you've just arrived at crazy math, my own little corner on the web where I post random wierd ideas about stuff I think is interesting. Most of it has to do with math, etc. Most of it is pretty crazy and naieve, but hey we're having fun... Without further adieu, here's a random crazy idea for the day:

Harmonic quantum computing

The idea is this -- I don't know how nasty the math is for this (i.e., is it possible? Does anyone care?), but I had this idea the other night that it might be possible to build a hybrid classical/quantum computer. Instead of trying to keep a quantum system in the state of coherence for a long period of time (i.e., more than a few seconds), is it possible to design a system that oscillates between classical and quantum states? If so, then perhaps a computer could be built to take advanatage of this state flipping to perform both classical and quantum computations. I'm just barely beginning to pound into my head the math behind quantum computing, if you want more information check out this wonderful site. There are some obvious problems with this (how do you store all the information from the quantum cycle during the classical cycle), so I doubt it'd be terribly useful. It's fun to think about, though.