はじめに

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桁増やして求めてから桁を切ることになると思います。