# Ticket #11802(needs_review enhancement)

Opened 21 months ago

## Generation of Lucas sequences modulo an integer

Reported by: Owned by: somindu AlexGhitza minor sage-5.11 basic arithmetic Lucas sequence ecc2011 jpflori, robertwb N/A Somindu Chaya Ramanna, Shashank Singh, Srinivas Vivek Venkatesh

### Description

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]
```

## Change History

### comment:1 Changed 21 months ago by 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]
```

### comment:3 Changed 21 months ago by jpflori

• Status changed from new to needs_review
• Authors set to Somindu Chaya Ramanna, Shashank Singh, Srinivas Vivek Venkatesh

### comment:4 Changed 21 months ago by 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.

### Changed 21 months ago by jpflori

Patch with both functions.

### Changed 21 months ago by jpflori

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

Note: See TracTickets for help on using tickets.