候補の選択(篩)

まずは探索する範囲 (a,b) を決めます。探索量は条件(後述)を満たす候補がFactor Baseの数を超えればいいので、実際には自由に探索してもらって構いません。

一般的には a を [-u, u] の範囲で、 b を [1, v] の範囲で探索するようになってます。これは条件を満たす候補が多いというわけではなく、（コンピュータでの計算として）探索を速く行うことができるという理由によるものだと思います。a が連続（数学的には整数なので離散的ですが）しているので、下の擬似コードのようにループにせず配列に何か記録していけば高速アクセスできるわけです。

for( b = 1 ; (条件をパスした候補の数) < (FBの総数) ; b++ ) {
  for( a = -u ; a ≤ u ; a++ ) { // アルゴリズムの説明のためにループ
    if( check(a, b) ) record(a, b);
  }
}

[実装向き ; 長くなるので指数の記録等省略]
for( b = 1 ; (条件をパスした候補の数) < (FBの総数) ; b++ ) {
  double flag[-a:a] = 1.0; // -aからaまでアクセスできる配列
  for( i = 0 ; i < (RFBの数) ; i++ ) {
    j = (b * m - a) % p[i]; // %の結果は正(か0)になるとする
    for( j = -a + j ; j ≤ a ; j = j + p[i] ) flag[j] = flag[j] * p[i];
  }
  for( i = -a ; i ≤ a ; i++ ) {
    if( b * m + i < flag[i] * p[最大] ) // 指数が2以上になるものを捕獲する意味もこめて
      flag[i] = 1.0;
    else
      flag[i] = 0.0;
  }
  for( i = 0 ; i < (AFBの数) ; i++ ) {
    j = (b * q[i].s - a) % q[i].q; // q[i]はi番目のイデアル
    for( j = -a + j ; j ≤ a ; j = j + q[i].q ) flag[j] = flag[j] * q[i].q;
  }
  // ここでまず候補を落とす
  for( j = -a ; j ≤ a ; j++ ) {
    if( flag[j] < 1.01 ) { // ここもちょっと誤差を許してる
      flag[j] = 0.0;
      continue;
    }
    flag[j] = norm( j, b );
  }
  for( i = 0 ; i < (AFBの数) ; i++ ) {
    if( q[i].q == q[i - 1].q ) continue;
    for( j = -a ; j ≤ a ; j++ ) {
      if( flag[j] == 0.0 ) continue; // 既に落ちてるものは計算しない
      for( k = 0 ; flag[j] % q[i].q == 0.0 ; k++ ) // double型だけど % 演算許して
        flag[j] = flag[j] / q[i].q;
    }
  }
}

RFB-smooth

17 3 1010100