Gerhard Niklasch on Wed, 22 Jul 1998 14:37:47 +0200 (MET DST) |
[Date Prev] [Date Next] [Thread Prev] [Thread Next] [Date Index] [Thread Index]
Re: ispseudoprime behavior |
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