3 ms·
Relevant code (from https://gitlab.com/swisspost-evoting/crypto-primitives/crypto-primitives/-/raw/master/Crypto-Primitives-Specification.pdf https://gitlab.com
by Someone 4y ago
Relevant code (from https://gitlab.com/swisspost-evoting/crypto-primitives/crypto-primitives/-/raw/master/Crypto-Primitives-Specification.pdf 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 4y agoSpecifically 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_test https://en.wikipedia.org/wiki/Baillie%E2%80%93PSW_primality_...
- threatripper 4y agoLet 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 4y agoIt’s not easily testable if it’a pseudocode that hasn’t been implemented yet.