-
- いいね！0
おめ
@omeometo
@ut_math 特に名前とかはなさそうですがrng-hos法とかrng-hos-ome法とか呼ぼうとしてたこともありました たとえば23^-1 mod 97を計算するなら23*4=-5 5*19=-2 2*49=1より23^-1=(-1)^2*4*19*49=38とやるだけです
2012-01-09 21:45:44
コルン
@colun
@__DaLong ユークリッドの互除法に、「rng-hos-ome法」なんて名前を付けることが可能なはずがないじゃないですか。きっと何か革新的な理論なんですよ。。。たぶん。考えてみます。
2012-01-28 20:29:23
コルン
@colun
というか、rng-hos-ome法の挙動が、shinhさん経由で知って４〜５年前ぐらいから使ってるとある方法と非常に良く似た挙動をしている気がする。。。気のせいかな。。。
2012-01-28 20:41:35
大堀龍一 (Ryuichi OHORI)
@__DaLong
@colun ab = r (mod p) を ab+py = r と変形して代入を繰り返せば、正当性は明らかです。
2012-01-28 20:43:46
コルン
@colun
@__DaLong それだけだと、解が速く集束する証明は含まれていないと思うのです。正当性だけじゃなく、それがアルゴリズムとして優れているかどうかの証明が必要なのではないかと思います。（偉そうなことを言ってますが、DaLongさんが教えてくれたことを元に検証するので手一杯ですw
2012-01-28 21:21:29
コルン
@colun
速く集束するかどうかは、大量実験で裏付け……というのはもちろんアリだとは思うんですが、それだけだと、他にどう応用すれば良いかが分からない。なので、実験結果からだけではなく、論理的に速く集束することを示せることはとても重要な気がする。
2012-01-28 21:23:16
コルン
@colun
まぁ見てると、毎回残りが半分以下になっている様な気がするので、最悪でもlogNのオーダーで求まりそうな様には見えているんですけどね。だとすると、他のアルゴリズムがO(logN)以上になってるかどうかの検証等が必要になったり。。。
2012-01-28 21:25:14
jellies
@highjellies
@colun 既存手法（？）として「-を使わないで23*5=18 18*6=11 11*9=2 2*49=1（mod.97）みたいに減らしていく方法」があったらしいです。マイナスを使うことによって、毎回半分以下になることは保証されて、a^-1がO(loga)で出るように見えます
2012-01-28 21:26:48
大堀龍一 (Ryuichi OHORI)
@__DaLong
@colun 例えばループが6回かかるケースとしては 7 の mod 5039 (7!-1 is a prime) での逆元とかですね。
2012-01-28 21:27:39
jellies
@highjellies
@colun あー既存手法（？）も実はO(loga)って可能性はあるのでオーダーの意味では同じかもしれません。そこは考えてません。
2012-01-28 21:29:22
大堀龍一 (Ryuichi OHORI)
@__DaLong
@colun x0 で割って x1 余り、x1 で割って x2 余り、… xn で割ってやっと割り切れるときに n 回くらいかかるので、中国人剰余定理とかでなんとかなると思います。(余りとして負数をとらない場合)
2012-01-28 21:30:59
大堀龍一 (Ryuichi OHORI)
@__DaLong
負の剰余を許すと、n の mod p での剰余を求めるのが O(lg n) になって、ユークリッド互除法だとフィボナッチ数が最悪 = O(log[φ]p) になって、プラマイ1とか定数倍しか変わらないからオーダーは同じ。
2012-01-28 21:33:11
コルン
@colun
だめだ、、、「付いていくのがやっと」なんてのは大嘘だw 実際には取り残されてる感がたっぷりです。なので、ゆっくり考えるので、頭の良い方々はしばらく僕を放置していてください。
2012-01-28 21:35:09
jellies
@highjellies
しかし自分程度の脳内メモリではrng-hos-ome法すら途中経過を覚えていられないので、現役理Ⅲ東大生のどなたかa^-1(mod.p)（pは素数）を簡単に暗算できるメソッドを開発してくれませんかね。プレートを使ってもよい
2012-01-28 21:36:04
大堀龍一 (Ryuichi OHORI)
@__DaLong
正の剰余のみの場合だと、最悪の場合 (n, p が小さいのにループが多くかかる、って曖昧すぎ乙) が p = n!-1 で p 回だと思われるが、まだ証明できてない。にしても n だから p! の逆関数くらいで、実用上は十分と思われる。
2012-01-28 21:37:57
コルン
@colun
とりあえず、根本的な所で、2以外の素数pに対して、((p+1)*2/2)%p=1が明白であることから、(2^-1)%p = (p+1)/2が成り立つことはよく分かった。。。これを倍倍に拡張していくことから始めねば。。。（どれだけ数学遅れているんだ、僕は。
2012-01-28 21:43:30
大堀龍一 (Ryuichi OHORI)
@__DaLong
例を作るために中国人剰余定理を使って実際に計算しようとして「それにはどうやるんだっけ」と思ったら、今まさにその方法の話をしていたことに気がついたｗ
2012-01-28 21:43:52