Koopman interpretation and analysis of a public-key cryptosystem: Diffie-Hellman key exchange ⋆

The paper’s main claim is that, for Diffie–Hellman dynamics x_{k+1} = m x_k (mod p) with m a primitive root and p>3 prime, the minimal Koopman lift using time-delay observables h_j(x_k)=x_{k+j} has dimension q̃+1 with q̃=(p−1)/2. The paper establishes existence at q=q̃ by exploiting m^{(p−1)/2}≡−1 (mod p) to derive a companion matrix with α=[1, −1, 0,…,0, 1], and factors the annihilating polynomial as (λ^{q̃}+1)(λ−1) () () (). It also shows that q=q̃−1 fails via a reduced system that only holds modulo p, not as an exact linear representation (). However, the proof of minimality is not fully comprehensive: beyond the single counterexample q̃−1 and a general rank obstruction for q<p−2 before applying the −1 congruence trick, the paper does not rigorously exclude all q<q̃ for the chosen observables () (). In contrast, the model’s solution proves a sharp lower bound by a spectral/DFT argument: the sequence’s Fourier support is exactly r=0 plus all odd r, giving q̃+1 distinct shift-eigenvalues, so any annihilating polynomial must have degree at least q̃+1; combined with the exhibited recurrence, the minimal lift is exactly q̃+1. Thus, the model provides a complete and correct minimality proof, while the paper’s proof leaves a gap.