6 ms·
My uncle's factorization algorithms
- zackzackzack 15y agoThis feels like the modern day equivalent of the secret to alchemy being found in some musty trunk in the attic. Does any of this actually advance the field?
- daoudc 15y agoThat's a good question, and I'm not entirely sure of the answer. I'm pretty sure my uncle believed it did, but I'm not sure how in touch he was with the state of the art, as he didn't use the internet. His idea of research was photocopying articles (and whole books, in particular I remember vol 2 of Knuth's TAOCP) from the British library. My plan is to get some of these algorithms running and compare running times with the other open source ones available.
- jnbiche 15y agoDid you find any copies of a data input file for (at least some of) the Fortran programs, called recl.dat? EDIT: I am so intrigued by this that I asked the question above without saying thank you for releasing this. So thank you! I don't know much Fortran but if ever there was something to induce me to dive in, it's this. I've compiled his test program using gfortran and am looking into some of the others.
- daoudc 15y agoYes, it seems to contain a lot of prime numbers (36,500 to be precise). I haven't uploaded any data files since the total size is 3Gb.
- walrus 15y agoCan you make a torrent of the data files and put the .torrent file on GitHub?
- daoudc 15y agoI've collected what I think are the most important files. They compress very well because they seem to be very inefficiently stored (lots of repetition). The compressed collection is now on github.
- primecommenter 15y agoWhile perhaps not an advance, the algorithms implemented are state-of-the-art (GNFS, Pollard's p-1 test, Williams' p+1 test, cyclotomic polynomial test). But whatever the running times, it is an astounding artifact.
- daoudc 15y agoThere is a year or two of work on top of the documentation I have included. Also, I think it is likely that there are some incremental improvements to the existing algorithms that my uncle put in place without necessarily documenting. Whilst these might not be theoretically interesting, their combined effect could be significant. There may also be some new maths in there too, as he was undoubtedly a brilliant mathematician.
- wbhart 15y agoIt's remarkable that we refer to algorithms invented as "late" as the 90's as state-of-the-art. But sadly, it is so.
- primecommenter 15y agoEven more remarkable is that they build directly upon the 400-year-old method of Fermat (http://en.wikipedia.org/wiki/Fermat%27s_factorization_method http://en.wikipedia.org/wiki/Fermat%27s_factorization_method).
- 15y ago
- aurelianito 15y agoI would love to have an uncle whom I could talk about cryptography with. You were very lucky!
- daoudc 15y agoTo be honest, most of the time I didn't have a clue what he was talking about, and I was by far the most mathematical of the family! He wasn't a great teacher, but he was certainly an inspiration. And apart from all this, he was a great uncle, and great company.
- anuml 15y agoThe prime numbers group on yahoo is quite good. You might be able to entice someone to explore what your uncle has done. http://tech.groups.yahoo.com/group/primenumbers http://tech.groups.yahoo.com/group/primenumbers The group contains experts in this field that manage to do a commendable job of responding to questions at many levels. It's a shame that your uncle didn't have a chance to connect with them. Good luck.
- daoudc 15y agoThanks for the suggestion, I will explore this.
- GuiA 15y ago>Sadly, he was never able to benefit from this work himself, although he tried many times to sell the software developed here. Instead, he entrusted his work to me as his death neared, and he told me that he wanted it to benefit his family. Since there is little hope of me succeeding in selling this, instead, I hope that by releasing it under the GPL it may benefit mankind. I only ask that if you use it, you use it for good, not evil, to liberate and not oppress, and to educate and not to spread ignorance. Thank you so much for this.
- Cyph0n 15y agoI can't be of much help, but I'm extremely interested in how this all unfolds. Good luck.
- wbhart 15y agoThis is very interesting. Thank you for devoting your time to putting this on the web. Otherwise it might have rotted in your attic! It's unclear to me whether there is anything theoretically new in here yet. The algorithms are all familiar to me except for the P^2 + 1 and P^2 + P + 1 algorithms. But don't read too much into that. They are probably well known. What I can tell you is that there is an extraordinary amount of work in implementing all those algorithms. I do this stuff for a living and it is a tremendously impressive feat for a single individual over any span of time. I'd be interested in hearing how fast the MPQS is. The state of the art for factoring a number like 840931001586212064794450601167289569811131781103613687750579 on a single core is probably around 6s or so on a modern 2GHz x86 processor. UBASIC already had a 32 bit x86 assembly optimised MPQS in it, and it performed pretty well actually. So it would be interesting if your uncle improved on that, especially if he had theoretical improvements. The state of the art for the number field sieve should factor the 79 digit number here: http://www.loria.fr/~zimmerma/records/rsa.html http://www.loria.fr/~zimmerma/records/rsa.html in around 10-20 minutes on a single core, though in general the GNFS is for much larger integers. It seems unlikely that a little UBASIC program could manage those, however. Having said that, I am still in shock that your uncle actually implemented the GNFS. That is a staggering accomplishment and is something to be genuinely impressed by. I don't know if you have a gold mine there or the cutting edge life's work of someone from yesteryear.
- primecommenter 15y agoIf p^2+p+1 is smooth or if p^2+1 is smooth then n can be factored with cyclotomic methods. http://www.ams.org/journals/mcom/1989-52-185/S0025-5718-1989-0947467-1/S0025-5718-1989-0947467-1.pdf http://www.ams.org/journals/mcom/1989-52-185/S0025-5718-1989...
- wbhart 15y agoOK, after some effort I got the first of the MPQS programs to compile. Unfortunately it fails with a runtime error so I can't evaluate it. The program itself requires two files to exist before it can operate. Then it asks for the input number in base 10000 as a set of digits separated by spaces or returns. This is pretty bizarre by today's standards. It does succeed in factoring very tiny numbers, but it seems to have bugs which prevent it from working for large numbers. The double large prime variant of the MPQS seems to allow numbers up to a pretty small bound. This strongly indicates that it is not competitive. I'll see if I can get anywhere with the double large prime variant version (edit: I tried the second program and it fails with the same runtime error), but given the extremely poor state of the code (no comments, full of gotos, no indication of structure, no documentation, no test suite, buggy, very poor interface, etc.) I would say this code is not going to be particularly interesting to modern day researchers. At the same time, it is a tremendously amazing accomplishment that one man essentially toiled away in secret and created a massive number theory library like this! When I google his name I find nothing. Was he associated with an institution? Did he publish any papers? I know he didn't use the web, so that explains why he doesn't have a web presence, but it is odd not to find him referred to anywhere. Or am I just looking in the wrong place?
- josephkern 15y agoThis is brilliant. Thank you.
- muyuu 15y agoWe are finally coming to the era when the first amateurs who grew up with Personal Computers are starting to die of old age. Stuff in BASIC coded by somebody in the anonymity of the pre-Internet. Maybe something truly novel in its time or even now. There's something extremely romantic to this, like a rescued roll from the Library of Alexandria. Naturally, most of that anonymous work will be lost forever. Heck, most of my 8-bit era stuff stored in tapes and 5 1/4 floppies must be dead by now. I had some original Sountracker mod files from Amiga times and when I tried recovering those it was too late.
- Retric 15y agoThis reminds me that my father had a printout for the first SGML (standard generalized markup language) parser which is only interesting as that's the parent language for HTML, XML, etc. Apparently he was on the standard committee while working for the navy and wrote a parser to verify that the standard was correct, but it was far to slow for machines of that time period or some such. http://en.wikipedia.org/wiki/Standard_Generalized_Markup_Language http://en.wikipedia.org/wiki/Standard_Generalized_Markup_Lan... PS: Not that I would be able to recognize what some random FORTRAN code did, but it's probably worth poking around the barn.
- blacksmythe 15y ago>> first amateurs who grew up with Personal Computers are starting to die of old age There are few people older than early 50's who had a computer in high school. Although mortality starts to rise in the early 50's, I wouldn't call this dying of old age.
- muyuu 15y agoActually "old age" is never a reason to die, but heart stroke and cancer are most common natural life terminators in our species and they are already likely in your 50's. So yep... they are starting to basically die of old age.
- jonhendry 15y agoThe error is in the phrase "grew up with", as it suggests they were kids in the early days of personal computers. The adult amateurs who went from programmable calculators to early single-board microcomputers are the generation who are starting to die off. My Dad is of that cohort. In his 40s he went from programmable calculators to building a simple computer with an octal keypad and a row of LEDs for output, to working on an AIM-65, coding in basic and (I think) machine code. He worked in elevator maintenance, being in charge of service in much of Connecticut for one company. At one point he designed and built, with circuit boards he etched himself, some kind of electronic box which I think the company adopted? Maybe? For some kind of elevator-related purpose. I was never clear on what it did, and he probably doesn't remember now. He didn't have an academic background that would have exposed him to computing, having joined the Navy at 15. He later took some radio repair/electronics night school classes. He's 80 now, and has forgotten most of that stuff, and uses a MacBook and an iPad.
- ronnier 15y agoMy fear is that this contains some sort of mathematical break through which is then copied and claimed by another person as their own work. Didn't something like this happen to Grigori Perelman where another man attempted to claim Perelman's work? This is really amazing, I hope something comes from it.
- plaes 15y ago"Manifold Destiny" - http://en.wikipedia.org/wiki/Manifold_Destiny http://en.wikipedia.org/wiki/Manifold_Destiny
- seanp2k2 15y ago...and somewhere out there, right now, P(=|!=)NP is probably solved on some 5 1/2" floppy, rotting away in an attic...
- rokhayakebe 15y agoDaoud, did you add this In the name of God, the Merciful, the Compassionate. or did your uncle?
- daoudc 15y agoI added this - my uncle was not religious.
- jbm 15y agoSad that someone would mod you down for having religious convictions. Thank you for giving a portion of your inheritance to the world.
- woogley 15y agoSad that someone already forked it for the sole purpose of removing it https://github.com/oscardelben/wartonlegacy/commit/bc528d4d7bfe411cdb6206ff5bc02d34ad007c7d https://github.com/oscardelben/wartonlegacy/commit/bc528d4d7... Pathetic "contribution"
- muyuu 15y agoI'm not religious either... and I wouldn't like anyone adding that kind of stuff to my work, but I guess you meant to do good.
- rokhayakebe 15y agoI was pleasantly surprise to see it. It would be interesting to see if you title all your work with it. Very nice, indeed.
- driverdan 15y agoSo you start it with something religious, which would probably go against your uncle's wishes if he wasn't religious, then in the first paragraph state you hope people use it "to educate and not to spread ignorance". I find the contradiction amusing.
- lell 15y agoLanguage files blank comment code Fortran 90 224 50999 8235 315981 ubasic 248 ? ? 107383