最大公約数+拡張ユークリッド・アルゴリズム
a=b*m+r
r=0⇔(def)b|a
最大公約数gcd(a,b) or (a,b)
(a,b) == 1 ⇔ 互いに素
ユークリッド互除法
アルゴリズム
入力を m, n (m ≧ n) とする。
- n = 0 なら、 m を出力してアルゴリズムを終了する。
- n が m を割り切るなら、 n を出力してアルゴリズムを終了する。
- m を n で割った余りを新たに n とし、更に 元のnを新たにm とし 3. に戻る。
上記の手順は「n, m に対して剰余の演算を行うことができる」という仮定だけに依っているので、整数環だけではなく任意のユークリッド整域においても同様にして最大公約因子を求めることができる。
例
(問題) 1071 と 1029 の最大公約数を求める。
- 1071 を 1029 で割った余りは 42
- 1029 を 42 で割った余りは 21
- 42 を 21 で割った余りは 0
よって、最大公約数は21である。
てな説明よりも、実際に組んでみるヨロシ。
| function euclidean([int]$m, [int]$n){ |
 |
今回はPowerShellで書いてみました。
ちなみに、はじめてPowerShellでスクリプトを走らせるときにはすこおし設定が必要です。
PowerShellスクリプトの実行セキュリティ・ポリシーを変更する
やたら横になげえダイアログウインドウで肺を洗濯するとでmatu。
定理
2つの整数abに対してd=(a,b)→∃x,y|d=ax+by
このようなｘｙは一意には決まらん。
なんか経過は良く解らんが・・・
(a,b)を求めるのと同時に与式を満たすｘ，ｙも求まるんだと、
これを拡張ユークリッド・アルゴリズムという
と、よくわからんかったが、ここが分かりやすい。
>拡張ユークリッドの互除法は，不定方程式の解を与えます。例として，不定方程式
>1004*x+1001*y=1
>を解きましょう。 ここで不定方程式とは上の等式を解として整数 (x,y) を考えるものです。またこれを解くとは上の等式を満たす>整数(x, y) のすべての組を求めるものです。
---------------------------------
>拡張ユークリッドの互除法は，整数の合同における逆元を計算します。例として，合同式
>12357 * x ≡ 102 mod 100102
>を解いてみましょう。この合同式を解くとは，x を 12357 倍して，100102 で割ったときの余りが 102 となる整数 x をすべて>求めることです。
合同式とフェルマーの小定理
合同⇔def 整数a,bに対してa-bが1よりも大きい自然数ｎで割り切れるとき、abはｎを法として合同であるという
a≡b(mod n)
ex.79≡25(mod 3) ・・・ 79 ? 25 = 54 = 3*18
nを1より大きい自然数としたとき、1からｎ-1までの自然数の中でｎと互いに素である数の個数をΦ(n)と表す：オイラー関数
ex.Φ(12)・・・5,7,9,11・・・＝4
オイラーの定理
素数pに対して
n=p1^e1 * p2^e2 *・・・・* pk^ekとするちょきグーパー
Φ(n) = n(1-1/p1)(1-1/p2)・・・・(1-pk)
=p1^(e1-1) * p2^(e2-1)・・・・ * pk^(ek-1)*(p1-1)(p2-1)・・・(pk-1)
ex.60=2^2 * 3 * 5
Φ(60) = 2^(2-1) * 3^(1-1) * 5^(1-1) * (2-1)(3-1)(5-1)
=2^1*1*1 * 1*2*4 = 16
定理
1より大きい自然数nに対して、整数aとｎが互いに素であるなら
a^Φ(n) ≡ 1(mod n)
こいつを利用すると・・・
7^Φ(60) = 7^16 ≡ 1(mod 60)
フェルマーの小定理
特にnが素数の場合・・・aで割れない整数aに対して、以下の合同式が成立
a^(n-1) ≡ 1(mod n)
これが暗号となんの関係がとの説明は以下が詳しい
てかbcて言語は俺のような使い方をする人間には扱い易そうな言語だな。
導入を検討しよう。
有限体
ある演算#が定義された集合Gに対して、以下の小売を満たすとき、Gと演算#の組(G,#)を代数系という。
def
代数系が以下の3つの小売を満たすとき、(G、#)あるいは単純にGを群という
1.任意の元abc∈Gに対して(a#b)#c=a#(b#c)
2.任意の元a∈Gに対してe#a=a#e=aなる元e∈Gが存在スルー
3.任意の元a∈Gに対してx#a=a#x=eなる元x∈Gが存在する
eを単位元という。xを逆元という
群Gに対して、集合Gの元の個数をこの群の位数といい|G|で表す。
こいつが有限なら有限GUN
#が加法+のときは加法GUN、乗法*の時は乗法群
任意の元ab∈Gにたいして、交換速が成立するような群を特に可換群、アベール群(オケツ・テロテロ群)という。
ex.
複素数全体C、実数全体R、整数全体Zは通常加算演算+に対して可換群
a^m=a*a*-------*a さらにa^-m=a^-1*--------a^-1
とし、a^0=eとする。
また、a^m=eとなる最小の自然数ｍを元aの位数という。
↑フォント綺麗、てか全体的にきれいなページですぅ
￣￣￣￣￣￣￣￣￣￣V￣￣￣￣￣￣￣￣￣￣￣￣￣￣
群(G,#)において、任意の元a∈Gを用いて
G=｛g^m:m∈Z｝
で表されるときGを巡回群といいgをGの生成元という。
def
2つの演算が定義された集合Rに関して、(R,+,#)が各演算に対して代数系であり、次の4つの公理を満たすとき(R,+,#)あるいは、単にRを環という。
1.(R,+)は可換群
2.任意の元abc∈Rに対して(a#b)#c=a#(b#c)
3.任意の元abc∈Rに対してa#(b#c)=a#b+a#cおよび(b+c)#a=b#a+c#a
4.乗法に関する単位元1が存在する
乗法に関して可換
ab∈Rに対してab=baが成立するとき可換環という。
[r]={an+r:m∈Z}={b∈Z:b≡r(mod n)}
この集合[r]をｎを法にした整数の剰余類という
代表元
Zn={0,1,2-------,n-1}
を各代表元の集合とする。任意の元ab∈Znに対して、a+bをnで割ったあまりをcとし、a*bをnで割った余りをdとしたとき
a+b≡c(mod n)及び a*b≡d(mod n)
特にこの環をｎを法とする整数剰余環という。cf剰余表
なんかだるくなってきたのでココマデ
0 件のコメント:
コメントを投稿