[Someone]

Relevant code (from https://gitlab.com/swisspost-evoting/crypto-primitives/crypt...):

  𝑠𝑝 ← 8530092
     ▷ I.e. 0b100000100010100010101100: for all primes 𝑝 ≤ 23,
       TestBit(𝑠𝑝, 𝑝) = true
  if 𝑛 ≤ 23 then
    ▷ Quick check for small values, simpler and faster
      than testing equality on each option
    return TestBit(𝑠𝑝, 𝑛)
  end if
  if ¬TestBit(𝑛, 0) then return ⊥
    ▷ I.e. 𝑛 is even and, as per line 2, 𝑛 > 2 thus composite
  end if

And it indeed is a bug. The function guarantees to return false “if the number can be determined to be composite” and true for all primes, so it should err in only one way.

I would further improve the code by having it shortcut for all primes smaller than 31 (adding 29 and 31) or 63.

[mkl]

Specifically a bug in that constant sp, which should have a 1 in bit 19 like it does for the other primes ≤ 23.

This is step 1 of the algorithm they're using: https://en.wikipedia.org/wiki/Baillie%E2%80%93PSW_primality_...

[threatripper]

Let me repeat if I understand it right:

* The function will return True for all primes.

* The function will return False if the number is detected as a composite by some tests.

* The function can return True or False for all other numbers.

* For numbers<=23 they implemented a shortcut using a lookup table which is implemented as bits in a number.

* The bit for number 19 is wrong. It returns false for a prime number which violates "return True for all prime numbers".

This is indeed quite shoddy programming for such an essential and easily testable piece of software.

[vmilner]

It’s not easily testable if it’a pseudocode that hasn’t been implemented yet.