Ok, Professor Landau replied to my request for more info with an exceptionally helpful link. Her short note in the link below helps a lot in understanding the algorithm. 1. The poly decomp work was done in 1986. 2. This was 3 years after her PhD (I was wrong!). 3. Maple does implement this algorithm (I was right!). BTW, I was also impressed by her Westinghouse Talent Search on odd perfect numbers. https://en.wikipedia.org/wiki/Susan_Landau http://privacyink.org/pdf/Timesharing_Dexter.pdf "My husband Neil Immerman returned from the 1986 STOC meeting with an interesting proposition. Juris Hartmanis and Dexter Kozen had a small pocket of funds, and they proposed that the two of us visit the Cornell Computer Science Department for a week." "Thus began Dexter’s and my adventure into polynomial decomposition. The week before I arrived at Cornell, I had been thinking about polynomial decomposition, that is, the issue of finding a non-trivial solution to the problem f(x) = g(h(x)) (non-trivial means that both g(x) and h(x) are of degree greater than 1). Barton and Zippel had a solution for fields of characteristic 0, noting that if f(x) = g(h(x)), then h(x) - h(y) divides f(x) - f(y). They used this — and a refinement, under the assumption that h(0) = 0,h(x)|(f(x) - f(0)) (without loss of generality, one can assume that h(0) = 0) — to find potential h(x) [2]. Their algorithm was exponential in n, the degree of f(x)." "Even with the lack of sleep that accompanies having a baby, I thought I could do better. Lüroth’s theorem states that if k is an arbitrary field, the fields between k(f(x)) and k(x) are in one-to-one correspondence with the decompositions of f(x). Each field between k(f(x)) and k(x) can be expressed as k(h(x)) for some composition factor of f(x) [7]." "The Kozen-Landau theorem shows that polynomial composition is not a good candidate for such public-key systems. Recently I was told that in the main Maple command “solve” for solving polynomial systems (and pretty much everything else), the algorithm begins by attempting to decompose any polynomials passed as input. This is because even while few polynomials are decomposable, the decomposition method is sufficiently fast that it provides a big win when it succeeds. The implementation is the Kozen-Landau technique [4]." "There was yet another consequence of Kozen-Landau. The polynomial x^4 + x+1 is the smallest polynomial over GF(2) that has a non-trivial decomposition: x^4 + x + 1 = g(h(x)), with g(x) = x^2 + x + 1 and h(x) = x^2 + x. Sometime after Neil and I left Ithaca and the Kozen domicile, Fran and Dexter retiled their bathroom shower. They included a strip of 4 × 4 small green and white tiles running along the wall; it is the cyclic multiplicative group of GF(16) as represented by polynomials mod(x^4 + x + 1) generated by x: [see picture]" At 09:55 AM 4/4/2016, Hilarie Orman wrote:

By using that magic thing called "the Internet", one can easily find that Susan Landau's doctorate predated the work in question by several years.

She is a close friend and colleague of several people on this list.

Hilarie