bridge/class-master/depend/pari/src/modules/mpqs.c
/*********************************************************************/
/**                                                                 **/
/**                        FACTOR BASE SETUP                        **/
/**                                                                 **/
/*********************************************************************/
/* fill in the best-guess multiplier k for N. We force kN = 1 mod 4.
 * Caller should proceed to fill in kN */
FACTOR BASE SETUP

fill in the best-guess multiplier k for N. We force kN = 1 mod 4.
Caller should proceed to fill in kN
FACTOR BASE SETUP fill in the best - guess multiplier k for N . We force kN = 1 mod 4 . Caller should proceed to fill in kN
static ulong
mpqs_find_k(mpqs_handle_t *h)
{
  const pari_sp av = avma;
  const long N_mod_8 = mod8(h->N), N_mod_4 = N_mod_8 & 3;
  forprime_t S;
  struct {
    const mpqs_multiplier_t *_k;
    long np; 
    double value; 
  } cache[MPQS_POSSIBLE_MULTIPLIERS];
  ulong p, i, nbk;
  for (i = nbk = 0; i < numberof(cand_multipliers); i++)
  {
    const mpqs_multiplier_t *cand_k = &cand_multipliers[i];
    long k = cand_k->k;
    double v;
    if ((k & 3) != N_mod_4) continue; 
    v = -0.35 * log2((double)k);
    if ((k & 7) == N_mod_8) v += M_LN2; 
    cache[nbk].np = 0;
    cache[nbk]._k = cand_k;
    cache[nbk].value = v;
    if (++nbk == MPQS_POSSIBLE_MULTIPLIERS) break; 
  }
  if (nbk > MPQS_POSSIBLE_MULTIPLIERS) nbk = MPQS_POSSIBLE_MULTIPLIERS;
  u_forprime_init(&S, 2, ULONG_MAX);
  while ( (p = u_forprime_next(&S)) )
  {
    ulong Np = umodiu(h->N, p);
    long kroNp, seen = 0;
    if (!Np) return p;
    kroNp = krouu(Np, p);
    for (i = 0; i < nbk; i++)
    {
      if (cache[i].np > MPQS_MULTIPLIER_SEARCH_DEPTH) continue;
      seen++;
      if (krouu(cache[i]._k->k % p, p) == kroNp) 
      {
        cache[i].value += log2((double) p)/p;
        cache[i].np++;
      }
    }
    if (!seen) break; 
  }
  if (!p) pari_err_OVERFLOW("mpqs_find_k [ran out of primes]");
  {
    long best_i = 0;
    double v = cache[0].value;
    for (i = 1; i < nbk; i++)
      if (cache[i].value > v) { best_i = i; v = cache[i].value; }
    h->_k = cache[best_i]._k; avma = av; return 0;
  }
}
static ulong mpqs_find_k ( mpqs_handle_t * h ) { const pari_sp av = avma ; const long N_mod_8 = mod8 ( h -> N ) , N_mod_4 = N_mod_8 & 3 ; forprime_t S ; struct { const mpqs_multiplier_t * _k ; long np ; double value ; } cache [ MPQS_POSSIBLE_MULTIPLIERS ] ; ulong p , i , nbk ; for ( i = nbk = 0 ; i < numberof ( cand_multipliers ) ; i ++ ) { const mpqs_multiplier_t * cand_k = & cand_multipliers [ i ] ; long k = cand_k -> k ; double v ; if ( ( k & 3 ) != N_mod_4 ) continue ; v = -0.35 * log2 ( ( double ) k ) ; if ( ( k & 7 ) == N_mod_8 ) v += M_LN2 ; cache [ nbk ] . np = 0 ; cache [ nbk ] . _k = cand_k ; cache [ nbk ] . value = v ; if ( ++ nbk == MPQS_POSSIBLE_MULTIPLIERS ) break ; } if ( nbk > MPQS_POSSIBLE_MULTIPLIERS ) nbk = MPQS_POSSIBLE_MULTIPLIERS ; u_forprime_init ( & S , 2 , ULONG_MAX ) ; while ( ( p = u_forprime_next ( & S ) ) ) { ulong Np = umodiu ( h -> N , p ) ; long kroNp , seen = 0 ; if ( ! Np ) return p ; kroNp = krouu ( Np , p ) ; for ( i = 0 ; i < nbk ; i ++ ) { if ( cache [ i ] . np > MPQS_MULTIPLIER_SEARCH_DEPTH ) continue ; seen ++ ; if ( krouu ( cache [ i ] . _k -> k % p , p ) == kroNp ) { cache [ i ] . value += log2 ( ( double ) p ) / p ; cache [ i ] . np ++ ; } } if ( ! seen ) break ; } if ( ! p ) pari_err_OVERFLOW ( " " ) ; { long best_i = 0 ; double v = cache [ 0 ] . value ; for ( i = 1 ; i < nbk ; i ++ ) if ( cache [ i ] . value > v ) { best_i = i ; v = cache [ i ] . value ; } h -> _k = cache [ best_i ] . _k ; avma = av ; return 0 ; } }
FACTOR BASE SETUP
FACTOR BASE SETUP
/* number of primes in factorbase so far for this k */ /* the larger, the better */ /* want kN = 1 (mod 4) */ /* kN = 1 (mod 8) */ /* enough */ /* next test is an impossible situation: kills spurious gcc-5.1 warnings
   * "array subscript is above array bounds" */ /* kronecker(k*N, p)=1 */ /* we're gone through SEARCH_DEPTH primes for all k */