香川大学創造工学部 富永浩之 tominaga@eng.kagawa-u.ac.jp 情報数学１ 第1-3章 素数と素因数分解 香川大学創造工学部 富永浩之 tominaga@eng.kagawa-u.ac.jp

概 要 ■ 素数と合成数 ■ 素数判定の算法 ■ 素因数の算法 ■ エラトステネスの篩 ■ 素因数分解と数論的関数 概 要 ■ 素数と合成数 素数 合成数 単数 素因数 ■ 素数判定の算法 素数列 素数判定 ■ 素因数の算法 素因数分解の一意性 候補による除算の範囲 効率化 ■ エラトステネスの篩 エラトステネスの篩 ■ 素因数分解と数論的関数 約数個数 約数和 互いに素

第01節 [1] 素数と合成数 ● 素数と合成数 ● 素数数列 素数 約数が2個 1と自分自身以外に約数を持たない正整数 第01節 [1] 素数と合成数 ● 素数と合成数 素数 約数が2個 1と自分自身以外に約数を持たない正整数 単数 約数が1個 1のみ 合成数 約数が3個以上 その他 (1は素数でも合成数でもない) ● 素数数列 ・ 明確な規則性がなく、k番目の素数 p(k) を一般項では表せない 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, ‥ ・ 100以下の素数は25個 ・ 素数は無限に存在 (有限すなわち最大の素数が存在と仮定すると矛盾) ユークリッドによる証明 全ての素数の積+1 は素数であり、最初に仮定した最大の素数よりも大きい

第01節 [2] 素数と合成数 ● 素数分布 ● 素数に関する定理 ● 素数に関する未解決問題 第01節 [2] 素数と合成数 ● 素数分布 ・ だんだん出現頻度が減っていく (大きい数はほとんどが合成数) ◎ 素数定理 ● 素数に関する定理 ◎ ウィルソンの定理 pが素数 ⇔ (p-1)！+1 がpで割り切れる 素数を判定する簡単な必要十分条件であるが、計算効率が悪すぎる ● 素数に関する未解決問題 ○ 双子素数 p, p+2 がともに素数となる組は無限に存在 ○ ゴールドバッハの予想 4以上の全ての偶数は、2つの素数の和で表せる

第02節 [1] 素因数と素因数分解 ● 素因数分解 ● 素因数分解の一意性 第02節 [1] 素因数と素因数分解 ● 素因数分解 2以上の正整数を素数の積の形に表したもの （素数は自分自身のみの形） 36＝2×2×3×3 210＝2×3×5×7 17＝17 個々の素数を重複も数えて素因数という 36は、異なる素因数2と3を持ち、2,2,3,3の4個の素因数を持つ 同じ素因数は巾乗にまとめて記述 36＝2^2 × 3^2 1の素因数分解は、1のみの形とする (1は素因数でないが、例外として) ● 素因数分解の一意性 順序を無視して、2以上の正整数は、唯一の素因数分解を持つ 途中でどのように積の形に分解していっても最後は同じ形に辿り着く 36＝4×9＝(2×2)×(3×3) → 2×2×3×3 ← 36＝6×6＝(2×3)×(2×3) 複素数の世界だと 10＝2×5=（3+i）(3-i)

素因数分解には効率的な算法が(今のところ)見つかっていない 第02節 [2] 素因数と素因数分解 ● 素因数分解の計算量 素因数分解には効率的な算法が(今のところ)見つかっていない 適当に与えられた正整数を素因数分解するには、 小さい方の素数から順に、実際に割り切れるかどうか調べていくしかない。 特に、2つの異なる大きな素数の積であるような合成数の素因数分解には、 膨大な計算時間が必要となる。 100桁以上の2つの素数の積である合成数だと、数億年かかるかも 大きな数の素因数分解が「実質的に計算不可能」という性質は、 公開鍵暗号系の1つであるRSA式公開鍵暗号系に応用されている。 大きな素数を知っていることが軍事機密や企業秘密になる！

