---
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 下的乘法反元素