Assistance finding prime numbers for cryptosystem

Question

I am a student in college and have an assignment which requires finding large prime numbers. I was given the following "simple" algorithm by the professor to find 2 likely prime numbers.

1. generate random a and p where 1 < a < p
2. confirm that gcd(a,p) is = 1 -- this is suppose to remove Carmichael numbers Edit(meant equal to 1)
3. perform "modular exponentiation" if x ^ (p-1) % p = 1 where x begins at zero and increments up to p-1 for both p and a

Example of the 3rd step.

suppose p = 5

1^4 %5 = 1

2^4 %5 = 1

3^4 %5 = 1

4^4 %5 = 1

This shows that 5 is prime.

I am realizing through this assignment that computing prime numbers is no joke. The problem I see with the above algorithm is that if I am guessing large numbers and testing them with the modular exponentiation, I could be attempting to raise a large number to a large number. This places a doubt in my mind. I have looked into Deterministic Finite Automata and the Sieve of Eratosthenes as well. Does anyone have any suggestions to either improve the given algorithm or provide any kind of assistance? Thank you for time.

Answer 1

Some time ago I wrote some functions in C# for personal use. I hope that it's good for you

public long tmp; public long[] tabnum = new long[1];

public void priminum(long NUM) { long Resto; long riso;

 // 2 is only number pair prime
 tabnum[0] = 2;

 for (tmp = 3; tmp <= NUM; tmp++)
 {
     if ((tmp % 2) == 0) continue;// if num it's pair is not prime

     for (long Y = 0; Y < tmp; Y++)
     {
          riso = Math.DivRem(tabnum[Y], tmp, out Resto);
          if (Resto == 0) break;
          if(riso <= tabnum[Y]) 
          {
                 Array.Resize(ref tabnum, tabnum.Length + 1);
                 tabnum[tabnum.Length - 1] = tmp;
                 List1.Items.Add(tmp.ToString("###,###"));
                 break;
           } 
      }
  }

}

next function return true if number is prime

private bool IsPrimo(ulong tmpNum) { ulong Y;

 if (tmpNum == 2) return true;

 if ((tmpNum % 2) == 0) return false;

 for (Y = 2; Y <= tmpNum; Y++)
 {
      if ((tmpNum % Y) == 0) break;
      if ((tmpNum / Y) <= Y) return true;
 }

 return false;

}

Answer 2

The algorithm you're following is called the Fermat primality test. However, there are several problems with your explanation:

• You say "confirm that gcd(a,p) is < 1". This doesn't make sense as the gcd will never be less than one. What you can check is that gcd(a,p)==1. If it isn't 1, then p is not a prime. This can detect Carmichael numbers, but may have only a small chance to do so.

• The way the test is conducted, is that for a certain value of p, you pick several random values of a and check if a ^ (p-1) % p == 1. If one of them is not 1, then p isn't prime. The more values of a you pick, the better your accuracy.

• You certainly can't check for all values of x as you say - since there are too many to check.

• There is a fast way to perform modular exponentiation, even for large base and exponent. See the Wikipedia article. You will still need a method to perform multiplication and modulo on large integers.

• The Sieve of Eratosthenes is only useful for finding small primes.

• This test may incorrectly determine that Carmichael numbers are prime. Other algorithms such as Rabin-Miller don't have this problem.

Answer 3

Somewhat simple in C#. I have no idea whether it'd be faster in terms of speed.

bool IsPrime(long n)
    {
        if (n == 1)
        {
            return false;
        }

        if (n < 4)
        {
            return true;
        }

        if ((n % 2) == 0)
        {
            return false;
        }

        if (n < 9)
        {
            return true;
        }

        if ((n % 3) == 0)
        {
            return false;
        }

        long r = (long)Math.Floor(Math.Sqrt(n));
        long f = 5;
        while (f <= r)
        {
            if ((n % f) == 0)
            {
                return false;
            }

            if ((n % (f + 2)) == 0)
            {
                return false;
            }

            f += 6;
        }

        return true;
    }