0.1. КАК ИЩУТ ПРОСТЫЕ ЧИСЛА (В НАШИ ДНИ) ?
Процедура довольно нехитрая, обычно состоит из 2 или 3 стадий:
* Просеивание намеченных кандидатов в Простые числа.
* Факторизация каждого из оставшихся кандидатов.
* Тест простоты для всех, кто не отсеялся ранее.
Теперь расскажу про каждый этап подробнее, а в конце заметки приведу свой живой пример.
1. ПРОСЕИВАНИЕ НАМЕЧЕННЫХ КАНДИДАТОВ В ПРОСТЫЕ ЧИСЛА (SIEVING)
В первую очередь, мы должны выбрать, Простые числа какого вида нас интересуют, и какой диапазон мы возьмем на проверку. Если взять слишком маленький, в нем в итоге может не оказаться ни одного Простого числа. Если же взять слишком огромный, то могут возникнуть неудобства с компьютером, т.к. процесс может занять слишком много памяти. Чаще всего я выбираю 10-миллионный диапазон, хотя в некоторых проектах оптимальнее оказывается еще более протяженный.
Итак, на этом этапе осуществляется отсеивание потенциальных кандидатов в Простые числа. Специальная программа ("сито", sieve) перебирает малые делители от 2 до некоторого P. Те кандидаты, которые делятся на очередной малый делитель, благополучно отсеиваются, исключаясь из дальнейшего рассмотрения (отсев работает по принципу Решета Эратосфена, более детально опишу в будущих выпусках).
Значение верхней границы P для малых делителей определяется самим искателем. Важно задать его в разумных пределах, чтобы, с одной стороны, не оставить слишком много составных чисел-претендентов, с другой - не слишком затягивать этап.
Оптимально продолжать до тех пор, пока среднее время отсева одного кандидата не окажется сопоставимо с длительностью финального теста простоты. Также можно закончить стадию по времени (допустим, отсеиваем 3 часа, потом движемся дальше), или по количеству оставшихся кандидатов (допустим, из 10-миллионного диапазона остается 500 тыс. претендентов - красивое круглое число, между прочим)!
Обычно на первой стадии удается избавиться от большей части составных чисел. Количество оставшихся претендентов сокращается в разы, а то и на порядки!
2. ФАКТОРИЗАЦИЯ КАЖДОГО ИЗ ОСТАВШИХСЯ КАНДИДАТОВ (FACTORING)
Вот эта фаза применяется не всегда. По сути - это попытка отыскать более крупный делитель, до которого было бы нелегко, а то и вовсе невозможно добраться полным перебором (даже за время существования Вселенной). Но и здесь искателям иногда везет
Разумеется, эти крупные делители берутся не с потолка. Уже разработано много методов факторизации (factoring, разложение числа на множители) для дополнительного отсева, казалось бы, непоколебимых гигантов.
Например, мы помним со школьных времен формулу разности квадратов: A^2 - B^2 = (A + B)*(A - B) - если нам вдруг удастся найти такие A и B, разность квадратов которых равняется числу-кандидату, значит оно точно составное, и тест простоты для него проводить уже не нужно!
В 1903 году это имело оглушительный успех! На заседании Американского математического общества американский математик Фрэнк Нельсон Коул привел разложение 21-значного числа Мерсенна:
M67 = 2^67 1 = 147573952589676412927 = 193707721 * 761838257287
И это без компьютеров и даже без калькуляторов!
Этот момент описывается на первом видео: 49-52 минуты:
Как видите, вторая фаза тоже бывает полезна, если тест простоты каждого числа-кандидата занимает продолжительное время, и особенно если проверяемое число настолько огромно, что его не удается целиком разместить в памяти компьютера для полноценного теста простоты.
3. ТЕСТ ПРОСТОТЫ ДЛЯ ВСЕХ, КТО НЕ ОТСЕЯЛСЯ РАНЕЕ (TESTING)
Наконец, третья фаза. На предыдущих шагах мы сделали все возможное, чтобы с минимальными издержками максимально избавиться от заведомо составных чисел. Здесь наступает момент истины - ДА или НЕТ ?
В зависимости от выбранного вида проверяемых чисел, тест простоты может дать нам как точный результат, так и предположительный. Обычно тестирующая программа сообщает свой вердикт так:
ЧИСЛО is composite! // Число составное
ЧИСЛО is not prime! // Число не является простым
ЧИСЛО is PRP! // Число предположительно простое (ПРП)
ЧИСЛО is prime! // Число точно простое
Для нас желаемыми являются последние 2 результата - либо проект уже считается успешным, и мы прекращаем проверки остальных кандидатов, либо мы продолжаем проверять диапазон до конца в поисках других Простых чисел (статус PRP потом перепроверяется другой программой).
А ТЕПЕРЬ - МОЙ ЖИВОЙ ПРИМЕР:
Однажды я решил найти Простое число Прота с круглой степенью: k*2^1000000 +1
На первом этапе с помощью программы NewPGen (сделаю на нее обзор) выбрал диапазон нечетных k = [3 .. 999.999] и стал просеивать кандидатов с помощью маленьких делителей. Дошел до числа 151.762.909.414.512 и решил остановиться - каждый новый претендент отсеивался за ~ 2 часа.
Количество претендентов k сократилось с 499.999 до 17.213 (в 29 раз)!
Вторую фазу я решил пропустить, как не столь критичную - факторизация каждого претендента заняла бы еще ощутимое время, в то время как каждый тест простоты ожидался не особо долгим.
На третьем этапе я использовал тестирующие программы LLR и PFGW (позднее тоже составлю обзоры на них) на нескольких компьютерах. Долго ли, коротко ли, но я протестировал все 17.213 кандидатов, и ... ничего!
Здесь я пожалел, что взял столь маленький диапазон, хотя по прогнозу ожидал найти в нем около 4 Простых чисел.
Ну да ладно, вернулся в начало, взял новый более широкий диапазон нечетных k = [1.000.001 .. 9.999.999], просеял его маленькими делителями уже до 1.000.000.000.000.000.
Из 4.499.999 претендентов k осталось 160.223 (сокращение в 28 раз)!
Снова запустил тесты простоты, и уже довольно скоро мне повезло:
1089927*2^1000000 +1 is prime! // 301.037 десятичных цифр!
Радости моей не было предела! Я даже решил дополнительно протестировать диапазон n = [2 .. 999.999], чтобы заодно найти и все маленькие Простые числа Прота вида 1089927 *2^n +1, вуаля (26 шт):
1089927*2^8 +1
1089927*2^11 +1
1089927*2^38 +1
1089927*2^52 +1
1089927*2^71 +1
1089927*2^80 +1
1089927*2^82 +1
1089927*2^338 +1
1089927*2^478 +1
1089927*2^1211 +1
1089927*2^1358 +1
1089927*2^2176 +1
1089927*2^2522 +1
1089927*2^4912 +1
1089927*2^8150 +1
1089927*2^21635 +1
1089927*2^24140 +1
1089927*2^31040 +1
1089927*2^123848 +1
1089927*2^224831 +1
1089927*2^229150 +1
1089927*2^326966 +1
1089927*2^331808 +1
1089927*2^352391 +1
1089927*2^415148 +1
1089927*2^984682 +1
Правда, потом я обнаружил, что меня в этом вопросе опередил некто Wataru Sakai - в 2006 и 2007 годах он уже нашел 2 Простых числа с этой красивой степенью: 1089927*2^1000000 +1 и 1611111*2^1000000 +1.
Теперь перед стартом очередного проекта я тщательно проверяю возможных конкурентов сразу в нескольких доступных базах Простых чисел!
Вот такая математика!
КОМУ ИНТЕРЕСНЫ ДАННЫЕ ПУБЛИКАЦИИ - ПОДПИСЫВАЙТЕСЬ НА КАНАЛ!
ПИШИТЕ В КОММЕНТАРИЯХ, ЕСЛИ ТОЖЕ ХОТИТЕ ПОУЧАСТВОВАТЬ В СОВМЕСТНЫХ ПОИСКАХ ПРОСТЫХ ЧИСЕЛ!
Поделитесь записью с друзьями
Посмотреть ещё 9 фотографий
Уморительные морды ныряющих собак
Знакомства для интима Сеготь без регистрации
Сайт знакомств Сеготь с женщинами кому за 35 без регистрации
Сайт знакомств Сеготь с мужчинами бесплатно
Сайт знакомств Сеготь с девушками с номерами телефонов бесплатно
Сайт знакомств Сеготь для серьезных отношений и брака бесплатно
Сайт знакомств онлайн Сеготь для взрослых бесплатно
Сайт знакомств Сеготь без регистрации бесплатно
Следующая запись: 0. ОГЛАВЛЕНИЕ
Лучшие публикации