、ウ、ホ・レ。シ・ク、、マ、ニ、ハ・ヨ・テ・ッ・゙。シ・ッ、ヒトノイテ、ウ、ホ・レ。シ・ク、エ゙、爨マ、ニ、ハ・ヨ・テ・ッ・゙。シ・ッ 、ウ、ホ・レ。シ・ク、livedoor ・ッ・・テ・ラ、ヒトノイテ、ウ、ホ・レ。シ・ク、エ゙、瀝ivedoor ・ッ・・テ・ラ

フワシ。

Miller・ニ・ケ・ネ

  • ・ユ・ァ・・゙。シ・ニ・ケ・ネ、ホイホノネヌ
  • ウホトナェ、ヒチヌソ、ネスト熙ケ、・「・・エ・・コ・
  • コヌーュキラササホフ。O(n^0.134)
    • 、筅キウネト・・遙シ・゙・ヘスチロ、ャタオ、キ、ア、、ミ。「、ウ、ホ・「・・エ・・コ・爨ホキラササホフ、マ(\log{n})^4~\log~\log~\log{n}トナル。「、ト、゙、O((\log{n})^4)トナル、ヌコム、爍」
  • Millerヒ。、ャSolovay-Strassen・ニ・ケ・ネ、Miller-Rabin・ニ・ケ・ネ、隍熙篁篦ョ、ヒシツケヤ、ヌ、ュ、ネマーマ、マソススキ蟆ハセ螟ホn、ホ、ネ、ュ、ヌ、「、。」

Miller・ニ・ケ・ネ、ホ・「・・エ・・コ・

  • ニホマ。ァn
  • スミホマ。ァ"チヌソ" or "ケ鄲ョソ"

1。ァn-1=2sm。ハm。ァエソ。ヒ、ヒ、ソ、ケs,m、キラササ、ケ、。」

2。ァn、ャチヌソ、ホポセ陦ハperfect power。ヒ。「ツィ、チn=pt。ハt。1。ヒ、ォ、ノ、ヲ、ォ、ク。セレ、ケ、。」、筅キタョ、ホゥ、ニ、ミ"ケ鄲ョソ"、スミホマ、ケ、。」、ス、ヲ、ヌ、ハ、ア、、ミーハイシ、シツケヤ、ケ、。」

3。ァn、ヌト熙゙、、「、セ蟲ヲb*1、゙、ヌ。「a=2,3,5,。ト,b(チヌソホ。ヒ、ヒ、ト、、、ニ。「シ。、ホ(1)。チ(3)、ク。セレ、ケ、。」

。。(1)a|n、ハ、鬢ミ。「"ケ鄲ョソ"、スミホマ、ケ、。」、ス、ヲ、ヌ、ハ、ア、、ミーハイシ、シツケヤ、ケ、。」

。。(2)a^{n-1}~\not{\equiv}~1~\pmod{n}、ハ、鬢ミ。「"ケ鄲ョソ"、スミホマ、ケ、。」、ス、ヲ、ヌ、ハ、ア、、ミーハイシ、シツケヤ、ケ、。」

。。(3)GCD(a^{\frac{n-1}{2^j}}~\pmod{n}~-1,~n)~\not{=}~1、ハ、鬢ミ。「"ケ鄲ョソ"、スミホマ、ケ、。」、ス、ヲ、ヌ、ハ、ア、、ミーハイシ、シツケヤ、ケ、。」

4。ァ"チヌソ"、スミホマ、ケ、。」

サイケヘハクク・

  • [1]。リクスツ蟆ナケ賚マタ。ルテモフソョー。「セョサウクャニ。。ツ13セマ。ァチヌソネストヒ。 pp.246-247


*1 a、ホセ蟲ヲb、マヘマタナェ、ヒキ隍゙、。」