素数を法とした原始根を求めるプログラム
素数pを法とした剰余環の乗法群(位数p-1)は巡回群になります。その巡回群の生成元のことを「素数pを法とした原始根」といいます。原始根の存在を予想したのはオイラーですが、存在の証明をしたのはガウスです。この証明は難しくて(じっくり考えれば追えるレベル)、オイラーでもできませんでした。
ともかく、原始根を求めるプログラムを書いてみようと思いました。
以下です。
// 素数を法とした原始根を求める // Usage: ./a.out [prime number] #include <iostream> #include <cstdlib> #include <vector> std::vector<int> cyclic_group_modm(int generator, int m); std::vector<int> primitive_root(int prime); int main(int argc, char* argv[]){ int prime = atoi(argv[1]); std::cout << "***** primitive root of " << prime << " *****" << std::endl; std::vector<int> result = primitive_root(prime); for(int i=0; i<result.size(); i++){ std::cout << result.at(i) << std::endl; } return 0; } // mを法とした巡回群 std::vector<int> cyclic_group_modm(int generator, int m){ std::vector<int> cyclic_group; int elem = generator; cyclic_group.push_back(elem); // 単位元になるまで生成元を掛ける while(elem != 1){ elem = (elem * generator) % m; cyclic_group.push_back(elem); } return cyclic_group; } // 素数primeを法とした原始根 std::vector<int> primitive_root(int prime){ std::vector<int> primitive_root; int rank = prime - 1; // 素数primeを法とした剰余環の乗法群の位数 int generator = 2; for(int i=generator; i<prime; i++){ if(cyclic_group_modm(i, prime).size() == rank){ primitive_root.push_back(i); } } return primitive_root; }