On the complexity of testing for the primality of a number by homogeneous structures

In this paper, it is shown that under Turing coding of natural numbers primality of a number is tested by homogeneous structures in time asymptotically equal to the half of the length of the code.
The research was supported by the Russian Foundation of Basic Research, grant 02–01–00162.