Рассматривается система линейных булевых уравнений с искажённой правой частью, истинное решение которой имеет заданный вес, не зависящий от числа неизвестных в системе. Предлагается вероятностный алгоритм нахождения этого решения, имеющий меньшую временную сложность по сравнению с методом максимума правдоподобия. В отличие от известных алгоритмов, обладающих указанным свойством, предложенный алгоритм использует только операции сравнения и (поразрядного и арифметического) сложения двоичных целых чисел, что позволяет применять его на практике в случае, когда другие алгоритмы оказываются менее эффективными.
Скачать электронную версию публикации
Загружен, раз: 69
- Title Быстрый алгоритм восстановления истинного решения фиксированного веса системы линейных булевых уравнений с искажённой правой частью
- Headline Быстрый алгоритм восстановления истинного решения фиксированного веса системы линейных булевых уравнений с искажённой правой частью
- Publesher
Tomsk State University - Issue Прикладная дискретная математика 2(20)
- Date:
- DOI
Ключевые слова
probabilistic algorithm, system of Boolean linear equations with noised right-hand side, вероятностный алгоритм. Введение, система булевых уравнений с искаженной правой частьюАвторы
Ссылки
Ширяев А. Н. Вероятность: учеб. пособие для вузов. М.: Наука, 1989. 640 с.
Ахо А., Хопкрофт Дж., Ульман Дж. Построение и анализ вычислительных алгоритмов: пер. с англ. М.: Мир, 1979. 535 с.
Рейнгольд Э., Нивергельт Ю., Део Н. Комбинаторные алгоритмы. Теория и практика: пер. с англ. М.: Мир, 1980. 476 с.
GolicJ. Cryptanalysis of alleged A5 stream cipher // Advances in Cryptology. Proc. EUROCRYPT'97. Springer Verlag, 1997. P. 239-255.
Babbage S. H. Improved "exhaustive search" attacks on stream ciphers // European Convention on Security and Detection, Brighton, May 16-18, 1995. P. 161-166.
Де Брёйн Н. Г. Асимптотические методы в анализе: пер. с англ. М.: ИЛ, 1961. 247 с.
Indyk P. and Motwani R. Approximate nearest neighbors: towards removing the curse of dimensionality // Proc. Symp. on Theory of Computing. New York, NY, USA: ACM, 1998. P. 604-613.
Dolev D., Harari Y., and Parnas M. Finding the neighborhood of a query in a dictionary // Proc. 2nd Israel Symp. on Theory and Computing Systems, Natanya, Israel, June 7-9, 1993. P. 33-42.
Greene D., Parnas M., and Yao F. Multi-index hashing for information retrieval // Proc. 35th Annual IEEE Symp. on the Foundations of Computer Science, Santa Fe, New Mexico, November 20-22, 1994. P. 722-731.
Алексейчук А. Н., Грязнухин А. Ю. Метод восстановления систематических линейных кодов по наборам искаженных кодовых слов // Прикладная радиоэлектроника. 2013. T. 12. №2. С. 128-132.
Andoni А. and Indyk P. Near-optimal hashing algorithms for approximate nearest neighbor in high dimension // Proc. 47th Symp. on Foundations of Computer Science, Berkeley, California, October 21-24, 2006. P. 459-468.
Valiant G. Finding correlations in subquadratic time, with applications to learning parities and juntas // Proc. 53rd Annual IEEE Symp. on the Foundations of Computer Science, New Brunswick, New Jersey, October 2-23, 2012. P. 11-20.
Grigorescu E., Reysin L., and Vempala S. On noise-tolerant learning of sparse parities and related problems // Proc. 22nd Intern. Conf. of Algorithmic Learning Theory. Berlin, Heidelberg: Springer Verlag, 2011. P. 413-424.
Балакин Г. В. Введение в теорию случайных систем уравнений // Труды по дискретной математике. М.: ТВП, 1997. T. 1. C. 1-18.
Быстрый алгоритм восстановления истинного решения фиксированного веса системы линейных булевых уравнений с искажённой правой частью | Прикладная дискретная математика. 2013. № 2(20).
Скачать полнотекстовую версию
Полнотекстовая версияЗагружен, раз: 193