Tuesday, May 25, 2004
Real 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!
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!
