title: Faster algorithm to find fibonacci n mod m
body: <p>I have almost 3 days hitting my head against the wall to find a fast algorithm to find the fib n mod m, that is, the remainder of fibonacci number n divided by m, <em>where: 1 &lt;= n &lt;= 10^18 and 2 &lt;= m &lt;= 10^5</em></p>
  
  <p>As an example, I'm given as:</p>
  
  <pre><code>Input: 281621358815590 30524 // n and m
  Output: 11963
  </code></pre>
  
  <p>With this test, my code works, but then the test fails with this:
  <code>100 100000</code></p>
  
  <p>This is my code:</p>
  
  <pre><code>import java.math.BigInteger;
  import java.util.Scanner;
  
  public class FibonacciHuge {
      private static BigInteger fibmod(long n, BigInteger m) {
          BigInteger a=BigInteger.ZERO;
          BigInteger b=BigInteger.ONE;
          BigInteger c;
          long i;
          for (i=2; i&lt;=n;i++){
              c=a.add(b);
              a=b;
              b=c;
          }
          return b.mod(m);
        }
  
      private static BigInteger fibComplex (long n, BigInteger m) {
          int count = 2;
          for (int i = 2; i &lt; (m.pow(2)).longValue()-1; i++) {
              long a2=fibmod(i+1,m).longValueExact();
              long a3=fibmod(i+2,m).longValueExact();
              count= count+1;
              if (a2==0 &amp;&amp; a3==1){
                  break;
              }
  
          }   
          return fibmod(n % count,m);
      }
  
        public static void main(String args[]) {
          Scanner in = new Scanner(System.in);
          long n = in.nextLong();
          BigInteger m = in.nextBigInteger();
          System.out.println(fibComplex(n,m));
          in.close();
        }
  }
  </code></pre>
  
  <p>In <code>fibmod()</code>, I find the fibonacci of n and at the end I use m as modulator.
  In <code>fibComplex()</code>, I'm suppose to find the length of the Pisani period, so I use reduce n to the remainder of <code>n % (lengthofPisaniPeriod)</code> and then apply the mod m (so n isn't so big).
  For Java, this should be done in 1.5 secs but for big Pisani periods (as 100,000) its just too much.
  Some friend said they have done it without finding the Fib n first, just iterating to find the length of the period and using the tip to reduce n to the remainder of <code>n % (length of period)</code>.</p>
  
  <p>I've searched for the fastest fibonacci algorithm <a href="http://www.geeksforgeeks.org/program-for-nth-fibonacci-number/" rel="nofollow">here</a> but the solution seems to be easier, about reducing n, as I describe before, but I can grasp the concept after 3 days. I'm working with BigIntegers but I'm not sure if its really needed,since the hint say:</p>
  
  <blockquote>
    <p>"In this problem, the given number n may be really huge. Hence an
    algorithm looping for n iterations will not fit into one second for
    sure. Therefore we need to avoid such a loop".</p>
  </blockquote>
  
  <p>You can find a Pisani cycle/period calculator <a href="http://www.maths.surrey.ac.uk/hosted-sites/R.Knott/Fibonacci/fibmaths.html#section6" rel="nofollow">here</a>, it works fast even for large numbers so I wish i could know what algorithm they use. </p>
  
  <p>Sorry if something in my question is not clear, it 11 am and I havent slept all night trying to solve this. I can edit it so its more clear afer a couple hours of sleep if needed.</p>