https://dl.acm.org/doi/pdf/10.1145/321328.321337?download=true
Unrecognizable Sets of Numbers (1966)
and he literally cites our boy rabin too
The technique described in this note enables one to show that certain sets cannot be recognized by finite state automata
GOD FUCKING DAMN IT IS THAT WHY AUTOMATA THEORY SUCKS TOO
We consider here only the binary representation, so as to avoid pompous statements, but the same results can be obtained for any radix by changing all 2’s to r’s in the sequel. We warn readers not to confuse the statement that the primes written in binary form are not a regular set with the trivial statement that the set of strings of prime length is not regular.
this is just the discrete log problem?????
If a_n is of odd length, 2k+1, it has the form a_n = b_n 2^{k+1] + d 2^k + b_n, where d is 0 or 1.
this also gives the q = 2p + 1 relation??? this is also an actual analysis of the appropriateness of discrete log as a CSPRNG???