« 2011年12月 | トップページ | 2013年3月 »

2012/02/18

多倍長整数 の処理考察

CPUの演算命令で扱える範囲を超える整数の演算方法。

やはり、機械語レベルのコードを考えると、C言語で記述すると無駄なコードを吐きまくる気がしてならない。
C言語には、『キャリー付きの演算』をする命令が無いから。
加算・減算は確実にアセンブリ言語で書く方が処理速度が速くなりそう。

例えば、足し算はMASM風にかくと、これで行けると思う。

; ecx : 扱う整数のバイト数を入れて。
; edi : 整数のポインタ
; esi : 整数のポインタ
; ebx : 返値

  xor edx, edx
  clc
  .repeat
    mov eax, [edi + edx * 4]
    adc eax, [esi + edx * 4]
    mov [ebx + edx * 4], eax
    inc edx
  .untilcxz


掛け算も、ようは筆算の要領でシフトと加算で表現する。
シフトも、アセンブリ言語でキャリー付きのシフトを使うと速い。

割り算も、掛け算どうよう、筆算の要領で。
割る数をシフトして、割られる数から引き算だから。


さて、RSA暗号処理に必要な演算 を考えてみる。

続きを読む "多倍長整数 の処理考察"

| | コメント (0) | トラックバック (0)

« 2011年12月 | トップページ | 2013年3月 »