Repository: ionspin/kotlin-multiplatform-bignum
Pull request #25 (2019-04-23 21:07:43)

Modular integer fixes


Patch:
diff --git a/README.md b/README.md
index e624181..1acd95f 100644
--- a/README.md
+++ b/README.md
@@ -428,12 +428,9 @@ Donald E. Knuth
 3rd Edition
 ```
 
-``
+```
 Refinement of a newton reciprocal algorithm for arbitrary precision numbers
-Yiping Cheng,
- Ze Liu
-
-
+Yiping Cheng, Ze Liu
 ```
 And many other blogs and posts scattered over the internet.
 
diff --git a/bignum/src/commonMain/kotlin/com/ionspin/kotlin/bignum/integer/BigInteger.kt b/bignum/src/commonMain/kotlin/com/ionspin/kotlin/bignum/integer/BigInteger.kt
index ddff777..418c211 100644
--- a/bignum/src/commonMain/kotlin/com/ionspin/kotlin/bignum/integer/BigInteger.kt
+++ b/bignum/src/commonMain/kotlin/com/ionspin/kotlin/bignum/integer/BigInteger.kt
@@ -275,6 +275,10 @@ class BigInteger internal constructor(wordArray: WordArray, val sign: Sign) : Bi
 
     }
 
+    /**
+     * Returns the remainder of division operation. Uses truncating division, which means
+     * that the sign of remainder will be same as sign of dividend
+     */
     override fun remainder(other: BigInteger): BigInteger {
         if (other.isZero()) {
             throw ArithmeticException("Division by zero! $this / $other")
@@ -310,7 +314,7 @@ class BigInteger internal constructor(wordArray: WordArray, val sign: Sign) : Bi
         val remainder = if (result.second == arithmetic.ZERO) {
             ZERO
         } else {
-            BigInteger(result.second, sign)
+            BigInteger(result.second, this.sign)
         }
         return Pair(
             quotient,
@@ -359,7 +363,7 @@ class BigInteger internal constructor(wordArray: WordArray, val sign: Sign) : Bi
 
     fun modInverse(modulo: BigInteger) : BigInteger {
         if (gcd(modulo) != ONE) {
-            throw ArithmeticException("BigInteger is not invertible. This and modulo are not relatively prime (coprime)")
+            throw ArithmeticException("BigInteger is not invertible. This and modulus are not relatively prime (coprime)")
         }
         var u = ONE
         var w = ZERO
@@ -376,6 +380,20 @@ class BigInteger internal constructor(wordArray: WordArray, val sign: Sign) : Bi
         return u
     }
 
+    /**
+     * Returns an always positive remainder of division operation
+     */
+    infix fun mod(modulo : BigInteger) : BigInteger {
+        val result = this % modulo
+        return if (result < 0) {
+            result + modulo
+        } else {
+            result
+        }
+    }
+
+
+
     fun compare(other: BigInteger): Int {
         if (isZero() && other.isZero()) return 0
         if (other.isZero() && this.sign == Sign.POSITIVE) return 1
@@ -582,7 +600,7 @@ class BigInteger internal constructor(wordArray: WordArray, val sign: Sign) : Bi
         return creator.fromBigInteger(this)
     }
 
-//    fun modularInverse(modulo : BigInteger) : BigInteger {
+//    fun modularInverse(modulus : BigInteger) : BigInteger {
 //
 //    }
 
diff --git a/bignum/src/commonMain/kotlin/com/ionspin/kotlin/bignum/modular/ModularBigInteger.kt b/bignum/src/commonMain/kotlin/com/ionspin/kotlin/bignum/modular/ModularBigInteger.kt
index 3738f8f..ca25372 100644
--- a/bignum/src/commonMain/kotlin/com/ionspin/kotlin/bignum/modular/ModularBigInteger.kt
+++ b/bignum/src/commonMain/kotlin/com/ionspin/kotlin/bignum/modular/ModularBigInteger.kt
@@ -21,6 +21,7 @@ import com.ionspin.kotlin.bignum.BigNumber
 import com.ionspin.kotlin.bignum.CommonBigNumberOperations
 import com.ionspin.kotlin.bignum.ModularQuotientAndRemainder
 import com.ionspin.kotlin.bignum.integer.BigInteger
+import com.ionspin.kotlin.bignum.integer.BigInteger.Companion.ONE
 import com.ionspin.kotlin.bignum.integer.Sign
 
 /**
@@ -34,10 +35,16 @@ import com.ionspin.kotlin.bignum.integer.Sign
 @ExperimentalUnsignedTypes
 class ModularBigInteger @ExperimentalUnsignedTypes constructor(
     val residue : BigInteger,
-    val modulo : BigInteger,
+    val modulus : BigInteger,
     private val creator: BigNumber.Creator<ModularBigInteger>) : BigNumber<ModularBigInteger>,
         CommonBigNumberOperations<ModularBigInteger>
 {
+
+    init {
+        if (modulus.sign == Sign.NEGATIVE) {
+            throw ArithmeticException("Modulus must be a positive number")
+        }
+    }
     companion object {
         fun creatorForModulo(modulo: ULong) : BigNumber.Creator<ModularBigInteger> = creatorForModulo(BigInteger.fromULong(modulo))
         fun creatorForModulo(modulo: UInt) : BigNumber.Creator<ModularBigInteger> = creatorForModulo(BigInteger.fromUInt(modulo))
@@ -98,6 +105,7 @@ class ModularBigInteger @ExperimentalUnsignedTypes constructor(
                         Sign.NEGATIVE -> result + modulo
                         Sign.ZERO -> BigInteger.ZERO
                     }
+                    return result
                 }
 
 
@@ -113,51 +121,54 @@ class ModularBigInteger @ExperimentalUnsignedTypes constructor(
     }
 
     private fun assertSameModulo(other : ModularBigInteger) {
-        if (this.modulo != other.modulo) {
-            throw RuntimeException("Different moduli! This $modulo\n Other ${other.modulo}")
+        if (this.modulus != other.modulus) {
+            throw RuntimeException("Different moduli! This $modulus\n Other ${other.modulus}")
         }
     }
 
     override fun add(other: ModularBigInteger): ModularBigInteger {
         assertSameModulo(other)
-        return ModularBigInteger((residue + other.residue) % modulo, modulo, creator)
+        return ModularBigInteger((residue + other.residue) % modulus, modulus, creator)
     }
 
     override fun subtract(other: ModularBigInteger): ModularBigInteger {
         assertSameModulo(other)
-        return ModularBigInteger((residue - other.residue) % modulo, modulo, creator)
+        return ModularBigInteger((residue - other.residue) % modulus, modulus, creator)
     }
 
     override fun multiply(other: ModularBigInteger): ModularBigInteger {
         assertSameModulo(other)
-        return ModularBigInteger((residue * other.residue) % modulo, modulo, creator)
+        return ModularBigInteger((residue * other.residue) % modulus, modulus, creator)
     }
 
     override fun divide(other: ModularBigInteger): ModularBigInteger {
         assertSameModulo(other)
-        val quotient = this.residue / other.residue
-        val result = quotient % modulo
-        return ModularBigInteger(result, modulo, creator)
+        val modInverse = other.residue.modInverse(modulus)
+        val result = (modInverse * residue) % modulus
+        return ModularBigInteger(result, modulus, creator)
+
     }
 
     override fun remainder(other: ModularBigInteger): ModularBigInteger {
         assertSameModulo(other)
+        checkIfDivisible(other)
         val remainder = this.residue % other.residue
-        val result = remainder % modulo
-        return ModularBigInteger(result, modulo, creator)
+        val result = remainder % modulus
+        return ModularBigInteger(result, modulus, creator)
     }
 
     override fun divideAndRemainder(other: ModularBigInteger): Pair<ModularBigInteger, ModularBigInteger> {
         assertSameModulo(other)
-        val quotientAndRemainder = this.residue divrem  other.residue
-        val quotient = quotientAndRemainder.quotient % modulo
-        val remainder = quotientAndRemainder.remainder % modulo
-        return Pair(ModularBigInteger(quotient, modulo, creator), ModularBigInteger(remainder, modulo, creator))
+        checkIfDivisible(other)
+        val quotientAndRemainder = this.residue divrem other.residue
+        val quotient = quotientAndRemainder.quotient % modulus
+        val remainder = quotientAndRemainder.remainder % modulus
+        return Pair(ModularBigInteger(quotient, modulus, creator), ModularBigInteger(remainder, modulus, creator))
     }
 
     fun inverse() : ModularBigInteger {
-        val inverse = residue.modInverse(modulo)
-        return ModularBigInteger(inverse, modulo, creator)
+        val inverse = residue.modInverse(modulus)
+        return ModularBigInteger(inverse, modulus, creator)
     }
 
     fun compare(other: ModularBigInteger): Int {
@@ -169,18 +180,16 @@ class ModularBigInteger @ExperimentalUnsignedTypes constructor(
         return residue.isZero()
     }
 
-    /**
-     *
-     */
-    // TODO Is this really a negation of a modular number? It's true that it will be congruent for the module, and it's
-    // also true that sign will be opposite, but still, all of our modular representations are 0 < a < modulo, so it doesn't
-    // really make sense
+
     override fun negate(): ModularBigInteger {
-        return when (residue.sign) {
-            Sign.ZERO -> this
-            Sign.POSITIVE -> ModularBigInteger(residue - modulo, modulo, creator)
-            Sign.NEGATIVE -> ModularBigInteger(residue + modulo, modulo, creator)
-        }
+        return this
+        //Code below doesn't make sense as negated number if original was positive, would be the same number we started
+        //from. Also a ModularBigInteger is never negative
+//        return when (residue.sign) {
+//            Sign.ZERO -> this
+//            Sign.POSITIVE -> ModularBigInteger(residue - modulus, modulus, creator)
+//            Sign.NEGATIVE -> ModularBigInteger(residue + modulus, modulus, creator)
+//        }
 
     }
 
@@ -189,19 +198,19 @@ class ModularBigInteger @ExperimentalUnsignedTypes constructor(
     }
 
     override fun pow(exponent: ModularBigInteger): ModularBigInteger {
-        return ModularBigInteger(residue.pow(exponent.residue) % modulo, modulo, creator)
+        return ModularBigInteger(residue.pow(exponent.residue) % modulus, modulus, creator)
     }
 
     fun pow(exponent: BigInteger): ModularBigInteger {
-        return ModularBigInteger(residue.pow(exponent) % modulo, modulo, creator)
+        return ModularBigInteger(residue.pow(exponent) % modulus, modulus, creator)
     }
 
     override fun pow(exponent: Long): ModularBigInteger {
-        return ModularBigInteger(residue.pow(exponent) % modulo, modulo, creator)
+        return ModularBigInteger(residue.pow(exponent) % modulus, modulus, creator)
     }
 
     override fun pow(exponent: Int): ModularBigInteger {
-        return ModularBigInteger(residue.pow(exponent) % modulo, modulo, creator)
+        return ModularBigInteger(residue.pow(exponent) % modulus, modulus, creator)
     }
 
     override fun signum(): Int {
@@ -250,7 +259,7 @@ class ModularBigInteger @ExperimentalUnsignedTypes constructor(
     }
 
     fun toStringWithModulo(base : Int = 10) : String {
-        return residue.toString(base) + " mod " + modulo.toString(base)
+        return residue.toString(base) + " mod " + modulus.toString(base)
     }
 
     infix fun divrem(other: ModularBigInteger): ModularQuotientAndRemainder {
@@ -262,6 +271,12 @@ class ModularBigInteger @ExperimentalUnsignedTypes constructor(
         return residue
     }
 
+    private fun checkIfDivisible(other : ModularBigInteger) {
+        if (other.residue.gcd(modulus) != ONE) {
+            throw ArithmeticException("BigInteger is not invertible. This and modulus are not relatively prime (coprime)")
+        }
+    }
+
 
 
 


Test patch:
diff --git a/bignum/src/commonTest/kotlin/com/ionspin/kotlin/bignum/integer/BigIntegerTest.kt b/bignum/src/commonTest/kotlin/com/ionspin/kotlin/bignum/integer/BigIntegerTest.kt
index e1e2759..3c941da 100644
--- a/bignum/src/commonTest/kotlin/com/ionspin/kotlin/bignum/integer/BigIntegerTest.kt
+++ b/bignum/src/commonTest/kotlin/com/ionspin/kotlin/bignum/integer/BigIntegerTest.kt
@@ -168,4 +168,49 @@ BigIntegerTest {
         assertTrue { a.gcd(c) == 2.toBigInteger() }
     }
 
+    @Test
+    fun divisionSign() {
+        assertTrue {
+            val a = 7.toBigInteger()
+            val b = 3.toBigInteger()
+            val (q,r) = a divrem b
+            a == (q * b + r)
+        }
+        assertTrue {
+            val a = -7.toBigInteger()
+            val b = 3.toBigInteger()
+            val (q,r) = a divrem b
+            a == (q * b + r)
+        }
+        assertTrue {
+            val a = 7.toBigInteger()
+            val b = -3.toBigInteger()
+            val (q,r) = a divrem b
+            a == (q * b + r)
+        }
+        assertTrue {
+            val a = -7.toBigInteger()
+            val b = -3.toBigInteger()
+            val (q,r) = a divrem b
+            a == (q * b + r)
+        }
+    }
+
+    @Test
+    fun testModInfix() {
+        assertTrue {
+            val a = -152.toBigInteger()
+            val b = a.mod(100.toBigInteger())
+            b == 48.toBigInteger()
+        }
+
+        assertTrue {
+            val a = 152.toBigInteger()
+            val b = a.mod(100.toBigInteger())
+            b == 52.toBigInteger()
+        }
+
+
+    }
+
 }
\ No newline at end of file
diff --git a/bignum/src/jvmTest/kotlin/com/ionspin/kotlin/bignum/integer/BigIntegerJvmTest.kt b/bignum/src/jvmTest/kotlin/com/ionspin/kotlin/bignum/integer/BigIntegerJvmTest.kt
index 056ce84..485f24a 100644
--- a/bignum/src/jvmTest/kotlin/com/ionspin/kotlin/bignum/integer/BigIntegerJvmTest.kt
+++ b/bignum/src/jvmTest/kotlin/com/ionspin/kotlin/bignum/integer/BigIntegerJvmTest.kt
@@ -19,6 +19,7 @@ package com.ionspin.kotlin.bignum.integer
 
 import com.ionspin.kotlin.bignum.integer.BigInteger.Companion.ZERO
 import com.ionspin.kotlin.bignum.integer.base63.toJavaBigInteger
+import com.ionspin.kotlin.bignum.modular.ModularBigInteger
 import kotlinx.coroutines.GlobalScope
 import kotlinx.coroutines.Job
 import kotlinx.coroutines.launch
@@ -46,6 +47,7 @@ class BigIntegerJvmTest {
             aInverse.toJavaBigInteger() == aJavaInverse
         }
     }
+
     //TODO need to implement better testcase, need better coprime generation
     @Test
     fun testRandomModInverse() {
@@ -90,4 +92,33 @@ class BigIntegerJvmTest {
             inverse.toJavaBigInteger().compareTo(javaInverse) == 0
         }
     }
+
+    @Test
+    fun testModPow() {
+        val creator = ModularBigInteger.creatorForModulo(10)
+
+        assertTrue {
+            val a = creator.fromInt(-3)
+            val aPow = a.pow(3)
+            val javaBigIntPow = (-3).toBigInteger().toJavaBigInteger()
+                .modPow(
+                    3.toBigInteger().toJavaBigInteger(),
+                    10.toBigInteger().toJavaBigInteger()
+                )
+            aPow.residue.toJavaBigInteger().compareTo(javaBigIntPow) == 0
+        }
+
+        assertTrue {
+            val a = creator.fromInt(3)
+            val aPow = a.pow(3)
+            val javaBigIntPow = (3).toBigInteger().toJavaBigInteger()
+                .modPow(
+                    3.toBigInteger().toJavaBigInteger(),
+                    10.toBigInteger().toJavaBigInteger()
+                )
+            aPow.residue.toJavaBigInteger().compareTo(javaBigIntPow) == 0
+        }
+    }
+
+
 }
\ No newline at end of file
diff --git a/bignum/src/jvmTest/kotlin/com/ionspin/kotlin/bignum/modular/ModularBigIntegerDivisionTest.kt b/bignum/src/jvmTest/kotlin/com/ionspin/kotlin/bignum/modular/ModularBigIntegerDivisionTest.kt
index bf77ea2..2b91aa1 100644
--- a/bignum/src/jvmTest/kotlin/com/ionspin/kotlin/bignum/modular/ModularBigIntegerDivisionTest.kt
+++ b/bignum/src/jvmTest/kotlin/com/ionspin/kotlin/bignum/modular/ModularBigIntegerDivisionTest.kt
@@ -20,6 +20,7 @@ package com.ionspin.kotlin.bignum.modular
 import com.ionspin.kotlin.bignum.integer.BigInteger
 import com.ionspin.kotlin.bignum.integer.Sign
 import com.ionspin.kotlin.bignum.integer.base63.toJavaBigInteger
+import com.ionspin.kotlin.bignum.integer.toBigInteger
 import kotlinx.coroutines.GlobalScope
 import kotlinx.coroutines.Job
 import kotlinx.coroutines.launch
@@ -37,7 +38,7 @@ import kotlin.test.assertTrue
 @ExperimentalUnsignedTypes
 class ModularBigIntegerDivisionTest {
     @Test
-    fun testRandomModularMultiplication() {
+    fun testRandomModularDivision() {
         val seed = 1
         val random = Random(seed)
         val jobList: MutableList<Job> = mutableListOf()
@@ -72,11 +73,19 @@ class ModularBigIntegerDivisionTest {
         }
     }
 
+    @Test
+    fun specificTest() {
+        val creator = ModularBigInteger.creatorForModulo(15)
+        val a = creator.fromInt(-10)
+        val b = creator.fromInt(4)
+        singleDivisionTest(a, b)
+    }
+
     fun singleDivisionTest(a : ModularBigInteger, b : ModularBigInteger) {
         assertTrue {
-            val result = a divrem  b
-            val javaResultQuotient = (a.residue.toJavaBigInteger() / b.residue.toJavaBigInteger()).mod(a.modulo.toJavaBigInteger())
-            val javaResultRemainder = (a.residue.toJavaBigInteger() % b.residue.toJavaBigInteger()).mod(a.modulo.toJavaBigInteger())
+            val result = a divrem b
+            val javaResultQuotient = (a.residue.toJavaBigInteger() / b.residue.toJavaBigInteger()).mod(a.modulus.toJavaBigInteger())
+            val javaResultRemainder = (a.residue.toJavaBigInteger() % b.residue.toJavaBigInteger()).mod(a.modulus.toJavaBigInteger())
             result.quotient.residue.toJavaBigInteger() == javaResultQuotient &&
                     result.remainder.residue.toJavaBigInteger() == javaResultRemainder
         }
diff --git a/bignum/src/jvmTest/kotlin/com/ionspin/kotlin/bignum/modular/ModularBigIntegerMultiplication.kt b/bignum/src/jvmTest/kotlin/com/ionspin/kotlin/bignum/modular/ModularBigIntegerMultiplication.kt
index d543fd9..0ecf747 100644
--- a/bignum/src/jvmTest/kotlin/com/ionspin/kotlin/bignum/modular/ModularBigIntegerMultiplication.kt
+++ b/bignum/src/jvmTest/kotlin/com/ionspin/kotlin/bignum/modular/ModularBigIntegerMultiplication.kt
@@ -75,7 +75,7 @@ class ModularBigIntegerMultiplication {
     fun singleMultiplicationTest(a : ModularBigInteger, b : ModularBigInteger) {
         assertTrue {
             val result = a * b
-            val javaResult = (a.residue.toJavaBigInteger() * b.residue.toJavaBigInteger()).mod(a.modulo.toJavaBigInteger())
+            val javaResult = (a.residue.toJavaBigInteger() * b.residue.toJavaBigInteger()).mod(a.modulus.toJavaBigInteger())
             result.residue.toJavaBigInteger() == javaResult
         }
     }