4

我是一名大学生，有一项需要找到大素数的作业。教授给了我以下“简单”算法，以找到 2 个可能的素数。

  1. 生成随机 a 和 p 其中 1 < a < p
  2. 确认 gcd(a,p) 是 = 1 - 这是假设删除 Carmichael 数字编辑（意味着等于 1）
  3. 如果 x ^ (p-1) % p = 1 则执行“模幂运算”，其中 x 从零开始，对于 p 和 a 都递增到 p-1

第三步的例子。

假设 p = 5

1^4 %5 = 1

2^4 %5 = 1

3^4 %5 = 1

4^4 %5 = 1

这表明 5 是素数。

我通过这个作业意识到计算素数不是开玩笑。我在上述算法中看到的问题是，如果我猜测大数并使用模幂来测试它们，我可能会尝试将大数提升为大数。这让我心中产生了疑问。我也研究了确定性有限自动机和埃拉托色尼筛法。有没有人有任何建议来改进给定的算法或提供任何帮助？谢谢你的时间。

4

3 回答 3

6

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.

于 2010-02-21T18:39:12.370 回答
-2

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;
    }
于 2010-02-21T19:13:25.943 回答
-3

前段时间我用C#写了一些函数供个人使用。我希望这对你有好处

公共长 tmp；public long[] tabnum = new long[1];

public void priminum(long NUM) { long Resto; 长里索;

 // 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;
           } 
      }
  }

}

如果数字是素数，下一个函数返回 true

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;

}

于 2010-02-21T18:38:09.300 回答