Tests of invmod fail with arc & orc GC

[dlesnoff]

The latest commit does not pass due to to an error with the arc garbage collector and the modular inverse function invmod. It fails at the very first test of the function line 388.

How can I debug the invmod function to fix it ?

[konsumlamm]

I'm pretty sure this is a Nim bug, especially since it works if i print r1 and s1 at the end of the loop.

[dlesnoff]

In the test, I have echo’ed invmod and it provides the good result for the two first result with arc gc. The assertion may fail due to the way the equality is tested.

[dlesnoff]

This is definitely a Nim bug.

I modified invmod in src/bigints.nim to output the r0 variable (that I should have called gcd by the way).

proc invmod*(a, modulus: BigInt): BigInt =
  ## Compute the modular inverse of `a` modulo `modulus`. 
  ## The return value is always in the range `[1, modulus-1]`
  runnableExamples:
    invmod(3.initBigInt, 7.initBigInt) = 5.initBigInt

  # extended Euclidean algorithm
  if modulus.isZero:
    raise newException(DivByZeroDefect, "modulus must be nonzero")
  elif modulus.isNegative:
    raise newException(ValueError, "modulus must be strictly positive")
  elif a.isZero:
    raise newException(DivByZeroDefect, "0 has no modular inverse")
  else:
    var
      r0 = ((a mod modulus) + modulus) mod modulus
      r1 = modulus
      s0 = one
      s1 = zero
      iteration = 0
    echo "After initialization : ", r0
    while r1 > 0:
      let
        q = r0 div r1
        rk = r0 - q * r1
        sk = s0 - q * s1
      r0 = r1
      r1 = rk
      s0 = s1
      s1 = sk
      echo "After iteration " & $iteration & " r0 = " & $r0
      iteration.inc
    if r0 != one:
      raise newException(ValueError, $a & " has no modular inverse modulo " & $modulus & " since the gcd is equal to " & $r0)
    result = ((s0 mod modulus) + modulus) mod modulus

I replaced the doAssert by affectations and echo'ed some variables tests/tbigints.nim

  block: # invmod
    # with prime modulus
    let a = "30292868".initBigInt
    let b = "48810860".initBigInt
    let p = "60449131".initBigInt # p is prime
    let first_res = invmod(a, p)
    let first_exp_res = "51713091".initBigInt
    doAssert first_res == first_exp_res

    echo "invmod(a, p): ", invmod(a, p)
    echo "expect : 51713091"
    echo "invmod(-b, p): ", invmod(-b, p)
    echo "expect : 31975542"

I got the output :

  Executing task test in /home/lullaby/Documents/nim/bigints/bigints.nimble
testing c backend
  using refc GC
After initialization : 30292868
After iteration 0 r0 = 60449131
After iteration 1 r0 = 30292868
After iteration 2 r0 = 30156263
After iteration 3 r0 = 136605
After iteration 4 r0 = 103163
After iteration 5 r0 = 33442
After iteration 6 r0 = 2837
After iteration 7 r0 = 2235
After iteration 8 r0 = 602
After iteration 9 r0 = 429
After iteration 10 r0 = 173
After iteration 11 r0 = 83
After iteration 12 r0 = 7
After iteration 13 r0 = 6
After iteration 14 r0 = 1
After initialization : 30292868
After iteration 0 r0 = 60449131
After iteration 1 r0 = 30292868
After iteration 2 r0 = 30156263
After iteration 3 r0 = 136605
After iteration 4 r0 = 103163
After iteration 5 r0 = 33442
After iteration 6 r0 = 2837
After iteration 7 r0 = 2235
After iteration 8 r0 = 602
After iteration 9 r0 = 429
After iteration 10 r0 = 173
After iteration 11 r0 = 83
After iteration 12 r0 = 7
After iteration 13 r0 = 6
After iteration 14 r0 = 1
invmod(a, p): 51713091
expect : 51713091
[...]
  using arc GC
After initialization : 30292868
After iteration 0 r0 = 60449131
After iteration 1 r0 = 0
After iteration 2 r0 = 0
/home/lullaby/Documents/nim/bigints/tests/tbigints.nim(544) tbigints
/home/lullaby/Documents/nim/bigints/tests/tbigints.nim(388) main
/home/lullaby/Documents/nim/bigints/src/bigints.nim(1055) invmod
Error: unhandled exception: 30292868 has no modular inverse modulo 60449131 since the gcd is equal to 0 [ValueError]
[...]

