Generation of Lucas sequences modulo an integer

[somindu]

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]

[somindu]

Add the patches for function lucas(k,p,q,n) which generates Lucas sequence V_k mod n (k >= 0) defined by V_k = PV_{k-1} - QV_{k-2} with V_0 = 2 and V_1 = P.

Tests::

        sage: from sage.rings.finite_rings.integer_mod import lucas
        sage: p = randint(0,100000)
        sage: q = randint(0,100000)
        sage: n = randint(0,100)
        sage: all([lucas(k,p,q,n)[0] == Mod(lucas_number2(k,p,q),n)
        ...        for k in Integers(20)])
        True

        sage: from sage.rings.finite_rings.integer_mod import lucas
        sage: p = randint(0,100000)
        sage: q = randint(0,100000)
        sage: n = randint(0,100)
        sage: k = randint(0,100)
        sage: lucas(k,p,q,n) == [Mod(lucas_number2(k,p,q),n),Mod(q^(int(k/2)),n)]
        True

Examples::

        sage: [lucas(k,4,5,11)[0] for k in range(30)]
        [2, 4, 6, 4, 8, 1, 8, 5, 2, 5, 10, 4, 10, 9, 8, 9, 7, 5, 7, 3, 10, 3, 6, 9, 6, 1, 7, 1, 2, 3]

        sage: lucas(20,4,5,11)
        [10, 1]

[jpflori]

The code looks ok to me.

Not sure that we should keep both the code in fast_lucas just for the case Q=1 and lucas function for the generic case.

Of course the specialized version for Q=1 is faster, so it might be a reason to keep it, even if I'm more inclined not to.

I provided two "reviewer" patches and if Robert has any preference, let him decide.

[jpflori]

Patch with both functions.

[jpflori]

Patch where fast_lucas is just a wrapper to the new implementation.