commit 2c5c28e55c353c2008af80ab82e2f17afd3862ae
parent fb3353e1d5178c69f5c17b9ba472df4d84e726e9
Author: Jared Tobin <jared@jtobin.io>
Date: Tue, 12 Mar 2019 15:25:51 +1300
Add @p tests.
Adds exhaustive tests for 'feis' over small and medium input spaces.
Diffstat:
| M | src/internal/ob.js | | | 95 | ++++++++++++++++++++++--------------------------------------------------------- |
| M | test/med.js | | | 101 | +++++++++++++++++++++++++++++-------------------------------------------------- |
| M | test/small.js | | | 63 | ++++++++++++++++++++------------------------------------------- |
| D | test/tiny.js | | | 72 | ------------------------------------------------------------------------ |
4 files changed, 83 insertions(+), 248 deletions(-)
diff --git a/src/internal/ob.js b/src/internal/ob.js
@@ -107,6 +107,13 @@ const rynd = (n, arr) => {
return [ r, l.add(muk(raku[n], 2, r)).mod(p) ]
}
+const raku = [
+ 0xb76d5eed,
+ 0xee281300,
+ 0x85bcae01,
+ 0x4b387af7,
+]
+
/**
* Reverse round.
*
@@ -121,78 +128,17 @@ const rund = (n, arr) => {
return [ r, l.add(p).sub(muk(raku[n], 2, r).mod(p)).mod(p) ]
}
-const raku = [
- 0xb76d5eed,
- 0xee281300,
- 0x85bcae01,
- 0x4b387af7,
-]
-const Fe = (r, a, b, k, m) => {
- const c = fe(r, a, b, m)
+const Fe = (r, a, b, k, f, m) => {
+ const c = fe(r, a, b, f, m)
return (
c.lt(k)
? c
- : fe(r, a, b, c)
+ : fe(r, a, b, f, c)
)
}
-// this is the "official" version that seems to correspond to the paper
-// const fe = (r, a, b, m) => {
-// const loop = (j, ell, arr) => {
-// if (j === 0) {
-// return (
-// r % 2 !== 0
-// ? a.mul(ell).add(arr)
-// : a.mul(arr).add(ell)
-// )
-// } else {
-// const f = muk(raku[r - j], 2, arr)
-//
-// const tmp =
-// j % 2 !== 0
-// ? ell.add(f).mod(a)
-// : ell.add(f).mod(b)
-//
-// return loop(j - 1, arr, tmp)
-// }
-// }
-//
-// const L = m.mod(a)
-// const R = m.div(a)
-//
-// return loop(r, L, R)
-// }
-
-// const fe = (r, a, b, m) => {
-// const loop = (j, ell, arr) => {
-// console.log(`${ell.toString()} ${arr.toString()}`)
-// if (j === 0) {
-// return (
-// r % 2 !== 0
-// ? a.mul(ell).add(arr)
-// : a.mul(arr).add(ell)
-// )
-// } else {
-// const f = muk(raku[r - j], 2, arr)
-//
-// const tmp =
-// j % 2 !== 0
-// ? ell.add(f).mod(b)
-// : ell.add(f).mod(a)
-//
-// return loop(j - 1, arr, tmp)
-// }
-// }
-//
-// const L = m.mod(a)
-// const R = m.div(a)
-//
-// return loop(r, L, R)
-// }
-
-// NB (jtobin): test me exhaustively
-const fe = (r, a, b, m) => {
+const fe = (r, a, b, f, m) => {
const loop = (j, ell, arr) => {
if (j > r) {
return (
@@ -201,12 +147,12 @@ const fe = (r, a, b, m) => {
: a.mul(arr).add(ell)
)
} else {
- const f = muk(raku[r - j], 2, arr)
+ const eff = f(r - j, arr)
const tmp =
j % 2 !== 0
- ? ell.add(f).mod(a)
- : ell.add(f).mod(b)
+ ? ell.add(eff).mod(a)
+ : ell.add(eff).mod(b)
return loop(j + 1, arr, tmp)
}
@@ -218,8 +164,19 @@ const fe = (r, a, b, m) => {
return loop(1, L, R)
}
+const F = (j, arr) => {
+ const raku = [
+ 0xb76d5eed,
+ 0xee281300,
+ 0x85bcae01,
+ 0x4b387af7,
+ ]
+
+ return muk(raku[j], 2, arr)
+}
+
const feis = arg =>
- Fe(4, u_65535, u_65536, ux_ffff_ffff, new BN(arg))
+ Fe(4, u_65535, u_65536, ux_ffff_ffff, F, new BN(arg))
const fein = (arg) => {
const loop = (pyn) => {
diff --git a/test/med.js b/test/med.js
@@ -1,8 +1,11 @@
const BN = require('bn.js')
+const { expect } = require('chai')
-const u_a = new BN(255)
-const u_b = new BN(256)
-const u_c = new BN(65280)
+const { Fe } = require('../src/internal/ob')
+
+const u_a = new BN(Math.pow(2, 4) - 1)
+const u_b = new BN(Math.pow(2, 4))
+const u_c = u_a.mul(u_b)
const emm = [
0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15,
@@ -19,76 +22,46 @@ const emm = [
176, 177, 178, 179, 180, 181, 182, 183, 184, 185, 186, 187, 188, 189, 190, 191,
192, 193, 194, 195, 196, 197, 198, 199, 200, 201, 202, 203, 204, 205, 206, 207,
208, 209, 210, 211, 212, 213, 214, 215, 216, 217, 218, 219, 220, 221, 222, 223,
- 224, 225, 226, 227, 228, 229, 230, 231, 232, 233, 234, 235, 236, 237, 238, 239,
- 240, 241, 242, 243, 244, 245, 246, 247, 248, 249, 250, 251, 252, 253, 254, 255
+ 224, 225, 226, 227, 228, 229, 230, 231, 232, 233, 234, 235, 236, 237, 238, 239
]
-
const v0 = [
- 71, 235, 196, 202, 11, 143, 250, 178, 182, 116, 94, 252, 253, 255, 179, 192,
- 81, 44, 227, 152, 112, 90, 130, 43, 124, 103, 55, 75, 17, 147, 22, 224,
- 27, 93, 51, 248, 218, 145, 146, 141, 48, 155, 54, 133, 41, 142, 207, 206,
- 5, 236, 127, 110, 91, 176, 200, 216, 72, 23, 246, 251, 151, 122, 140, 219,
- 14, 177, 135, 225, 201, 74, 36, 106, 0, 40, 247, 9, 203, 190, 53, 221,
- 3, 121, 70, 132, 80, 46, 100, 181, 232, 197, 29, 62, 114, 213, 88, 153,
- 243, 244, 86, 230, 69, 76, 123, 95, 96, 191, 150, 61, 210, 171, 20, 229,
- 188, 159, 68, 19, 195, 125, 107, 59, 175, 49, 113, 242, 102, 128, 101, 105,
- 237, 223, 118, 167, 240, 117, 4, 226, 144, 108, 208, 162, 129, 131, 99, 111,
- 161, 77, 78, 185, 126, 205, 228, 233, 18, 194, 120, 249, 56, 85, 34, 154,
- 98, 97, 241, 52, 7, 204, 16, 166, 58, 73, 234, 119, 50, 163, 12, 84,
- 1, 214, 189, 238, 215, 82, 156, 66, 160, 33, 245, 115, 28, 24, 35, 57,
- 173, 254, 172, 83, 168, 169, 64, 239, 165, 184, 139, 109, 148, 32, 26, 217,
- 134, 39, 164, 174, 231, 222, 136, 47, 30, 199, 38, 211, 87, 25, 13, 138,
- 193, 8, 170, 104, 212, 60, 89, 180, 10, 149, 45, 67, 15, 209, 186, 37,
- 183, 65, 157, 158, 21, 92, 31, 198, 6, 42, 63, 2, 79, 137, 220, 187
- ].map(x => new BN(x))
-
-const eff = m => v0[m]
+ 106, 54, 57, 110, 216, 157, 90, 138, 148, 205, 214, 229, 25, 104, 217, 70, 16, 91,
+ 180, 108, 189, 176, 67, 213, 154, 194, 122, 199, 136, 140, 36, 56, 87, 112, 8, 34,
+ 14, 171, 227, 160, 211, 228, 37, 121, 119, 65, 132, 45, 224, 61, 141, 59, 82, 77,
+ 74, 20, 130, 181, 123, 186, 166, 42, 81, 172, 105, 196, 44, 135, 156, 192, 116, 39,
+ 7, 40, 84, 169, 193, 131, 88, 142, 24, 128, 38, 222, 197, 218, 159, 30, 145, 58,
+ 53, 85, 62, 49, 158, 86, 72, 210, 225, 52, 73, 149, 143, 195, 124, 179, 219, 9,
+ 200, 64, 51, 48, 26, 234, 27, 232, 231, 153, 190, 133, 109, 126, 6, 178, 183, 151,
+ 117, 46, 161, 43, 185, 236, 127, 89, 223, 23, 69, 68, 209, 139, 19, 33, 79, 164,
+ 207, 50, 144, 31, 134, 170, 29, 107, 220, 184, 47, 103, 206, 201, 175, 125, 35, 114,
+ 146, 10, 55, 152, 98, 1, 168, 215, 28, 237, 101, 17, 155, 118, 83, 147, 115, 100,
+ 233, 4, 66, 0, 150, 203, 22, 5, 174, 11, 18, 177, 3, 165, 99, 167, 202, 212,
+ 163, 182, 80, 162, 71, 97, 12, 60, 113, 221, 204, 41, 226, 187, 63, 230, 2, 188,
+ 208, 76, 191, 235, 93, 13, 111, 238, 78, 198, 21, 92, 95, 94, 96, 102, 120, 239,
+ 32, 129, 15, 173, 137, 75
+ ]
-// NOTE this appears to be a correct implementation
-const fe = (r, a, b, m) => {
- const loop = (j, ell, arr) => {
- if (j > r) {
- return (
- r % 2 !== 0
- ? a.mul(ell).add(arr)
- : a.mul(arr).add(ell)
- )
- } else {
- const f = eff(arr)
+const eff = (_, m) => new BN(v0[m])
- const tmp =
- j % 2 !== 0
- ? ell.add(f).mod(a)
- : ell.add(f).mod(b)
+const feis = arg =>
+ Fe(4, u_a, u_b, u_c, eff, new BN(arg))
- return loop(j + 1, arr, tmp)
- }
- }
+// test
- const L = m.mod(a)
- const R = m.div(a)
+describe('feis -- medium input space', () => {
- return loop(1, L, R)
-}
+ const perm = emm.map(x => feis(x).toString())
+ const distincts = perm.filter((x, i, a) => a.indexOf(x) === i)
-const Fe = (r, a, b, k, m) => {
- const c = fe(r, a, b, m)
- return (
- c.lt(k)
- ? c
- : fe(r, a, b, c)
- )
-}
+ it('produces distinct outputs', () => {
+ expect(distincts.length).to.equal(perm.length)
+ })
-const feis = arg =>
- Fe(4, u_a, u_b, u_c, new BN(arg))
+ it('permutes the input space', () => {
+ expect(perm.reduce((acc, x) => emm.includes(parseInt(x)) && acc, true))
+ .to.equal(true)
+ })
-module.exports = {
- eff,
- emm,
- fe,
- Fe,
- feis
-}
+})
diff --git a/test/small.js b/test/small.js
@@ -1,10 +1,11 @@
const BN = require('bn.js')
+const { expect } = require('chai')
-const u_a = new BN(3)
-const u_b = new BN(4)
-const u_c = new BN(12)
+const { Fe } = require('../src/internal/ob')
-const emm = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11]
+const u_a = new BN(Math.pow(2, 2) - 1)
+const u_b = new BN(Math.pow(2, 2))
+const u_c = u_a.mul(u_b)
const eff = (j, m) => {
let v0 = [5, 9, 2, 6, 4, 0, 8, 7, 1, 10, 3, 11]
@@ -23,49 +24,25 @@ const eff = (j, m) => {
)
}
-// NOTE this appears to be a correct implementation
-const fe = (r, a, b, m) => {
- const loop = (j, ell, arr) => {
- if (j > r) {
- return (
- r % 2 !== 0
- ? a.mul(ell).add(arr)
- : a.mul(arr).add(ell)
- )
- } else {
- const f = eff(4 - j - 1, arr)
+const feis = arg =>
+ Fe(4, u_a, u_b, u_c, eff, new BN(arg))
- const tmp =
- j % 2 !== 0
- ? ell.add(f).mod(a)
- : ell.add(f).mod(b)
+// test
- return loop(j + 1, arr, tmp)
- }
- }
+describe('feis -- small input space', () => {
- const L = m.mod(a)
- const R = m.div(a)
+ const emm = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11]
+ const perm = emm.map(x => feis(x).toString())
+ const distincts = perm.filter((x, i, a) => a.indexOf(x) === i)
- return loop(1, L, R)
-}
+ it('produces distinct outputs', () => {
+ expect(distincts.length).to.equal(perm.length)
+ })
-const Fe = (r, a, b, k, m) => {
- const c = fe(r, a, b, m)
- return (
- c.lt(k)
- ? c
- : fe(r, a, b, c)
- )
-}
+ it('permutes the input space', () => {
+ expect(perm.reduce((acc, x) => emm.includes(parseInt(x)) && acc, true))
+ .to.equal(true)
+ })
-const feis = arg =>
- Fe(4, u_a, u_b, u_c, new BN(arg))
+})
-module.exports = {
- eff,
- emm,
- fe,
- Fe,
- feis
-}
diff --git a/test/tiny.js b/test/tiny.js
@@ -1,72 +0,0 @@
-const BN = require('bn.js')
-
-const u_a = new BN(3)
-const u_b = new BN(4)
-const u_c = new BN(12)
-
-const emm = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11]
-
-const eff = (j, m) => {
- let v0 = [5, 9, 2, 6, 4, 0, 8, 7, 1, 10, 3, 11]
- let v1 = [2, 1, 0, 3, 10, 4, 9, 5, 7, 11, 6, 8]
- let v2 = [10, 6, 7, 1, 0, 11, 3, 9, 5, 2, 8, 4]
- let v3 = [11, 0, 3, 5, 9, 8, 6, 10, 4, 1, 2, 7]
-
- return (
- j === 0
- ? new BN(v0[m])
- : j === 1
- ? new BN(v1[m])
- : j === 2
- ? new BN(v2[m])
- : new BN(v3[m])
- )
-}
-
-// NOTE this appears to be a correct implementation
-const fe = (r, a, b, m) => {
- const loop = (j, ell, arr) => {
- if (j > r) {
- return (
- r % 2 !== 0
- ? a.mul(ell).add(arr)
- : a.mul(arr).add(ell)
- )
- } else {
- const f = eff(4 - j - 1, arr)
-
- const tmp =
- j % 2 !== 0
- ? ell.add(f).mod(a)
- : ell.add(f).mod(b)
-
- return loop(j + 1, arr, tmp)
- }
- }
-
- const L = m.mod(a)
- const R = m.div(a)
-
- return loop(1, L, R)
-}
-
-const Fe = (r, a, b, k, m) => {
- const c = fe(r, a, b, m)
- return (
- c.lt(k)
- ? c
- : fe(r, a, b, c)
- )
-}
-
-const feis = arg =>
- Fe(4, u_a, u_b, u_c, new BN(arg))
-
-module.exports = {
- eff,
- emm,
- fe,
- Fe,
- feis
-}
-
