A modular version of LinearRecurrence?

Question

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.

Daniel Huber · 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] ]

A modular version of LinearRecurrence?

One Answer

Add your own answers!

Ask a Question