Polynomials over second-degree finite field extensions seem to loop forever on GCD operations

[kozross]

I'm currently writing some test code in a second-degree extension of GF(11). Specifically, elements of this extension are represented as (x + yu), where u^2 = 2. I am using the semirings interface for this, defining things as so:

-- Prelude is imported qualified as P, any clashing operations not qualified as from `semirings`

newtype GF11Elem2 = GF11E2 (Int, Int)
    deriving (Eq) via (Int, Int)

instance Semiring GF11Elem2 where
    plus (GF11E2 (r1, i1)) (GF11E2 (r2, i2)) = GF11E2 . reduce $ (r1 + r2, i1 + i2)
    times (GF11E2 (r1, i1)) (GF11E2 (r2, i2)) =
        let r1r2 = r1 * r2
            r1i2 = r1 * i2
            i1r2 = i1 * r2
            i1i2 = i1 * i2
         in GF11E2 . reduce $ (r1r2 + 2 * i1i2, r1i2 + i1r2)
    zero = GF11E2 (0, 0)
    one = GF11E2 (1, 0)
    fromNatural n = GF11E2 (P.fromIntegral $ n `mod` 11, 0)

instance Ring GF11Elem2 where
    negate (GF11E2 (r, i)) = GF11E2 . reduce $ (negate r, negate i)

instance GcdDomain GF11Elem2

instance Euclidean GF11Elem2 where
  quot (GF11E2 (u, v)) = \case
    GF11E2 (0, 0) -> P.error "Division by zero"
    GF11E2 (x, y) -> let recipExpr = (x * x) - (2 * y * y)
                         (_, recipr) = gcdExt recipExpr 11
                         ux = u * x
                         yv = y * v
                         xv = x * v
                         uy = u * y
                        in GF11E2 . reduce $ ((ux - (2 * yv)) * recipr, (xv - uy) * recipr)
  rem _ = \case
    GF11E2 (0, 0) -> P.error "Division by zero"
    _ -> zero
  quotRem x y = let !q = quot x y
    in (q, zero)
  degree = const zero

-- Helpers

reduce ::
    forall (f :: Type -> Type -> Type) (a :: Type).
    (Bifunctor f, Integral a) => f a a -> f a a
reduce = bimap (`mod` 11) (`mod` 11)

Part of my test code requires testing for squarefreeness of polynomials over GF11Elem2, as per this method. My 'initial' polynomials are always of the form toPoly [B, A, 0, 1], where A and B are constants. However, I find that even the initial gcd f (deriv f) loops forever, or at least runs so slowly it might as well loop forever. Furthermore, if I use the boxed polynomial representation, I rapidly exhaust all available RAM; switching to unboxed representation solves this (but still runs forever).

Am I missing something here, or is there some kind of bug or performance limitation in poly I need to be aware of?

[Bodigrim]

I gave it a quick test with

#!/usr/bin/env cabal
{- cabal:
    build-depends: base, semirings, tasty, tasty-quickcheck, quickcheck-classes
    default-language: GHC2024
-}

