VMS passwords are hashed with the Purdy Polynomial [1]:
\[p(x) \equiv x^{16777213} - 24 x^{16777153} - 120 x^3 - 198 x^2 - 264 x - 304\pmod{2^{64}-59}\]
In 1986 I hit upon the idea that I could find a string of powers of \(x\) that contained \(x, x^2,x^3,x^{16777153},x^{16777213}\). This is an example of an addition sequence problem. I coded up a poor backtracking search in VAX assembler (MACRO32) and tried to find a chain. This would take some time, so I loaded this code into the kernel of an 11/750 VAX and had it replace the idle process of the VAX. These were single processor machines, and the idle process would go away once muti-processors came along as they were replaced by a schedular loop.
It's easy now to find optimal addition sequences for this problem:
1 2 3 6 12 15 30 60 63 126 252 504 1008 2016 4032 8064 16128 32256 64512 129024 258048 516096 1032192 2064384 4128768 4129776 8259552 8517600 8517601 16777153 16777213
Looking at this problem led me to Knuth Vol 2 §4.6.3 "Evaluation of Powers". Learning about all the strange properties of addition chains from Vol 2 got me interested in this topic. Since the book talks about a program to calculate optimal addition chains in Volume 4 I tried to order that. It was obviously not available at the time.
For Volume 4 Knuth asked me to find an optimal addition chain for \(2^3\cdot 3^2\cdot 5\cdot 7\cdot 17\cdot 31\cdot 127-1=168661079\) to be used for inverting 8x8 binary matrices. So, I managed to get a mention in the book I couldn't purchase for multiple decades. Maximizing squares, I get a chain like this:
1 2 4 5 10 20 40 80 160 320 640 1280 2560 5120 10240 20480 40960 40965 40967 81934 163868 327736 655472 1310944 2621888 5243776 10487552 10528517 21057034 21077514 42155028 84310056 168620112 168661079
It's now possible to invert the Purdy polynomial using Pari/GP on a large computer using what's called distinct degree factorization. Essentially \(x^{2^{64}-59}-x\) is the product of all linear terms \(x(x-1)(x-2)...(x-2^{64}+60)\) so you calculate
\(GCD(x^{2^{64}-59}-x,p(x))\) to isolate the linear terms.
[1] George B. Purdy. 1974. A high security log-in procedure. Commun. ACM 17, 8, 442–445.