コンテンツ

• ステップ
• パート1/3：シンプルさのテスト
• パート2/3：シンプルさテストのしくみ
• 3のパート3：中国の剰余定理の使用
• チップ
• あなたは何が必要ですか

素数は、それ自体と1でのみ割り切れる数です。他のすべての数は合成数と呼ばれます。数が素数であるかどうかを判断する方法はたくさんあり、それらにはすべて独自の長所と短所があります。一方で、いくつかの方法は非常に正確ですが、多数を扱う場合は非常に複雑です。一方、はるかに高速な方法がありますが、それらは誤った結果につながる可能性があります。適切な方法の選択は、使用している数値の大きさによって異なります。

ステップ

パート1/3：シンプルさのテスト

ノート： すべての式で NS チェックする番号を示します。

1. 1 除数の列挙。 分割するだけで十分です NS 2から四捨五入された値までのすべての素数（${ displaystyle { sqrt {n}}}$).
2. 2 フェルマーの小定理。 警告：aのすべての値であっても、テストで合成数が素数として誤って識別されることがあります。
   • 整数を選びましょう NS2≤a≤n-1となるように。
   • a（mod n）= a（mod n）の場合、その数はおそらく素数です。等式が満たされない場合、数nは合成されます。
   • 複数の値が等しいかどうかを確認します NSテストされている数が実際に素数である可能性を高めるため。
3. 3 ミラーラビン検定。 警告：まれですが、aの複数の値について、テストで合成数が素数として誤って識別されることがあります。
   • 次のような量sとdを見つけます ${ displaystyle n-1 = 2 ^ {s} * d}$.
   • 整数を選択してください NS 2≤a≤n-1の範囲。
   • a = +1（mod n）または-1（mod n）の場合、nはおそらく素数です。この場合、テスト結果に移動します。等式が成り立たない場合は、次の手順に進みます。
   • あなたの答えを二乗する（${ displaystyle a ^ {2d}}$）。 -1（mod n）を取得した場合、nはおそらく素数です。この場合、テスト結果に移動します。等式が失敗した場合は、（${ displaystyle a ^ {4d}}$ など）まで ${ displaystyle a ^ {2 ^ {s-1} d}}$.
   • 以外の数を二乗した後のある段階で ${ displaystyle pm 1}$ （mod n）、+ 1（mod n）を得たので、nは合成数です。もしも ${ displaystyle a ^ {2 ^ {s-1} d} neq pm 1}$ （mod n）の場合、nは素数ではありません。
   • テスト結果：nがテストに合格した場合、他の値に対してそれを繰り返します NS自信を高めるために。

パート2/3：シンプルさテストのしくみ

1. 1 除数の列挙。 定義上、数 NS 2と、1とそれ自体を除く他の整数で割り切れない場合にのみ単純です。上記の式を使用すると、不要な手順を削除して時間を節約できます。たとえば、数値が3で割り切れるかどうかを確認した後、9で割り切れるかどうかを確認する必要はありません。
   • フロア（x）関数は、xをx以下の最も近い整数に丸めます。
2. 2 モジュラー演算について学びます。 演算「xmody」（modはラテン語の「モジュロ」の省略形、つまり「モジュール」）は、「xをyで除算して余りを求める」ことを意味します。言い換えれば、モジュラー算術では、特定の値に達すると、 モジュール、数字は再びゼロに「変わります」。たとえば、時計はモジュール12でカウントダウンします。10、11、12時間表示された後、1に戻ります。
   • 多くの電卓にはmodキーがあります。このセクションの最後に、多数のこの関数を手動で計算する方法を示します。
