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.

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. 
@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},
     publisher = {mathdoc},
     volume = {15},
     number = {3},
     year = {2003},
     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
PB  - mathdoc
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
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DM_2003_15_3_a2/
%G ru
%F DM_2003_15_3_a2
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/

[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