---
# System prepended metadata

title: 模(mod)運算
tags: [crypto]

---

---
title: 模(mod)運算
tags: crypto
lang: zh_tw
---

* [筆記總覽](https://hackmd.io/@LJP/rkerFdnqS)

[TOC]

# 模(mod)運算
- If $a\ mod\ n\ =\ b\ mod\ n$
    - $a\ \equiv\ b\ mod\ n$

- Identities (單位)
    - $(0\ +\ w)\ mod\ n\ =\ w\ mod\ n$
    - $(1\ \times\ w)\ mod\ n\ =\ w\ mod\ n$

- inverse 反元素
    - 加法反元素
        - $-w$
    - 乘法反元素
        - 借助 Extended GCD Algorithm
        - 若給 a, p 且 p 為 prime, 則可以快速找到非負整數 x 符合
            - $ax + py = gcd(a, p)$
            - $ax\ \equiv\ 1\ mod\ p$
        - x 即是 a 在 mod p 下的乘法反元素