読者です 読者をやめる 読者になる 読者になる

1の平方根(無限整数)

数学

はじめに

tailsさんの「無限整数」について考えたこと - Tails の(仮)および、そこから生まれたanagolの問題square root of 1 in mod 1e300に関するちょっとしたお話です。
なお、「コードゴルフ」の問題ではありながら、私はそっちの方では散々だったので、あくまで数学的な側面について、です。

簡単な解

 x^2 \equiv 1~mod~10^{300} の解 ( の1つ ) は、A224476 - OEISにある一般解の通り、  x \equiv \left( 2 \times 16^{\left( 5^n \right)} + \frac{10^n}{2}-1 \right)~mod~10^n に n=300 を代入することで求められます。
しかし、この計算はべき乗のべき乗を含むため、かなりの計算時間を要します。で、実は簡単な解の出し方もあり上記のマイナスの解 (  x \equiv aが解ならば x \equiv -aも解 ) は、次のように求めることができます。
 x = modinv \left( 5^{300},2^{298} \right)\times 5^{300} \times 2 - 1
modinvについては次を。

modinvについて

合同式の方程式  ax\equiv 1~mod~n があったとします。つまり、aに何かをかけて n で割った余りが 1 になるような、そんな x は求められるかと。modulo における逆数 ( inverse ) なので modinv という事で、合同式なら  x \equiv a^{-1}~mod~n と表します。
逆数が存在するのか、という問題がある訳ですが、これは gcd(a,n)=1 なら存在することが分かっています。で、modinv はユークリッドの互除法の拡張版によって高速に求めることができます。( 拡張ユークリッド互除法あたりが良いでしょうか )
なお、Perlの場合はbigintモジュールのbmodinvがこれに相当し、modinv(a,n) は、$a->bmodinv($n) や bmodinv{$a}$n などで求めることができます。

一般的なお話

冒頭のような解を求める計算がどこから出てきたのか? 一般的なお話から説明したいと思います。

素数pに対するp進法

つまり、 x^2\equiv 1~mod~p^r\left(r\geq 1\right)というケースです。
r=1 の時は話は簡単で、 x\equiv\pm 1~mod~p しか解はありません。なぜなら (x-1)(x+1)\equiv 0~mod~pで、x-1, x+1 いずれかが p の倍数であることが必要十分だからです。で、一般の r に対しても状況は同じで、 x\equiv \pm 1~mod~p^rとなります。

n=pqに対するn進法

今度は、 x^2\equiv 1~mod~n^r\left(r\geq 1,~n=pq\right)と、n が異なる2素数p,qの積であるケースに対して考えてみます。なお、2 はちょっと特殊なので除外して、p,qとも3以上とします。
さて、r=1 のケースに対して。今回も同じように、
 (x-1)(x+1)\equiv 0~mod~pq が成立し、 x\equiv\pm 1~mod~pqは解となるのですが、これだけではありません。なぜならば、x-1 が p の倍数で x+1 が q の倍数 ( あるいは逆 ) となる場合も解となるからです。ここから計算を進めてみましょう。

  •  x-1\equiv 0~mod~p,~x+1\equiv 0~mod~q
  •  \Leftrightarrow x=zq-1\left(\exists z\right),~x-1\equiv 0~mod~p
  •  \Leftrightarrow x=zq-1\left(\exists z\right),~zq\equiv 2~mod~p
  •  \Leftrightarrow x=zq-1\left(\exists z\right),~z\equiv q^{-1}\times 2~mod~p
  •  \Leftrightarrow x\equiv modinv(q,p)\times q\times 2-1~mod~pq

ここでmodinvが出てきましたね。この x\equiv modinv(q,p)\times q\times 2-1~mod~pqが、追加で出てくる解となります。
一般の r についても同様に
 x\equiv modinv(q^r,p^r)\times q^r\times 2-1~mod~(pq)^r
あるいは
 x\equiv (modinv(q,p^r)\times q)^r\times 2-1~mod~(pq)^r
です。なお、p,qをとっかえて計算すると、これの負のバージョンが出てくることになります。

ところで余談ながら、modinv(p,q)というのは他の場面でも使われる例がありまして。暗号アルゴリズムとして有名なRSA秘密鍵データは、幾つかの要素を含んでいるのですが、この中のcoefficientがそうです。RSAの公開鍵側・秘密鍵側の処理は対称にもできるのですが、秘密鍵側は公開鍵側より多くの情報を持っているので、それで高速化ができるようになっているのですね。( 詳細は探してください )

