素数
ChatGPT4君まかせ。
約数
約数とは、ある整数を割り切ることができる整数のことを指します。例えば、12の約数は1, 2, 3, 4, 6, 12です。これは、12をこれらの数で割ったときに余りが0になるからです。
約数の性質や関連情報を以下に示します。
正の約数: ある整数の正の約数は、その整数と1の間にあります。
完全数: 自分自身を除く正の約数の和が元の数自体と等しい数を完全数といいます。例えば、6は1, 2, 3の和であり、6の約数は1, 2, 3, 6なので、6は完全数です。
素数: 素数は1と自分自身以外の約数を持たない正の整数です。例: 2, 3, 5, 7, 11, ...
約数の探し方: ある整数Nの約数を探すとき、Nの平方根までの数を調べれば十分です。Nの平方根より大きい数aがNの約数である場合、その対となる約数b (N/a = b) はNの平方根より小さくなります。
約数の求め方の例:
24の約数を求める場合、
1は全ての整数の約数なので、1は24の約数。
2で割ると12なので、2と12は24の約数。
3で割ると8なので、3と8は24の約数。
4で割ると6なので、4と6は24の約数。
5では割り切れない。
6で割ると4なので、4は既にリストにある。
これにより、24の約数は1, 2, 3, 4, 6, 8, 12, 24となります。
約数は数学や暗号学、コンピューターサイエンスなど、さまざまな分野で使用されます。
最大公約数
ユークリッドの互除法
def gcd(a, b):
while b:
a, b = b, a % b
return abs(a)ユークリッドの互除法の基本的なアイディアは以下のとおりです：
2つの数 $${a}$$ と $${b}$$（$${a \geq b}$$ と仮定）が与えられたとき、$${b}$$ が0であれば、$${a}$$ が2つの数の最大公約数になります。
$${b}$$ が0でなければ、$${a}$$ と $${b}$$ の最大公約数は、$${b}$$ と $${a \mod b}$$（$${a}$$ を $${b}$$ で割った余り）の最大公約数と同じです。
このアルゴリズムは、余りが0になるまでこのプロセスを繰り返し、余りが0になった時の除数（割る方）が最大公約数となります。
合成数
素数じゃない数。
合成数（ごうせいすう）は、素数ではない1より大きい自然数のことを指します。言い換えると、1と自分自身以外にも約数を持つ整数です。
以下は合成数の基本的な性質や特徴です：
定義: 1より大きく、自分自身と1以外にも約数を持つ整数。例としては、4, 6, 8, 9, 10, 12, ... などが挙げられます。
2, 3, 5, 7, 11, 13, …は素数です。素因数分解:
合成数は2つ以上の素数の積として表されることができます。これを素因数分解といいます。素因数分解は一意的です。つまり、同じ数に対する素因数分解の結果は1つしか存在しないという性質があります。
素因数分解の例
$${ 4 = 2 \times 2 }$$
$${ 6 = 2 \times 3 }$$
$${ 8 = 2 \times 2 \times 2}$$
$${ 9 = 3 \times 3}$$
$${ 10 = 2 \times 5}$$
$${ 12 = 2 \times 2 \times 3}$$最小の合成数: 4は最小の合成数です。なぜなら、2×2として2つの素数の積として表すことができ、1と自分自身以外の約数を持っているからです。
合成数と素数: 自然数の中で1より大きい数は、素数または合成数のいずれかとなります。1自体は素数でも合成数でもありません。
フェルマーの小定理
フェルマーの小定理は、数論の基本的な定理の一つであり、特に暗号学や計算数学においても応用される重要な定理です。定理の内容は次の通りです。
フェルマーの小定理:
$${ p }$$ が素数で $${ a }$$ が $${ p }$$ で割り切れない整数のとき、あるいは$${ a }$$ と $${ p }$$ が互いに素（$${ a }$$ と $${ p }$$ の最大公約数が１）である時、以下の関係が成り立つ。
$$
a^{p-1} \equiv 1 \mod p
$$
$${ a }$$ と $${ p }$$の大小は関係ない。
が、フェルマーテスト等の実用上は$${ 0 < a < p }$$が好ましい。
また、両辺にaを乗ずると
$$
a^p \equiv a \pmod{p}
$$
言い換えると、$${ p }$$ が素数で $${ a }$$ が $${ p }$$ の倍数でないとき、$${ a }$$ の $${ p-1 }$$ 乗を $${ p }$$ で割った余りは1である、ということです。
この定理は、モジュラー算術や数論的アルゴリズムにおける基本的なツールとして使われます。例えば、フェルマーテストという素数判定アルゴリズムにもこの定理が応用されます。
証明のアイディアは、グループ論を使用する方法や、整数の性質を直接利用する方法など、いくつかの異なるアプローチが存在しますが、すべてをここで詳細に説明するのは長くなってしまいます。特定の証明方法に興味がある場合や、この定理の詳細や応用についての質問があれば、お気軽にお知らせください。
フェルマーテストの場合、素数かどうか調べたい数をpとして、
aを適当に選んだ上で$${a^{p-1}}$$を割ってみて余りを見る。
aを適当に選ぶため、またカーマイケル数のような特殊な合成数としてpが存在するため、フェルマーテストは確率的である。
これはaがpの倍数であるケース（aの選択ミス:aとpが互いに素でない）
およびpがカーマイケル数であるケース（pの選択ミス:p側にへんな性質）
およびaとpの組み合わせによるケース（フェルマー小定理は素数については必ず成り立つが、合成数が成り立たないとは言ってない。つまりaとpの組み合わせによってはテストを抜ける）
フェルマーテストなどの実用上、aは$${ 0 < a < p }$$の範囲でランダムに取得され、また互いに素であることのチェック機構を挟む。この場合、aのみに関する確率性はなくなり、テストの可否はn, およびaとpの組み合わせに依存する。
互いに素
「互いに素」とは、二つの整数が最大公約数（GCD）として1しか持たない関係を指す言葉です。言い換えれば、それらの整数を除算するどのような他の整数も共有しないということです。
例:
15 と 28 は互いに素である。なぜなら、15の約数は1, 3, 5, 15で、28の約数は1, 2, 4, 7, 14, 28であり、これらの約数の中で共通しているのは1だけだからです。
14 と 21 は互いに素ではない。なぜなら、両者の最大公約数は7で、1よりも大きいからです。
互いに素な数同士を掛け合わせると、その結果もまた他の数と互いに素となるという特徴があります。
code
最大公約数はユークリッド互除法で求められます。
def gcd(a, b):
while b:
a, b = b, a % b
return a
def are_coprime(x, y):
return gcd(x, y) == 1
# テスト
x, y = 15, 28
if are_coprime(x, y):
print(f"{x}と{y}は互いに素です。")
else:
print(f"{x}と{y}は互いに素ではありません。")
オイラーのトーシェント関数
オイラーのトーシェント関数、または単にトーシェント関数、は、ある正の整数 $${ n }$$ に対して $${ n }$$ より小さく、$${ n }$$ と互いに素（最大公約数が1）である正の整数の個数を表します。この関数は通常、$${ \phi(n) }$$ として表されます。
以下はトーシェント関数の基本的な性質や公式をいくつか示します：
素数に対するトーシェント関数
ある素数 $${ p }$$ に対して、$${ \phi(p) = p - 1 }$$ です。これは、素数より小さいすべての正の整数がその素数と互いに素であるためです。乗数に対するトーシェント関数
ある素数 $${ p }$$ と正の整数 $${ k }$$ に対して、$${ \phi(p^k) = p^k - p^{k-1} }$$ です。積の性質
$${ m }$$ と $${ n }$$ が互いに素である場合、$${ \phi(m \times n) = \phi(m) \times \phi(n) }$$ です。公式
$${ n }$$ の素因数分解が $${ n = p_1^{k_1} \times p_2^{k_2} \times \dots \times p_r^{k_r} }$$ となる場合、
$${\phi(n) = n \left(1 - \frac{1}{p_1}\right) \left(1 - \frac{1}{p_2}\right) \dots \left(1 - \frac{1}{p_r}\right)}$$オイラーの定理
$${ a }$$ と $${ n }$$ が互いに素である場合、以下の式が成立します：
$${a^{\phi(n)} \equiv 1 \mod n}$$
トーシェント関数は、数論や暗号学（特にRSA暗号）など、さまざまな分野で使用されます。
code
def gcd(a, b):
"""最大公約数を返す関数"""
while b:
a, b = b, a % b
return a
def is_coprime(a, b):
"""aとbが互いに素である場合はTrueを返す関数"""
return gcd(a, b) == 1
def euler_phi(n):
"""オイラーのトーシェント関数を返す関数"""
result = 0
for i in range(1, n + 1):
if is_coprime(i, n):
result += 1
return result
# 使用例
n = 10
print(f"phi({n}) =", euler_phi(n))
位数 (order)
その１
群の位数 (Order of a group):
群の元の総数を指します。例えば、集合が $${ G = { e, a, b, c } }$$ と4つの元からなる場合、群 $${ G }$$ の位数は4です。元の位数 (Order of an element):
群のある元 $${ a }$$ に対して、その元を何回演算すると単位元 $${ e }$$ になるかを表します。具体的には、最小の正の整数 $${ n }$$ で $${ a^n = e }$$ となるものを、元 $${ a }$$ の位数といいます。もし、そのような正の整数 $${ n }$$ が存在しない場合、元 $${ a }$$ の位数は無限大とします。
フェルマー定理, あるいはAKS素数判定の文脈だと元の位数。
また、元の位数に用いる演算は群を構成するなら回転でも何でもいいが、通常の文脈では冪が用いられる。
その２
「元の位数」とは、ある元が生成する部分群の要素数のことを指します。より数学的に言うと、群$${ G }$$の元$${ a }$$に対して、$${ a }$$の最小の正の冪$${ n }$$で、$${ a^n }$$が単位元となるような$${ n }$$を、元$${ a }$$の位数と言います。この$${ n }$$を記号で $${ \text{ord}(a) }$$ とも表します。
例として、有限群$${ G }$$が与えられ、その元$${ a }$$が考えられるとき、$${ a }$$の位数が$${ n }$$であるとは、以下の2つの条件を満たすことを意味します：
$${ a^n }$$ は群の単位元$${ e }$$である。
任意の正の整数$${ k < n }$$ に対して、$${ a^k }$$ は単位元$${ e }$$でない。
一般的に、群の任意の元の位数はその群の位数（すなわち、群の要素数）を割り切ることが知られています（ラグランジュの定理）。
具体例として、加法的群 $${ \mathbb{Z}/4\mathbb{Z} }$$ を考えます。この群の元[2]の位数は2です。なぜなら、[2] + [2] = [0] (群の単位元) であり、[2]単体では[0]にならないからです。
位数の概念は、群論における基本的なものであり、さまざまな数学的背景や応用において重要な役割を果たしています。
例
乗法的群における位数の例:
群$${ \mathbb{Z}/7\mathbb{Z}^* }$$は、0を除く7未満の正の整数に対する乗法に関する群です。この群の元として[3]を考えます。
$$
3^1 \equiv 3 \mod 7\\
3^2 \equiv 9 \equiv 2 \mod 7\\
3^3 \equiv 27 \equiv 6 \mod 7\\
3^4 \equiv 81 \equiv 4 \mod 7\\
3^5 \equiv 243 \equiv 5 \mod 7\\
3^6 \equiv 729 \equiv 1 \mod 7\\
$$
$${3^6 \equiv 1 \mod 7}$$ となり、それより小さい冪では1にはなりません。したがって、[3]の位数は6です。
加法的群における位数の例:
群 $${ \mathbb{Z}/9\mathbb{Z} }$$ を考えます。この群の元として[4]を考えます。
[4]
[4] + [4] = [8]
[4] + [4] + [4] = [12] = [3]
[4] + [4] + [4] + [4] = [16] = [7]
[4] + [4] + [4] + [4] + [4] = [20] = [2]
[4] + [4] + [4] + [4] + [4] + [4] = [24] = [6]
[4] + [4] + [4] + [4] + [4] + [4] + [4] = [28] = [1]
[4]を7回足すと、結果が[1]（この群の単位元）になります。したがって、[4]の位数は7です。
これらの例から、群の中のある元の位数を知るためには、その元を何回操作すると単位元になるかを調べる必要があります。位数は、その元が単位元になるまでの「ステップ数」と考えることもできます。
code
def ord_n(r, n):
k = 1
while (r ** k) % n != 1:
k += 1
return k原始根
原始根 (primitive root) とは、数論の中での重要な概念の一つで、モジュラ算術におけるべき乗の周期性を表すものです。具体的には、ある正の整数 $${ n }$$ に対して、$${ n }$$ の原始根とは以下の性質を持つ正の整数 $${ g }$$ のことを指します。
定義:
ある正の整数 $${ n }$$ に対して、$${ g }$$ が $${ n }$$ の原始根であるとは、以下の条件を満たす $${ g }$$ のことを指します：
$${ g }$$ と $${ n }$$ が互いに素である：$${ \text{gcd}(g, n) = 1 }$$
任意の $${ 1 \leq m < \phi(n) }$$ に対して、$${ g^m \not\equiv 1 \mod n }$$
すなわち、
$${ g^{\phi(n)} \equiv 1 \mod n }$$
この定義は、$${ g }$$ のべき乗が $${ n }$$ の法に関して全ての異なる残余を一度ずつとるという性質を持つことを意味しています。したがって、$${ g }$$ は $${ n }$$ の法に関して周期的になるとき、その周期（指数）は正確に $${ \phi(n) }$$ であるということを示しています。
ここで $${ \phi(n) }$$ はオイラーのトーシェント関数で、$${ n }$$ 以下の正の整数で $${ n }$$ と互いに素なものの個数を示します。
原始根の位数
原始根の位数とは、モジュロ $${ n }$$ での $${ g }$$ のべき乗が初めて 1 となる最小の正の整数を指します。原始根の定義から、その位数は $${ \phi(n) }$$ となります。
例
注意すべきは、すべての正の整数が原始根を持つわけではないということです。原始根が存在するのは、$${ n }$$ が $${ 2, 4, p^k, 2p^k }$$ の形をしたときのみであり、ここで $${ p }$$ は奇素数、$${ k }$$ は正の整数を指します。
以下は、いくつかの数に関する原始根の例を挙げるものです：
$${ n = 2 }$$
原始根は $${ g = 1 }$$ のみ。
$${ n = 3 }$$
原始根は $${ g = 2 }$$ のみ。
$${ n = 5 }$$
原始根は $${ g = 2 }$$ および $${ g = 3 }$$。
$${ n = 7 }$$
原始根は $${ g = 3, 5 }$$ です。
$${ n = 11 }$$
原始根は $${ g = 2, 6, 7, 8 }$$ です。
n = 11 と g = 2 の場合
$${ n = 11 }$$ と $${ g = 2 }$$ の場合、$${ g }$$ が $${ n }$$ の原始根であることを示すには、以下の2つの条件を確認します。
$${ g }$$ と $${ n }$$ が互いに素であること。
$${ g^m \mod n }$$ が $${ 1 \leq m < \phi(n) }$$ の範囲で1になることがないが、$${ g^{\phi(n)} \mod n }$$ は1であること。
まず、
$${ \text{gcd}(2, 11) = 1 }$$
2 と 11 は互いに素であるので、最初の条件は満たされます。
次に、$${ \phi(11) }$$ を計算します。11は素数なので、$${ \phi(11) = 11 - 1 = 10 }$$
すなわち、2の11に関する指数は10であるべきです。
これを確認するために、$${ 2^m \mod 11 }$$ の値を $${ m = 1 }$$ から $${ m = 10 }$$ まで計算してみます。
$$
2^1 \mod 11 = 2\\
2^2 \mod 11 = 4 \\
2^3 \mod 11 = 8 \\
2^4 \mod 11 = 5 \\
2^5 \mod 11 = 10 \\
2^6 \mod 11 = 9 \\
2^7 \mod 11 = 7 \\
2^8 \mod 11 = 3 \\
2^9 \mod 11 = 6 \\
2^{10} \mod 11 = 1\\
$$
この結果、$${ 2^m \mod 11 }$$ が $${ m = 1 }$$ から $${ m = 9 }$$ の範囲で1になることはありませんが、$${ m = 10 }$$ のとき1となることが確認できます。これにより、2は11の原始根であることが示されました。
素数の原始根
$${ p }$$ が素数のとき、整数 $${ g }$$ が $${ p }$$ の原始根であるとは、以下の性質を持つことを指します:
$${ 0 < g < p }$$
$${ g^k \mod p }$$ が $${ 1 \leq k < p }$$ の範囲で $${ p-1 }$$ 個の異なる値を取る。
この性質は、$${ g^k \mod p }$$ が1から $${ p-1 }$$ までのすべての整数を一度ずつ取ることを意味しています。
例:
$${ p = 5 }$$ のとき、2と3は5の原始根です。なぜならば、
2の冪を5で割った余り: $${ 2^1 \mod 5 = 2, 2^2 \mod 5 = 4, 2^3 \mod 5 = 3, 2^4 \mod 5 = 1 }$$
3の冪を5で割った余り: $${ 3^1 \mod 5 = 3, 3^2 \mod 5 = 4, 3^3 \mod 5 = 2, 3^4 \mod 5 = 1 }$$
それぞれ、1から4までの整数を一度ずつ取ることが確認できます。
$${ p = 7 }$$ のとき、数 4 は7の原始根ではありません。なぜならば、4の冪を7で割った余りは:
$${ 4^1 \mod 7 = 4, 4^2 \mod 7 = 2, 4^3 \mod 7 = 1, 4^4 \mod 7 = 4 }$$
1から6までの整数を一度ずつ取るという性質を満たしていないため、4は7の原始根ではありません。
このように、ある数がある素数の原始根であるかどうかは、その数の冪をその素数で割った余りの値を調べることで判断することができます。
code
未確認
def is_prime(n):
if n <= 1:
return False
if n <= 3:
return True
if n % 2 == 0 or n % 3 == 0:
return False
i = 5
while i * i <= n:
if n % i == 0 or n % (i + 2) == 0:
return False
i += 6
return True
def prime_factors(n):
factors = set()
while n % 2 == 0:
factors.add(2)
n //= 2
for i in range(3, int(n**0.5) + 1, 2):
while n % i == 0:
factors.add(i)
n //= i
if n > 2:
factors.add(n)
return list(factors)
def primitive_root(p):
if not is_prime(p):
return -1 # Not a prime number
phi = p - 1
factors = prime_factors(phi)
for g in range(2, p):
flag = False
for q in factors:
if pow(g, phi // q, p) == 1:
flag = True
break
if not flag:
return g
return -1
# Example usage
p = 7
root = primitive_root(p)
print(f"The primitive root of {p} is {root}")
この実装に関して以下の点を指摘します：
is_prime関数: この関数は素数判定を行いますが、6k ± 1の形の数だけをチェックするというアイディアに基づいています。このアイディアは、すべての素数（2と3を除く）は6k ± 1の形であることを利用しています。この素数判定の方法は、大きな数の場合には非常に効率的でない可能性がありますが、このコードのコンテキストにおいては十分です。
prime_factors関数: 与えられた数のすべての素因数を返す関数です。効率的に実装されています。
primitive_root関数:
入力として素数のみを受け入れるようにしています。これは原始根を求めるための正しいアプローチです。
与えられた素数pの原始根を見つけるために、2からp-1までのすべての数gをチェックしています。これは一般的な方法ですが、最悪の場合、O(p log p)の時間がかかる可能性があります。
各gに対して、gがpの原始根であるかどうかを確認するために、phi(p) = p-1のすべての素因数でgの冪をチェックしています。これは、原始根の定義と一致しています。
コード全体:
実装はクリーンで読みやすいです。
ただし、非常に大きな素数p（例えば、10^5以上）の場合、このアルゴリズムは効率的ではありません。そのような場合には、より高度なアルゴリズムやテクニックを採用する必要があります。
結論として、このコードは中小規模の数に対して非常にうまく機能しますが、大きな数に対しては効率的ではありません。
sympyの場合
from sympy.ntheory import totient, factorint
def is_primitive_root(r, n):
# n has a primitive root only if n is of the form 2, 4, p^k, or 2p^k
if n not in [2, 4] and n % 2 != 0 and (n // 2) % 2 != 0:
return False
phi = totient(n)
for q in factorint(phi).keys():
if pow(r, phi // q, n) == 1:
return False
return True
`is_primitive_root` は、与えられた数が特定のモジュロで原始根 (primitive root) であるかどうかを確認する関数です。`sympy` ライブラリには、この関数が含まれています。
原始根とは、数論において、与えられた素数 ( p ) に対して、その剰余体 ( \mathbb{Z}/p\mathbb{Z} ) の各非ゼロ元が ( r ) の冪として表現できるとき、( r ) を ( p ) の原始根と言います。別の言い方をすると、( r ) が ( p ) の原始根であるとは、( \text{ord}_p(r) = p-1 ) であることを意味します。
`is_primitive_root` の実装は、`sympy` のソースコードで確認することができますが、基本的なアイディアとしては：
( n ) が原始根を持つかどうかを確認します。原始根は、( n = 2, 4 )、または ( n ) が奇数の力、または奇数の力の2倍である場合のみ持ちます。
( n ) の原始根が存在する場合、( \phi(n) ) （オイラーのトーシェント関数）のすべての異なる素因子 ( q ) に対して ( r^{(\phi(n)/q)} \not\equiv 1 \mod n ) であるかどうかを確認します。すべての ( q ) に対してこの条件が成立する場合、( r ) は ( n ) の原始根です。
ただし、`sympy` に組み込まれている `is_primitive_root` 関数の実装は、上記よりも最適化されている可能性があります。
素数判定法
素朴な方法 (Naive Method)
2から$${\sqrt n}$$までのすべての整数でnを割ってみる。
もしnが2から$${\sqrt n}$$のいずれの数でも割り切れないならば、nは素数である。
エラトステネスの篩 (Sieve of Eratosthenes)
ある範囲内の全ての素数を効率的に見つけ出す方法。
最初に2から所定の数までの数字をリストアップし、そこから最小の数（最初は2）の倍数を全て取り除いていく。これを繰り返し、最終的に残った数がその範囲の素数となる。
フェルマーテスト (Fermat's Little Theorem)
この方法は確率的な素数判定法で、高速に動作するが誤判定の可能性がある。
$${\sqrt a^{n-1} \equiv 1 \mod n }$$ の性質を利用する。
ミラー–ラビン素数判定法 (Miller-Rabin Primality Test)
これも確率的な方法で、n回のテストを行うことで誤判定の確率を$${2^{-n}}$$まで下げることができる。
AKS素数判定法 (AKS Primality Test)
確定的な素数判定法で、多項式時間で動作することが証明されている。
素朴な方法
プッチ神父は多分これを用いている。
def is_prime_naive(n):
if n <= 1:
return False
for i in range(2, int(n**0.5) + 1):
if n % i == 0:
return False
return True
def list_primes_up_to_limit(limit):
return [num for num in range(2, limit + 1) if is_prime_naive(num)]
# 使用例
limit = 100
print(list_primes_up_to_limit(limit))
結果
[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]
2以外の偶数飛ばし(step数2)
def is_prime_naive(n):
if n <= 1:
return False
if n == 2:
return True
if n % 2 == 0:
return False
for i in range(3, int(n**0.5) + 1, 2):
if n % i == 0:
return False
return True
def list_primes_up_to_limit(limit):
return [2] + [num for num in range(3, limit + 1, 2) if is_prime_naive(num)]
# 使用例
limit = 100
print(list_primes_up_to_limit(limit))以下２行が変更部分(step数2)
他に２だけ例外処理
for i in range(3, int(n**0.5) + 1, 2): return [2] + [num for num in range(3, limit + 1, 2) if is_prime_naive(num)]`n**0.5`
この部分は、数`n`の平方根を計算しています。``はPythonの累乗演算子であり、`n0.5`は`n`の0.5乗、すなわち`n`の平方根を意味します。
`int(...)`
この部分は、実数値を最も近い整数に変換します。具体的には、小数部分を切り捨てる動作を行います。
組み合わせると、`int(n**0.5)`は数`n`の平方根の整数部分、平方根より小さい整数のうち最大の整数、を返すことになります。
素数判定の文脈での利用
この`int(n**0.5)`の式は、素数判定のアルゴリズムにおいて、効率的な計算のための要件を満たすものです。
`n`が素数でない場合、`n`の約数のうち`1`と`n`を除いた最小の約数を`a`とし、対応する最大の約数を`b`とすると、`a * b = n`となります。
このとき以下の2つのケースにおける`a`と`b`のペアはあり得ません。
`a`と`b`が共に`n`の平方根より小さい場合：
この場合、`a * b`は`n`よりも小さくなります。なぜなら、最も大きい`a`と`b`の積であっても、`n`の平方根同士の積、すなわち`n`には達しないためです。
`a`と`b`が共に`n`の平方根より大きい場合：
この場合、`a * b`は`n`よりも大きくなります。なぜなら、最も小さい`a`と`b`の積であっても、`n`の平方根同士の積を超えるためです。
したがって、`a`と`b`の両方が`n`の平方根を超える、または両方が`n`の平方根未満であるようなペアは、非素数`n`に対して存在しえません。
これは、`n`が非素数である場合、その約数のうち少なくとも1つが`n`の平方根以下に存在することを保証しています。よって、`n`の平方根までを調査するだけで、`n`が素数かどうかを判定することができます。
例：
n = 12
12の約数は1, 2, 3, 4, 6, 12。
1と12を除いた最小の約数は2、対応する最大の約数は6。
2 (a) * 6 (b) = 12 (n)
$${\sqrt 12 = 3.464101615137755…}$$
n = 20
20の約数は1, 2, 4, 5, 10, 20。
1と20を除いた最小の約数は2、対応する最大の約数は10。
2 (a) * 10 (b) = 20 (n)
$${\sqrt 20 = 4.472135954999579…}$$
n = 21
21の約数は1, 3, 7, 21。
1と21を除いた最小の約数は3、対応する最大の約数は21。
3 (a) * 7 (b) = 21 (n)
$${\sqrt 20 = 4.58257569495584…}$$
n = 30
30の約数は1, 2, 3, 5, 6, 10, 15, 30。
1と30を除いた最小の約数は2、対応する最大の約数は15。
2 (a) * 15 (b) = 30 (n)
$${\sqrt 30 = 5.477225575051661…}$$
n = 49
49の約数は1,7,49。
1と49を除いた最小の約数も最大の約数も7。
7 (a) * 7 (b) = 49 (n)
$${\sqrt 7 = 7}$$
この説明が、`n`の約数に関する理論を明確にしていることを願っています。再び誤った情報を提供してしまったこと、お詫び申し上げます。
エラトステネスの篩
しばしばアルゴリズムの入門本を買うと、ユークリッドの互除法とハノイの塔の間くらいの２P目くらいにあるやつ。
def sieve_of_eratosthenes(limit):
sieve = [True] * (limit + 1)
sieve[0:2] = [False, False]
for i in range(2, int(limit**0.5) + 1):
if sieve[i]:
for j in range(i*i, limit + 1, i):
sieve[j] = False
return [i for i, is_prime in enumerate(sieve) if is_prime]
# 使用例
limit = 100
print(sieve_of_eratosthenes(limit))アルゴリズムの手順
2から所定の上限値`n`までの整数をリストアップします。
最初の数字、すなわち2を素数として記録します。
2の倍数（4, 6, 8, ...）をリストから削除します。
次に残った最小の数字、すなわち3を素数として記録します。
3の倍数（9, 12, 15, ...）をリストから削除します。
上記の手順を、リストの終わりに達するか、次に残る数字の二乗が上限値`n`を超えるまで繰り返します。
例：10までの素数を求める場合
数字のリスト: [2, 3, 4, 5, 6, 7, 8, 9, 10]
2を素数として記録し、2の倍数を削除 -> [2, 3, 5, 7, 9]
3を素数として記録し、3の倍数を削除 -> [2, 3, 5, 7]
結果として、10までの素数は2, 3, 5, 7です。
アルゴリズムの特徴
エラトステネスの篩は、指定された上限値までのすべての素数を効率的に求めることができます。
アルゴリズムの実行時間はおおよそ$${\sqrt O(n \log \log n)}$$であり、大きな数値範囲に対しても比較的高速に動作します。
エラトステネスの篩（Sieve of Eratosthenes）は、特定の上限までのすべての素数を効率的に見つけるための古典的なアルゴリズムです。このアルゴリズムの時間複雑度は $${O(n \log \log n)}$$ であり、小さい上限（例：$${10^6}$$ または $${10^7}$$ までの範囲）の素数を探索するためには非常に効率的です。
しかし、以下の理由でエラトステネスの篩が「遅い」と考えられる場合があります：
大きな上限: 上限が非常に大きい場合（例：$${10^{12}}$$ など）、エラトステネスの篩はメモリの使用量や計算時間が増加するため、非効率的になる可能性があります。
単一の素数の判定: ある1つの大きな数が素数かどうかを判定するだけの場合、エラトステネスの篩は過剰であり、より効率的な素数判定法（例：ミラー–ラビン素数判定法やAKS素数判定法）の使用が推奨されます。
最適化の欠如: 基本的なエラトステネスの篩の実装は最適化されていない場合があり、実行速度が低下する原因となることがあります。たとえば、偶数の排除や篩のステップのスキップなどの簡単な最適化で、実行速度を大幅に向上させることができます。
総じて、エラトステネスの篩は、特定の範囲内のすべての素数を効率的に探索するための優れたアルゴリズムですが、目的や使用シナリオに応じて、他の方法がより適切である場合があります。
フェルマーテスト
フェルマーテストは、ある数が素数であるかを確認するための確率的な方法です。基本的なアイディアは、以下のフェルマーの小定理に基づいています：
もし $${ p }$$ が素数で、 $${ a }$$ が $${ p }$$ の倍数でない任意の数であるならば、
$${ a^{p-1} \equiv 1 \mod p }$$
この定理を用いて、ある数 $${ n }$$ が素数であるかをチェックするためには、ランダムに選ばれた数 $${ a }$$ について上記の等式が成り立つかを確認します。もし成り立たなければ、 $${ n }$$ は合成数です。
プログラム的には
a^{p-1} mod p == 1 mod pであって、
1 mod pは1であることが自明。
よって
a**(p-1) % p == 1この式はpythonだと第3引数を伴ったpow()で実装できる。
import random
def fermat_test(n, k=5):
if n <= 1:
return False
if n <= 3:
return True
for _ in range(k):
a = random.randint(2, n - 2)
if pow(a, n-1, n) != 1:
return False
return True
def primes_up_to_limit(limit):
primes = []
for i in range(2, limit + 1):
if fermat_test(i):
primes.append(i)
return primes
# 使用例
result = primes_up_to_limit(100)
print(result)aとnが互いに素であること（最大公約数が1）の確認を加えたもの
aとnが互いに素でない場合、nは合成数。
import random
import math
def fermat_test(n, k=5):
if n <= 1:
return False
if n <= 3:
return True
for _ in range(k):
a = random.randint(2, n - 2)
# aとnが互いに素でない場合は、nは合成数
if math.gcd(a, n) != 1:
return False
if pow(a, n-1, n) != 1:
return False
return Trueただしカーマイケル数はこのテストをすり抜ける可能性があります。
pow()
python組み込み`pow()` の強力な特性の一つは、第3引数をとることができる点です。この第3引数は、計算結果をその数で割った余りを返すモジュロ計算に使います。
pow(x, y, z)いくつかの注意点：
`x` および `y` は整数でなければなりません。`z` が指定された場合、それも整数でなければなりません。
`y` が負の場合、`x` は逆数を持つ必要があります。`z` が指定されている場合、`x` はモジュロ `z` の乗法的逆元を持つ必要があります。
通常のべき乗計算よりもモジュロべき乗の方が効率的に行われます。
この関数を使うことで、特に大きな数のべき乗やモジュロ計算を高速に行うことができます。
カーマイケル数
カーマイケル数は、合成数（すなわち、素数でない数）です。
合成数の中で、フェルマーの小定理を「だます」性質を持った特殊な数を指します。フェルマーの小定理は以下のように表されます：
もし $${ p }$$ が素数で、 $${ a }$$ が $${ p }$$ の倍数でない任意の数であるならば、
$${ a^{p-1} \equiv 1 \mod p }$$
カーマイケル数 $${ n }$$ は、1より大きく $${ n }$$ と互いに素な任意の整数 $${ a }$$ に対して、以下の性質を持ちます：
$${ a^{n-1} \equiv 1 \mod n }$$
この性質のため、カーマイケル数はフェルマーテストによる素数判定を誤認させる可能性があります。
カーマイケル数の例
最小のカーマイケル数は561です。これは合成数であり、実際には3, 11, 17という3つの異なる素因数を持ちます。しかし、上記の定義に従い、1より大きく561と互いに素な任意の数 $${ a }$$ に対して、 $${ a^{560} }$$ は1を模倣561で割った余りとして与えられます。
カーマイケル数の特性
すべてのカーマイケル数は奇数です。
カーマイケル数は3つ以上の異なる素因数を持つものが多いですが、例外も存在します。
カーマイケル数は無限に存在します。
なぜカーマイケル数は重要か？
カーマイケル数は、フェルマーテストのような確率的な素数判定アルゴリズムの限界を示すものとして重要です。カーマイケル数は合成数であるにも関わらず、フェルマーテストによって「おそらく素数」と判定される可能性があるため、フェルマーテストだけを信頼して素数判定を行うのはリスクが伴います。そのため、実際の応用においては、他の素数判定手法と組み合わせることが多いです。
ミラー–ラビン素数判定法
ミラー–ラビン素数判定法は、フェルマーテストを強化した確率的素数判定法の一つです。大きな数が素数であるかどうかを効率的に判定するためのものです。確率的というのは、ある確率で誤った結果を返す可能性があるという意味です。しかし、テストを繰り返すことでその確率を非常に低くすることができます。
def miller_rabin_test(n, k=5):
if n <= 1:
return False
if n == 2:
return True
if n % 2 == 0:
return False
r, s = 0, n - 1
while s % 2 == 0:
r += 1
s //= 2
for _ in range(k):
a = random.randint(2, n - 1)
x = pow(a, s, n)
if x == 1 or x == n - 1:
continue
for _ in range(r - 1):
x = pow(x, 2, n)
if x == n - 1:
break
else:
return False
return True
def primes_up_to_limit(limit):
primes = []
for i in range(2, limit + 1):
if miller_rabin_test(i):
primes.append(i)
return primes
# 使用例
result = primes_up_to_limit(100)
print(result)基本的なアイディア
ミラー–ラビンテストの基本的なアイディアは、次の性質に基づいています：
もし数 $${ n }$$ が素数でなく、ある数 $${ a }$$ が $${ n }$$ の証人である（すなわち、$${ n }$$ が合成数であることを示す証拠となる数）場合、以下のいずれかが成立します：
$${ a^{d} \not\equiv 1 \mod n }$$ および
$${ a^{2^r d} \not\equiv -1 \mod n }$$ すべての $${ 0 \leq r < s }$$
ここで、$${ n-1 = 2^s d }$$ という形になるように $${ s }$$ および $${ d }$$ を選びます（$${ d }$$ は奇数）。
アルゴリズムの手順
与えられた数 $${ n }$$ が偶数であるか、あるいは特定の小さな素数のいずれかで割り切れるかを確認します。もし該当するなら、$${ n }$$ は合成数です。
$${ n-1 = 2^s d }$$ の形に分解します。
指定された回数だけ以下の手順を繰り返します：
a. 2以上 $${ n-2 }$$ 以下の範囲からランダムに基数 $${ a }$$ を選びます。
b. $${ x = a^d \mod n }$$ を計算します。
c. もし $${ x = 1 }$$ または $${ x = n-1 }$$ であれば、次の基数を試します。
d. $${ s-1 }$$ 回以下のステップで、$${ x = (x^2) \mod n }$$ を計算します。もし結果が $${ n-1 }$$ になれば、次の基数を試します。
e. 上記の手順を経ても $${ x = n-1 }$$ にならなければ、$${ n }$$ は合成数であると判定されます。
注意点
ミラー–ラビン素数判定法は、与えられた数が合成数であることを正確に判定できますが、それが素数であることは「高確率で」しか判定できません。しかし、テストを多くの異なる基数 $${ a }$$ で繰り返すことで、誤判定の確率を非常に小さくすることができます。
ミラー–ラビンテストは特に大きな数に対する素数判定に効率的であり、多くの数値計算ライブラリや暗号関連のアプリケーションで使用されています。
AKS素数判定法
実装できんかった。調査中。
アトキンの篩
ChatGPT君が普通に実装してくれたが何やってんのかよくわかんない。
def sieve_of_atkin(limit):
P = [2,3]
sieve=[False]*(limit+1)
for x in range(1,int(limit**0.5)+1):
for y in range(1,int(limit**0.5)+1):
n = 4*x**2 + y**2
if n<=limit and (n%12==1 or n%12==5) : sieve[n] = not sieve[n]
n = 3*x**2+y**2
if n<= limit and n%12==7 : sieve[n] = not sieve[n]
n = 3*x**2 - y**2
if x>y and n<=limit and n%12==11 : sieve[n] = not sieve[n]
for x in range(5,int(limit**0.5)):
if sieve[x]:
for y in range(x**2,limit+1,x**2):
sieve[y] = False
for p in range(5,limit):
if sieve[p] : P.append(p)
return P
# 上限を指定して素数を列挙
print(sieve_of_atkin(100))
アトキンの篩（またはアトキンソンの篩）は、素数を効率的に列挙するためのアルゴリズムの1つで、2003年に A. O. L. Atkin と Daniel J. Bernstein によって提案されました。エラトステネスの篩よりも高速であるとされていますが、実装がやや複雑です。
アトキンの篩の基本的なアイディアは、数学的な性質を利用して、素数の候補を事前に絞り込むことです。具体的には、以下の3つの二次方程式を利用して、数nが素数である可能性があるかどうかを判定します。
$${4x^2 + y^2 = n}$$
nが12で割って1余るか5余る場合に解が存在する。
$${3x^2 + y^2 = n}$$
nが12で割って7余る場合に解が存在する。
$${3x^2 - y^2 = n}$$（ただし、x > y）
nが12で割って11余る場合に解が存在する。
アトキンの篩のアルゴリズムの手順：
リストを作成し、すべての項目を「合成数」とマークする。
上記の3つの方程式を使用して、制限値 $${\sqrt{n}}$$ までのすべての解を見つけ、nの値でリストの項目を切り替える（すなわち、素数候補とマークされている場合は合成数としてマークし、逆も同様）。
この手順を終了すると、リスト内の数の素数である可能性がある項目だけが「素数候補」としてマークされています。
5以下の素数（2, 3, 5）は手動でリストに追加する。
最後に、リスト内のすべての「素数候補」としてマークされている数に対して、それが実際に素数であるかどうかを確認する。これは、それぞれの「素数候補」の平方根以下のすべての数で割り切れないことを確認することで行われます。
アトキンの篩は、エラトステネスの篩に比べて一般的には高速ですが、実装が難しいという欠点があります。実際の応用においては、最適なアルゴリズムを選択するために、必要な条件や状況を考慮することが重要です。
この記事が気に入ったらサポートをしてみませんか？