docs: def _lucas_sequence(n, P, Q, k):
      """Return the modular Lucas sequence (U_k, V_k, Q_k).
      Given a Lucas sequence defined by P, Q, returns the kth values for
      U and V, along with Q^k, all modulo n.
      """
      D = P * P - 4 * Q
      if n < 2:
          raise ValueError("n must be >= 2")
      if k < 0:
          raise ValueError("k must be >= 0")
      if D == 0:
          raise ValueError("D must not be zero")
  
      if k == 0:
          return 0, 2
      U = 1
      V = P
      Qk = Q
      b = _bitlength(k)
      if Q == 1:
          # For strong tests
          while b > 1:
              U = (U * V) % n
              V = (V * V - 2) % n
              b -= 1
              if (k >> (b - 1)) & 1:
                  t = U * D
                  U = U * P + V
                  if U & 1:
                      U += n
                  U >>= 1
                  V = V * P + t
                  if V & 1:
                      V += n
                  V >>= 1
      elif P == 1 and Q == -1:
          # For Selfridge parameters
          while b > 1:
              U = (U * V) % n
              if Qk == 1:
                  V = (V * V - 2) % n
              else:
                  V = (V * V + 2) % n
                  Qk = 1
              b -= 1
              if (k >> (b - 1)) & 1:
                  t = U * D
                  U = U + V
                  if U & 1:
                      U += n
                  U >>= 1
                  V = V + t
                  if V & 1:
                      V += n
                  V >>= 1
                  Qk = -1
      else:
          # The general case with any P and Q
          while b > 1:
              U = (U * V) % n
              V = (V * V - 2 * Qk) % n
              Qk *= Qk
              b -= 1
              if (k >> (b - 1)) & 1:
                  t = U * D
                  U = U * P + V
                  if U & 1:
                      U += n
                  U >>= 1
                  V = V * P + t
                  if V & 1:
                      V += n
                  V >>= 1
                  Qk *= Q
              Qk %= n
      U %= n
      V %= n
      return U, V