# A modular version of LinearRecurrence?

I'm playing around with implementing the Lucas probable prime test (mainly so I can understand it better), and would love a version of the LinearRecurrence function that used addition modulo n (with n supplied by the user) instead of ordinary addition (which can easily result in overflows).

It wouldn't be all that crazy-hard to implement one, I think, and might even be quite interesting to do, but I thought I'd ask whether anyone already knows of such a thing.

• A concrete example, with input and desired output, would be useful here. – Daniel Lichtblau Sep 7 at 14:27
• There isn't a built-in function, but you might be interested in the undocumented function AlgebraMatrixPowerMod[], which might help in your implementation. – J. M.'s discontentment Sep 10 at 11:17
• Oh, wow--I think that's almost certainly going to do the trick. Thanks so much! – Phil Ramsden Sep 11 at 12:29
• p = NextPrime[10^100]; Mod[(AlgebraMatrixPowerMod[{{0, 1}, {1, 1}}, p -2 - JacobiSymbol[p, 5], p].{1, 1})[[2]], p] returns 0, very quickly; exactly what I was trying to do. That's Fibonacci; adapting to other recurrence relations will be a breeze. Thanks again. – Phil Ramsden Sep 11 at 13:14

## 1 Answer

You can build your own "LinearRecurrence" and then use any function you like. Here is an example from MMA help:

LinearRecurrence[{a, b}, {1, 1}, 5]


this gives:

{1, 1, a + b, b + a (a + b), b (a + b) + a (b + a (a + b))}


We can do the same by:

Reap[Nest[(Sow[t = #.{b, a}]; {#[[2]], t}) &, {1, 1}, 3] ]


To introduce Mod, you would write:

Reap[Nest[(Sow[t =Mod[ #.{b, a},n]; {#[[2]], t}) &, {1, 1}, 3] ]

• Your answer might be improved for the OP & future users if you can link to the “MMA help” page you pull this from. – CA Trevillian Sep 7 at 21:06
• Hi, thanks for this! I realise I need to clarify. The thing is, my guess is that LinearRecurrence uses some clever stuff to cope with large n, probably based on repeated doubling of the index. My n will be large, so my programming task would involve duplicating that clever stuff, rather than simply nesting (n-2) times. That's doable, but I wondered if anyone had already done it. – Phil Ramsden Sep 8 at 15:09
• So for example LinearRecurrenceMod[{1,1},{1,1},10^100+1,10^100] would return the googol-plus-oneth Fibonacci number, reduced mod googol. Kind of like a LinearRecurrence version of PowerMod, if you take my meaning. – Phil Ramsden Sep 8 at 15:14
• (At least, it's doable for second order recurrence relations, via Lucas U and V sequences; not sure if that generalises; number theory's not really my comfort zone.) – Phil Ramsden Sep 8 at 15:19