View Single Post
Old 2021-01-03, 22:16   #2
carpetpool's Avatar
Nov 2016

22·83 Posts

The examples involving Trinomial Coefficients and Catalan numbers (also see here) are examples of P-recursive sequences, which is what I am generally after.

After doing a bit of research, I was able to find this article, which explicitly states that the N-th term of a P-recursive sequence can be computed in no more than O(N^(1/2)) operations. This paper also seems to agree.

Unfortunately, that's not practical for (primality) testing large numbers. That being said, it's not impossible to design an algorithm that can reduce the complexity from almost linear to polynomial time, as is the case of C-recursive sequences (Fibonacci, Lucas, Mersenne,..).

My idea is to reduce the baby-step giant step techniques with something analogous to square-multiply for P-recursive sequences, which I'm sure exists.

If anyone know of a paper that proves otherwise, or some better ideas, please let me know.

Last fiddled with by carpetpool on 2021-01-03 at 22:20
carpetpool is offline   Reply With Quote