n進数とアルゴリズム Integer and Algorithms

１０進数…decimal (base 10)

２進数…binary (base 2)

８進数…octal (base 8)

１６進数…hexadecimal (base 16)

０から１５までの変換表

b: integer > 1, n: integer > 0, それぞれの進数は、次のようにして１０進数で表せる。

例：

The decimal expansion (base 10) of the integer that has  as its binary expansion is

101011111は９桁あるので最初のkはk＝9-1＝8、そして徐々に減っていき0に近づく。

その10のk乗に、それぞれの桁の数字をかける。９桁目なら1、８桁目なら0。

The decimal expansion of the number with dexadecimal expansion  is

2AE0Bは５桁なのでk＝4から始まる。

５桁目は2なので、2・10の４乗。

１６進数のそれぞれの桁は４ビットを表している（ビット…binary digitの略。１桁の２進数＝１ビット。４ビット＝４桁の２進数）。そして８ビットを１バイトといい、これが２桁の１６進数に相当する。

次に、１０進数からそれぞれの基数へ変換する場合。

１０進数の数字を基数で割っていく。そしてその余りを最後から順番に並べたものがその基数での数字になる。

例：　

To find the octal expansion of 、

Hence, 

To find the hexadecimal expansion of ,

10進数以外での基数同士の変換。

例：

Find the octal and hexadecimal expansions of  and the binary expansions of  and .

８は２の３乗なので右から３桁ずつ。１６は２の４乗なので４桁ずつ取る。

表を使うと簡単。

2進数の加法。

右端から順に足していき、係数×基数＋余りの形に直していく。

余りを最後から順に組み合わせたものが加法の答えになる。

例：

Add a = , b = .

一番右端同士の足し算は、a0＋b0＝０＋１＝０・２＋１

上記よりc0＝０、s0＝１

次の位がa1＋b1＋c0＝１＋１＋０＝１・２＋０

上記よりc1=1, s1=0

次の位がa2+b2+c1＝１＋０＋１＝１・２＋０

c2=1, s2=0

a3+b3+c2＝１＋１＋１＝１・２＋１

c3=1, s3=1→s4=c3=1

∴ s = a + b = ＝

2進数同士の掛け算。

2の累乗分だけ０を右側に付け足す。

例：

Find the product of .

Modular Exponentiation

2進数を使って大きな数の余りを求める事が出来る。

b: integer, , m: positive integers

x := 1

power := b mod m

for i := 0 to k-1

      if ai = 1 then x := (x・power) mod m

      power := (power・power) mod m

return x{x equals }

例:

Use that algorithm to find .