Constructing a minimal polynomial

[arseniiv]

Here in the code there’s a wish to use minimal polynomials to compute a hash of the number. I propose the following simple algorithm to calculate a minimal polynomial, with some additional optimizations, though without a proof this computes what it intends to (but I’d be surprised if it doesn’t).

---

Let K = Q[√r_1]...[√r_n] and let K_i be its “subtower” Q[√r_1]...[√r_i]. (Including the cases i = 0 or n = 0.)

For a = (b + c √r_i) ∈ K_i, let conj_i a = (b − c √r_i) ∈ K_i.

For P ∈ K_i[x], let conj_i P be a coefficientwise conj_i, which is again a polynomial in K_i[x].

Observe that for a ∈ K_i ≠ Q, (a conj_i a) can be treated as being in K_{i − 1}. The same applies to polynomials too.

Finally, let s ∈ K be our number. Define:

• P_0 = (x − s) ∈ K[x]
• P_{i + 1} = (P_i conj_{n − i} P_i) ∈ K_{n − (i + 1)}[x], if conj_{n − i} P_i ≠ P_i
• P_{i + 1} = P_i ∈ K_{n − (i + 1)}[x], if conj_{n − i} P_i = P_i

P_n should be the minimal polynomial of s over Q.

---

Now we can observe that P conj P, with successive lowering in the tower, can be computed a bit more effectively than simple multiplication.

First, let f(a) = a conj a, and g(a, b) = a conj b + b conj a, which both can (and should, here) be lowered one step in the tower.

Let P = a_0 + a_1 x + ... + a_k x^k. Then

• for 0 ≤ i = 2 j + 1 ≤ k, [x^i] (P conj P) = g(a_0, a_i) + g(a_1, a_{i − 1}) + ... + g(a_j, a_{j + 1})
• for 0 ≤ i = 2 j ≤ k, [x^i] (P conj P) = g(a_0, a_i) + g(a_1, a_{i − 1}) + ... + g(a_{j − 1}, a_{j + 1}) + f(a_j)
• and for k ≤ i ≤ 2 k, define [x^i] (P conj P) in the same manner. Collecting all the coefficients, we get P conj P, which is also already lowered one step.

(Observing that a_k = 1 for any P computed above, we can represent such a polynomial of degree k as k numbers, which may be an insignificant optimization; note k will always be a power of 2.)

[arseniiv]

(Maybe I’ll even implement that myself but first I’d need to become more familiar with the code. Thank you for writing this library, and thanks to Anders Kaseorg for the Haskell.)

[leovt]

I would welcome your contribution.
It is a long time since I wrote this, and I will also need some time to understand your algorithm.
Thank you for your interest on this library and sharing your ideas.

[arseniiv]

Hm it seems you’ve already implemented a matrix approach for this in a separate branch but didn’t merge it for some reason. 😁 Anyway I think I’ll try my approach too, then one would be able to compare their running time etc..