bug in IntegerMod

[Ralf Hemmecke]

First the problem.

Z ==> Integer
SI ==> SingleInteger
p:=prevPrime((max()$SI)::Z)$IntegerPrimesPackage(Z)
F ==> PrimeField p
FZ ==> SUP F
f: FZ := monomial(1, 2)$FZ - 2
factor(f)

If running this in a session one ends up with a nasty

(6) -> f: FZ := monomial(1, 2)$FZ - 2
Compiling function G387 with type Integer -> Boolean
Compiling function G389 with type NonNegativeInteger -> Boolean

2
(6) ? + 4611686018427387845
Type:
SparseUnivariatePolynomial(PrimeField(4611686018427387847))
(7) -> factor(f)

>> System error:
The value
4684986446884335550
is not of type
FIXNUM


That's probably not a very big surprise when looking at the special
implementation of a finite field for a prime that is just a bit smaller
than the maximum size of a SingleInteger.

However, of course, that shouldn't happen.

I first thought that the multiplication in PrimeField is problematic,
but no, it works fine. The problem is addmod $ SingleInteger.
See session below.

The documentation for addmod of SingleInteger is inherited from
IntegerNumberSystem.

addmod: (%, %, %) -> %
addmod(a, b, p), 0<=a, b<p>1, means a+b mod p.

Well, one might probably expect that there are problems if the domain
has only the size of a lisp fixnum. But that's certainly implementation
dependent. And seemingly mulmod works just fine for these border cases.

Although, I would somehow like that the ++ docstring for addmod $
SingleInteger would mention the restriction that not only a<p, b<p, but
also a+b<=max(), I can live with the implicit restriction, that a
programmer has to take care in the SingleInteger case.

However, there is a real bug that results from this restriction and that
is in IntegerMod(p)

It says

if p <= convert(max()$SingleInteger)@Integer then
Rep := SingleInteger
q := p::SingleInteger
...
else
Rep := Integer
...

Of course it should rather say:

if p <= convert(shift(max()$SingleInteger, -1))@Integer then

Bugfix is attached.
Can I commit?

Ralf


(1) -> I ==> SingleInteger
(2) -> p: I := max()$I -123456

(2) 4611686018427264447
Type: SingleInteger
(3) -> a: I := p - 1

(3) 4611686018427264446
Type: SingleInteger
(4) -> b: I := shift(a, -1)+100

(4) 2305843009213632323
Type: SingleInteger
(5) -> a + a

>> System error:
The value
9223372036854528892
is not of type
FIXNUM

(5) -> b + b

(5) 4611686018427264646
Type: SingleInteger
(6) -> addmod(a, a, p)

>> System error:
The value
9223372036854528892
is not of type
FIXNUM
(6) -> addmod(b, b, p)

(6) 199
Type: SingleInteger
(7) -> mulmod(a, a, p)

(7) 1
Type: SingleInteger
(8) -> mulmod(a, b, p)

(8) 2305843009213632124
Type: SingleInteger

[Waldek Hebisch]

Yes, thanks. One can probably slightly improve addmod, but
there are good reasons to use primes significantly smaller
than max()$SingleInteger.

--
Waldek Hebisch