[ 新着記事
| 数学・プログラミング
| 天文・暦
| シリア語・Unicode・詩
| ジョーク
| 漫画・アニメ
| 字幕
| 哲学・ファンタジー
| 全記事
| チラ裏 ]
チラ裏
2021-10-20 Wikipedia over .onion Searx風
説明 https://codeberg.org/orenom/Wikiless
Onionインスタンスの例 http://dj2tbh2nqfxyfmvq33cjmhuw7nb6am7thzd3zsjvizeqf374fixbrxyd.onion/
一般論としては、プロキシを信用せず、普通に Tor Browser で見た方がいい（プロキシ自体がスパイかもしれないし、ウィキペディアは、閲覧に関してはもともと Tor friendly なので）。けれど .onion なら、場合によっては利用価値もあるかと。
2021-10-14 複素整数「ゴルゴ13」 565+13i
g = 565+13i はガウス整数の範囲で素数だろうか、それとも分解されるのか？
a = 123+45i と g の最大公約数は何か？ （もし 1 でないとすれば、もちろんゴルゴ13は素数でない。）
まずは準備体操として、普通の整数の範囲での「ユークリッドの互除法」を思い出そう。
【例題】 3195億7869万7969 と 6385億0876万1014 の最大公約数は何か？
【互除法＝ユークリッドのアルゴリズム】 2個の整数が与えられる。大きい方を M、小さい方を N としよう。M と N の最大公約数を求めたい。
ステップ1 M を N で割る。割り切れれば、もちろん最大公約数は N そのものだが、割り切れない場合を考える。M の方がでかいのだから、商は1以上だが、商はとりあえず無視。問題は余り。余りが r1 だったとする。
ステップ2 今度は N を割る。何で割る？ 直前のステップの余り r1 で割る。今度は余りが r2 だったとしよう。
ステップ3 r1 を r2 で割って、余りを r3 とする。
ステップ4 r2 を r3 で割って、余りを r4 とする。
ステップ5 r3 を r4 で割って、余りを r5 とする。
以下同様に、割り切れるまで（余りがゼロになるまで）続ける。ゼロでなかった最後の余りが、M と N の最大公約数。
さっそく上の例題に適用。
N = 319578697969 M = 638508761014 MをNで割る → 余り r1 = 318930063045 Nをr1で割る → 余り r2 = 648634924 r1をr2で割る → 余り r3 = 450315361 r2をr3で割る → 余り r4 = 198319563 r3をr4で割る → 余り r5 = 53676235 r4をr5で割る → 余り r6 = 37290858 r5をr6で割る → 余り r7 = 16385377 r6をr7で割る → 余り r8 = 4520104 r7をr8で割る → 余り r9 = 2825065 r8をr9で割る → 余り r10 = 1695039 r9をr10で割る → 余り r11 = 1130026 r10をr11で割る → 余り r12 = 565013 r11をr12で割る → 余り r13 = 0 割り切れた
従って、ゼロでなかった最後の余り r12 = 565013 が gcd(M,N) ということに。比較として、素因数分解を強行するなら…
M = 2 × 565013 × 565039
N = 565013 × 565613
…となって、同じ結論が得られるが、この分解を試行除算で行うと、何万回も割り算する必要がある。ユークリッドの互除法なら、たった13回の割り算で答えが出るのだから、桁違いに効率が良い。
もちろん重要なのは「なぜこのアルゴリズムでうまくいくのか」。
普通の整数の範囲での互除法の証明は、ウィキペディアなど、多くの場所で見ることができるだろう。例えばオンライン教科書『Elementary Number Theory: Primes, Congruences, and Secrets』
https://wstein.org/books/ent/ent.pdf
では、§1.1.2に当たる。同じアルゴリズムが一般の整域で通用するかどうかは、ケースバイケースで微妙だが、ガウス整数に関しては、それほど難しくない。
2021-10-13 123+45i と 678+90i の最大公約数
ピタゴラス・トリオも、フェルマーの最終定理の n=4 の場合も、ガウス整数の問題として考えるのが正道だろうし、多くの教科書に必ず出る話題だろうが、普通に群・環から始めると、結構だるい。
ここでは具体的な問題を考えてみたい。
【問題】 ガウス整数 a = 123+45i と b = 678+90i の最大公約数は何か？
これらの数を凝視すると「実部も虚部も3で割り切れる」。だから 3+3i が公約数だろうけど、それは最大だろうか？
そもそもガウス整数の大小とは…？ 素朴な発想は、a と b をそれぞれ素因数分解してみることだろう。それで共通の素因数を全部抜き出して、それらを掛け算すれば、それが最大公約数に違いない。ただし、素因数分解は易しくない。
a = −i⋅3(1+i)(13+28i)
b = −i⋅3(1+i)(8+3i)(8+5i)
もし上記の分解を事実と認めるなら、単数倍の違いを無視して、最大公約数は 3(1+i) だろうが、どうやって上記のように分解されるのか。そもそも一意分解が成り立つのか…。
普通の整数の場合もそうだが、最大公約数を知りたいだけなら、素因数分解よりユークリッドの互除法の方が、単純で、効率が良い。ガウス整数でも、同じ方法を試してみたい。
複素数の範囲で b/a = 5.0975… − i1.1332…
ガウス整数としては、b を a で割ると、割り切れずに、商が 5−i で余りが発生すると予想される。この余りを r1 とすると…
b = a(5−i) + r1 つまり r1 = b − a(5−i) = 18−12i
同様に a/r1 = 3.5769… + i4.8846… だから
a = r1(4+5i) + r2 つまり r2 = a − r1(4+5i) = −9+3i 余りが r1 より「小さく」なった。良い兆候。
次に r1/r2 = −2.2 + 0.6i だから
r1 = r2(−2+i) + r3 つまり r3 = r1 − r2(−2+i) = 3+3i 余りが r2 よりさらに「小さく」なった。
最後に r2/r3 = −1 + 2i これで余りがゼロ、割り切れた！
互除法によれば、割り切れる1個手前の余り r3 = 3+3i が a と b の最大公約数。ユークリッドのありがたみがよく分かる。素因数分解と比べると単純計算だし、厳密化も比較的簡単そうだ。まずは「最大公約数」の意味を定義して、次にガウス整数でも互除法ができることを示せばいいだろう。上記の例から「互除法を使うと、余りの絶対値がだんだん小さくなる。余りはガウス整数なので、有限の値からだんだん小さくなるとしたら、いつかはゼロになるしかない」ということが分かる。
「チラ裏」は、きちんとまとまった記事ではなく、断片的なメモです。
![2016 = (28+28+28)×[28−(28+28+28+28)/28]](/image/2016/2016-28.png)
Map の長所、splice より速い要素挿入法も紹介。 〔最終更新: 2016年4月10日〕bdi 要素と Unicode 6.3 の新しい双方向アルゴリズム (2012-12-04)dir 属性は落とし穴が多い。HTML5 の <bdi> は役立つ。近い将来、「ユーザー入力欄などの語句は、このタグで隔離」が常識になるかも。 〔最終更新: 2014年4月27日〕
fad() は濁りやすい。各種の代替手段を紹介。forum.doom9.org / videolan.org
Tor Project | Anonymity Online / 
Tor Browser
The SeaMonkey® Project
LibreWolf Browser