多倍長演算における実行時間と計算量の差
数学の論文において数値実験が必要だったため，
多倍長演算をC++で実行したところ，計算量とのギャップが生じました．
その原因をコンピュータに詳しい方にアドバイスを頂きたいと思って質問させていただきました．
具体的には，n,m を同ビット として 以下の二つの演算を考えます．
演算(1) n * m
演算(2) n^2 % m (n^2は先に計算しておき，% (mod)の演算のみ)
--------------------------------------------------
■計算量評価
大雑把に(1)と(2)の計算量を比較すると
(1) lg n * lg m = (lg n)^2
(2) (2*lg n - lg m) * lg m = (lg n)^2
となるので，(1) と (2)はほぼ同じ計算量となります．
--------------------------------------------------
しかしながら，実際に計算をしてみると，
n,m が 1000bit ほどまでは，ほぼ同じ計算時間なのですが，
2000bit, 4000bit ,..., と数を大きくしていくと，大きくしただけ (2) の速度が遅くなります．
具体的な実験結果は画像で添付いたします．
画像 (http://puu.sh/6iBQf.png)
(1) と (2)の実行時間のギャップは何処から生じたものなのか，何かわかるかたがいらっしゃいましたら教えていただけたら嬉しいです．
よろしくお願い致します．
予想：
コンピュータの知識があまりないですが，自分なりの予想では，(2)のn^2という数が大きすぎるため，演算においてメモリ間とのデータのやり取りで何かのオーバーヘッドが生じているのではないかと予想していますが，確証がもてません．
![その他([技術者向] コンピューター) イメージ](https://gazo.okwave.jp/okwave/spn/images/related_qa/c205_4_thumbnail_img_sm.png)
![その他([技術者向] コンピューター) イメージ](https://gazo.okwave.jp/okwave/spn/images/related_qa/c205_2_thumbnail_img_sm.png)
