素数判定アルゴリズム内の剰余計算

質問

今勉強している任意倍長精度整数の素数を判定するアルゴリズム内で
x^q mod n
という計算をするところがあるのですが、
正確に計算しようとすると計算量が膨れ上がってしまって
高速にできなくて困っています。
参考にしている文献に
"x^q mod nの計算ではx^q mod nを正確に求める必要は無く、
x^q ≡ x^q' (mod n)となる x^q'でよい"という記述があるのですが
どういう意味なのかよくわかりません。

どなたか教えていただけないでしょうか？

回答No.3

Tacosan

ん～, 「繰り返しごとにやると計算量が増えてしまい」の意味が今一つわからない (ビット数が減るので x^q を計算してから n で割るよりは高速なはず) んですけど....
とりあえず, 「現在どのように計算しているのか」を挙げてもらえればヒントになるかもしれません.

回答No.2

rabbit_cat

フェルマーの小定理（オイラーの定理）は使ってますか？
http://ja.wikipedia.org/wiki/%E3%83%95%E3%82%A7%E3%83%AB%E3%83%9E%E3%83%BC%E3%81%AE%E5%B0%8F%E5%AE%9A%E7%90%86

回答No.1

Tacosan

どうせ x^q は一発で計算できないわけです. 言い替えれば何らかの処理を繰り返して x^q を計算するんだから, その繰り返しごとに mod n を計算すれば出てくる数値は必ず n 未満になりますよね.

お礼

回答ありがとうございます。

qが９桁前後で、繰り返しごとにやると計算量が増えてしまい
高速にできなくて困っています