Re: mpz_powm crashes with modulus>2^2100000

[Jens Kruse Andersen]

Jens Kruse Andersen wrote:
>    I inserted the patch including all printf. My earlier sent test program
still
>    crashes with p=2^2100000+1 after outputting:
>    Calling mpz_powm_ui...Done. Calling mpz_powm...k=1
>    computing x^2
>
>    Note the test program only tries to compute 3^3 mod p, the exponent is
tiny
>    and the patch does not change k.
>    I am running under Windows XP with 256 MB physical memory.
>


Paul Zimmermann wrote:
> I could not reproduce the problem under Linux, so I guess it is Windows
> specific. Did you try to configure GMP with --disable-alloca (if possible
> under Windows)?
>
> Paul
>

Thanks, with ./configure --disable-alloca, it works. Using powm on 3^3 mod p
still works for p=2^25000000+1 (25 million bits).

I inserted printf statements in powm.c to locate the last performed statement
with the default ./configure:

  printf ("301,");
  mpn_sqr_n (tp, gp, mn);
  printf ("303,");
  if (use_redc) {
    printf ("305,");
    redc (xp, mp, mn, invm, tp);  /* xx = x^2*R^n */
  }
  else {
    printf ("309,");
    mpn_tdiv_qr (qp, xp, 0L, tp, 2 * mn, mp, mn);
  }
  printf ("312,");
  this_gp = gp;
  printf ("314,");

In my original test program to compute 3^3 mod (2^2100000+1), the above prints
"301,303,309," and crashes without "312,", so apparently mpn_tdiv_qr never
returns. The same happens for mpz_powm calls with other modulus>2^2100000 and
other base and exp values. I know nothing about the GMP implementation and
have not tried to figure out what could be problematic about the call. I guess
it tries and fails to allocate memory, but it seems strange to me
that --disable-alloca works with more than 11 times as many bits in the
modulus.
My test program still terminates without a crash (meaning a Windows message
saying an error occurred) and without reaching "314," for modulus 2^2083000+1
and other modulus around this.
For modulus 2^2050000+1, everything works fine and prints
"301,303,309,312,314,". There is a 1 second pause between 309 and 312.

Kevin Ryde wrote:
> You might be running out of stack space, various temporaries are
> allocated on the stack.
>
> I don't know how to change the stack size on mingw.  But to have gmp
> use malloc instead of the stack you can configure with
>
> ./configure --enable-alloca=malloc-notreentrant
>
> (Or malloc-reentrant if you need multi-threading or other reentrancy.)

I don't know how to see or change the stack size on mingw.
I tried ./configure --enable-alloca=malloc-notreentrant
A library was built with make but when I try to compile my program with gcc, I
get:
D:\msys\1.0\home\Administrator\gmp-4.1.2malloc-notreentrant\.libs\libgmp.a(mul
_n.o): In function `interpolate3':
D:/msys/1.0/home/Administrator/gmp-4.1.2disable-alloca/mpn/mul_n.c:629:
undefined reference to `__gmp_tmp_reentrant_alloc'

And then many more of: undefined reference to `__gmp_tmp_reentrant_alloc' (or
_alloc replaced with _free).
I am new with gcc and am probably missing something. Never mind, I have a
working solution.

--
Jens Kruse Andersen