[Pkg-javascript-devel] Bug#926720: node-miller-rabin: FTBFS randomly (uses a non-prime to test the test)

[Jakub Wilk]

* Santiago Vila , 2019-04-09, 15:32:
AFAIK, this being a primality test, I assume the outcome is either "not 
prime" or "maybe prime", so the only way to test the test is by giving 
a known prime and expect "maybe prime" as output.


So: Why is the test calling mr.test with 221, which is not prime? (221 
= 13 x 17)


Correctly implemented Miller-Rabin test should have false positives only 
with negligible probability.


And why this fails randomly? Does the test perform random calculations 
internally and it's therefore not deterministic?


Yes.

Even in such case I don't see how a non-prime like 221 may help to 
catch obvious errors in a test suite for a primality test.


It's just proven to be useful.

Please restore the test and fix the code instead.

NB, it's been already reported upstream that the number of iterations 
this implementation chooses in not adequate:

https://github.com/indutny/miller-rabin/issues/9

--
Jakub Wilk

--
Pkg-javascript-devel mailing list
Pkg-javascript-devel@alioth-lists.debian.net
https://alioth-lists.debian.net/cgi-bin/mailman/listinfo/pkg-javascript-devel

[Pkg-javascript-devel] Bug#926720: node-miller-rabin: FTBFS randomly (uses a non-prime to test the test)

[Santiago Vila]

Package: src:node-miller-rabin
Version: 4.0.1-4
Severity: serious
Tags: ftbfs patch

Dear maintainer:

I tried to build this package in buster but it failed:


[...]
 debian/rules build-indep
dh build-indep --with nodejs
   dh_update_autotools_config -i
   dh_autoreconf -i
   dh_auto_test --buildsystem=nodejs -i
/bin/sh -e debian/tests/pkg-js/test


  Miller-Rabin
1) should test number for primality


  0 passing (93ms)
  1 failing

  1) Miller-Rabin
   should test number for primality:

  AssertionError [ERR_ASSERTION]: The expression evaluated to a falsy value:

  assert(!mr.test(new bn(221)))

  + expected - actual

  -false
  +true
  
  at Context. (test/api-test.js:8:5)
  at callFn (/usr/lib/nodejs/mocha/lib/runnable.js:354:21)
  at Test.Runnable.run (/usr/lib/nodejs/mocha/lib/runnable.js:346:7)
  at Runner.runTest (/usr/lib/nodejs/mocha/lib/runner.js:442:10)
  at /usr/lib/nodejs/mocha/lib/runner.js:560:12
  at next (/usr/lib/nodejs/mocha/lib/runner.js:356:14)
  at /usr/lib/nodejs/mocha/lib/runner.js:366:7
  at next (/usr/lib/nodejs/mocha/lib/runner.js:290:14)
  at Immediate._onImmediate (/usr/lib/nodejs/mocha/lib/runner.js:334:5)



dh_auto_test: /bin/sh -e debian/tests/pkg-js/test returned exit code 1
make: *** [debian/rules:8: build-indep] Error 1
dpkg-buildpackage: error: debian/rules build-indep subprocess returned exit 
status 2


The failure happens randomly. Sometimes it happens, sometimes it does not,
so the only recipe to reproduce it is to try many times.

I've put two build logs here:

https://people.debian.org/~sanvila/build-logs/node-miller-rabin/

AFAIK, this being a primality test, I assume the outcome is either
"not prime" or "maybe prime", so the only way to test the test is by
giving a known prime and expect "maybe prime" as output.

So: Why is the test calling mr.test with 221, which is not prime? (221 = 13 x 
17)

And why this fails randomly? Does the test perform random calculations
internally and it's therefore not deterministic? Even in such case I
don't see how a non-prime like 221 may help to catch obvious errors in
a test suite for a primality test.

Proposed patch below.

Thanks.

--- a/test/api-test.js
+++ b/test/api-test.js
@@ -5,7 +5,6 @@ var bn = require('bn.js');
 describe('Miller-Rabin', function() {
   it('should test number for primality', function() {
 this.timeout(8000);
-assert(!mr.test(new bn(221)));
 assert(mr.test(new bn(257)));
 
 var p = new bn('dba8191813fe8f51eaae1de70213aafede8f323f95f32cff' +

-- 
Pkg-javascript-devel mailing list
Pkg-javascript-devel@alioth-lists.debian.net
https://alioth-lists.debian.net/cgi-bin/mailman/listinfo/pkg-javascript-devel