問題（１）の解説と同様に加法的秘密分散法を用います。
もし加法的秘密分散法を知らない方は先に問題（１）の解説をご覧ください。
また、ここでは整数 $n$ を Share $n^{(1)}, n^{(2)}$ に分割する際は必ず $n^{(1)}, n^{(2)}$ が整数であるように分割するとします。
まず, 本問題は以下の LTZ アルゴリズムがあれば解けることを示します。
ある自然数 $k$ について $|x|<2^{k}$ を満たす整数 $x$ に対して、人 1,2 がそれぞれ Share $x^{(1)}, x^{(2)}$ を持っているときに $x< 0$ が成り立つかどうかを求めるアルゴリズム。
ただしこのアルゴリズムにおいて、 $x< 0$ か否かを人 1,2 が知ることを除き、 $x$ についての情報は一切漏れない。
太郎くんと花子さんは問題（１）と同様にそれぞれ $a,b$ の Share を作成し、互いに配布します。
この時、太郎くんと花子さんはそれぞれ $a^{(1)} - b^{(1)}$ と $a^{(2)} - b^{(2)}$ を求めることが出来ます。
これは $a-b$ の Share であるため、 $k=100$ として LTZ を適用することで $a-b < 0$、すなわち $a< b$ であるか否かを求めることが出来ます。
同様に二人は $b-a$ の Share を求めることで $b< a$ であるか否かも求めることが出来ます。
以上の結果から、 $a,b$ の大小関係を求めることが出来ました。
以下では LTZ を解説します。
まず LTZ は以下の RS アルゴリズムがあれば解けることを示します。