SAT@home

Материал из Википедии — свободной энциклопедии
SAT@Home
Платформа BOINC
Объём загружаемого ПО 10 МБ
Объём загружаемых данных задания 2 КБ
Объём отправляемых данных задания 20 КБ
Объём места на диске 10 МБ
Используемый объём памяти 80 МБ
Графический интерфейс нет
Среднее время расчёта задания до 5 часов
Deadline 10 дней
Возможность использования
GPU
 нет

SAT@home — российский проект

флопс[2]. Участвовать в проекте может любой желающий, обладающий компьютером с выходом в Интернет, установив на него программу BOINC
.

История проекта

Вычисления в рамках проекта стартовали[3] в сентябре 2011 года с решения задачи криптоанализа генератора A5/1, применяющегося в GSM-связи. По известному фрагменту ключевого потока требовалось определить инициализирующую последовательность, то есть начальное заполнение регистров

генератора. Целью проводимых вычислений являлось доказательство применимости SAT-подхода к решению данной задачи для тех случаев, когда другими методами (например, с использованием радужных таблиц) отыскание решения невозможно. В результате расчетов к маю 2012 года были решены 10 тестовых задач криптоанализа A5/1[4]
.

Первая пара ортогональных диагональных латинских квадратов порядка 10, найденная в проекте SAT@Home пользователями tanos и notnA

В июне 2012 года был запущен новый эксперимент, целью которого являлся поиск ортогональных пар диагональных латинских квадратов порядка 9. К августу 2012 года было найдено 134 пары, что доказало применимость данного подхода к поставленной задаче. Следом за этим был запущен эксперимент по поиску ортогональных пар диагональных латинских квадратов порядка 10. В результате вычислений на данный момент найдены 13 пар латинских квадратов[4], которые не совпадают с известными парами, приведенными в статье[5].

Научные достижения

2012 год
  • Показана применимость SAT-подхода для криптоанализа поточных шифров на примере генератора A5/1.
  • Показана применимость SAT-подхода для нахождения ортогональных пар диагональных латинских квадратов. Найдено 5 ортогональных пар порядка 10[4].
2013 год
  • Найдено 12 ортогональных пар диагональных латинских квадратов порядка 10[4].

Судя по всему, проект прекратил своё существование в 2016 году.

Примечания

  1. ↑ SAT@Home. Дата обращения: 26 декабря 2012. Архивировано 21 декабря 2012 года.
  2. ↑ SAT@home detailed stats. Дата обращения: 5 сентября 2013. Архивировано 11 августа 2013 года.
  3. ↑ Архив новостей SAT@home. Дата обращения: 26 декабря 2012. Архивировано из оригинала 4 января 2013 года.
  4. ↑ 1 2 3 4 Найденные решения SAT@home. Дата обращения: 26 декабря 2012. Архивировано из оригинала 21 декабря 2012 года.
  5. ↑ Brown et al. Completion of the Spectrum of Orthogonal Diagonal Latin Squares. Lecture notes in pure and applied mathematics. 1992. Vol. 139. Pp 43–49.

Ссылки

Источник — https://ru.wikipedia.org/w/index.php?title=SAT@home&oldid=120675297