暗号理論2-1

# 初等整数論(1)
### 2.1 整除
#### Def 2.1.1 
> ある整数 $ n , a \in \mathbb{Z} $ に対して $ n = ab $ を満たすような $ b \in \mathbb{Z} $ が存在するとき, $ a $ は $ n $ を**割り切る**という. これを **$ a \  | \  n $** と書く.
このとき, $ a $ は $ n $ の**約数**であるといい, $ n $ は $ a $ の**倍数**であるという.

#### Theorem 2.1.2
以下の性質が成り立つ。
> 
- 1. $ a \  | \  b $ , $ b \  | \  c $ $\Rightarrow$ $ a \  | \  c $
- 2. $ a \  | \  b $ $\Rightarrow$ $ \forall c \in \mathbb{Z} $ , $ ac \  | \  bc $
- 3. $ c \  | \  a $ , $ c \  | \  b $ $\Rightarrow$ $ \forall d,e \in \mathbb{Z} $ ,  $ c \  | \  da + eb $
- 4. $ a \  | \  b $ , $ b \neq 0 $ $\Rightarrow$ $ |a| \leq |b| $
- 5. $ a \  | \  b $ , $ b \  | \  a $ $\Rightarrow$ $ a = b$

#### Theorem 2.1.3 (整除)
> $ a,b \in \mathbb{Z} $ , $ b > 0 $ $\Rightarrow$ $ \exists_1 \  q,r \in \mathbb{Z} 
\  s.t. \  a = qb + r , a \leq r < b $ 
これを $ a \equiv r \  (\mathrm{mod} \  b) $ と書き, $ a $ は $ b $ を**法として** $ r $ と**合同**であるという.
このとき, $ q $ を**商**といい, $ r $ を**剰余**という. 

### 2.2 整数の表現法
通常,整数は10進法で書かれるが,コンピュータ上では2進展開された形で格納している.
ここではより一般的なp進展開について確認する.
そのために,以下の記法を用いることにする.
>
集合 $ M $ に対し, $ M^k $ を次のように定める.
$ M^k := M $ の要素による長さ $ k $ の全ての数の組の集合

例.
$ M = \left \\{ 1,2,3 \right \\} $ なら
$ M^2 = \left \\{ (1,1),(1,2),(1,3),(2,1),(2,2),(2,3),(3,1),(3,2),(3,3) \right \\} $
$ M^3 = \left \\{ (1,1,1),(1,1,2), \dots ,(3,3,2),(3,3,3) \right \\} $

#### Theorem 2.2.1
>
$ p $ は自然数で $ p > 1 $ であるとする.任意の自然数 $ a $ に対して,一意的に定まる自然数 $ k $ と一意的に定まる数の列
$$ (a\_1,\dots,a\_k) \in \left \\{ 0,\dots,p-1 \right \\} $$ が $ a\_1 \neq 0 $ かつ
$$ a = \sum\_{i=1}^{k} a_{i} p^{k-i} $$ となるように定まる.
ここで $ k = \lfloor \mathrm{log}\_{p} \ a \rfloor + 1 $ であり $ a\_i $ は $ a - \sum_{j=1}^{i-1} a\_j p^{k-j} $ の $ p^{k-i} (1 \leq i \leq k) $ による除法の商である.

#### Def 2.2.2 (p進展開)
>
Theorem 2.2.1 の列 $ (a\_1,\dots,a\_k) $ を $ a $ の **$ p $ 進展開** という.
その列の**長さ**は $ k = \lfloor \mathrm{log}\_p a \rfloor + 1 $ である.

 今後は主に整数の二進展開や十六進展開を扱うことになる.
自然数の二進展開の長さをその自然数の**二進長**とよび,0の二進長については1と定義する.
整数 $ a $ の二進長はその整数の絶対値 $ |a| $ の二進長によって定め, $ \mathrm{size}(a) $ と表す.

### おまけ
C言語によるp進展開(p=2,...,16)の実装例

```C:expansion.c
#include <stdio.h>
#include <math.h>

int main(void){
    int i = 0, p, decimal;
    int expansion[256];

    printf("変換したい10進数で表された整数を入力してください：");
    scanf("%d",&decimal);
    printf("何進数に変換しますか？：");
    scanf("%d",&p);

    /* p進長:length を計算する */
    int length = 1;
    while( (decimal / (int)pow(p,length) ) != 0){
        length++;
    }
    printf("length:%d\n",length);

    /* p進展開を求める */
    for(i=0;i<length;i++){
        expansion[i] = decimal / (int)pow(p,length-i-1);
        if(expansion[i] != 0) decimal = decimal - expansion[i] * (int)pow(p,length-i-1);
    }

    for(i=0;i<length;i++){
        switch(expansion[i]){
            case 10:
                printf("A");
                break;
            case 11:
                printf("B");
                break;                
            case 12:
                printf("C");
                break;
            case 13:
                printf("D");
                break;
            case 14:
                printf("E");
                break;
            case 15:
                printf("F");
                break;
            default:
                printf("%d",expansion[i]);
                break;
        }
    }
    return 0;
}
```
#### 実行例
![expansion.png](https://qiita-image-store.s3.amazonaws.com/0/268256/54d4674a-f353-affe-5a71-6d54e2b7c6bd.png)

# 次へ
- [暗号理論2-2(初等整数論)](https://qiita.com/latticelsy/items/e4061b00ff2d7bd75eb7)