素数判定の式を実装できません。。。

Question

前提・実現したいこと

ミラーラビンの素数判定法を用いて、素数判定のプログラムを実装しています。
ウィキペディアで調べたアルゴリズムを実装しようとしていますが、なかなかうまくいきません。

ミラーラビンの素数判定法（Wikipediaより）

入力： n > 1 → 素数判定対象の奇数の整数,  k → 判定の正確度を指定するパラメータ
出力： n が合成数なら composite、さもなくば probably prime

n - 1 を 2 のべき乗で割って、 2^s * d の形式にする。
以下を k 回繰り返す:
　　[ 1, n - 1 ] の範囲から a をランダムに選ぶ。
　　a^d != 1 mod n  で、かつ  [0,s-1] の範囲の全ての r について  a^{(2^r)*d} mod != -1 なら、composite を返す。
probably primeを返す。

該当のソースコード

function assert_iterate($n, $s, $d) {
  $a = mt_rand(1, $n - 1);
  if((pow($a, $d) - 1) % $n !== 0) {
    for($r = 0; $r <= $s-1; $r++) {
      echo $x = pow(2, $r) * $d;
      if($x % $n !== -1) {
        return false;
      }
    }
  }
}

function is_prime(int $n){
  if($n < 2){
    return false;
  }
  if($n >= 4 && $n % 2 === 0) {
    return false;
  }
  if($n === 2) {
    return true;
  }

  $s = 0;
  $d = $n - 1;
  while(($d % 2) === 0){
    $s ++;
    $d = $d / 2;
  }

  $k = 10000;
  while($k) {
    assert_iterate($n, $s, $d);
    $k--;
  }

  return true;
}

###問題のある部分

ソースコードの問題点は、素数でテストをしてもfalseが返ってくることです（素数であれば、trueが返ってきます）。
is_primeの引数に13を入れて調べてみたところ、上の assert_iterate関数 の1回目のイテレートでfalseに入ってしまいました。

アドバイスをよろしくお願いします。????‍♂️

Comments

[m.ts10806]

現状のコードの問題点は何でしょう。「うまくいかない」では何も伝わりませんので具体的に記載してください

[KK0618]

コードの問題点は、素数でテストをしてもfalseが返ってくることです（素数であれば、trueが返ってきます）！
is_primeの引数に13を入れて調べてみたところ、上の assert_iterate関数 の1回目のイテレートでfalseに入ってしまいました。

[m.ts10806]

質問は編集できますので適宜追記願います

Answer 1

アルゴリズム的なところは追ってませんが

  while($k) {
    assert_iterate($n, $s, $d);
    $k--;
  }

はassert_iterateの結果を何も反映せず、素通りしてます。

Comments

[KK0618]

申し訳ありませんが、あまり理解できていません。。。
>```assert_iterate```の結果を何も反映せず、素通りしてます。
こちらは、そもそもwhile文の中に入れていない、ということを表していますでしょうか。

[退会済みユーザー]

該当の while は assert_iterate() の返り値をどこにも反映していないので、単純に $k を 10000 から 0 にするだけの処理になっています。

[KK0618]

ご指摘ありがとうございます！！

勘違い部分：returnしていれば、全ての処理が終わる
→これは、assert_iterate関数の処理が終わるだけでしたね,,,汗

while文の方で返り値を反映させたらできました！！