Riesel Sieve Project

версія українською

авторы - Sunni , nikelong

Riesel Sieve Project

Ссылки:

• Официальный сайт проекта
• Официальная статистика по команде Ukraine
• Расширеная статистика по команде Ukraine
• Обсуждение у нас на форуме
• Обсуждение на Русском форуме
• Сайт о простых числах

Цель:
Простое число – это целое положительное число (больше единицы), которое не делится ни на одно другое (кроме самого себя и единицы) без остатка.

В 1956 Hans Riesel доказал, что cуществует бесконечно много нечетных чисел k такие, что k*2^n-1 составное при любом n > 1.
Он также доказал, что k = 509203 такое число (подобные числа стали называть числами Ризеля).

Осталось доказать гипотезу, что k = 509203 - минимальное подобное число.
Для этого надо доказать, что для любого нечетного k < 509203 существует какое-то число m, что k*2^m-1 простое число.

Доказательство простоты числа k*2^n-1 рабивается на две фазы:

1. поиск маленького делителя (Sieve - просеивание)
2. доказательство числа на простоту (LLR).

Алгоритм Sieve это первый этап поиска простых чисел (каждый найденный фактор - минус одно или несколько сочетаний k и n из рассматриваемого диапазона).

Алгоритм LLR (второй этап) - проверяет простое число или нет.

Для того чтобы иметь возможность получить LLR блоки нужно совершить два действия:

1. Нужно избавиться от оптимизированных приложений, а точнее от файла app_info.xml , а то он будет неразрешать закачивать новое llr приложение (поэтому встает выбор:  или оптимизированное приложение Sieve или LLR).
2. В вашем аккаунте ("You account") в RieselSieve preferences разрешить "Run test applications?". 
   Разработчики рекомендуют запускать LLR только на компьютерах с процессорами intel, т.е. создать "предпочтение" (home, work или school) в нём разрешить "Run test applications?" и задать его для машин с интеловскими процессорами.
   
   

Фактор.

Фактор - это делитель. Если найден делитель, то число не простое (а составное) и не надо запускать модуль LLR, который долго работает. А найти делитель, особенно относительно маленький, можно намного быстрее.
Если найдено простое число, то число к выбывает из числа претендентов. Подробнее (но на английском) описано здесь.

Зачем их ищут?

Большие простые числа используются в системах криптозащиты. Например в Украинском стандарте по шифрованию ДСТУ 4145-2002 "Информационные технологии. Криптографическая защита информации. Цифровая подпись, которая основывается на элиптичных кривых. Формирование и проверка" используются длинные простые числа. И это только один пример где эти числа используются!

Известно, также что большие простые числа используются в NASA...

Факты:

• Проект существует с 2005.
• Графического интерфейса у проекта нет.
• Существует версия только для windows (для linux в стадии тестирования).
• Официальные оптимизированые ядра для расчетов можно загрузить здесь. Они дают небольшую, но всё-же прибавку во времени расчетов.
• У заданий ВСЕГДА одно и тоже время расчетов, такого беспредела как в проекте ABC нет (тоесть не такого - пишет, что задание на 2 часа, а считается 20 часов).
• Так-же, дополнительные очки начисляются за найденые факторы.

Табличка со статистикой.

Существуют официальные сигнатуры (например, чтобы вставить себе в подпись на форуме). URL картинки выглядит так:

http://boinc.aqstats.com/sigrs/xxxx.png

где ХХХХ - Ваш ID в проекте. Чтобы его узнать зайдите к себе в профиль и найдите "Account number Used in URLs".

Клиент:

• В базе для каждого k перечисляются значения n, для которых надо искать делители.
• В задании (файл wu_хххххх.txt) указывается верхний и нижний диапазон делителей (разница 500 000 000).
• В процессе выполнения задания для каждой пары (k, n) проверяются делители из заданого диапазона.
• За каждый найденый делитель добавляется 3 кредита.

Ресурсоемкость: