---
title: Primitive root 原根
tags: crypto
lang: zh_tw
---

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

[TOC]

# Primitive root 原根
參考 [wiki: Primitive root modulo n](https://en.wikipedia.org/wiki/Primitive_root_modulo_n)

請先閱讀 [Euler's phi Function](https://hackmd.io/@LJP/r1ujih8IY)

$a, m$ 互質, 使得 $a^d \equiv 1\ (mod\ m)$ 成立的最小正整數 $d$ 定義為 $\delta_m(a)$

若 $\delta_m(a) = \phi(m)$ 則稱 **$a$ 是 $mod\ m$ 的原根**
英文則是 **$a$ is a primitive root modulo n**