2021.03.21 06:17:26 (1373503999182209030) from Daniel J. Bernstein, replying to "Аlекsеi Udovenko (@hellman1908)" (1373187820320342020):
Indeed, testing w^((n-1)/2) where w has Jacobi symbol -1 isn't much slower than the strong-probable-prime test; but it's more work to implement and has a different analysis. The question is whether the strong-probable-prime test should be credited to Artjuhov, or to Selfridge.
2021.03.20 08:40:52 (1373177706527952896) from Daniel J. Bernstein:
Request for math-history help from readers fluent in Russian: strong-probable-prime tests (see https://en.wikipedia.org/wiki/Probable_prime) are sometimes credited to Artjuhov (http://matwbn.icm.edu.pl/ksiazki/aa/aa12/aa12125.pdf) but the closest I've found there (middle of page 363) needs Jacobi symbols. Am I missing something?
2021.03.20 09:13:45 (1373185984247033857) from "Аlекsеi Udovenko (@hellman1908)":
I don't see page 363 in the pdf.. And what's wrong with Jacobi symbols?
2021.03.20 09:21:03 (1373187820320342020) from "Аlекsеi Udovenko (@hellman1908)", replying to "Аlекsеi Udovenko (@hellman1908)" (1373185984247033857):
Artjuhov does mention the algorithm for Jacobi symbols based on the quadratic reciprocity law, so factorization is not needed.