Class: GMP::Z

Inherits:

Integer

• Object
• Integer
• GMP::Z

Defined in:

ext/ecm.c

Instance Method Summary

• #ecm_factor(b1, ecm_params) ⇒ Object

  Search for a factor of ‘z`, using GMP-ECM’s ‘ecm_factor()` method.

Instance Method Details

#ecm_factor(b1, ecm_params) ⇒ Object

Search for a factor of ‘z`, using GMP-ECM’s ‘ecm_factor()` method.

Parameters:

• b1 (Fixnum, GMP::Z) —

  the stage 1 bound

• ecm_params (Hash) —

  auxiliary parameters; must be a Hash for now.

Options Hash (ecm_params):

• :method (Symbol) —

  the factorization method (‘:ecm_ecm` for ECM, `:ecm_pm1` for P-1, `:ecm_pp1` for P+1). Default is ECM_ECM.

• :x (Fixnum, GMP::Z) — default: if non zero —

  is the starting point (ECM, P-1, P+1). For ECM, we take as starting point $(x_0 : y_0)$ where $x_0=x$, $y_0=1$; for P-1, we take $x_0$; for P+1, we take $x_0$ as starting point of the Lucas sequence. When ‘ecm_factor()` returns, p->x is the point obtained after stage 1.

• :sigma (Fixnum, GMP::Z) — default: ECM only —

  is the “sigma” parameter. The elliptic curve chosen is $b * y^2 = x^3 + a*x^2 + x$ where $a = (v-u)^3 * (3*u+v) / (4*u^3*v) -2$, $u = sigma^2-5$, $v = 4*sigma$ (Suyama’s parametrization). The initial point (if p->x is zero) is taken as $x_0=u^3/v^3$, $y0=1$ (thus $b$ is taken as $x_0^3 + a*x_0^2 + x_0$).

• :sigma_is_A (-1, 0, 1) — default: ECM only —

  indicates that ‘:sigma` is the `a` parameter from the elliptic curve.

• :go (Fixnum, GMP::Z) —

  the initial group order to preload (default is 1).

• :B1done (Float) —

  tells that step 1 was already done up to this value. This means that all prime powers <= this value were dealt with. If for example ‘:B1done => 100` and `:B1 => 200`, prime 2 was dealt with up to power 6, thus it remains to “multiply” once by 2 to go up to power 7. Of course, all primes $p$ such that $B1done < p <= B1$ will be considered with power 1.

• :B2min (Fixnum, GMP::Z) —

  the lower bound for stage 2, which will treat all primes $p$ such that $B2min <= p <= B2$. If negative, ‘:B2min` will be set to `:B1`.

• :B2 (Fixnum, GMP::Z) —

  the upper bound for stage 2 (default is automatically computed from ‘:B1`, to optimize the efficiency of the method).

• :k (Fixnum) —

  the number of blocks used in stage 2 (default is ‘ECM_DEFAULT_K`).

• :S (Fixnum) —

  defines the polynomial used for Brent-Suyama’s extension in stage 2. If positive, the polynomial used is $x^S$; if negative, it is Dickson’s polynomial of degree $S$ with parameter $a=-1$, where $D_{1,a}(x) = x, D_{2,a}(x) = x^2-2*a$, and $D_{k+2,a}(x) = x*D_{k+1,a}(x) - a*D_{k,a}(x)$, or equivalently $D_{k,a}(2*sqrt(a)*cos(t)) = 2*a^{k/2}*cos(k*t)$. If zero, choice is automatic (and should be close to optimal). Default is ‘ECM_DEFAULT_S`.

• :repr (Fixnum) —

  defines the representation used for modular arithmetic: 1 means the ‘mpz’ class from GMP, 2 means ‘modmuln’ (Montgomery’s multiplication, quadratic implementation), 3 means ‘redc’ (Montgomery’s multiplication, subquadratic implementation), -1 indicates not to use a special base-2 representation (when the input number is a factor of $2^n +/- 1$). Other values (including 0) mean the representation will be chosen automatically (hopefully in some optimal way).

• :verbose (Fixnum) —

  the verbosity level: 0 for no output, 1 for normal output (like default for GMP-ECM), 2 for diagnostic output without intermediate residues (like ‘-v` in GMP-ECM), 3 for diagnostic output with residues (like `-v -v`), 4 for high diagnostic output (`-v -v -v`), and 5 for trace output (`-v -v -v -v`).

• :os (IO) —

  the output stream used for verbose output. Default is stdout.

• :es (IO) —

  the output stream used for errors. Default is stderr.

# File 'ext/ecm.c', line 178

VALUE r_ecm_factor (int argc, VALUE *argv, VALUE self_value) {
  MP_INT *self, *res;
  VALUE res_value, b1_value, params_arg, params_value;
  ECM_PARAMS *params;
  double b1;
  int found;
  (void)self;

  mpz_get_struct (self_value, self);
  mpz_make_struct (res_value, res);
  mpz_init (res);

  rb_scan_args (argc, argv, "02", &b1_value, &params_arg);
  if (params_arg == Qnil) {
    params = NULL;
  } else if (ECM_PARAMS_P (params_arg)) {
    ecm_params_get_struct (params_arg, params);
  } else if (TYPE (params_arg) == T_HASH) {
    params_value = build_ecm_params_from_hash (params_arg);
    ecm_params_get_struct (params_value, params);
  } else {
    rb_raise (rb_eArgError, "Second argument must be an ECMParams");
  }
  if (b1_value == Qnil) {
    b1 = 1000000;
  } else if (FIXNUM_P (b1_value)) {
    b1 = (double) NUM2INT (b1_value);
  } else if (FLOAT_P (b1_value)) {
    b1 = NUM2DBL (b1_value);
  } else {
    rb_raise (rb_eArgError, "b1 argument must be a Fixnum");
  }

  found = ecm_factor (res, self, b1, params);

  return rb_assoc_new(INT2FIX (found), res_value);
}