The microblog: 2021.03.21 06:17:26

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 are sometimes credited to Artjuhov ( 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.