Re: ispseudoprime behavior

[Gerhard Niklasch <nikl@mathematik.tu-muenchen.de>]

In response to:
> Message-Id: <19980721160057.Q25633@io.txc.com>
> Date: Tue, 21 Jul 1998 16:00:57 -0400
> From: Igor Schein <igor@txc.com>

> Hi, consider the following function
> 
> f(n)=while(1,print(ispseudoprime(n)))
> 
> Now let n be a negative integer whose absolute
> value is an odd composite integer.  For example
> let n=-9.  In a few iterations you'll see the
> following:
> ***   impossible inverse modulo: Mod(3, 9).
> 
> I was trying to figure out what's going on in
> the code, I noticed that negative sign gets
> stripped out by the time millerrabin() is called,
> but couldn't figure out where.

It used to get stripped out in init_miller()  (in src/basemath/ifactor1.c),
_after_ subtracting 1 from it to get the appropriate exponent, so a nega-
tive n will lead to an exponent which is (a) negative and (b) doesn't
have the correct absolute value either.  Thanks for spotting this --
another one of the sort `if you know exactly what the code is supposed
to be doing, you'll never see it'. ;^/

(The addsi() instead of subis() is a minor optimization.)

Enjoy, Gerhard

bash$ diff -u src/basemath/ifactor1.c.gn19980721 src/basemath/ifactor1.c
--- src/basemath/ifactor1.c.gn19980721  Wed Jul 22 14:16:21 1998
+++ src/basemath/ifactor1.c     Wed Jul 22 14:23:11 1998
@@ -12,10 +12,11 @@
 static GEN
 init_miller(GEN n)
 {
-  t=subis(n,1); r1=vali(t); t1 = shifti(t,-r1);
+  if (signe(n) < 0) n = absi(n);
+  t=addsi(-1,n); r1=vali(t); t1 = shifti(t,-r1);
   sqrt1=cgeti(lg(t)); sqrt1[1]=evalsigne(0)|evallgefint(2);
   sqrt2=cgeti(lg(t)); sqrt2[1]=evalsigne(0)|evallgefint(2);
-  return (signe(n) < 0)? absi(n): n;
+  return n;
 }
 
 /* is n strong pseudo-prime for base a ? `End matching' (check for square