- 299 名前： ◆QZaw55cn4c mailto:sage [2012/05/07(月) 01:25:25.23 ]
- >>297
なるほど、定義どおりにいけば、n が p について原始根であるかどうかをみるのに、現状では
n^1, n^2, n^3, ... n^(p-2) について 1 (mod p) をみなければならない
ところが、教えていただいた方法では
p - 1 の約数についてのみ、と個数を絞り込むことができる
のですね。仮にメルセンヌ素数 2^1279 - 1を目標にすると、
2^1279 - 1 = 2(2^640 + 1)(2^320 + 1)(2^160 + 1) .... (2^5 + 1)(2^5 - 1)
まで因数分解できるので、個々の因数を素因数分解していくと、チェックしなければならない場合の数が激減しますね。少なくとも 2^1279 とおり、ということはないはず。
あとは何が原始根の候補となりうるのかが判別すればいいのですが、これは、>>292 でも使用しているのですが、計算量が増えるにしても 2 から順次チェックするのが絞り込みやすいのかもしれません。
しんどいですけれども。
|
 |
