`divRem_vartime` doesn't seem to work

[bkomuves]

In constantine/math_arbitrary_precision/arithmetic/limbs_divmod_vartime there is a divRem_vartime function, which I assume is supposed to implement arbitrary precision integer division with remainder.

(I couldn't find any other function implementing this operation)

However, this appears to be completely broken. For example with inputs a = 2^64 + 3 and b = 1234567 I get the result q = 0 and r = 3

Example code:

import pkg/constantine/platforms/abstractions
import pkg/constantine/math/arithmetic/bigints
import pkg/constantine/math/io/io_bigints
import pkg/constantine/math_arbitrary_precision/arithmetic/limbs_divmod_vartime

proc printSecretArray(xs: array[4, SecretWord]) = 
  echo " - limbs[0] = " & $uint64(xs[0])
  echo " - limbs[1] = " & $uint64(xs[1])
  echo " - limbs[2] = " & $uint64(xs[2])
  echo " - limbs[3] = " & $uint64(xs[3])

proc main() =

  var x : BigInt[256]
  # let _ = x.fromDecimal("18446744073709551613")     # 2^64 - 3   // this works
  let _ = x.fromDecimal("18446744073709551619")       # 2^64 + 3   // this doesn't

  var y : BigInt[256]
  let _ = y.fromDecimal("1234567")

  let a: array[4, SecretWord] = x.limbs
  let b: array[4, SecretWord] = y.limbs
  var q: array[4, SecretWord]
  var r: array[4, SecretWord]
  
  let res = divRem_vartime(q,r,a,b)
  echo "function returns: " & $res

  echo "quotient limbs:"
  printSecretArray(q)
  echo "remainder limbs:"
  printSecretArray(r)

  let qbig: BigInt[256] = BigInt[256](limbs: q)  
  let rbig: BigInt[256] = BigInt[256](limbs: r)

  echo "x = " & toDecimal(x)
  echo "y = " & toDecimal(y)
  echo "q = " & toDecimal(qbig)
  echo "r = " & toDecimal(rbig)

  var mverybig: BigInt[512] 
  prod[512,256,256](mverybig,qbig,y)       # q*y

  var mbig: BigInt[256]
  copyTruncatedFrom[256,512](mbig,mverybig)

  var reconstr_x: BigInt[256] = rbig
  reconstr_x += mbig                       # q*y + r

  echo "q * y           = " & toDecimal(mbig)
  echo "reconstructed x = " & toDecimal(reconstr_x)

  echo "OK = " & $(bool(x == reconstr_x))

when isMainModule:
  main()

[mratsim]

Indeed,

That function only returns the correct remainder and there is an issue with the quotient hence why it's not public in https://github.com/mratsim/constantine/blob/master/constantine/lowlevel_bigints.nim or used or tested anywhere. And it also doesn't have a constant-time counterpart.

Unfortunately I didn't have the time to fix it then and there was no use case for arbitrary bigint division.

The error is likely either here:

constantine/constantine/math_arbitrary_precision/arithmetic/limbs_divmod_vartime.nim

Lines 57 to 70 in 74faa5f

	# m0 has its high bit set. (a0, a1)/m0 fits in a limb.
	# Get a quotient q, at most we will be 2 iterations off
	# from the true quotient
	var q: SecretWord # Estimate quotient
	if bool(a0 == m0): # if a_hi == divisor
	q = MaxWord # quotient = MaxWord (0b1111...1111)
	elif bool(a0.isZero()) and
	bool(a1 < m0): # elif q == 0, true quotient = 0
	q = Zero
	return q
	else:
	var r: SecretWord
	div2n1n_vartime(q, r, a0, a1, m0) # else instead of being of by 0, 1 or 2
	q -= One # we return q-1 to be off by -1, 0 or 1

or

constantine/constantine/math_arbitrary_precision/arithmetic/limbs_divmod_vartime.nim

Lines 90 to 103 in 74faa5f

	# Fix quotient, the true quotient is either q-1, q or q+1
	#
	# if carry < q or carry == q and overM we must do "a -= M"
	# if carry > hi (negative result) we must do "a += M"
	if bool(carry > hi):
	var c = Carry(0)
	for i in 0 ..< a.len:
	addC(c, a[i], a[i], M[i], c)
	q -= One
	elif overM or bool(carry < hi):
	var b = Borrow(0)
	for i in 0 ..< a.len:
	subB(b, a[i], a[i], M[i], b)
	q += One

[bkomuves]

ok, i may look into fixing this if i find the time (which is not likely in the next 2 weeks)