1
$\begingroup$

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.

Improve this question
$\endgroup$
4
  • 1
    $\begingroup$ A concrete example, with input and desired output, would be useful here. $\endgroup$
    – Daniel Lichtblau
    Commented Sep 7, 2020 at 14:27
  • $\begingroup$ There isn't a built-in function, but you might be interested in the undocumented function Algebra`MatrixPowerMod[], which might help in your implementation. $\endgroup$
    – J. M.'s missing motivation ♦
    Commented Sep 10, 2020 at 11:17
  • $\begingroup$ Oh, wow--I think that's almost certainly going to do the trick. Thanks so much! $\endgroup$
    – Phil Ramsden
    Commented Sep 11, 2020 at 12:29
  • $\begingroup$ p = NextPrime[10^100]; Mod[(Algebra`MatrixPowerMod[{{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. $\endgroup$
    – Phil Ramsden
    Commented Sep 11, 2020 at 13:14

1 Answer 1

Reset to default
1
$\begingroup$

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] ]
Improve this answer
$\endgroup$
4
  • $\begingroup$ Your answer might be improved for the OP & future users if you can link to the “MMA help” page you pull this from. $\endgroup$
    – CA Trevillian
    Commented Sep 7, 2020 at 21:06
  • $\begingroup$ 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. $\endgroup$
    – Phil Ramsden
    Commented Sep 8, 2020 at 15:09
  • $\begingroup$ 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. $\endgroup$
    – Phil Ramsden
    Commented Sep 8, 2020 at 15:14
  • $\begingroup$ (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.) $\endgroup$
    – Phil Ramsden
    Commented Sep 8, 2020 at 15:19

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.