n の最小の素因数を p とすれば、 n/p≧p より、 n≦p^2 で √n≦p 第03節 [1] 素数判定の算法 2以上の正整数　n を入力とする。 [1] まず、 q←2 と代入し、 n が q で割り切れるかどうか調べる。 割り切れれば合成数である(処理終了)。 [2] 次に、 q←3 と代入し、 n が q で割り切れるかどうか調べる。   [3] 以降は、奇数を順に q に代入し、　n が q で割り切れるか調べていく。 ここで、 次の奇数 q←q+2 と値を更新しながら、調べていくことになる。 [4] 除数が q^2＞n となったとき、素因数が存在しないことが分かる。 すなわち、素数であると判定される(処理終了)。 [5] q^2≦n のとき、 n が q で割り切れるかどうか調べる。 割り切れなければ、[3]に戻る。 n の最小の素因数を p とすれば、 n/p≧p より、 n≦p^2 で √n≦p

第03節 [2] 素数判定の算法 入力 n＝77 [1] q←2 として、 q=2 で割ってみると割り切れない。[2]へ進む。 第03節 [2] 素数判定の算法 入力 n＝77 [1] q←2 として、 q=2 で割ってみると割り切れない。[2]へ進む。 [2] q←3 として、 q=3 で割ってみると割り切れない。[3]へ進む。 [3] q←3+2＝5 とする。[4]へ進む。 [4] q^2＝5^2＝25≦77 より、[5]へ進む。 [5] q=5 で割ってみると割り切れない。[3]に戻る。 [3] q←5+2＝7 とする。[4]へ進む。 [4] q^2＝7^2＝49≦77 より、[5]へ進む。 [5] q＝7 で割ってみると割り切れる。 よって、合成数であると判定され、処理は終了する。 入力 n＝37 [1] q←2 として、 q=2 で割ってみると割り切れない。[2]へ進む。 [2] q←3 として、 q=3 で割ってみると割り切れない。[3]へ進む。 [3] q←3+2＝5 とする。[4]へ進む。 [4] q^2＝5^2＝25≦37 より、[5]へ進む。 [5] q=5 で割ってみると割り切れない。[3]に戻る。 [3] q←5+2＝7 とする。[4]へ進む。 [4] q^2＝7^2＝49＞37 より、素因数が存在しないと分かる。 よって、素数と判定され、処理は終了する。

第04節 [1] 素因数分解の算法 [1] 被除数 n を入力 とする。初期化として、除数を q←2 とし、添字を k＝0 とする。 第04節 [1] 素因数分解の算法 [1] 被除数 n を入力 とする。初期化として、除数を q←2 とし、添字を k＝0 とする。 [2] 除数 q の2乗 q^2 と被除数 n の大小を比較する。 [2-1][2-2]の場合分けに進む。   [2-1] q^2＞n のとき、 n には q 以上の素因数が存在しない。[4]に進む。 [2-2] q^2≦n のとき、[3]に進む。 [3] n が q で割り切れるかどうか調べ、[3-1][3-2]の場合分けに進む。 [3-1] n が q で割り切れるとき、 q は n の素因数である。 添字の更新 k←k+1 の後に、 k 番目の素因数を d_k←q と代入する。 以降の計算では、除数 q はそのままで、商を次の被除数 n←n/q とし、再び [3] を行う。 [3-2] n が q で割り切れないとき、 n に q 以下の素因数はない。 以降の計算では、被除数 n はそのままで、次の除数を q を求め、再び [2] を行う。 ただし、次の除数は q1=2, q2=3 を初期値とし、以降は q←q+2 と求める。 [4] n=1 かどうかを調べる。 [4-1] n≠1 のとき、 n は素数となる。 添字の更新 k←k+1 の後に、 d_k←n と代入して、終了処理[5]に進む。 [4-2] n=1 のとき、そのまま終了処理[5]に進む。   [5] d1, d2, ‥ を出力として並べれば、素因数分解 n＝d1×d2×‥ が得られる。 添字 k の値は、素因数の個数を表している。

第05節 [1] 素因数分解の計算過程 被除数 ① 182 91 = 13 二乗以上 ④ ○ × 二乗 ③ 4 9 25 49 81 除数 第05節 [1] 素因数分解の計算過程 被除数 ① 182 91 = 13 二乗以上 ④ ○ × 二乗 ③ 4 9 25 49 81 除数 ② 2 3 5 7 整除判定 ⑤ 1超上 ⑤' 添字 ⑥ 1 素因数 ⑦ 被除数 ① 375 = 125 25 5 1 二乗以上 ④ ○ × 二乗 ③ 4 9 49 除数 ② 2 3 7 整除判定 ⑤ 1超上 ⑤' 添字 ⑥ 素因数 ⑦

