BSU Bulletin. Mathematics, Informatics
Bibliographic description:
АВОUТ А TEST OF EMBEDDING WIТH МARGIN FOR DISCRETE SEQUENCES // BSU Bulletin. Mathematics, Informatics. - 2018. №4. . - С. 3-15.
Title:
АВОUТ А TEST OF EMBEDDING WIТH МARGIN FOR DISCRETE SEQUENCES
Financing:
Codes:
Annotation:
Sequence Х is а subsequence with margin d о[ sequence У if Х is constructed from У Ьу deleting non-adjacent segments consisted of at most d letters. 1n this case we saу that Х can Ье embedded into У with margin d. Тhе article presents а sequential test for the hypothesis of embedding with margin d for discrete random sequences over а finite alphabet and study its properties. Тhе probaЬility of type I error (the probaЬility of re jection of true hypothesis of embedding with margin) of the constructed test is equal to zero. We derive an expression for the probaЬility of type II error under the altemative hypothesis that the discrete sequences under consideration consist of mutually inde pendent random variaЫes with uniform distributions on finite alphaЬet. Wе find out the average number of letters of the embedded sequence used Ьу test before the decision is made under the altemative hypothesis. Тhе complexity of the proposed procedure is proportional to the length of the embedded sequence under true hypothesis of embed ding with margin and is smaller under the altemative hypothesis which is less than complexity oftotal testing Ьу order ofmagnitude. We have presented numerical values of the probaЬility of type II error and the average number of used letters for different values of d and the alphabet size.
Keywords:
dense embedding; embedding with margin; sequential test; hypothesis of independence; probaЬilities of type I and type II errors; discrete random sequence.
List of references:
Golic J. Dj. Constrained Embedding ProbaЬility for Two Binary Strings. SIAM J Discrete Math. 1996. V. 9. No. 3. Рр. 360-364. DOI: 10.1137/S0895479894246917
Mikhailov V. G., Mezhennaya N. М. Otsenki dlya veroyatnosti plotnogo vloz heniya odnoi diskretnoi posledovatelnosti v druguyu [Bounds for the ProbaЬility of а Dense Embedding ofOne Discrete Sequence into Another]. Diskretnaya matematika - Discrete Mathematics. 2005. V. 15. No. 4. Рр. 377-386. DOI: 10.1515/156939205774464864
Mezhennaya N. М., Мikhailov V. G. Nizhnie otsenki dlya veroyatnosti vloz heniya s proizvolnym dopuskom [Lower Bounds for ProbaЬilities of Embedding with ArЬitrary Margin]. Vestnik Moskovskogo gosudarstvennogo tekhnicheskogo univer siteta im. N Е. Ваитапа. Ser. Estestvennye nauki - Bulletin of Ваитап Moscow State Technical University. Ser. Natural Sciences. 2012. No. 2. Рр. 3-11.
Donovan D. М., Lefevre J., Simpson L. А Discussion of Constrained Binary Embeddings with Applications to Cryptanalysis of lrregularly Clocked Stream Ciphers. Balakrishnan R., Veni Madhavan С. (Eds.) Discrete Mathematics. Proceedings of the lntemational Conference on Discrete Mathematics. Bangalore: lndian lnstitute of Sci ence, 2006. Рр. 73-86.
Golic J. Dj. Embedding ProbaЬilities for the Altemating Step Generator. IEEE Trans. lnform. Theory. 2005. V. 51(7). Рр. 2543-2553. DOI: 10.1109/ТIТ.2005.850114
Annknecht F., Mikhalev V. On Lightweight Stream Ciphers with Shorter lnter nal States. Leander G. (Ed.) Fast Software Encryption. Proceedings of 22nd lntema tional Workshop, FSE 2015. lstanbul: Springer-Verlag, 2015. Рр. 451-470. DOI: 10.1007/978-3-662-48116-5 22
Asimi У., Amghar А , Asimi А , Sadqi У. New Random Generator of а Safe Cryptographic Salt per Session. l nt. J Netw. Secur. 2016. V. 18. No. 3. Рр. 445-453.
El-Razouk Н., Reyhani-Masoleh А , Gong G. New lmplementations ofthe WG Stream Cipher. IEEE Transactions оп Very Large Scale lntegration (VLSI) Systems. 2014. V. 22. No. 9. Рр. 1865-1878. DOI: 10. l 109/ТVLSl.2013.2280092
Ма W., Feng D. Clock-Controlled Key-Stream Generator and lts Cryptographic Properties. Front. Electr. Electron. Eng. China. 2008. V. 3. No. 3. Рр. 327-332. DOI: 10.1007/sl 1460-008-0014-6
Jiang S., Tang Z., Wang М. On the CLD Attack to а Statistical Model ofa Кеу Stream Generator. lnt. J Netw. Secur. 2016. V. 18. No. 5. Рр. 987-992.
Deepthi Р. Р., Deepa S. J., Sathidevi Р. S. Design and Analysis of а Нighly Se cure Stream Cipher Based on Linear Feedback Shift Register. Computer & Electrical Engineering. 2009. V. 35. No. 2. Рр. 235-243. DOI: 10.1016/j.compeleceng.2008.06.005
Shuvaev D. V. О podposledovatelnostyakh markovskikh posledovatelnostei [On Subsequences of Markovian Sequences]. Matematicheskie voprosy kriptografii - Mathematical Aspects of Cryptography. 2016. V. 7. No. 4. Рр. 133-142. DOI: 10.4213/mvk208
Comblnatorial Pattern Matching. Proceedings of СРМ 2013, LNCS 7922.
J. Fischer, Р. Sanders (Eds.). Bad Herrenalb: Springer-Verlag, 2013. 259 р. DOI: 10.1007/978-3-642-38905-4
Reinert G., Waterman М. S. On the Length of the Longest Exact Position Match in а Random Sequence. IEEEIACM Transactions оп Computational Biology and Bioinformatics. 2007. V. 4. No. 1. Рр. 153-156. DOI: 10.1109/ТСВВ.2007.1023
Saparov А Yu., Beltyukov А Р. Primenenie regulyamykh vyrazhenii v raspoznavanii matematicheskikh tekstov [Application of Regular Expressions in the Recognition of Mathematical Text]. Vestnik Udmurtskogo universiteta. Matematika. Mekhanika. Kompyuternye nauki - Bulletin of Udmurt University. Mathematics. Me chanics. Computer Science. 2012. No. 2. Рр. 63-73. DOI: 10.20537/vml 20206
lvchenko G. 1., Medvedev Yu. 1. Vvedenie v matematicheskuyu statistiku [In
troduction to Mathematical Statistics]. Moscow: LКI РuЫ., 2010. 600 р.
Mezhennaya N. М. О proverke gipotezy о plotnom vlozhenii dlya diskretnykh sluchainykh posledovatelnostei [About Testing the Dense Embedding Hypotesis for Discrete Random Sequences]. Vestnik Buryatskogo gosudarstvennogo universiteta. Matematika, lnformatika - Bulletin of Buryat State University. Mathematics, lnfor matics. 2017. No. 4. Рр. 9-20. DOI: 10.18101/2304-5728-2017-4-9-20
Proverka gipotezy о vlozhenii s dopuskom dlya diskretnykh sluchainykh posle dovatelnostei [Testing of Embedding with Margin for Discrete Random Sequences].
Prikladnaya diskretnaya matematika. Prilozhenie - Applied Discrete Mathematics. Supplement. 2018. V. 11. Рр. 12-14. DOI: 10.17223/2226308Х/11/3
Feller W. Ап lntroduction to Probabllity Theory and lts Applications. 2nd Ed.
New-York: John Wiley and Sons РuЫ., 1968. V. 1. 528 р.
Feller W. Ап lntroduction to Probabllity Theory and lts Applications. 2nd Ed. New-York: John Wiley and Sons, 1971. V. 2. 704 р.
Prokhorov Yu. V., Ponomarenko L. S. Lektsii ро teorii veroyatnostei i mate maticheskoi statistike [Lectures on ProbaЬility Theory and Mathematical Statistics]. 2nd Ed. Moscow: Moscow State University РuЫ., 2012. 256 р.
Rogozin В. А А Remark to а Theorem due to W. Feller. Тheory Probab. Appl.
1969. V. 14. No. 3. Рр. 554-555. DOI: 10.1137/1114070
Mogulskii А А, Rogozin В. А Lokalnaya teorema dlya momenta dostizheniya fiksirovannogo urovnya sluchainym Ыuzhdaniem [А Local Theorem for the First Нit ting Time of а Fixed Level Ьу а Random Walk]. Matematicheskie trudy - Siberian Advances in Mathematics. 2005. V. 8. No. 1. Рр. 43-70.
Mikhailov V. G., Mezhennaya N. М. Otsenki dlya veroyatnosti plotnogo vloz heniya odnoi diskretnoi posledovatelnosti v druguyu [Bounds for the ProbaЬility of а Dense Embedding ofOne Discrete Sequence into Another]. Diskretnaya matematika - Discrete Mathematics. 2005. V. 15. No. 4. Рр. 377-386. DOI: 10.1515/156939205774464864
Mezhennaya N. М., Мikhailov V. G. Nizhnie otsenki dlya veroyatnosti vloz heniya s proizvolnym dopuskom [Lower Bounds for ProbaЬilities of Embedding with ArЬitrary Margin]. Vestnik Moskovskogo gosudarstvennogo tekhnicheskogo univer siteta im. N Е. Ваитапа. Ser. Estestvennye nauki - Bulletin of Ваитап Moscow State Technical University. Ser. Natural Sciences. 2012. No. 2. Рр. 3-11.
Donovan D. М., Lefevre J., Simpson L. А Discussion of Constrained Binary Embeddings with Applications to Cryptanalysis of lrregularly Clocked Stream Ciphers. Balakrishnan R., Veni Madhavan С. (Eds.) Discrete Mathematics. Proceedings of the lntemational Conference on Discrete Mathematics. Bangalore: lndian lnstitute of Sci ence, 2006. Рр. 73-86.
Golic J. Dj. Embedding ProbaЬilities for the Altemating Step Generator. IEEE Trans. lnform. Theory. 2005. V. 51(7). Рр. 2543-2553. DOI: 10.1109/ТIТ.2005.850114
Annknecht F., Mikhalev V. On Lightweight Stream Ciphers with Shorter lnter nal States. Leander G. (Ed.) Fast Software Encryption. Proceedings of 22nd lntema tional Workshop, FSE 2015. lstanbul: Springer-Verlag, 2015. Рр. 451-470. DOI: 10.1007/978-3-662-48116-5 22
Asimi У., Amghar А , Asimi А , Sadqi У. New Random Generator of а Safe Cryptographic Salt per Session. l nt. J Netw. Secur. 2016. V. 18. No. 3. Рр. 445-453.
El-Razouk Н., Reyhani-Masoleh А , Gong G. New lmplementations ofthe WG Stream Cipher. IEEE Transactions оп Very Large Scale lntegration (VLSI) Systems. 2014. V. 22. No. 9. Рр. 1865-1878. DOI: 10. l 109/ТVLSl.2013.2280092
Ма W., Feng D. Clock-Controlled Key-Stream Generator and lts Cryptographic Properties. Front. Electr. Electron. Eng. China. 2008. V. 3. No. 3. Рр. 327-332. DOI: 10.1007/sl 1460-008-0014-6
Jiang S., Tang Z., Wang М. On the CLD Attack to а Statistical Model ofa Кеу Stream Generator. lnt. J Netw. Secur. 2016. V. 18. No. 5. Рр. 987-992.
Deepthi Р. Р., Deepa S. J., Sathidevi Р. S. Design and Analysis of а Нighly Se cure Stream Cipher Based on Linear Feedback Shift Register. Computer & Electrical Engineering. 2009. V. 35. No. 2. Рр. 235-243. DOI: 10.1016/j.compeleceng.2008.06.005
Shuvaev D. V. О podposledovatelnostyakh markovskikh posledovatelnostei [On Subsequences of Markovian Sequences]. Matematicheskie voprosy kriptografii - Mathematical Aspects of Cryptography. 2016. V. 7. No. 4. Рр. 133-142. DOI: 10.4213/mvk208
Comblnatorial Pattern Matching. Proceedings of СРМ 2013, LNCS 7922.
J. Fischer, Р. Sanders (Eds.). Bad Herrenalb: Springer-Verlag, 2013. 259 р. DOI: 10.1007/978-3-642-38905-4
Reinert G., Waterman М. S. On the Length of the Longest Exact Position Match in а Random Sequence. IEEEIACM Transactions оп Computational Biology and Bioinformatics. 2007. V. 4. No. 1. Рр. 153-156. DOI: 10.1109/ТСВВ.2007.1023
Saparov А Yu., Beltyukov А Р. Primenenie regulyamykh vyrazhenii v raspoznavanii matematicheskikh tekstov [Application of Regular Expressions in the Recognition of Mathematical Text]. Vestnik Udmurtskogo universiteta. Matematika. Mekhanika. Kompyuternye nauki - Bulletin of Udmurt University. Mathematics. Me chanics. Computer Science. 2012. No. 2. Рр. 63-73. DOI: 10.20537/vml 20206
lvchenko G. 1., Medvedev Yu. 1. Vvedenie v matematicheskuyu statistiku [In
troduction to Mathematical Statistics]. Moscow: LКI РuЫ., 2010. 600 р.
Mezhennaya N. М. О proverke gipotezy о plotnom vlozhenii dlya diskretnykh sluchainykh posledovatelnostei [About Testing the Dense Embedding Hypotesis for Discrete Random Sequences]. Vestnik Buryatskogo gosudarstvennogo universiteta. Matematika, lnformatika - Bulletin of Buryat State University. Mathematics, lnfor matics. 2017. No. 4. Рр. 9-20. DOI: 10.18101/2304-5728-2017-4-9-20
Proverka gipotezy о vlozhenii s dopuskom dlya diskretnykh sluchainykh posle dovatelnostei [Testing of Embedding with Margin for Discrete Random Sequences].
Prikladnaya diskretnaya matematika. Prilozhenie - Applied Discrete Mathematics. Supplement. 2018. V. 11. Рр. 12-14. DOI: 10.17223/2226308Х/11/3
Feller W. Ап lntroduction to Probabllity Theory and lts Applications. 2nd Ed.
New-York: John Wiley and Sons РuЫ., 1968. V. 1. 528 р.
Feller W. Ап lntroduction to Probabllity Theory and lts Applications. 2nd Ed. New-York: John Wiley and Sons, 1971. V. 2. 704 р.
Prokhorov Yu. V., Ponomarenko L. S. Lektsii ро teorii veroyatnostei i mate maticheskoi statistike [Lectures on ProbaЬility Theory and Mathematical Statistics]. 2nd Ed. Moscow: Moscow State University РuЫ., 2012. 256 р.
Rogozin В. А А Remark to а Theorem due to W. Feller. Тheory Probab. Appl.
1969. V. 14. No. 3. Рр. 554-555. DOI: 10.1137/1114070
Mogulskii А А, Rogozin В. А Lokalnaya teorema dlya momenta dostizheniya fiksirovannogo urovnya sluchainym Ыuzhdaniem [А Local Theorem for the First Нit ting Time of а Fixed Level Ьу а Random Walk]. Matematicheskie trudy - Siberian Advances in Mathematics. 2005. V. 8. No. 1. Рр. 43-70.
Article.pdf