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.

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

1 Answer 1

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.

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

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.