失礼しました。そうです、"Riemann 予想" でした。

Miller 法も、多分正確には "Miller-Rabin's Primality Test"
だとおもいます。以下、私の浅い理解レベルで解説してみます。
間違っていたら御指摘ください。

基本的にはフェルマーテストと、sqrt(1) が 1 or -1 である
ことをある範囲の数について確かめるのですが、この範囲が
Riemann Hypothesis が証明さればかなり狭い範囲でよいと言
うことです。

1. フェルマーテスト
フェルマーの小定理は、「p が素数なら、 0 以外のどんな a
についても、a^p \equiv a \pmod p」。(aをp乗してpで割った余り
がaになるってこと。この証明は簡単ですよね。)
さて、この命題の対偶は、(以下、TeXっぽい記号はよみにくいので
プログラム言語っぽく書きます。)
「ある a (!=0) について a^p%p が a でないならば、p は
素数ではない」。
です。そこで、ある数 p についてさまざまな a を持って来て
a^p%p を計算し、一つでも a にならない a があったらその時点で
p が素数ではないことが分かります。

ここで、注意ですが、1 <= a <=p-1 の全ての a について、
a^p%a=a になるのに、p が素数ではない場合があるってことです。

さらに捕捉ですが、a^p%p の計算は a, a^2%p, a^4%p, ... を作り
必要なのを掛け合わせます(%p しながら)。特に a や p が大きい
場合はそうしないと手間が極端に増加します。