整数と基礎
整数
Integer
記号
ℤ意味
負の数、ゼロ、または正の数の整数。
使用場面
整数を、方向、インデックス、差、および正確な離散計算に使用します。
計算例
-4、0、および27は整数です。数学リファレンス
数論の用語集と計算ガイド
整数、素数、剰余算術、巡回群の生成元、二次剰余、ディオファントス方程式、および RSA を、公式と豊富な例を用いて検索する。
7 を法とする生成元のサイクル
3 の逐次べき乗は、1 に戻る前に、すべてのゼロでない剰余を訪れる。
7 を法とする二次剰余
ゼロでない剰余数を二乗すると、1, 2, および 4 のみが得られる。
55 件
整数と基礎
自然数
Natural number
記号
ℕ意味
整数。0を含むかどうかは、使用する規約によって異なります。
使用場面
自然数を証明、仕様、またはプログラムで使用する前に、規約を明記する。
注意
一部の書籍では、自然数を1から開始すると定義しているため、常に規約を確認してください。
計算例
This guide uses ℕ = {0, 1, 2, 3, ...}.整数と基礎
絶対値
Absolute value
記号
|a|意味
整数からゼロまでの数直線上の非負の距離。
使用場面
大きさ、距離、誤差、および対称的な範囲を表現するために使用します。
計算例
|-7| = 7 and |5 - 12| = 7.整数と基礎
偶数性
Parity
記号
n mod 2意味
整数が偶数または奇数であるという性質。
使用場面
分岐、交互パターン、証明、チェックサム、およびビットレベルのロジックにパリティを使用します。
計算例
18 mod 2 = 0, so 18 is even.整数と基礎
除算アルゴリズム
Division algorithm
記号
a = bq + r意味
整数 a と正の整数 b の場合、0 ≤ r < b を満たす一意の整数 q と r が存在します。
使用場面
商、剰余、ユークリッドのアルゴリズム、およびモジュラー演算の基礎として使用します。
計算例
29 = 6 × 4 + 5, so q = 4 and r = 5.割り算可能性
約数
Divisor
記号
d | n意味
整数dは、n = dk (kは整数) の場合、nの約数です。
使用場面
約数を使用して、因数構造、共通因数、および正確な約数可能性を分析します。
計算例
6 | 42 because 42 = 6 × 7.割り算可能性
倍数
Multiple
記号
n = dk意味
整数を別の整数で乗算した結果得られる数。
使用場面
スケジュール、共通周期、周期的なシステム、および分母の調整に倍数を適用します。
計算例
5 の倍数には、0, 5, 10, 15, および 20 が含まれます。割り算可能性
割り算可能性の判定
Divisibility test
記号
n mod d = 0意味
整数が別の整数を割り切るかどうかを判断する規則。ただし、長除法を完了させる必要はありません。
使用場面
簡単なチェック、暗算、入力検証、および位取り構造の教育に使用します。
計算例
7,452 is divisible by 3 because 7 + 4 + 5 + 2 = 18.割り算可能性
最大公約数
Greatest common divisor
記号
gcd(a, b)意味
2つの整数を割り切る最大の正の整数。
使用場面
分数を簡略化し、共素性をテストし、合同式を解き、比率を計算するために使用します。
計算例
gcd(84, 30) = 6.割り算可能性
最小公倍数
Least common multiple
記号
lcm(a, b)意味
2つのゼロでない整数の公倍数である最小の正の整数。
使用場面
サイクルを同期させ、分数を組み合わせ、および繰り返しのスケジュールを計算するために使用します。
計算例
lcm(12, 18) = 36.割り算可能性
GCD-LCM の関係
GCD-LCM identity
記号
gcd(a,b)lcm(a,b)=|ab|意味
2つのゼロでない整数の最大公約数と最小公倍数を結びつける関係。
使用場面
他の量がすでにわかっている場合に、ある量を効率的に計算するために使用します。
計算例
gcd(12,18)=6, so lcm(12,18)=|12×18|/6=36.割り算可能性
ユークリッドの互除法
Euclidean algorithm
記号
gcd(a,b)=gcd(b,a mod b)意味
最大公約数を求めるための、剰余演算を繰り返すアルゴリズム。
使用場面
入力整数が大きい場合でも、高速なGCD計算に使用します。
計算例
gcd(252,105) = gcd(105,42) = gcd(42,21) = 21.割り算可能性
拡張ユークリッドの互除法
Extended Euclidean algorithm
記号
ax + by = gcd(a,b)意味
ユークリッドのアルゴリズムを拡張し、ベズー係数xとyも求めるアルゴリズム。
使用場面
モジュラー逆数を計算し、線形ディオファントス方程式を解くために使用します。
計算例
35×(-1) + 12×3 = 1なので、-1は35の係数です。割り算可能性
互いに素な整数
Coprime integers
記号
gcd(a,b)=1意味
2つの整数の最大公約数が1の場合、それらは互いに素です。
使用場面
互素性を使用して、n を法とする可逆性を判断し、オイラーの定理を適用します。
計算例
8と15は、どちらの数も素数ではありませんが、互いに素です。素数と因数分解
素数
Prime number
記号
p意味
1より大きく、正の約数が1とそれ自身のみである整数。
使用場面
素数を、整数因数分解と公開鍵暗号の基本的な構成要素として使用します。
計算例
2、3、5、7、および11は素数です。素数と因数分解
合成数
Composite number
記号
n = ab意味
1より大きく、1とそれ自身以外の正の約数を持つ整数。
使用場面
因数分解可能な整数と素数を区別するために使用します。
計算例
21 is composite because 21 = 3 × 7.素数と因数分解
素因数分解
Prime factorization
記号
n=∏pᵢ^aᵢ意味
整数を素数のべき乗の積として表現する。
使用場面
約数、GCD、LCM、および算術関数を計算するために使用します。
計算例
360 = 2^3 × 3^2 × 5.素数と因数分解
算術の基本定理
Fundamental theorem of arithmetic
記号
n=∏pᵢ^aᵢ意味
1 より大きいすべての整数は、素因数分解が可能であり、その順序を除いては一意です。
使用場面
素数指数に基づくアルゴリズムと証明を正当化するために使用します。
計算例
72 = 2^3 × 3^2 は、72の素因数分解の一意な表現です。素数と因数分解
エラトステネスのふるい
Sieve of Eratosthenes
意味
発見された各素数の倍数を繰り返しマークすることで、ある上限までの素数を列挙するアルゴリズム。
使用場面
多くの素数クエリが同じ適度な上限を共有する場合に使用します。
計算例
30までの素数を見つけるには、2、3、および5の倍数をマークします。素数と因数分解
素数判定
Primality test
意味
与えられた整数が素数であるかどうかを判断するアルゴリズム。
使用場面
小さな入力には試行除法を使用し、大きな入力にはミラー・ラビンなどの確率的テストを使用します。
注意
素数判定テストは、意図する整数の範囲に応じて、複数のラウンドまたは決定的な基本集合を必要とする場合があります。
計算例
試行錯誤法では、候補の約数は√nまでで十分です。剰余算術
合同
Congruence
記号
a ≡ b (mod n)意味
2つの整数が、その差が n で割り切れる場合、合同です。
使用場面
周期的な計算において、整数を同値な剰余で置き換えるために使用します。
計算例
29 ≡ 5 (mod 12) となるのは、12が29 - 5を割りきれるためです。剰余算術
剰余類
Residue class
記号
[a]ₙ意味
整数 n を法とする固定された整数に合同なすべての整数の集合。
使用場面
モジュラー値を、孤立した数ではなく、同値クラスとして扱うために使用します。
計算例
[2]₅ = {..., -8, -3, 2, 7, 12, ...}.剰余算術
剰余演算
Modulo operation
記号
a mod n意味
割り算を行った後の剰余値を返す操作。
使用場面
インデックスのラップ、クロック、ハッシュバケット、および周期的な状態に使用します。
計算例
(23 + 5) mod 24 = 4.剰余算術
剰余算術
Modular arithmetic
記号
ℤ/nℤ意味
剰余類に対して演算を行い、結果をnで割った余りに還元する演算。
使用場面
暗号、符号理論、循環バッファ、および暦計算に使用します。
計算例
(17 × 19) mod 12 = 11.剰余算術
剰余逆元
Modular inverse
記号
a⁻¹ mod n意味
ax ≡ 1 (mod n) を満たす値 x。gcd(a,n)=1 の場合にのみ存在します。
使用場面
モジュラー演算における除算、合同式の解法、および暗号アルゴリズムの実装に使用します。
注意
剰余除算を行う前に、除数が法と互いに素であることを確認してください。
計算例
3⁻¹ mod 7 = 5 because 3 × 5 ≡ 1 (mod 7).剰余算術
剰余べき乗
Modular exponentiation
記号
a^k mod n意味
潜在的に非常に大きな完全なべき乗を構築せずに、nを法とするべき乗を計算する。
使用場面
暗号、素数判定、および大きな指数の問題に、二乗剰余法を適用します。
計算例
3^13 mod 7 = 3 using repeated squaring.剰余算術
線形合同式
Linear congruence
記号
ax ≡ b (mod n)意味
整数xが、線形合同方程式を満たすかどうかを問う合同式。
使用場面
GCDの条件とモジュラー逆数を使用して、解を決定および計算します。
計算例
3x ≡ 4 (mod 7) は、x ≡ 6 (mod 7) を与えます。剰余算術
中国剰余定理
Chinese remainder theorem
記号
x ≡ aᵢ (mod nᵢ)意味
互いに素な法を持つ場合、合同式を組み合わせることで、一意の解を法積で得ることができる定理。
使用場面
独立した周期的な制約を組み合わせ、大きな整数の計算を高速化するために使用します。
計算例
x ≡ 2 (mod 3), x ≡ 3 (mod 5) は、x ≡ 8 (mod 15) を与えます。剰余算術
オイラーの総和関数
Euler's totient function
記号
φ(n)意味
1からnまでの整数の中で、nと互いに素な整数の数。
使用場面
オイラーの定理、RSA鍵の計算、および既約剰余系に使用します。
計算例
φ(12) = 4 なのは、1, 5, 7, および 11 が 12 と互いに素だからです。剰余算術
オイラーの定理
Euler's theorem
記号
a^φ(n) ≡ 1 (mod n)意味
a と n が互いに素である場合、a を φ(n) で累乗すると、1 (mod n) になります。
使用場面
指数を減らし、モジュラー恒等式を証明し、RSAを説明するために使用します。
計算例
gcd(3,10)=1 and φ(10)=4, so 3^4 ≡ 1 (mod 10).剰余算術
フェルマーの小定理
Fermat's little theorem
記号
a^(p-1) ≡ 1 (mod p)意味
素数 p であり、a が p で割り切れない場合、a^(p-1) は 1 ≡ a (mod p) となります。
使用場面
素数法によるモジュラー逆数、および素数判定に使用します。
注意
フェルマーのテストに合格しても、それが素数であることを証明するわけではありません。疑似素数が存在するためです。
計算例
2^6 ≡ 1 (mod 7).巡回群と生成元
群
Group
記号
(G, *)意味
結合法則を満たす演算、単位元、およびすべての要素に対する逆元を持つ集合。
使用場面
演算を合成および逆演算できる算術構造を記述するために、群を使用します。
計算例
整数は、0 を単位元とし、a に対して -a を逆元とする加法演算によって群を形成します。巡回群と生成元
アーベル群
Abelian group
記号
a*b=b*a意味
演算が可換である群。
使用場面
剰余加算、ベクトル加算、および演算の順序が重要でない多くの算術群に使用します。
計算例
(ℤ/nℤ, +) は、アーベル群である。巡回群と生成元
n を法とする加法群
Additive group modulo n
記号
(ℤ/nℤ, +)意味
n を法とする剰余類。加算は n を法とする剰余演算で行われます。
使用場面
巡回カウンタ、周期状態、および加法演算による合同類をモデル化するために使用します。
計算例
In ℤ/5ℤ, 3+4=2.巡回群と生成元
単位群
Multiplicative group of units
記号
(ℤ/nℤ)×意味
n と互いに素な剰余類。乗算は n を法とする剰余演算です。
使用場面
剰余逆元、原始根、オイラーの定理、および公開鍵暗号を研究するために使用します。
計算例
(ℤ/8ℤ)×={1,3,5,7}.巡回群と生成元
巡回群
Cyclic group
記号
G=⟨g⟩意味
すべての要素が、ある 1 つの要素のべき乗または繰り返し和である群。
使用場面
群演算を、指数または整数の乗数に対する演算に減らすために使用します。
計算例
加法群 ℤ/6ℤ は、1 と 5 によって生成されます。巡回群と生成元
生成元
Generator
記号
⟨g⟩=G意味
繰り返し群演算によって、巡回群のすべての要素を生成する要素。
使用場面
巡回群を列挙し、指数ベースの暗号操作を定義するために使用します。
注意
要素が、ある構造を生成する可能性があるが、別の構造を生成しない可能性があるため、常に群と演算を明示的に記述する。
計算例
3 のべき乗は、7 を法とする剰余において、3, 2, 6, 4, 5, 1 となり、3 は (ℤ/7ℤ)× の生成元である。巡回群と生成元
元の位
Order of an element
記号
ord(g)意味
g^k が単位元となる最小の正の整数 k。
使用場面
要素が生成元であるかどうかをテストし、サイクル長を決定するために使用します。
計算例
7 を法とする剰余において、ord(2)=3 となるのは、2^3≡1 であり、それより小さい正の指数では成り立たないから。巡回群と生成元
原始元
Primitive root
記号
ordₙ(g)=φ(n)意味
n を法とする乗法群の生成元。
使用場面
原始根を使用して、ゼロでない剰余をべき乗として表現し、離散対数を定義します。
計算例
3 は、その位数が φ(7)=6 であるため、7 を法とする原始根である。巡回群と生成元
原始元の存在
Primitive root existence
意味
原始元は、n = 1, 2, 4, p^k、または 2p^k の場合にのみ存在する (p は奇素数)。
使用場面
複合数の法に対する原始根を検索する前に、この基準を使用してください。
計算例
8 は必要な形式を持たないため、原始根は 8 を法とするものはありません。巡回群と生成元
離散対数
Discrete logarithm
記号
g^x=h意味
生成元 g と群の要素 h が与えられた場合、離散対数は、g^x=h を満たす指数 x を求める問題。
使用場面
Diffie-Hellman、ElGamal、および楕円曲線暗号のセキュリティ仮定を理解するために使用します。
注意
離散対数は、小さいグループや適切に選択されていないグループでは簡単に計算できますが、適切なパラメータ下でのみ困難です。
計算例
生成元 3 を持つ 7 を法とする剰余において、log₃(5)=5 となるのは、3^5≡5 だから。巡回群と生成元
カーマイケル関数
Carmichael function
記号
λ(n)意味
a^m ≡ 1 (mod n) がすべての a (n と互いに素) に対して成り立つ、最小の正の指数 m。
使用場面
剰余べき乗および RSA 解析のための、普遍的な指数 φ(n) よりもタイトなものを取得するために使用します。
計算例
λ(8)=2 なぜなら、すべての奇数 a は a²≡1 (mod 8) を満たすからです。二次剰余
二次剰余
Quadratic residue
記号
x²≡a (mod n)意味
x²≡a modulo n が解を持つ剰余 a。
使用場面
剰余平方根、素数判定、および二次剰余暗号を分析するために使用します。
計算例
2 は、3²≡2 であるため、7 を法とする二次剰余である。二次剰余
二次剰余ではない数
Quadratic nonresidue
意味
x²≡a modulo n が解を持たない、ゼロでない剰余。
使用場面
剰余を分類し、既知の二次特性を持つテストまたは暗号パラメータを構築するために使用します。
計算例
3 は、7 を法とする二次非剰余である。二次剰余
剰余に関する平方根
Modular square root
記号
x=√a mod n意味
x²≡a modulo n の解である x。
使用場面
点の非圧縮、数論アルゴリズム、および剰余ベースの暗号に使用します。
計算例
7 を法とする 2 の平方根は、3 と 4 です。二次剰余
ルジャンドル記号
Legendre symbol
記号
(a/p)意味
奇素数 p の場合、p による可分性または p を法とする二次剰余の状態を示す 0、1、または -1 の値。
使用場面
二次特性をテストし、オイラーの基準と二次剰余を簡潔に記述するために使用します。
計算例
(2/7)=1 となるのは、2 が 7 を法とする二次剰余であるため。二次剰余
ヤコビ記号
Jacobi symbol
記号
(a/n)意味
正の奇数の合成数に対する分母に対するルジャンドル記号の乗法的な拡張。
使用場面
効率的な特性計算および、n を最初に素因数分解する必要のないアルゴリズムに使用します。
注意
ヤコビ記号が 1 であっても、a が合成数 n を法とする二次剰余であることを保証するものではない。
計算例
(5/21)=(5/3)(5/7)=1.二次剰余
オイラーの判定法
Euler's criterion
記号
a^((p-1)/2)≡(a/p) (mod p)意味
奇素数に対する二次剰余の状態を、合同累乗を用いて判定する基準。
使用場面
すべての平方数を列挙せずに、ルジャンドル記号を計算するために使用します。
計算例
p=7 の場合、3^3≡-1 (mod 7) なので、3 は二次剰余ではない。二次剰余
二次剰余の相互法則
Quadratic reciprocity
記号
(p/q)(q/p)=(-1)^((p-1)(q-1)/4)意味
1 つの奇素数が、別の奇素数に対する二次剰余であるかどうかに関する定理。
使用場面
大きなルジャンドル記号計算を、より小さなものに減らすために使用します。
計算例
3 と 11 はどちらも 4 を法とする 3 であるため、(3/11)=-(11/3)。二次剰余
補足法則
Supplementary laws
記号
(-1/p), (2/p)意味
奇素数法における -1 および 2 の二次特性を決定する公式。
使用場面
これらを、二次剰余を使用して、ルジャンドル記号の計算を完了します。
計算例
(2/p)=1 は、p≡1 または 7 (mod 8) のとき、-1 は、p≡3 または 5 (mod 8) のときに成り立つ。二次剰余
Tonelli-Shanks アルゴリズム
Tonelli-Shanks algorithm
意味
奇素数に対する二次剰余の平方根を見つけるためのアルゴリズム。
使用場面
法が素数であり、単純な p≡3 (mod 4) のショートカットが適用されない場合に、これを使用してください。
計算例
p=13 の場合、Tonelli-Shanks 法は、x²≡10 (mod 13) を満たす x = 6 または 7 を見つける。二次剰余
複合数を法とする平方根
Square roots modulo a composite
意味
素数べき乗因子に関する剰余平方根を見つけ、中国剰余定理と組み合わせる。
使用場面
Rabin 型システムおよび合成剰余を持つ合同式を分析するために使用します。
注意
異なる奇素数の積の場合、1 つの剰余は複数の平方根を持つ可能性があるため、意図した平方根を選択するには追加の情報が必要である。
計算例
x²≡1 を 3 と 5 で解き、次に 15 を法とする符号の選択を組み合わせる。整数方程式
ディオファントス方程式
Diophantine equation
意味
整数解のみを求める方程式。
使用場面
約数、GCD、合同、および境界を使用して、整数解が存在するかどうかを判断します。
計算例
3x + 5y = 17 has the integer solution x = 4, y = 1.整数方程式
線形ディオファントス方程式
Linear Diophantine equation
記号
ax + by = c意味
未知数が整数でなければならない線形方程式。解が存在するのは、gcd(a,b) が c を割り切る場合のみです。
使用場面
正確な割り当て、コイン問題、スケジュール、および格子制約に使用します。
計算例
6x + 9y = 30 は、gcd(6,9)=3 が 30 を割り切るため、解を持つ可能性があります。応用
RSA暗号
RSA arithmetic
記号
c ≡ m^e (mod n)意味
べき乗剰余を利用した公開鍵暗号方式。大きな素数の積を素因数分解することの困難性に基づいています。
使用場面
数論が暗号化とデジタル署名をどのようにサポートするかを理解するために使用します。
注意
試験用の値は学習用であり、実際のRSAには、標準化されたパディング、安全な鍵サイズ、および監査済みのライブラリが必要です。
計算例
例として、n=55、e=3、およびm=7の場合、c=7^3 mod 55=13 となります。