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

Georg-Johann Lay avr at gjlay.de
Ven 20 Mar 13:02:08 CET 2020


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
-------------- next part --------------
A non-text attachment was scrubbed...
Name: main.c
Type: text/x-csrc
Size: 930 bytes
Desc: not available
URL: <http://lists.gforge.inria.fr/pipermail/ecm-discuss/attachments/20200320/9fd03c81/attachment.c>


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