計算整数論

def-cnt-length の不等式を掛けると $2^{\operatorname{len}(x)+\operatorname{len}(y)-2}\le xy < 2^{\operatorname{len}(x)+\operatorname{len}(y)}$ である。$xy$ のビット長は $2^{k-1}\le xy < 2^k$ となる $k$ なので、$\operatorname{len}(x)+\operatorname{len}(y)-1\le k\le\operatorname{len}(x)+\operatorname{len}(y)$ である。$\square$

段 1（2 段で半分以下）． $r_i\le r_{i-1}/2$ なら $r_{i+1} < r_i\le r_{i-1}/2$ である。$r_i>r_{i-1}/2$ なら、$r_i\le r_{i-1} < 2r_i$ から $q_i=1$ であり、$r_{i+1}=r_{i-1}-r_i < r_{i-1}/2$ である。
段 2（回数）． 段 1 をくり返すと、$k\ge0$ について $r_{2k+1}\le b/2^k$、$k\ge1$ について $r_{2k}\le r_2/2^{k-1} < b/2^{k-1}$ である（$r_2 < r_1=b$）。$r_\lambda\ge1$ なので、$\lambda=2k+1$ なら $2^k\le b < 2^{\operatorname{len}(b)}$ から $k\le\operatorname{len}(b)-1$、すなわち $\lambda\le2\operatorname{len}(b)-1$ である。$\lambda=2k$ なら $2^{k-1} < b < 2^{\operatorname{len}(b)}$ から $k\le\operatorname{len}(b)$、すなわち $\lambda\le2\operatorname{len}(b)$ である。$\square$

$b=0$ なら $a$ を出力するだけである。$b>0$ とする。rem-cnt-basic-arithmetic により、$i$ 回目の割り算は時間 $O(\operatorname{len}(r_i)\operatorname{len}(q_i))$ で、$r_i\le b$ なので、ある定数 $C$ について手間は $C\operatorname{len}(b)\operatorname{len}(q_i)$ 以下である（$\operatorname{len}(q_i)\ge1$ なので、余りの入れ替えなどの一定の手間もここに含められる）。よって全体の手間は $C\operatorname{len}(b)\sum_{i=1}^\lambda\operatorname{len}(q_i)$ 以下である。
$r_{i+1}\ge0$ なので $r_{i-1}\ge r_iq_i$ であり、lem-cnt-length-product により
$$ \operatorname{len}(r_{i-1})\ge\operatorname{len}(r_iq_i)\ge\operatorname{len}(r_i)+\operatorname{len}(q_i)-1, $$
すなわち $\operatorname{len}(q_i)\le\operatorname{len}(r_{i-1})-\operatorname{len}(r_i)+1$ である。$i=1,\dots,\lambda$ について足すと右辺の和は打ち消し合い、
$$ \sum_{i=1}^\lambda\operatorname{len}(q_i)\le\operatorname{len}(r_0)-\operatorname{len}(r_\lambda)+\lambda\le\operatorname{len}(a)+2\operatorname{len}(b) $$
を得る（lem-cnt-euclid-steps）。$\operatorname{len}(b)\le\operatorname{len}(a)$ なので、全体の手間は $3C\operatorname{len}(a)\operatorname{len}(b)$ 以下である。$\square$

$e_j:=\lfloor e/2^j\rfloor=(b_{m-1}\cdots b_j)_2$ とおく。$e_m=0$、$e_0=e$ であり、$e_j=2e_{j+1}+b_j$ である。
主張． $j$ についての操作を終えた時点で $y\equiv a^{e_j}\pmod n$ である。
$j=m-1$ の操作の前では $y=1=a^{e_m}$ である。$j+1$ の操作のあと $y\equiv a^{e_{j+1}}$ とすると、$j$ の操作 1 で $y\equiv a^{2e_{j+1}}$ になり、操作 2 で $b_j=1$ なら $a$ が掛かって、どちらの場合も $y\equiv a^{2e_{j+1}+b_j}=a^{e_j}$ となる。合同式は積と両立し、各段で $n$ で割った余りをとっても法 $n$ の値は変わらないからである。$j=0$ で $y\equiv a^{e_0}=a^e$ で、$0\le y < n$ なので $y$ は $a^e$ を $n$ で割った余りである。
手間． 操作は $m=\operatorname{len}(e)$ 回で、各回の掛け算は 2 回以下なので、法 $n$ での掛け算は $2\operatorname{len}(e)$ 回以下である。掛ける数はどれも $n$ 未満なので、rem-cnt-basic-arithmetic により 1 回は時間 $O(\operatorname{len}(n)^2)$ である。$\square$

1 は Fermatの小定理 である。2 は、擬素数 の記事の系「擬素数にならない底の割合」の 2 から次のように従う。$a\in L_n$ なら $a\cdot a^{n-2}\equiv1\pmod n$ なので $a$ は $n$ と互いに素で、$1,\dots,n-1$ は法 $n$ で相異なるから、$\lvert L_n\rvert$ は $(\mathbb{Z}/n\mathbb{Z})^\times$ の元 $x$ で $x^{n-1}=1$ を満たすものの個数に等しい。2 の仮定は $n$ が Carmichael数 でないということなので、引いた系によりこの個数は $\varphi(n)/2$ 以下であり、$\varphi(n)\le n-1$ から $\lvert L_n\rvert\le(n-1)/2$ である。$\square$