しらみつぶしと break

整数 $A$, $P$ に対し, $x^2 \equiv A \bmod P$ を満たす整数 $x$ があるか どうか調べたい. 明らかに, $0 \le x < P$ に対して調べればよいので, 次のプログラムが書ける.

/* A が平方剰余なら 1, 非剰余なら 0 を返す */
def q_res(A,P) {
  for ( I = 0; I < P; I++ ) {
    R = (I^2-A) % P;
    if ( R == 0 )  /* みつけた */
      return 1;
  }
  return 0;
}

このプログラムは次のようにも書ける.

def q_res(A,P) {
  for ( I = 0; I < P; I++ ) {
    R = (I^2-A) % P;
    if ( R == 0 )
      break;
  }
  if ( I < P )
    return 1;
  else
    return 0;
}

違いは, 条件を満たす $I$ を見つけた場合の処理に break を 使っていることである. break のはたらきは, 「その break を囲んでいる最も内側のループを脱出する」 である. returnと違って関数の実行自体は継続する. 二番目の プログラムの場合, if 文の先頭に来るのは, break で脱出した場合と, I=P-1 まで行っても見つからなかった場合の 二通りあるが, どうやって見分けられるだろうか.

実は, 見つからなかった場合には I を 1 増やすので I==P となっているが, break で脱出した場合には I は当たり の値のままである. よって上のプログラムで正しく動作する.