유군

• 영어 명칭: Class Group
• 속도 향상: 초다항적
• 구현 코드: ∅

$\theta$를 근으로 갖는 다항식 중 가장 낮은 차수가 $d$일 때, 수체 $\mathbb{Q}(\theta )$의 차수를 $d$라고 한다. $\mathbb{Z}[x]$ 상에서 최고차항의 계수가 1인 다항식의 근인 $\mathbb{Q}(\theta )$의 원소로 이루어진 집합 $\mathcal{O}$은 환을 이루는데, 이 환을 $\mathbb{Q}(\theta )$의 정수환이라고 하며, 이는 데데킨트(Dedekind) 정역이기도 하다. 데데킨트 정역 상에서 $0$이 아닌 주아이디얼을 법으로 하는 $0$이 아닌 분수 아이디얼은 유군을 이룬다. 홀그렌(Hallgren)이 보인 바와 같이 [50], 고정된 차수의 수체에 대하여, 양자 컴퓨터는 주어진 $\theta$를 토대로 정수환 유군의 생산자를 $\mathrm{poly}(\log (|\mathcal{O}|))$ 시간에 찾을 수 있다. 차수 $d$에 따라 다항 시간에 이 문제를 해결하는 향상된 양자 알고리즘도 발견되었다 [329]. 이를 다항 시간에 해결하는 고전 알고리즘은 알려지지 않았다. 아벨 숨은 부분군을 참고.