原始根を求めるCプログラム

2024年の10月から秋葉原ロボット部の「ガロア理論の頂を踏む」読書会に参加していますが、1章9節に原始根という言葉が出てきました。

定義は、既約剰余類群(Z/pZ)*¹の元であってそのべき乗を計算すると全ての(Z/pZ)*の元を表せるもの²、です。

また1章10節によるとpが素数ならば原始根は必ず存在します。原始根を探すアルゴリズムも載っているのですが少々複雑なので、単純に定義に基づいてpに対する原始根を全て求めるプログラムをC言語で作ってみました。

#include <stdio.h>

// nがpの原始根であるか判定
int isPrimitiveRoot(int p, int n)
{
	int count = 0;
	long long m = 1; // intだと溢れた
	char already[110000] = {0}; // 10000個目の素数は104729

	while (1) {
		m *= n; // mにnのべき乗が入る
		m %= p; // 溢れないよう即mod p
		count++;

		//if (m != 1) // pが素数なら原始根でなくても必ず1に到達する前提のコード←NG
		if (already[m] == 0) { // pが素数でなくても無限ループにならないようにするため
			already[m] = 1;
			continue;
		}

		if (m != n) // pが素数なら起きないみたいだが、素数でないと起きる場合があった
			printf("%d %d\n", m, n);
		//if (count == p - 1) // pが素数なら原始根でなくても必ず1に到達する前提のコード←NG
		if (count == p)
			return 1;
		else
			return 0;
	}
}

int main(void)
{
	int p;

	printf("prime number: ");
	scanf("%d", &p);

	int count = 0;
	for (int i = 2; i < p; i++)
		if (isPrimitiveRoot(p, i)) {
			printf("%d ", i);
			count++;
			count %= 10;
			if (count == 0)
				printf("\n");
		}
	printf("\n");

	return 0;
}

本に載っていた41の原始根を求めてみた例です。

prime number: 41
6 7 11 12 13 15 17 19 22 24
26 28 29 30 34 35

グロタンディーク素数には原始根はありませんでした。:-)

prime number: 57

このプログラムは、入力されたpに対し2からp-1の数が原始根であるかをisPrimitiveRoot関数で判定し、原始根であれば表示しています。

pが素数でない場合にも原始根がありうるのか(いくつか調べた感じではなさそうですが)、あったとして数学的に使い道があるのかは分かりませんが、一応素数でないpを入力されても無限ループに陥らないためにnのべき乗を計算していて既に出現した値が再び出現したかをチェックするようにしました。

ネットで原始根をある程度まで求めた情報が載っていましたが、それとは一致していました。またネットで素数表を探したところ10000個目の素数は104729ですが無限ループに陥ることなく終了できました。

抽象的な議論だけだとどこかもやもやするので具体的に原始根の値を計算してみたお話でした。

1. 整数をpで割った余りは0、1、、p-1のp通りなので、整数を余りによってp個に分類でき($0$、$1$、$2$、、$p-1$と表し数のように扱う)、これらの集合をZ/pZと表します。Z/pZは足し算に関して群を成します。
   Z/pZの元からpと互いに素であるものだけを選ぶと掛け算に関して群を成し既約剰余類群と呼び(Z/pZ)*と表します。 ↩

2. 具体例として(Z/5Z)*の元は$1$、$2$、$3$、$4$の4個ですがどれが原始根か定義に従って確認してみます。各元をべき乗して5で割った余りを求めると、
   $1$は何乗しても$1$以外の元が出てこないので$1$は原始根ではありません。
   $2^1=2$、$2^2=4$、$2^3=8=3$、$2^4=16=1$ と全ての元が出てきたので$2$は原始根です。
   $3^1=3$、$3^2=9=4$、$3^3=27=2$、$3^4=81=1$ と全ての元が出てきたので$3$は原始根です。
   $4^1=4$、$4^2=16=1$、$4^3=64=4$、$4^4=256=1$ となり$4$と$1$しか出てこないので$4$は原始根ではありません。 ↩