mod p の逆元

jellies @highjellies

マイナスを使わないと反復回数どのくらいかの評価を考えるのサボったら　@__DaLong　さんがやってくれているっぽい。ありがとうございます

大堀龍一 (Ryuichi OHORI) @__DaLong

@highjellies もっと良い例がないことは証明していないのでなんとかしましょう or してください。

コルン @colun

@__DaLong あ、すみません。後で読み返した時に「２以上の」に見えたので、「２以上の素数って、素数全部やん」っていう自己突っ込みが入ったのですが。。。「２以上」じゃなく「２以外」って、ちゃんと書けていたんですね。

大堀龍一 (Ryuichi OHORI) @__DaLong

@colun 3で成り立つことを確かめたあとに2でも成り立つかどうかを一瞬だけ考えましたが、2だとダメですね。標数2はこれだから面白い。

jellies @highjellies

とりあえずいちおう本人にも話題を投げておこう　@omeometo　a^-1(mod.p)（pは素数）「-を使わないで23*5=18 18*6=11 11*9=2 2*49=1みたいに減らしていく方法」の減らしていく回数のオーダーってどう評価できますかね

コルン @colun

3以上の素数pに対して、nが2の倍数である場合は、((p+1)*(n/2))%p=n/2が成り立つことも、明白。nが2の倍数じゃない場合に、どうなるか、、、かなぁ。

コルン @colun

@colun ……っと、なんか全然違う方向に証明を持っていってた。そこ、証明する所、違うやん。

コルン @colun

証明はできてないけど、なんとなくは分かって来た。。。＞rng-hos-ome法

大堀龍一 (Ryuichi OHORI) @__DaLong

【急募】正整数 p 自然数の狭義減少列 x[0..n] であって ∀i ∈ [0..n) に対し p を x[i] で割ると x[i+1] 余る例であって p < 2^31 のうち n が最大となる例

コルン @colun

https://t.co/5y7Ah3c4 とりあえず、ようやくここまで追いつけました。 RT @highjellies: @colun 毎回半分以下になることの証明は、毎回aを2つに分けて小さい方をとっていることより。

jellies @highjellies

実験結果からマイナスを使わずともO(log p)説が有力

コルン @colun

@highjellies マイナスを使わない場合は、どういう迂回をするんですか？　迂回結果が循環しないことは、素数pが「素数である＝合成数じゃない」ことから証明できそうではあるんですが、、、無駄すぎる迂回をしないことをどうやって証明すれば良いんでしょうかね。

jellies @highjellies

@colun 「迂回」というのはどういうことですか？

大堀龍一 (Ryuichi OHORI) @__DaLong

@colun @highjellies 迂回とは何を指しているのでしょうか。絶対値が減少列であることは、剰余の定義から明らかです。

コルン @colun

@__DaLong @highjellies すみません、なんか勘違いしていました。そうですね。マイナスじゃなくても平均的にO(logN)になりそうです。

大堀龍一 (Ryuichi OHORI) @__DaLong

@highjellies log n でなく log p に比例した時間がかかるケースってありますか? (正のみと負を許すのとどちらの場合についてのことかわかりませんが、私の例は p = n!-1 に対して O(n) なので、log より少しだけ良いです)

コルン @colun

@__DaLong @highjellies むしろ、平均オーダーはlogNですが、最悪オーダーはNの可能性ってないでしょうかね。

jellies @highjellies

@__DaLong　n=p-1のとき、p-1　→　p-2　→　p-4　→　p-8　→　p-16　→　……（p/2より大きいうちはこの調子で続く）　と推移するので、O(log p)はかかります

コルン @colun

@__DaLong @highjellies ああ、すみません。最悪のオーダーはmin(N, log p)っていう可能性について、DaLongさんは言及しているんですね。読解力がありませんでした。 @colun

コルン @colun

@highjellies @__DaLong でも、n=p-1のときは、logpとlognの区別がほとんどない状態ですよね。

コルン @colun

@highjellies @__DaLong ちょっと捕捉します。「p/2より大きい場合はその調子で続く」とのことですが、log(p)とlog(p/2)の差は1しかないことが証明されますので、ここは定数オーダー分の差と見なせます。 @colun

コルン @colun

@highjellies @__DaLong つまり、O(log(2N))=O(1+logN)=O(logN)ですし、O(logN+logN)=O(2logN)=O(logN)です。 @colun

コルン @colun

@highjellies @__DaLong より進めて書くなら、n→n-1→n-2→n-4→n-8→n-16→……がもしも証明されているのであれば、それはO(log(n))を証明しているのと同じです。 @colun

コルン @colun

んでまぁ、たぶん話をしてみた感触だと、最悪パターンで従来法と比べて2倍速になりそうな気がする。＞rng-hos-ome法　／／　そしておそらく平均だと、1.5倍程度の高速化なのか、もしくは1.33倍程度なのか。。。。（1.5の方には根拠があるけど、1.33の方は根拠なしw

コルン @colun

@colun ごめん。ちがう。1.5倍〜1.33倍じゃなくて、2〜4倍になりそうな気がしてきた。