[Ecm-discuss] Need assist with an ECM-GMP program.

paul zimmermann Paul.Zimmermann at inria.fr
Ven 20 Mar 14:19:36 CET 2020


       Dear Georg-Johann,

it appears that ep->sigma, which is initially 0 (un-initialized) is set
by ecm_factor, and then if the first call fails, since now ep->sigma is
non-zero, it is taken as the sigma value, and it fails again and again.

With mpz_set_ui (ep->sigma, 0) after the ecm_factor() call it works better,
but there still seems to be a problem.

Paul

> From: Georg-Johann Lay <avr at gjlay.de>
> Date: Fri, 20 Mar 2020 13:02:08 +0100
> 
> Hi there, I am new to ecm-gmp and am having problems with the following 
> program:
> 
> #include "ecm.h"
> 
> // a^b + c
> void abc (mpz_t n, int a, int b, int c)
> {
>    mpz_set_si (n, a);
>    mpz_pow_ui (n, n, b);
>    if (c >= 0)
>      mpz_add_ui (n, n, c);
>    else
>      mpz_sub_ui (n, n, -c);
> }
> 
> void div (mpz_t n, const char *str)
> {
>    mpz_t q, r;
>    mpz_init (r);
>    mpz_init_set_str (q, str, 0);
> 
>    mpz_mod (r, n, q);
>    if (mpz_cmp_si (r, 0) != 0)
>      gmp_printf ("==\n== no divisor\n==\n");
>    mpz_div (n, n, q);
> 
>    mpz_clear (q);
>    mpz_clear (r);
> }
> 
> int main()
> {
>    ecm_params ep;
>    ecm_init (ep);
> 
>    mpz_t n, f, r;
>    mpz_inits (n, f, r, NULL);
> 
>    abc (n, 10, 43, -1);
>    div (n, "9");
>    div (n, "264307843");
> 
>    int i = 0, res = 0;
>    while (res == 0)
>      {
>        mpz_urandomm (r, ep->rng, n);
>        gmp_printf ("== %d %Zd\n", ++i, r); fflush (stdout);
>        res = ecm_factor (f, n, 100000.0, ep);
>      }
>    gmp_printf ("f = %Zd\n", f);
>    gmp_printf ("n = %Zd\n", n);
> 
>    ecm_clear (ep);
>    mpz_clears (n, f, r, NULL);
> 
>    return 0;
> }
> 
> 
> It tries to factor n = 4203852214522105994074156592890477 which has a 
> factor f = 1963506722254397.
> 
> The artifact is as follows:
> 
> The program finds the factor in around 1/3 or so cases it is run, and it 
> then finds the factor always in the 1st loop iteration:
> 
> $ ./ecm.x
> == 1 3241356043731196002706696862857315
> f = 1963506722254397
> n = 4203852214522105994074156592890477
> 
> However, if it does not find a factor in the 1st iteration, it appears 
> to run forever and never finds a factor:
> 
> $ ./ecm.x
> == 1 3241356043731196002706696862857315
> == 2 3724808314033102171939228424113020
> == 3 766533432404370843772082030728991
> == 4 2451799029480016192286417568643270
> == 5 802450095647754875892910331245171
> ...
> == 1421 662636955203428614468260234866648
> == 1422 4154066885625790430984808857975502
> ...
> 
> As ECM is probabilistic, my guess was that GMP's random number generator 
> does not work properly, but mpz_urandomm() gives different results each 
> time it is called.
> 
> What am I missing here?
> 
> * ECM revision is 7.0.5-dev from current SVN trunk r3078.
> 
> * GMP is v6.1.2
> 
> * Build compiler is GCC 7.4 on x86_64-linux-gnu.
> 
> * ECM configure: $ ../../source/ecm-trunk/configure 
> --prefix=.../install/gmp-native --enable-static --disable-shared 
> --with-gnu-ld CPPFLAGS=-D__USE_MINGW_ANSI_STDIO 
> --with-gmp=.../install/gmp-native
> 
> * GMP configure: $ ../../source/gmp-6.1.2/configure 
> --prefix=.../install/gmp-native --enable-static --disable-shared 
> --with-gnu-ld CPPFLAGS=-D__USE_MINGW_ANSI_STDIO --enable-cxx
> 
> * Building the program above with:
> 
> $ gcc -c main.c -o main.o -I .../install/gmp-native/include
> $ gcc main.o -o ecm.x -L.../install/gmp-native/lib -lecm -lgmp -lm
> $ ./ecm.x
> 
> Thanks for your assistance.
> 
> Johann
> 
> [2:text/x-csrc Show Save:main.c (930B)]
> 
> 
> [3:text/plain Hide]
> 
> _______________________________________________
> Ecm-discuss mailing list
> Ecm-discuss at lists.gforge.inria.fr
> https://lists.gforge.inria.fr/mailman/listinfo/ecm-discuss


Plus d'informations sur la liste de diffusion Ecm-discuss