第06節 [1] 素数判定と素因数分解の応用 ● 3の倍数の除数列からの除去 第06節 [1] 素数判定と素因数分解の応用 ● 3の倍数の除数列からの除去 素数判定の算法では、2より大きい偶数を除いた奇数列を除数に選んだが、 3より大きい3の倍数も省略することができる。 2でも3でも割りきれない数は、 6k±1 という一般形で表される。 したがって、 q の次の除数として、 2,3,5 の後からは q←q+2, q←q+4 と交互に計算していけばよい。 すなわち、 q=5 までを初期値とし、以降は q4=q3+2=7, q5=q4+4=11, ‥ と求めることになる。 除数の列を具体的に列挙すると、2, 3, 5, 7, 11, 13, 17, 19, 23, 25, 29, 31, 35, ‥ となる。 この方法は、素因数分解の算法における除数にも適用できる。 さらに、5の倍数も省略しようとすると、多くが既に2,3の倍数として省略されているので、 25,55,85,‥ にしか効果がない。 しかも、除数を更新する規則が複雑になるので、かえって非効率となる。

第06節 [2] 素数判定と素因数分解の応用 ● 最小の素因数の出力 素数判定の算法と全く同様 第06節 [2] 素数判定と素因数分解の応用 ● 最小の素因数の出力 素数判定の算法と全く同様 最後の出力において、「合成数」か「素数」かとするのではなく、 その時点での除数 q の値を出力すればよい。 ● 最大の素因数の出力 素因数分解の算法とほぼ同様 入力 n が 1 ならば、そのまま 1 を出力する。 入力 n が 2 の累乗ならば、2 を出力する。 それ以外のとき、素因数分解の算法で、除数 q による反復に進む。 ただし、途中での素因数の出力は行わない。 除数 q による反復が終了した後、 n＞1 ならば、n が最大の素因数なので、n を出力する。 n＝1 ならば、直前の除数が最大の素因数であるが、 除数 q は既に更新されているので、以前の値 q-2 を出力する。

第07節 [1] エラトステネスの篩 ● エラトステネスの篩 第07節 [1] エラトステネスの篩 ● エラトステネスの篩 素数を列挙する素朴な算法である。素朴だが、これより効率的な方法は知られていない。 準備段階として、2以上の自然数を小さい順に(調べたい範囲で)全て書き出しておく。 まず、2を素数として確定し、2より大きい2の倍数4, 6, 8, ‥ を合成数として全て消去する。 次に、3を素数として確定し、3より大きい3の倍数 6, 9, 12, ‥ を全て消去する。 その次に、消去されている4を飛ばし、 5を素数として確定し、5より大きい5の倍数10, 15, 20, ‥ を全て消去する。 このように、未確定部分で、消去されていない最小の数を素数として確定し、 その倍数を消去していく操作を続けていくと、最後に素数の完全な列挙ができる。 素数pの倍数のうち、p^2 未満は、既に他の素数の倍数として消去されているから、 実際には、p^2から消去を始める。 逆に、pまできたらp^2未満で残っている数は素数である。 nまでの範囲で、素数を列挙する場合は、√n 以下の倍数まで調べればよい。

第07節 [2] エラトステネスの篩 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200

第08節 [1] エラトステネスの篩の応用 ● エラトステネスの篩の算法 ● 範囲内の素数列の列挙の算法 第08節 [1] エラトステネスの篩の応用 ● エラトステネスの篩の算法 [1] n以下の正整数に対し、結果を格納する箱を用意する。 [2] m＝[√n] とする。 p←2 とし、 p≦m の間、以下を実行する。 [3] q←p^2 から n までの各整数に対し、 p の倍数に印を付けていく。 これは、 q←q+p と更新しながら、 qに印を付けていけばよい。 [4] 印のない正整数は素数であり、これらを小さい方から列挙する。 ● 範囲内の素数列の列挙の算法 [1] N1 以上 N2 以下の正整数に対し、結果を格納する箱を用意する。 [2] m＝[√N2] までの正整数に対し、エラトステネスの篩を実行し、 m 以下の素数を求める。これを素数列 p(k) とおく。 [3] 各 p(k) について、 N1 未満の最大の倍数 s(k)＝(N1-1)-(N1-1)%p(k) を求め、 s(k) の次からの p(k) の倍数 s(k)+p(k), s(k)+2p(k), ‥ を N2 までの範囲で消去する。 [4] 消去されずに残った正整数は素数であり、これらを小さい方から列挙する。