## Introduction

This WPF C# .NET 4.5 code takes advantage of a 2-dimensional system of linear difference equations that gives a very fast implementation of generating large Fibinocci numbers (and Fibonacci numbers modulo N).

The Fibonacci numbers series starts 0,1,1,2,3,5,8,13,21,34,55,89.....

and is defined as: F[n] = F[n-2] + F[n-1]

They are found everywhere in mother nature and define the most efficient packing order of two dimensional objects:

They have some interesting properties when it comes to prime numbers. In fact, the algorithm (in the code below) tests for primality. The first few pseudoprimes are: 4181, 5777, 6479, 6721.

The graph of the first 332 pseudoprimes looks like this:

(If you can create an algorithm to test for the pseudoprimes, please be sure to drop a line in the comments below. I'd be glad to investigate it.)

Also, the Fibonacci sequence can be used to calculate the golden ratio. This is because F[**n**+1] / F[**n**] approaches the golden ratio as **n** approaches infinity.

## Background

While looking for new methods for integer factorization and primality testing, I stumbled accross the Fibonacci series and was thoroughly fascinated by its properties.

I've always wondered: is there an efficient way to calculate the index (**i**) of Fib(**i**) where Fib(**i**) modulo **m** is congruent to zero and the factors of m are unknown?

And what about calculating the index (**i**) where Fib(**i**) % **m** is positve or negative one (and the factors of **m** are unknown)?

## Some Speed Tests

Fibonacci.Fib(1000000);

Takes ~ 9169 milliseconds.

Fibonacci.FibMod(BigInteger.Parse("1000000000000"), BigInteger.Parse("1000000000001")) ;

Takes ~ 2 milliseconds

## Using the Code

You will need to reference `System.Numerics `

in C# .NET 4.5 or higher.

This implementation makes use of some simple matrix operations for calculating Fibonacci numbers by index:

public static BigInteger Fib(BigInteger idx)
{
if (idx == 0) return 0;
if (idx == 1) return 0;
var m = new FibMatrix(1, 1, 1, 0);
m = m.RaiseMatrixByPower(idx - 1);
return m.Result();
}

The matrix is raised to a power (idx - 1) and the resultant value in cell location (0,0) is the Fibonacci value. The first few digits of the 1 millionth Fibonacci number is:

195328212870775773163201494759625633244354299659187339695340519457162525788701569476664198...

Also note, to calculate the golden ratio you can simply divide two consecutive Fibonacci numbers:

var dgs = BigInteger.Parse
("10000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000");
var f1 = Fibonacci.Fib(10000);
var f2 = Fibonacci.Fib(10001) * dgs;
var rs = f2 / f1;
var tmp = rs.ToString();

which gives (after placing the decimal):

1.6180339887498948482045868343656381177203091798057628621354486227052604628189024497072072041893911374

The following method handles the modular reduction of our Fibonacci numbers by some divisor:

public static BigInteger FibMod(BigInteger idx, BigInteger divisor)
{
if (idx == 0) return 0;
if (idx == 1) return 0;
var m = new FibMatrix(1, 1, 1, 0);
m = m.RaiseMatrixByPowerMod(idx - 1, divisor);
return m.Result();
}

And it can be used to test for probable primality:

public static bool IsProbablePrime(BigInteger value)
{
if (value <= 6)
{
if (value == 2) return true;
if (value == 3) return true;
if (value == 5) return true;
return false;
}
if (value % 2 == 0) return false;
if (value % 3 == 0) return false;
if (value % 6 != 1 && value % 6 != 5) return false;
var md = FibMod(value, value);
var primeTest = false;
var res = value % 5;
if (res == 2 || res == 3)
{
if (md == (value - 1)) primeTest = true;
}
else
{
if (md == 1) primeTest = true;
}
return primeTest;
}

Notice that this is a "probable prime" test. That means if it returns "`true`

", there's a strong possibility that the number being tested is prime. However, if it returns `false`

, it's absolutely NOT a prime.

Also, if you are asked to calculate the last 5 digits of the 10,000^{th} Fibonacci number:

var f1 = Fibonacci.FibMod(BigInteger.Parse("10000"), 100000);

which gives: `66875`

.

## Points of Interest

- Consecutive Fibonacci numbers are the worst case scenario in Euclid's GCD problem
- Primality testing
- Pisano periods, totients, and integer factorization
- Possible to create a non-recursive method (to prevent stack overflows)
- Possible speedups that utilize multiple threads

## Some Interesting Equations

- Golden Ratio = (1 + SQRT(5)) / 2
- F(n) = [(1 + SQRT(5))^n - (1 - SQRT(5))^n] / [2^n * SQRT(5)]
- GCD(F(m), F(n)) = F(GCD(m,n))

## References

This member has not yet provided a Biography. Assume it's interesting and varied, and probably something to do with programming.