Fermats primtals tester

Hej alle,

Jeg sidder med en opgave i programmering på mit studie, der går ud på at lave en funktion der tester om et tal er et primtal og derefter returner true.

Jeg har valgt, at kigge på Fermat og jeg ved godt den er "probabilistic" og derved kun angiver at der mulighed for at et tal er et primtal.

(Se mere her: http://en.wikipedia.org/wiki/Fermat_primality_test )

Jeg er kommet frem til følgende kode:

CSharp kode 

 static bool isPrime(int n)
         {
             bool isPrime = true;
 
             Random a = new Random();
 
             for (double i = 1; i < 100000; i++)
             {
                 int j = a.Next(1, (n - 1));
 
                 if (Math.Pow((double) j, (double)(n - 1)) % n != 1)
                 {
                     isPrime = false;
 
                     break;
                 }
                 else
                 {
                     isPrime = true;
                 }
             }
 
             return isPrime;
         }

Den falder dog allerede sammen ved 17 og siger det er et sammensat tal. Som jeg har forstået det, så er et Fermat Liar et sammensat tal, eller er det et tal som er et primtal, men som foregives at være sammensat?

Jeg håber i har et forslag. På forhånd tak.

Kode 

private static long simplePow(int b, int power) {
  long result = 1;
  for (int i = 0; i < power; i++)
    result *= b;
  return result;
}

CSharp kode 

 using System;
 using System.Collections.Generic;
 using System.Linq;
 using System.Text;
 
 namespace Programming_Challenges_3._12
 {
     class Program
     {
         static void Main(string[] args)
         {
             Console.Write("Indtast et tal, for at se om det er et primtal: ");
             int input = Convert.ToInt32(Console.ReadLine());
 
             if (isPrime(input))
                 Console.WriteLine("Er primtal");
             else
                 Console.WriteLine("Er sammensat tal.");
         }
 
         static long simplePow(int b, int power)
         {
             long result = 1;
 
             for (int i = 0; i < power; i++)
                 result *= b;
             return result;
         }
 
         static bool isPrime(int n)
         {
             bool isPrime = true;
 
             Random a = new Random();
 
             for (double i = 1; i < 100000; i++)
             {
                 int j = a.Next(1, (n - 1));
 
                 if (simplePow(j, (n - 1)) % n != 1)
                 {
                     isPrime = false;
 
                     break;
                 }
             }
             return isPrime;
         }
     }
 }