既存のPCは計算が得意なようで除算が苦手
掛け算と違って桁数が増えると割り算は遅くなる
除算で一番簡単で分かりやすい方法は、割り算の基本理念に基づいて、割られる数から割る数を引いていき
商が1以下になるまで何回引いたかをカウントする
2進数を右にSビット論理シフトすると2-S倍すること(2Sで割ること)に相当
乗算に関してはKaratsuba法では半分の桁の掛け算を、4つではなく3つに減らすことができるので、両方の桁数の積より速く計算することが可能
(n桁×n桁の掛け算でで0(n^1.59)程度)し、3つの乗算のうち2つは並列実行
さらに桁数が増えれば、高速フーリエ変換を使ったアルゴリズムがあって、0(n log n)より少し大きいぐらいのオーダーで処理
除算の場合、PCは馬鹿なので珠算のように分けて計算するという方法が使えない
割る数の桁数に比例した処理を割られる数の桁数に比例した回数だけ繰り返すことになる
桁が決まらないと並列実行できないので除算が遅い、乗算が高速化できるから相対的に遅くなってしまう

素因数分解で割る数を小さくするというアイデアは、素因数分解の手間自体が莫大となるので高速化にはほぼ使えない