Like a lot of strange adventures,
It began with a drifter in a corner booth. He was new in town—a six and a half foot tall, wild-haired, wild-eyed, algo-mystic with a tendency to monologue until sunrise. We met at a late-night diner, the kind of place with bottomless coffee and worn-out booths. There were only a handful of programmers in our small town in the late 90s, and we could spot each other a mile away.
He spoke of fluid dynamics, genetic algorithms, simulated annealing, woodworking, and the factorization of the products of unthinkably large prime numbers. Rumor has it that he contributed in some fashion to the development of the GIF algorithm/image format. The drifter managed to weave them all together into a vivid tapestry of physics, biology, and computer science. At the time, I was more interested in trying my hand at creating one of those DNA-based "living programs" that he told me about, but the odd revelation that the security of many of the world's public key encryption systems rely solely on a math problem's being “difficult”, stuck with me.
If I asked you to multiply two numbers together, say 7 times 11, most likely you could perform that calculation in your head within a matter of seconds. However, if I asked you what two numbers were multiplied together to produce the number 143, you might have to think about it for a while. This is the entire basis for the security of many of the world's top crypto-systems, although with numbers that are hundreds of digits long.
Challenge accepted.
I decided to embark on a journey to create my own factorization algorithm. I studied the classics and the best of the best, from Trial Division and Fermat's Difference of Squares, to the Quadratic and General Number Field Sieves. They all left me wondering, instead of blindly trying to come up with ways to divide n (the number to be factored), why hasn't anyone tried to reverse the process of multiplication itself? After years of research, discovery, trial and error, what I ended up with is the World's Worst Factoring Algorithm.
It is currently painfully inefficient. It is worse than the "Hello World" of factoring (Trial Division). However, it works! And to the best of my knowledge, the approach is novel (Using binary "puzzle pieces" and implied bits to reverse engineer the 2d binary multiplication partial product matrix of n). It also transfers the problem domain from that of a traditional math problem to a binary logic puzzle, perfect for SAT solvers, machine learning, etc...
Throughout the development of this algorithm, I have truly lived the old cliché: "It's not about the destination, it's about the journey". Attempting the impossible will take you down many interesting pathways, and sharing ideas is how we all grow. Now it's your turn. Where will you take it? Can you turn the World's Worst Factoring Algorithm into something incredible?