Geodesic
Reachability problem for continuous piecewise-affine mappings of a~circle having degree~2
Prikladnaya Diskretnaya Matematika. Supplement, no. 7 (2014), pp. 26-28.

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

For the continuous piecewise-affine mappings of a circle into itself having degree 2, the algorithmic decidability of the point-to-point reachability problem is proved. All these piecewise-affine mappings are topological conjugate to chaotic mapping $E_2\colon\mathbb{R/Z\to R/Z}$ where $E_2(x)=2x\pmod1$. It is known that the orbit $O(x)$ of $E_2$ is uniformly distributed for almost all $x\in\mathbb{R/Z}$, i.e. $O(x)$ is chaotic. But none of the “almost all” $x$ is representable in a computer because they all are infinite real numbers. The behaviour complexity of $E_2$ lies in the complexity of its initial state. Thus the mathematical fact that $E_2$ is chaotic is vacuous from the computer science point of view. But from the proof of the main result of this work, it follows that each continuous piecewise-affine mapping with rational coefficients that conjugate to $E_2$ shows chaotic behaviour not only for real but also for some rational states. It makes them interesting in problems of cryptographic information transformation.
Keywords: deterministic chaos, cryptography, piecewise-affine mapping, reachability problem. 
@article{PDMA_2014_7_a9,
     author = {O. M. Kurganskyy},
     title = {Reachability problem for continuous piecewise-affine mappings of a~circle having degree~2},
     journal = {Prikladnaya Diskretnaya Matematika. Supplement},
     pages = {26--28},
     publisher = {mathdoc},
     number = {7},
     year = {2014},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/PDMA_2014_7_a9/}
}
TY  - JOUR
AU  - O. M. Kurganskyy
TI  - Reachability problem for continuous piecewise-affine mappings of a~circle having degree~2
JO  - Prikladnaya Diskretnaya Matematika. Supplement
PY  - 2014
SP  - 26
EP  - 28
IS  - 7
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/PDMA_2014_7_a9/
LA  - ru
ID  - PDMA_2014_7_a9
ER  - 
%0 Journal Article
%A O. M. Kurganskyy
%T Reachability problem for continuous piecewise-affine mappings of a~circle having degree~2
%J Prikladnaya Diskretnaya Matematika. Supplement
%D 2014
%P 26-28
%N 7
%I mathdoc
%U http://geodesic.mathdoc.fr/item/PDMA_2014_7_a9/
%G ru
%F PDMA_2014_7_a9
O. M. Kurganskyy. Reachability problem for continuous piecewise-affine mappings of a~circle having degree~2. Prikladnaya Diskretnaya Matematika. Supplement, no. 7 (2014), pp. 26-28. http://geodesic.mathdoc.fr/item/PDMA_2014_7_a9/

[1] Ptitsyn N. V., Prilozhenie teorii determinirovannogo khaosa v kriptografii, Izd-vo MGTU im. N. E. Baumana, M., 2002, 80 pp.

[2] Savchenko A. Ya., Kovalev A. M., Kozlovskii V. A., Scherbak V. F., “Inverse dynamical systems in secure communication and its discrete analogs for information transfer”, Proc. NDES, 2003, 112–116

[3] Delvenne J.-C., “What is a universal computing machine?”, Appl. Math. Comput., 215:4 (2009), 1368–1374 | DOI | MR | Zbl

[4] Kurganskyy O., Potapov I., Sancho-Caparrini F., “Reachability problems in low-dimensional iterative maps”, Int. J. Found. Comput. Sci., 19:4 (2008), 935–951 | DOI | MR | Zbl

[5] Asarin E., Mysore V., Pnueli A., Schneider G., “Low dimensional hybrid systems – decidable, undecidable, don't know”, Inform. Comput., 211 (2012), 138–159 | DOI | MR | Zbl