Geodesic
On the complexity of testing for the primality of a number by homogeneous structures
Diskretnaya Matematika, Tome 15 (2003) no. 3, pp. 54-65 
A. M. Stepanenkov. On the complexity of testing for the primality of a number by homogeneous structures. Diskretnaya Matematika, Tome 15 (2003) no. 3, pp. 54-65. http://geodesic.mathdoc.fr/item/DM_2003_15_3_a2/
@article{DM_2003_15_3_a2,
     author = {A. M. Stepanenkov},
     title = {On the complexity of testing for the primality of a number by homogeneous structures},
     journal = {Diskretnaya Matematika},
     pages = {54--65},
     year = {2003},
     volume = {15},
     number = {3},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/DM_2003_15_3_a2/}
}
TY  - JOUR
AU  - A. M. Stepanenkov
TI  - On the complexity of testing for the primality of a number by homogeneous structures
JO  - Diskretnaya Matematika
PY  - 2003
SP  - 54
EP  - 65
VL  - 15
IS  - 3
UR  - http://geodesic.mathdoc.fr/item/DM_2003_15_3_a2/
LA  - ru
ID  - DM_2003_15_3_a2
ER  - 
%0 Journal Article
%A A. M. Stepanenkov
%T On the complexity of testing for the primality of a number by homogeneous structures
%J Diskretnaya Matematika
%D 2003
%P 54-65
%V 15
%N 3
%U http://geodesic.mathdoc.fr/item/DM_2003_15_3_a2/
%G ru
%F DM_2003_15_3_a2

Voir la notice de l'article provenant de la source Math-Net.Ru

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.

[1] Kudryavtsev V. B., Aleshin S. V., Podkolzin A. S., Vvedenie v teoriyu avtomatov, Nauka, Moskva, 1985 | MR

[2] Kudryavtsev V. B., Podkolzin A. S., Bolotov A. A., Osnovy teorii odnorodnykh struktur, Nauka, Moskva, 1990 | MR

[3] Vasilenko O. N., “Sovremennye sposoby proverki prostoty chisel. Obzor”, Kibern. sb., 25, 162–188 | MR | Zbl