3. 3 フェルマーの小定理の落とし穴について学びます。 テスト条件が満たされていないすべての数値は複合ですが、残りの数値は 多分 シンプルです。誤った結果を避けたい場合は、検索してください NS 「カーマイケル数」（このテストを満たす合成数）と「フェルマー擬素数」（これらの数は、一部の値についてのみテスト条件を満たす）のリストにあります。 NS).
4. 4 便利な場合は、ミラーラビン検定を使用します。 この方法は手動計算にはかなり面倒ですが、コンピュータプログラムでよく使用されます。許容可能な速度を提供し、フェルマーの方法よりもエラーが少なくなります。計算が¼を超える値に対して実行される場合、合成数は素数とは見なされません。 NS..。ランダムに異なる値を選択した場合 NS そして、それらすべてについて、テストは肯定的な結果をもたらすでしょう、私たちはかなり高い信頼度で次のことを仮定することができます NS は素数です。
5. 5 大きな数の場合は、モジュラー演算を使用します。 mod計算機が手元にない場合、または計算機がそのような大きな数値を処理するように設計されていない場合は、電力プロパティとモジュラー演算を使用して計算を簡単にします。以下はの例です ${ displaystyle 3 ^ {50}}$ mod 50：
   • 式をより便利な形式に書き直します。 ${ displaystyle（3 ^ {25} * 3 ^ {25}）}$ mod50。手動計算では、さらに簡略化する必要がある場合があります。
   • ${ displaystyle（3 ^ {25} * 3 ^ {25}）}$ mod 50 = ${ displaystyle（3 ^ {25}}$ mod 50 ${ displaystyle * 3 ^ {25}}$ mod 50）mod50。ここでは、モジュラー乗算のプロパティを考慮しました。
   • ${ displaystyle 3 ^ {25}}$ mod 50 = 43。
   • ${ displaystyle（3 ^ {25}}$ mod 50 ${ displaystyle * 3 ^ {25}}$ mod 50）mod 50 = ${ displaystyle（43 * 43）}$ mod50。
   • ${ displaystyle = 1849}$ mod50。
   • ${ displaystyle = 49}$.

3のパート3：中国の剰余定理の使用

1. 1 2つの数字を選んでください。 数値の1つは複合である必要があり、もう1つは単純化のためにテストするものとまったく同じである必要があります。
   • 番号1 = 35
   • 番号2 = 97
2. 2 ゼロより大きく、それぞれ数値1と数値2より小さい2つの値を選択します。 これらの値は同じであってはなりません。
   • 値1 = 1
   • 値2 = 2
3. 3 Number1とNumber2のMMI（Mathematical Multiplicative Inverse）を計算します。
   • MMIを計算する
     • MMI1 = Number2 ^ -1 Mod Number1
     • MMI2 = Number1 ^ -1 Mod Number2
   • 素数の場合のみ（これにより合成数の数値が得られますが、彼のMMIにはなりません）：
     • MMI1 =（Number2 ^（Number1-2））％Number1
     • MMI2 =（Number1 ^（Number2-2））％Number2
   • 例えば：
     • MMI1 =（97 ^ 33）％35
     • MMI2 =（35 ^ 95）％97
4. 4 log2モジュールまでの各MMIのテーブルを作成します。
   • MMI1の場合
     • F（1）= Number2％Number1 = 97％35 = 27
     • F（2）= F（1） * F（1）％数値1 = 27 * 27％35 = 29
     • F（4）= F（2） * F（2）％数値1 = 29 * 29％35 = 1
     • F（8）= F（4） * F（4）％数値1 = 1 * 1％35 = 1
     • F（16）= F（8） * F（8）％数値1 = 1 * 1％35 = 1
     • F（32）= F（16） * F（16）％数値1 = 1 * 1％35 = 1
   • ペアの数を計算する1-2
     • 35 -2 = 33（10001）基数2
     • MMI1 = F（33）= F（32） * F（1）mod 35
     • MMI1 = F（33）= 1 * 27 mod 35
     • MMI1 = 27
   • MMI2の場合
     • F（1）= Number1％Number2 = 35％97 = 35
     • F（2）= F（1） * F（1）％数値2 = 35 * 35 mod 97 = 61
     • F（4）= F（2） * F（2）％数値2 = 61 * 61 mod 97 = 35
     • F（8）= F（4） * F（4）％数値2 = 35 * 35 mod 97 = 61
     • F（16）= F（8） * F（8）％数値2 = 61 * 61 mod 97 = 35
     • F（32）= F（16） * F（16）％数値2 = 35 * 35 mod 97 = 61
     • F（64）= F（32） * F（32）％数値2 = 61 * 61 mod 97 = 35
     • F（128）= F（64） * F（64）％数値2 = 35 * 35 mod 97 = 61
   • ペア数を計算する2-2
     • 97-2 = 95 =（1011111）基数2
     • MMI2 =（（（（（F（64） * F（16）％97） * F（8）％97） * F（4）％97） * F（2）％97） * F （1）％97）
     • MMI2 =（（（（（35 * 35）％97） * 61）％97） * 35％97） * 61％97） * 35％97）
     • MMI2 = 61
