3
$\begingroup$

The value of $k$ can be very large indeed (up to $10^{12}$). Is there an efficient way to calculate the output?

Edit : 'm' is a prime number.

Improve this question
$\endgroup$
1
  • $\begingroup$ If you know the factorization of $m$ maybe compute fibonacci(k) mod something fast? $\endgroup$
    – joro
    Commented Dec 17, 2013 at 14:38

1 Answer 1

Reset to default
7
$\begingroup$

Assuming $n$ and $m$ are coprime and $m$ is factored, first compute $a=\text{fibonacci}(k) \mod \varphi(m)$. Computing linear recurrence efficiently modulo $n$ is possible, e.g. via matrix exponentiation.

Then your expression is equal to $n^a \mod m$ which is easy to compute efficiently working $\mod m$ and fast exponentiation.

$\varphi$ is Euler totient function.

If the factorization of $m$ is unknown and $k$ is sufficiently large, I suspect the problem is quite hard.

Improve this answer
$\endgroup$
2
  • $\begingroup$ Actually m is a prime number. I forgot to mention it on my problem description. Thanks for your hint! $\endgroup$
    – Khazhak Keghart Sahak
    Commented Dec 18, 2013 at 11:31
  • $\begingroup$ @KhazhakKeghartSahak nice, m prime is easier. $\endgroup$
    – joro
    Commented Dec 18, 2013 at 12:24

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .