## Summary Two functions in `GHC.Num.Integer` produce incorrect results. * `integerPowMod# 0 e m` returns `(# 0 | #)` for m \> 1 and e < 0. It should fail and return `(# | () #)`. * `integerRecip# 0 1` fails and returns `(# | () #)`. It should succeed and return `(# 0 | #)` ## Steps to reproduce ``` $ cat Test.hs {-# LANGUAGE MagicHash #-} {-# LANGUAGE UnboxedSums #-} module Test where import GHC.Natural import GHC.Num.Integer -- Wrappers to make things easier in ghci integerPowMod :: Integer -> Integer -> Natural -> Maybe Natural integerPowMod b e m = case integerPowMod# b e m of (# n | #) -> Just n (# | () #) -> Nothing integerRecip :: Integer -> Natural -> Maybe Natural integerRecip b m = case integerRecipMod# b m of (# n | #) -> Just n (# | () #) -> Nothing $ ghci Test.hs GHCi, version 9.12.2: https://www.haskell.org/ghc/ :? for help [1 of 1] Compiling Test ( Test.hs, interpreted ) Ok, one module loaded. ghci> integerPowMod 34 (-1) 17 Nothing -- correct ghci> integerPowMod 0 (-1) 17 Just 0 -- incorrect: should be Nothing. Note that `34 ≡ 0 (mod 17)` but 34 and 0 give different results. ghci> integerRecip 0 1 Nothing -- incorrect: should (arguably) be Just 0 ``` ## Expected behaviour ### integerPowMod# The exact behaviour of `integerPowMod#` and `integerRecipMod#` doesn't appear to be specified or documented anywhere, but when e\<0 I'd expect `integerPowMod# b e m` to return an integer b' with `b'^(-e)*b^(-e) ≡ 1 (mod m)` if `gcd b m == 1` (note that -e\>0, so the powers make sense) and to fail if `gcd b m /= 1`. When b=0, e\<0, and m\>1 it returns 0, which is certainly incorrect. This happens because the [implementation of `integerPowMod#`](https://hackage-content.haskell.org/package/ghc-bignum-1.3/docs/src/GHC.Num.Integer.html#integerPowMod%23) begins ``` integerPowMod# :: Integer -> Integer -> Natural -> (# Natural | () #) integerPowMod# !b !e !m | naturalIsZero m = (# | () #) | naturalIsOne m = (# naturalZero | #) | integerIsZero e = (# naturalOne | #) | integerIsZero b = (# naturalZero | #) | integerIsOne b = (# naturalOne | #) -- when the exponent is negative, try to find the modular multiplicative -- inverse and use it instead | integerIsNegative e = case integerRecipMod# b m of ... ``` The `integerIsZero b` case returns 0 prematurely when b=0 and e\<0; it should be something like ``` | integerIsZero b && e>0 = (# naturalZero | #) ``` and then either there should be a separate case for `integerIsZero b && e<0` or it should fall through to the `integerIsNegative` case and allow `integerRecipMod#` to produce an error. ### integerRecipMod# The implementation of `integerRecipMod#` is ``` integerRecipMod# :: Integer -> Natural -> (# Natural | () #) integerRecipMod# x m | integerIsZero x = (# | () #) | naturalIsZero m = (# | () #) | naturalIsOne m = (# | () #) | True = Backend.integer_recip_mod x m ``` so it always fails when m=1. I believe that it should return 0 in this case. I would expect `integerRecipMod# b m` to return an integer b' such that `b*b' ≡ 1 (mod m)`; in the case m=1, `0*0 = 0 ≡ 1 (mod m)`, as required. We're essentially working in the [zero ring](https://en.wikipedia.org/wiki/Zero_ring), which has a single element 0 with 0\*0=0, so 0 is a multiplicative identity element that happens to be called 0 instead of 1, and the multiplicative inverse of 0 is 0. Python's `pow` function and Sage's `power_mod` function both agree with this interpretation; note also that `integerPowMod# 0 (-1) 1` returns 0, so it agrees with my interpretation and disagrees with `integerRecipMod#`. The expected behaviour can be obtained by changing the implementation to ``` integerRecipMod# x m | naturalIsZero m = (# | () #) | naturalIsOne m = (# 0 | #) | integerIsZero x = (# | () #) | True = Backend.integer_recip_mod x m ``` ## Environment GHC 9.2.12