Matrix power limit

[Albert Chan]

I am not sure about HP Prime, but XCas 1.4.9-57(win32) had a matrix power 31 bits limit.

Example: Perrin Primality test

qpowmod(n) := ([[0,1,1],[1,0,0],[0,1,0]] % n) ^ (n-1)
perrin(n) := dot(qpowmod(n)(2), [2,0,3]) == 0

map(range(2, 10), x -> x * perrin(x)) ==> [2, 3, 0, 5, 0, 7, 0, 0]

However, the code will not work for n > 2^31

perrin(9876543211) ==> "Abs Error: Bad Argument Type"

To fix it, need another matpow version that can handle bigger n:

matpow2hlp(a, n, half) := ifte(odd(n), a*half, half) * half
matpow2(a, n) := ifte(n<2^31, a^n, matpow2hlp(a, n, matpow2(a, n div 2)))

qpowmod2(n) := matpow2([[0,1,1],[1,0,0],[0,1,0]] % n, n-1)
perrin2(n) := dot(qpowmod2(n)(2), [2,0,3]) == 0

perrin2(9876543211) ==> true

Update: it seems the limit is not really due to matrix power, but the modulo.

[Joe Horn]

HP Prime in CAS view:
[[1]]^(2^8198) --> [[1]]
[[1]]^(2^8199) --> undef