$ openssl rsa -text -noout < rsa.key
Private-Key: (1024 bit)
modulus:
…
publicExponent: 65537 (0x10001)
privateExponent:
…
prime1:
…
prime2:
…
exponent1:
…
exponent2:
…
coefficient:
    00:a8:5f:e0:87:6c:34:75:70:6c:b0:49:40:5a:08:
    68:5a:6d:9f:13:12:dd:e9:86:1c:27:3f:96:f2:1c:
    db:ce:e4:45:03:0e:11:19:a7:de:67:ab:f7:ed:6a:
    1a:5e:ba:fe:24:ac:90:b3:ce:2c:74:53:d3:38:a7:
    84:98:00:e8:51

10進法

さて。でいよいよ10進法 x^2\equiv 1~mod~10^r\left(r\geq 1\right)です。上のn進法(n=pq)のp=2,q=5のケースと同等かと思いきや、2が特殊なので少し具合が変わってきます。
具体的には、n進法(n=pq)でのxの解は±1含め4通りですが、10進法では r が十分に大きければ8通りになります。どこに違いがあるかというと、  (x-1)(x+1)\equiv 0~mod~\left(2^r\times 5^r\right) x+1\equiv 0~mod~5^rとすると、x+1が自動的にp=2の倍数となるところです ( x+1,x-1の偶奇が一致するためです )。その分、x-1 の 2の指数が1少なくて済みます。

  •  x-1\equiv 0~mod~2^{r-1},~x+1\equiv 0~mod~5^r
  •  \Leftrightarrow x=z5^r-1\left(\exists z\right),~x-1\equiv 0~mod~2^{r-1}
  •  \Leftrightarrow x=z5^r-1\left(\exists z\right),~z5^r\equiv 2~mod~2^{r-1}
  •  \Leftrightarrow x=z5^r-1\left(\exists z\right),~2w5^r\equiv 2~mod~2^{r-1}\left(\exists w:~z=2w\right)
  •  \Leftrightarrow x=2w5^r-1\left(\exists w\right),~w5^r\equiv 1~mod~2^{r-2}
  •  \Leftrightarrow x=2w5^r-1\left(\exists w\right),~w\equiv (5^r)^{-1}~mod~2^{r-2}
  •  \Leftrightarrow x\equiv modinv(5^r,2^{r-2})\times 5^r\times 2-1~mod~\frac{10^r}{2}

同じように計算してみると、2^{r-2}が現れるところ、mod~\frac{10^r}{2}~\left(mod~5^r\times2^{r-1}\right)が最後の形になるところが違ってきます。
特に後者により解の数が倍増しています。例えば r=3 の時なら、x\equiv 1,999,501,499,249,751,749,251~mod~1000と、最上位、百の位が5違いのペアができているのが分かります。( ただし無限整数とした場合、このペアの内一方は使えない、その桁数限りの解となります )
…という事で、長くなりましたが、冒頭の x = modinv \left( 5^{300},2^{298} \right)\times 5^{300} \times 2 - 1につながる訳です。ただ、最上位の違い、無限整数として適切な方を選べるかどうかは運なので、安定させるならもう1桁増やして求めてから桁を切ることになると思います。

その他の話題-開平算

開平算はご存じでしょうか…? 平方根 ( √ ) の計算を筆算で行えるものですね ( 算盤でもできたはず )。
通常の開平算のやり方は、次の図のような感じになります。 f:id:ange1:20150927213725p:plain
特徴としては次の通り。

  • 小数点を基準に2桁ずつ区切って、上位から答えの各桁を決めていく
  • 答えの各桁を決める際、左側の縦に並んだ2数の積を元の数から引いた差が最小になるように ( つまり選べる最大の数を ) 選ぶ
  • 答えの各桁を決定する毎に、積を計算した数同士加算して更新していく

実は、この無限整数の平方根も似たような開平算で求めることができます。次の図のように。 f:id:ange1:20150927214310p:plain
ただ、解は1つではありませんから、最初の2桁は何かしら選ぶ必要があります。そして、特徴は次のようになります。

  • 下位から2桁ずつ区切って、下位から答えの各桁を決めていく
  • 答えの各桁を決める際、右側の縦に並んだ2数の積を元の数から引いた差が20の倍数になるように ( つまり下位の桁が消えるように ) 選ぶ
  • 答えの各桁を決定する毎に、積を計算した数同士加算して更新していく

という事で、大小関係を見て、上の桁から抑え込んでいく通常の開平算と、積の下位の桁が合うように下の桁から詰めていく無限整数の開平算の違いで、基本的な構造は類似しているように見えます。 まあ、この類似性が何を意味するのか、は良く分かっていませんが。

おわりに

まあ良く分かっていないので、結論めいたものはないのですが…。面白いネタだと思いますので、今後何か分かれば記事にしようかと思います。