Upgrade to Pro
— share decks privately, control downloads, hide ads and more …
Speaker Deck
Sign up for free
Menu
Search
Features
All features
Private URLs
Password Protection
Custom URLS
Scheduled publishing
Remove Branding
Restrict embedding
Deck Collections
Notes
Features
All features
Private URLs
Password Protection
Custom URLS
Scheduled publishing
Remove Branding
Restrict embedding
Deck Collections
Notes
Explore
Featured decks
Featured speakers
Programming
Technology
Storyboards
Explore
Featured decks
Featured speakers
Programming
Technology
Storyboards
Pricing
Search
Sign in
Sign up for free
拡張ユークリッドの互除法の紹介
Search
Sponsored
·
SiteGround - Reliable hosting with speed, security, and support you can count on.
→
matumoto
December 17, 2022
Technology
410
0
Share
Embed
Copy iframe code
Copy JS code
Copy link
Start on current slide
拡張ユークリッドの互除法の紹介
2022/12月に行われた部内LTでの発表資料です
イベントページはこちら
https://zli.connpass.com/event/268175/
matumoto
December 17, 2022
Transcript
26 slides
拡張ユークリッドの互除法の 紹介 matumoto
• 学年:28期 • 所属:会津大学コンピュータ理工学部 • 今興味のある技術:vanilla-extract • 趣味: ◦ 競プロ,
Go, React,... ◦ ゲームしたり漫画読んだり ◦ Splatoon3にはまってます • Twitter:@matumoto_1234 matumoto 松本 響輝 自己紹介
拡張ユークリッドの互除法?
拡張ユークリッドの互除法って? • ユークリッドの互除法を拡張したやつ • なんかいろんなとこで出てくる ◦ extgcdとかって名前見たことない? ◦ mod 上での逆元を求めるとかもできる
• じゃあ、そもそもユークリッドの互除法って?
ユークリッドの互助法って? • ユークリッドの互除法(ユークリッドのごじょほう、 英: Euclidean Algorithm)は、2 つの自然数の最大公約数を求める手法の一つであ る。 (ユークリッドの互除法 -
Wikipedia より) • 2つの自然数a,bの最大公約数dを求める感じ • gcd(a, b) = d みたいな感じの関数はだいたいユークリッドの互除法が使われている ◦ gcd は greatest common devisor の略
ユークリッドの互助法って? • 実装はかなり簡単
ユークリッドの互助法って? • なにをしているのか? • 2 つの自然数 a, b (a ≧
b) について、a の b による剰余を r とすると、 a と b との最大公約数は b と r と の最大公約数に等しいという性質がある • それを利用して求めている • ※証明は省略
ユークリッドの互助法って? • 計算量は? • r = aをbで割ったあまり(a%b)とする 実は、r <= a/2
が成り立つ • よって、大雑把に見積もると およそ O(log max(a, b)) 回程度
改めて、拡張ユークリッドの互助法って? • じゃあ、改めて拡張ユークリッドの互助法はなにができるの? ax + by = gcd(a,b) なる(x,y)の組を求めることができる a,
b := 定数 gcd(a,b) := aとbの最大公約数 • 具体例 ◦ 111x+30y=3 なる(x,y)の組を求めよ ◦ 111x+30y=12 なる(x,y)の組を求めよ ▪ これも工夫すれば求められる
拡張ユークリッドの互助法の実装 • コードとしての結論から
拡張ユークリッドの互助法の実装 • なにをしているのか? • 基本的には、式変形をそのままコードにしてる • ここで注目なのが、extgcd(b, a%b, y, x)
(a, b) → (b, a%b) に変化している!!!! • (a,b)の遷移だったり計算量だったりは一緒
拡張ユークリッドの互助法の理論 • a = qb + r とおく。※ q =
floor(a/b), r = a%b ax + by = gcd(a,b) を式に代入すると、 (qb + r)x + by = gcd(a,b) qbx + rx + by = gcd(a,b) (qx + y)b +rx = gcd(a,b) となる。
拡張ユークリッドの互助法の理論 • 得られた式:(qx + y)b +rx = gcd(a,b) s=qx +
y t=x とおくと、 bs + rt = gcd(a,b) と表せる。 • ax + by = gcd(a,b) →bs + rt = gcd(a,b) になってる!(そうなるように変形した) ◦ (a, b) → (b, r) r = a % bなので、 (a, b) →(b, a%b)
拡張ユークリッドの互助法の理論 • あとは、(s, t) →(x, y) を求められればOK ◦ ax +
by = gcd(a,b)という問題が bs + rt = gcd(a,b) という小問題になったということは、解である (s, t)が求まったとき、(x, y) を求める必要がある ◦ 最初の状態→次の状態→さらに次の状態... ◦ (x,y)を求めたい→(s, t)を求めたい→(s’, t’)を求めたい... ◦ (x,y)を求めたい→(s, t)を求めたい→(s’, t’)が求まった! ◦ (x,y)を求めたい→(s, t)を求まった!→(s’, t’)が求まった! ◦ (x,y)を求まった!→(s, t)を求まった!→(s’, t’)が求まった!
拡張ユークリッドの互助法の理論 • x=t xは求まる。(t = xとおいたので) • s=qx+y とおいたのを利用すると、 s-qx=y
y=s-qx y=s-qt より、yも求まる。
理論をコードに • ax + by = gcd(a, b) →sb +
rt = gcd(s, t)となったとき、 s = qx + y, x = t を代入すると (qx + y)b +rx = gcd(a,b) となる。
理論をコードに • b == 0 のとき、なんで x = 1, y
= 0 なの? • ax + by = gcd(a, b) に b = 0 を代入すると、 ax = gcd(a, b) gcd(a, 0) = a なので、 ax = a よって、x = 1 y は数学的にはなんでも問題ない ※y = 0 とすると、|x| + |y| が最小になるらしい
理論をコードに
応用的な使いみち(本題)
あなたは突然 mod 上での逆元を 求めたくなりました
どう求めますか?
応用的な使いみち(本題) • フェルマーの小定理で求める方法 ◦ ◦ ちょっと制約が厳しい ◦ modの法が素数じゃないといけない • 実は、拡張ユークリッドの互除法を使って逆元を求められる
◦ フェルマーの小定理よりは制約が優しい
応用的な使いみち(本題) • 逆元ってそもそもなに? a * a^-1 ≡ 1 (mod m)
となる、a^-1 のこと • これを式変形する
応用的な使いみち(本題) • a * a^-1 ≡ 1 (mod m) a
* a^-1 - 1 ≡ 0 (mod m) a * a^-1 - 1 = m * n ←m の倍数 a * a^-1 + m * n = 1 x = a^-1, y = n とおくと,,,, a * x + m * y = 1 • つまり、ax + my = 1 = gcd(a, m) なる (x, y) を求めたとき、x がaの逆元
応用的な使いみち(本題) • 拡張ユークリッドの互除法で aの逆元(mod m)を求めるときの制約 ◦ ax + my =
1 = gcd(a, m) ◦ aとm が互いに素 ▪ 最大公約数が1なので • 応用的な使いみち おしまい
ありがとうございました
More Decks by matumoto
See All by matumoto
Go標準パッケージのI/O処理をながめる
matumoto
0
550
testingを眺める
matumoto
1
230
sync/v2 プロポーザルの 背景と sync.Pool について
matumoto
0
860
Goトランザクション処理
matumoto
1
100
いまいちどスライスの 挙動を見直してみる
matumoto
0
440
Go1.22のリリース予定の機能を見る
matumoto
0
110
GoのUnderlying typeについて
matumoto
0
250
Typed-nilについて
matumoto
0
410
GoのType Setsという概念
matumoto
0
73
Other Decks in Technology
See All in Technology
個人ASを取得して、自宅Kubernetes上のVMをグローバルIPで公開した話
munenick
0
210
PHPで家庭用ゲーム機の専用コントローラーをMIDIデバイスとして扱ってみる
wind111
0
170
AIエージェントのアーキテクチャ設計
nsatoh
0
350
その修正で本当に速くなったのか? k6とOpenTelemetryで確かめる性能改善 / Performance review with k6 and OpenTelemetry
ymotongpoo
3
350
異夢同船〜異なる夢でも同じ船でなんとかする〜
fortegp05
1
560
飯から始まるデータエンジニア
sansantech
PRO
0
120
落とし穴にハマってわかった 開発生産性を測るときに気をつけたいこと
munakata
3
460
現地速報! Microsoft Ignite アップデートレポート
kasada
0
350
Kansai WordPress Meetup@大阪『ブロックテーマを作る上で知っておくべきこと
torounit
0
260
目を覚ませ!僕らの認証情報が何者かに侵略されてるぞ
tkito
2
480
さようならSSH鍵、こんにちはゼロトラスト ― AIフレンドリーで快適な自宅鯖SSH
atalie2m
14
7.3k
高品質と高スピードを支える品質のシフトレフトのアプローチ
goyoki
4
1.7k
Featured
See All Featured
Skip the Path - Find Your Career Trail
mkilby
1
290
Designing Experiences People Love
moore
143
24k
Bridging the Design Gap: How Collaborative Modelling removes blockers to flow between stakeholders and teams @FastFlow conf
baasie
0
780
Crafting Experiences
bethany
1
450
AI Search: Where Are We & What Can We Do About It?
aleyda
0
8.2k
KATA
mclloyd
PRO
35
16k
Impact Scores and Hybrid Strategies: The future of link building
tamaranovitovic
0
490
Darren the Foodie - Storyboard
khoart
PRO
5
4.1k
Java REST API Framework Comparison - PWX 2021
mraible
34
9.8k
Web Performance Is a Journey [PerfNow 2026]
tammyeverts
2
78
Site-Speed That Sticks
csswizardry
13
1.6k
DBのスキルで生き残る技術 - AI時代におけるテーブル設計の勘所
soudai
PRO
68
60k