[dlesnoff]

Ok I have pinpoint the problem. The compile time tests

static: main()

functions correctly. but the runtime then fails :

After initialization : 30292868
After iteration 0initializations, q = 0
After iteration 0initializations, r0 = 30292868
After iteration 0initializations, r1 = 60449131
After iteration 0initializations, rk = 30292868
After iteration 0initializations, sk = 1
After iteration 0 r0 = 60449131
After iteration 0 r1 = 30292868
After iteration 0 rk = 30292868
After iteration 0 sk = 1
After iteration 1initializations, q = 1
After iteration 1initializations, r0 = 60449131
After iteration 1initializations, r1 = 0
After iteration 1initializations, rk = 60449131
After iteration 1initializations, sk = 0
After iteration 1 r0 = 0
After iteration 1 r1 = 60449131
After iteration 1 rk = 60449131
After iteration 1 sk = 0
After iteration 2initializations, q = 0
After iteration 2initializations, r0 = 0
After iteration 2initializations, r1 = 0
After iteration 2initializations, rk = 0
After iteration 2initializations, sk = 0
After iteration 2 r0 = 0
After iteration 2 r1 = 0
After iteration 2 rk = 0
After iteration 2 sk = 0

The expected output should be :

After initialization : 30292868
After iteration 0initializations, q = 0
After iteration 0initializations, r0 = 30292868
After iteration 0initializations, r1 = 60449131
After iteration 0initializations, rk = 30292868
After iteration 0initializations, sk = 1
After iteration 0 r0 = 60449131
After iteration 0 r1 = 30292868
After iteration 0 rk = 30292868
After iteration 0 sk = 1
After iteration 1initializations, q = 1
After iteration 1initializations, r0 = 60449131
After iteration 1initializations, r1 = 30292868
After iteration 1initializations, rk = 30156263
After iteration 1initializations, sk = -1
After iteration 1 r0 = 30292868
After iteration 1 r1 = 30156263
After iteration 1 rk = 30156263
After iteration 1 sk = -1
After iteration 2initializations, q = 1
After iteration 2initializations, r0 = 30292868
After iteration 2initializations, r1 = 30156263
After iteration 2initializations, rk = 136605
After iteration 2initializations, sk = 2
After iteration 2 r0 = 30156263
After iteration 2 r1 = 136605
After iteration 2 rk = 136605
After iteration 2 sk = 2
[..]

There should be 14 iterations. It fails at the second iteration. The r0 variable gets an unexpected 0 value. I thought at first that the problem came from the type inference not working correctly. rk and sk have to be BigInt (or int at least) since they get negative values. But as far as I understand the issue comes from before sk initialization. It might not like the q initialization inside the while loop, or something goes wrong with the value of r0.

[konsumlamm]

A simpler example that also fails is invmod(1.initBigInt, 2.initBigInt).

[konsumlamm]

The issue seems to be in the definition of rk and 'sk`. If you replace

      let
        q = r0 div r1
        rk = r0 - q * r1
        sk = s0 - q * s1

with

      let
        q = r0 div r1
        rk = if q.isZero: r0 else: r0 - q * r1
        sk = if q.isZero: s0 else: s0 - q * s1

then everything works.

[dlesnoff]

I tried to test on an equivalent function with only integers as parameters. This works well even with arc (and orc) GC. So the problem is specific to bigints.

func invmod*(a, modulus: int): int =
  ## Compute the modular inverse of `a` modulo `modulus`. 
  ## The return value is always in the range `[1, modulus-1]`
  runnableExamples:
    invmod(3, 7) = 5

  # extended Euclidean algorithm
  if modulus == 0:
    raise newException(DivByZeroDefect, "modulus must be nonzero")
  elif modulus < 0:
    raise newException(ValueError, "modulus must be strictly positive")
  elif a == 0:
    raise newException(DivByZeroDefect, "0 has no modular inverse")
  else:
    var
      r0 = ((a mod modulus) + modulus) mod modulus
      r1 = modulus
      s0 = 1
      s1 = 0
    while r1 > 0:
      let
        q = r0 div r1
        rk = r0 - q * r1
        sk = s0 - q * s1
      r0 = r1
      r1 = rk
      s0 = s1
      s1 = sk
    if r0 != 1:
      raise newException(ValueError, $a & " has no modular inverse modulo " & $modulus)
    result = ((s0 mod modulus) + modulus) mod modulus

echo invmod(30, 29)
when isMainModule:
  echo invmod(30, 29)