Exponent Recovery via Repeated Eigenvalue (Logarithmic Derivative Trick)

Updated 13 Sep 2026

• •

  What it is

  • •

    When a genuine reduction a(X) of X^s is known modulo a polynomial with a nonzero double root lambda, its value and formal derivative reveal s modulo the field characteristic p. This determines the integer s only with a suitable bound or additional information. Recovering a from matrix/vector data also requires attention to rank.

• •

  When to apply

  • •

    The reduction polynomial from Cayley-Hamilton has a repeated root over the field you're working in — check this explicitly (e.g. via $\gcd(f(X), f'(X)) \ne 1$) before reaching for a full discrete-log solve, since this shortcut is both faster and doesn't need to identify a generator or factor any group order at all.

• •

  Symbols and assumptions

  • •

    We know a genuine remainder $a(X)\equiv X^s\pmod{f(X)}$, and $(X-\lambda)^2$ divides f with $\lambda\ne0$. The field has prime characteristic p.

• •

  Math — step by step

  • •
    1. The difference $X^s-a(X)$ contains a double factor $(X-\lambda)^2$. Both its value and formal derivative vanish at $\lambda$. Consequently $a(\lambda)=\lambda^s$ and $a^{\prime}(\lambda)=s\lambda^{s-1}$.
  • •
    2. Multiply the second equality by $\lambda$ and divide by the nonzero first: $s\equiv\lambda a^{\prime}(\lambda)/a(\lambda)\pmod p$. Inverses are field inverses.
  • •
    3. The result is s modulo p. It determines the integer s only with a suitable bound, or after combining other information. A repeated characteristic root alone is insufficient if the recovered a came from a rank-deficient observation system.
• •

  Worked example

  • •

    Use $f=(X-1)^2$ over $GF(5)$ and the previous example’s $a(X)=3+3X$, representing $X^3$. Here $\lambda=1$, $a(1)=6\equiv1$, and $a^{\prime}(1)=3$.

  • •

    The formula gives $1\cdot3\cdot1^{-1}=3\pmod5$. It cannot distinguish exponent 3 from 8 by this derivative information alone; if $0\le s<5$, it identifies s=3.

• •

  Python

  • •

    def poly_eval(coeffs, x, p):
        result, xp = 0, 1
        for c in coeffs:
            result = (result + c*xp) % p
            xp = (xp * x) % p
        return result
     
    def poly_derivative(coeffs, p):
            return [(i*coeffs[i]) % p for i in range(1, len(coeffs))]
     
    a_lambda = poly_eval(a_coeffs, lam, p)
    a_prime_lambda = poly_eval(poly_derivative(a_coeffs, p), lam, p)
    secret = (lam * a_prime_lambda % p) * pow(a_lambda, -1, p) % p
    

• •

  SageMath

  • •

    a_prime = a_poly.derivative()
    secret = int((lam * a_prime(lam) * a_poly(lam)^-1) % p)
    

• •

  Related

  • •

    Cayley-Hamilton Reduction of Matrix Exponentiation to Polynomial Coefficients

• •

  Cards

  • •

    What condition on the reduction polynomial does this technique require?

    • •

      A nonzero root of multiplicity at least 2 in the polynomial modulo which a(X) is known to equal X^s. A repeated characteristic root alone is not enough if the observation failed to recover the needed remainder.

  • •

    What quantity does this trick actually recover — the exponent mod the eigenvalue's order, or mod the field's characteristic?

    • •

      Mod the field's characteristic p — a subtle but important distinction, since it's a formal algebraic identity rather than a discrete-log statement.

◌ Explore connections in Graph view