4

私は大学の学生で、大きな素数を見つける必要がある課題があります。私は教授から次の「単純な」アルゴリズムを与えられ、2つの可能性のある素数を見つけました。

  1. 1 < a < p の場合、ランダムな a と p を生成します
  2. gcd(a,p) が = 1 であることを確認します -- これは、カーマイケル数を削除することを想定しています Edit(meant equal to 1)
  3. x ^ (p-1) % p = 1 の場合、「モジュラー累乗」を実行します。ここで、x はゼロから始まり、p と a の両方で p-1 まで増加します

3番目のステップの例。

p = 5 とします。

1^4 %5 = 1

2^4 %5 = 1

3^4 %5 = 1

4^4 %5 = 1

これは 5 が素数であることを示しています。

この課題を通して、素数の計算は冗談ではないことに気づきました。上記のアルゴリズムで見られる問題は、大きな数を推測して剰余累乗でテストしている場合、大きな数を大きな数に上げようとしている可能性があることです。これは私の心に疑問を投げかけます。私は決定論的有限オートマトンとエラトステネスのふるいも調べました。指定されたアルゴリズムを改善するか、何らかの支援を提供するための提案はありますか? ありがとうございました。

4

3 に答える 3

6

あなたがフォローしているアルゴリズムは、フェルマー素数性テストと呼ばれます。ただし、あなたの説明にはいくつかの問題があります。

  • あなたは「gcd(a,p) が < 1 であることを確認してください」と言います。gcd が 1 未満になることは決してないため、これは意味がありません。確認できることは、gcd(a,p)==1 です。1 でない場合、p は素数ではありません。これはカーマイケル数を検出できますが、検出できる可能性はわずかです。

  • テストの実施方法は、p の特定の値に対して、a のいくつかのランダムな値を選択し、a ^ (p-1) % p == 1 かどうかを確認することです。そのうちの 1 つが 1 でない場合、p はプライムではありません。選択する a の値が多いほど、精度が向上します。

  • あなたが言うように x のすべての値をチェックすることは確かにできません-チェックするには多すぎるためです。

  • 底と指数が大きい場合でも、剰余累乗を実行する高速な方法があります。ウィキペディアの記事を参照してください。大きな整数に対して乗算とモジュロを実行するメソッドが必要です。

  • エラトステネスのふるいは、小さな素数を見つける場合にのみ役立ちます。

  • この検定では、カーマイケル数が素数であると誤って判断される場合があります。Rabin-Millerなどの他のアルゴリズムには、この問題はありません。

于 2010-02-21T18:39:12.370 に答える
-2

C# ではやや単純です。速度の点で速いかどうかはわかりません。

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 を返します

プライベート 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 に答える