{-# LANGUAGE DerivingVia #-}

module Main where

import Data.Bifunctor
import Data.Euclidean
import Data.Kind
import Data.Proxy
import Data.Semiring
import Prelude hiding (negate, quot, (-), (*), (+))
import Prelude qualified as P
import Test.QuickCheck.Classes
import Test.Tasty
import Test.Tasty.QuickCheck

main :: IO ()
main = defaultMain $ testGroup "All"
    [ testLaws (semiringLaws (Proxy @GF11Elem2))
    , testLaws (ringLaws (Proxy @GF11Elem2))
    , testLaws (gcdDomainLaws (Proxy @GF11Elem2))
    , testLaws (euclideanLaws (Proxy @GF11Elem2))
    ]

testLaws :: Laws -> TestTree
testLaws (Laws cl ls) = testGroup cl $ map (\(n, p) -> testProperty n p) ls

instance Arbitrary GF11Elem2 where
    arbitrary = do
        x <- arbitrary
        y <- arbitrary
        pure $ GF11E2 $ reduce (x, y)

newtype GF11Elem2 = GF11E2 (Int, Int)
    deriving (Eq) via (Int, Int)
    deriving (Show)

and it fails with

All
  Semiring
    Additive Commutativity:                         OK
      +++ OK, passed 100 tests.
    Additive Left Identity:                         OK
      +++ OK, passed 100 tests.
    Additive Right Identity:                        OK
      +++ OK, passed 100 tests.
    Multiplicative Associativity:                   OK
      +++ OK, passed 100 tests.
    Multiplicative Left Identity:                   OK
      +++ OK, passed 100 tests.
    Multiplicative Right Identity:                  OK
      +++ OK, passed 100 tests.
    Multiplication Left Distributes Over Addition:  OK
      +++ OK, passed 100 tests.
    Multiplication Right Distributes Over Addition: OK
      +++ OK, passed 100 tests.
    Multiplicative Left Annihilation:               OK
      +++ OK, passed 100 tests.
    Multiplicative Right Annihilation:              OK
      +++ OK, passed 100 tests.
    FromNatural Maps Zero:                          OK
      +++ OK, passed 100 tests.
    FromNatural Maps One:                           OK
      +++ OK, passed 100 tests.
    FromNatural Maps Plus:                          OK
      +++ OK, passed 100 tests.
    FromNatural Maps Times:                         OK
      +++ OK, passed 100 tests.
  Ring
    Additive Inverse:                               OK
      +++ OK, passed 100 tests.
  GcdDomain
    divide1:                                        FAIL
      *** Failed! Falsified (after 5 tests):
      GF11E2 (10,4)
      GF11E2 (4,9)
      Just (GF11E2 (1,7)) /= Just (GF11E2 (10,4))
      Use --quickcheck-replay="(SMGen 2075115090340582181 11326437548579242649,4)" to reproduce.
      Use -p '/divide1/' to rerun this test only.
    divide2:                                        FAIL
      *** Failed! Falsified (after 1 test):
      GF11E2 (10,0)
      GF11E2 (1,1)
      GF11E2 (10,0) /= GF11E2 (1,0)
      Use --quickcheck-replay="(SMGen 6736168943341781556 3447776827761876821,1)" to reproduce.
      Use -p '/divide2/' to rerun this test only.
    gcd1:                                           OK
      +++ OK, passed 100 tests; 10 discarded.
    gcd2:                                           OK
      +++ OK, passed 100 tests; 11 discarded.
    lcm1:                                           OK
      +++ OK, passed 100 tests; 13 discarded.
    lcm2:                                           OK
      +++ OK, passed 100 tests; 12 discarded.
    coprime:                                        OK
      +++ OK, passed 100 tests; 11 discarded.
  Euclidean
    degree:                                         OK
      +++ OK, passed 100 tests; 12 discarded.
    quotRem:                                        FAIL
      *** Failed! Falsified (after 4 tests):
      GF11E2 (0,8)
      GF11E2 (2,9)
      GF11E2 (0,8) /= GF11E2 (0,3)
      Use --quickcheck-replay="(SMGen 1941107553198948133 14602211831618025785,3)" to reproduce.
      Use -p '/quotRem/' to rerun this test only.
    quot:                                           OK
      +++ OK, passed 100 tests; 11 discarded.
    rem:                                            OK
      +++ OK, passed 100 tests; 10 discarded.

3 out of 26 tests failed (0.01s)

so presumably something is off with your definition of division.

Why is degree = const zero?

[Bodigrim]

Setting

                         (g, recipr') = gcdExt recipExpr 11
                         recipr = case g of
                            1 -> recipr'
                            -1 -> negate recipr'
                            _ -> error $ "unexpected g = " ++ show g

fixes it for me.

[kozross]

degree = const zero was something I was unsure about. I was trying to follow

\x y -> y == 0 || let (q, r) = x `quotRem` y in (r == 0 || degree r < degree y)

As we're working in a field, the remainder is always zero when dividing anything by any nonzero element. Thus, r == 0 || degree r < degree y should always be true, thus I assumed a constant function returning anything was fine. Did I misunderstand something?

Also, what would be the fix to division needed here?

[Bodigrim]

Did I misunderstand something?

I think you are fine, thanks.

Also, what would be the fix to division needed here?

Does the fix above work for you?
(The thing is that gcdExt returns any of the greatest (by absolute value) common divisors, not necessarily a positive one)

[kozross]

Ah, I understand now. The mistake I made was that I assumed gcdExt would return a greatest positive common divisor. Thanks so much!