5. 5 計算（Value1 * Number2 * MMI1 + Value2 * Number1 * MMI2）％（Number1 * Number2）
   • 回答=（1 * 97 * 27 + 2 * 35 * 61）％（97 * 35）
   • 回答=（2619 + 4270）％3395
   • 回答= 99
6. 6 Number1が素数でないことを確認してください
   • 計算（回答-値1）％数値1
   • 99 – 1 % 35 = 28
   • 28は0より大きいため、35は素数ではありません。
7. 7 Number2が素数であることを確認します。
   • 計算（回答-値2）％数値2
   • 99 – 2 % 97 = 0
   • 0は0なので、97が素数である可能性があります。
8. 8 手順1から7を少なくともあと2回繰り返します。
   • 手順7で0を取得した場合：
     • Number1が素数でない場合は、別のNumber1を使用します。
     • Number1が素数の場合は、別のNumber1を使用します。この場合、ステップ6と7で0を取得する必要があります。
     • 異なるMeaning1とMeaning2を使用します。
   • ステップ7で一貫して0を取得する場合、2番が素数である可能性が非常に高くなります。
   • Number1が素数ではなく、Number2がNumber1の約数である場合、手順1〜7でエラーが発生する可能性があります。説明されている方法は、両方の数が素数である場合にすべて機能します。
   • 手順1から7を繰り返す必要がある理由は、場合によっては、番号1と番号2が素数でなくても、手順7で0（一方または両方の番号）を取得するためです。これはめったに起こりません。別のNumber1（複合）を選択します。Number2が素数でない場合、ステップ7でNumber2はゼロに等しくなりません（Number1がNumber2の約数である場合を除きます。ここでは、ステップ7で素数は常にゼロに等しくなります）。

チップ

• 168から1000までの素数：2、3、5、7、11、13、17、19、23、29、31、37、41、43、47、53、59、61、67、71、73、79 、83、89、97、101、103、107、109、113、127、131、137、139、149、151、157、163、167、173、179、181、191、193、197、199、211 、223、227、229、233、239、241、251、257、263、269、271、277、281、283、293、307、311、313、317、331、337、347、349、353、359 、367、373、379、383、389、397、401、409、419、421、431、433、439、443、449、457、461、463、467、479、487、491、499、503、509 、521、523、541、547、557、563、569、571、577、587、593、599、601、607、613、617、619、631、641、643、647、653、659、661、673 、677、683、691、701、709、719、727、733、739、743、751、757、761、769、773、787、797、809、811、821、823、827、829、839、853 、857、859、863、877、881、883、887、907、911、919、929、937、941、947、953、967、971、977、983、991、997。
• ブルートフォーステストは、多数を処理する場合は面倒なテストですが、少数の場合は非常に効率的です。大きな数の場合でも、小さな除数をテストすることから始めて、次に、数の単純さをチェックするためのより洗練された方法に進みます（小さな除数が見つからない場合）。

あなたは何が必要ですか

• 紙、ペンまたはコンピューター