2020.07.15 06:37:40 (1283259414556729344) from Daniel J. Bernstein, replying to "Bram Cohen🌱 (@bramcohen)" (1283158595215884288):
There's some batching of primality tests in Section 3 of https://cr.yp.to/papers.html#pqrsa (executive summary of this part: https://cr.yp.to/talks.html#2018.07.19), which becomes more and more effective if you have to test more and more candidates for primes. (Deterministic; no need for witnesses.)
2020.07.14 12:08:45 (1282980346024394754) from "OOTS (@AusDemStrom)", replying to "Steven Galbraith (@EllipticKiwi)" (1282955115058491393):
So for ~1000 Bit numbers you would expect ~128 kB of witnesses (give or take a factor of log(2)). If that's too much in your application, forget I said something :)
2020.07.14 21:43:59 (1283125108001796097) from "Bram Cohen🌱 (@bramcohen)", replying to "OOTS (@AusDemStrom)" (1282980346024394754):
For values that large almost all fermat witnesses work so hinting at which ones to try for the failures doesn't save much CPU
2020.07.14 22:59:35 (1283144132416999426) from "OOTS (@AusDemStrom)", replying to "Bram Cohen🌱 (@bramcohen)" (1283125108001796097):
You're right. Forgot about that/wasn't aware of it.
2020.07.14 23:57:03 (1283158595215884288) from "Bram Cohen🌱 (@bramcohen)", replying to "OOTS (@AusDemStrom)" (1283144132416999426):
It would be helpful if someone could find a logarithmic sized witness to the non-primality of list of numbers which only required logarithmically many multiplications for each value instead of the numbers's length