solution

Căn nguyên thủy nhỏ nhất modulo n

Một căn nguyên thủy $g$ modulo $n$ là phần tử có bậc bằng $\varphi(n)$, tức sinh ra toàn bộ nhóm nhân $\mathbb{Z}_n^*$. Đây là yếu tố then chốt trong Diffie–Hellman và ElGamal.

Tiêu chuẩn: $g$ nguyên tố cùng nhau với $n$ và với mọi ước nguyên tố $q$ của $\varphi(n)$:

$g^{\varphi(n)/q} \not\equiv 1 \pmod n$

Cho $n$, in căn nguyên thủy nhỏ nhất trong $[1,n)$; nếu không tồn tại in $-1$.

Ví dụ

Với $n=7$: $g=3$ vì $3^1,3^2,\dots,3^6$ sinh đủ $1..6$.