The Lucas sequence modulo an integer n is given by V_k = PV_{k-1} - Q V_{k-2} mod n with V_0 = 2 and V_1 = P. This is not implemented in Sage. There are algorithms fast_lucas and slow_lucas that compute this sequence only for the special case Q=1.

sage: from sage.rings.finite_rings.integer_mod import fast_lucas
sage: [fast_lucas(i, Mod(8,11)) for i in range(15)]
[2, 8, 7, 4, 3, 9, 3, 4, 7, 8, 2, 8, 7, 4, 3]

sage: from sage.rings.finite_rings.integer_mod import slow_lucas
sage: [slow_lucas(i, Mod(8,11)) for i in range(15)]
[2, 8, 7, 4, 3, 9, 3, 4, 7, 8, 2, 8, 7, 4, 3]

CC: @jpflori @robertwb @zimmermann6

Component: basic arithmetic

Keywords: Lucas sequence ecc2011

Author: Somindu Chaya Ramanna, Shashank Singh, Srinivas Vivek Venkatesh, Travis Scrimshaw

Branch/Commit: public/arith/lucas_seqences-11802 @ 7c11ef2

Reviewer: Travis Scrimshaw, Jean-Pierre Flori

Issue created by migration from https://trac.sagemath.org/ticket/11802