Знаходження нового числа Мерсенна - Арифметичний метод побудови великих простих чисел. Числа Мерсенна
Математик Кертіс Купер, учасник проекту GIMPS (Great Internet Mersenne Prime Search), виявив 48-е просте число Мерсенна. Десятковий запис такого числа складається з більш ніж 17 мільйонів знаків. Для порівняння, у "Війні і мирі" Толстого всього приблизно 3,1 мільйона символів. За своє відкриття професор Міссурського центрального університету цілком може отримати три тисячі доларів. Втім, він, як і інші учасники GIMPS, займається пошуком простих чисел Мерсенна зовсім не заради грошей.
Числа Мерсенна - це числа виду 2P - 1, де p - довільне ціле число, яке називають показником. Ці числа вабили математиків з найдавніших часів, орієнтовно з Евкліда (приблизно 300 р. до н. е.), правда, до XVI ст. вчені вважали, що всі ці числа прості (тобто діляться тільки на себе і одиницю). Це, звичайно ж, неправильно - досить поглянути на четверте число Мерсенна: воно дорівнює 15 і зображається у вигляді добутку 3 і 5.
Мабуть, першим, хто помітив, що не всі числа Мерсенна з простими показниками (відомо, що для складових показників число Мерсенна не може бути простим) є простими, був Худальрікус Региус в 1536 році. Він показав, що при p = 11 отримане число - це 2047 - виявляється складеним, оскільки зображується у вигляді добутку 23 і 89.
Треба сказати, що перемозі над гіпотезою Мерсенна сприяла поява так званого тесту Люка-Лемера. Суть його полягає в наступному: для фіксованого числа Мерсенна обчислюється деяка рекурентна послідовність. Рекурентна формула для членів цієї послідовності, по-перше, відносно проста, а по-друге, для перевірки потрібно взяти p - 2 члени послідовності, де p - непарний простий показник числа Мерсенна. Складність роботи алгоритму складає близько третього ступеня log n, де n - саме число Мерсенна. Використання різного роду методів швидкого множення, як, наприклад, методу Шенхаге-Штрассена, дозволяє трохи прискорити роботу, проте кардинально складності не змінює.
Многочлен Джонса. Формула для генерації простих чисел: множина невід'ємних значень цього многочлена від 26 змінних, для всіляких наборів з 26 натуральних чисел дає всі прості числа.
Потрібно розуміти, що це вкрай низька обчислювальна складність, тобто алгоритм працює досить швидко. Для порівняння, найшвидший детерміністський алгоритм перевірки простоти з існуючих - тест Агравала-Каяла-Саксени з поліпшеннями Померанса-Ленстра - має складність порядку (log n)6. Відносну простоту програмування та низьку обчислювальну складність тесту Люка-Лемера вчені оцінили тільки з появою комп'ютерів.
У 60-ті роки минулого століття інтерес до чисел Мерсенна став спадати. Пов'язано це було з тим, що перспективи обчислювальної техніки на той момент бачилися досить туманними, а використання суперкомп'ютерів для пошуку великих простих чисел здавалося досить марнотратним. У 1968 році в університеті Іллінойсу було відкрито 23-е просте число Мерсенна з показником 11213. На той момент це було настільки великим досягненням, що Пол Бейтман, який керував кафедрою теорії чисел в цьому університеті, замовив спеціальну печатку для кореспонденції, на якій, крім дати, красувався напис "211213 - 1 - просте число". У 1970-х роках інтерес до чисел Мерсенна знову активізувався. Причиною тому стала історія двох тоді ще американських школярів - Лаури Нікел і Лендона Нолла. Не особливо розбираючись в математичних тонкощах питання, вони написали програму для перевірки чисел Мерсенна на простоту за допомогою тесту Люка-Лемера і прогнали її на суперкомп'ютері в місцевому університеті. У результаті вони змогли знайти 25-е і 26-е прості числа Мерсенна з показниками 21 701 і 23 209 відповідно. Це були найбільші прості числа з відомих на той момент. Нолл після цього став володарем ще одного рекорду - в 1989 році він взяв участь у відкритті найбільшого простого числа, яке не є числом Мерсенна (це так зване просте число Амдала, назване так на честь робочої групи, яка відкрила його, і рівне 391581* 2216193-1).
Історія з відкриттям школярів потрапила на телеекрани, і пошук простих чисел Мерсенна знову повернувся в моду. Наступні успіхи у цій діяльності були пов'язані з суперкомп'ютерами Крей - один зі співробітників компанії-виробника Девід Словінскі написав програму для пошуку простих чисел Мерсенна, що працювала на цих машинах, поки вони не використовувалися. Нарешті, сучасний вигляд цей процес набув за допомогою програміста Джорджа Уолтмана, в 1995 році створив проект розподілених обчислень GIMPS (Great Internet Mersenne Prime Search).
Проект до кінця першого року існування налічував вже більше тисячі учасників. Це був перший дослідний проект розподілених обчислень в історії. Перше просте число Мерсенна (в даний час в рамках проекту їх відкрито вже 14) стало відомо в 1996 році. Зараз програму, що працює під усіма основними операційними системами, може встановити собі будь-який бажаючий. Сумарна обчислювальна потужність проекту до кінця 2012 року становила вже 95 терафлопс.
Найостаннішим відкриттям в проекті GIMPS стало виявлення 48-го простого числа Мерсенна. Це відкриття було зроблено математиком з Міссурського центрального університету Кертісом Купером. На прогонку тесту Люка-Лемера на одній з машин в університеті у Купера пішло 39 днів. Його результат був перевірений ще раз трьома незалежними користувачами, один з яких використовував 32-ядерний сервер, наданий компанією Новартіс. Розміри нового числа вражають - його запис у десятковій системі числення складається з 17425170 знаків. Для самого ж Кертіса це відкриття стало вже третім - раніше найбільші прості числа йому вдавалося виявляти в 2005 і 2006 роках.
У 2008-му рекорд Кертіса був побитий групою дослідників з Каліфорнійського університету в Лос-Анджелесі. Вони виявили просте число Мерсенна, в десяткового запису якого було 12978189 знаків. На момент відкриття це число було 45-м простим числом Мерсенна, проте через деякий час було відкрито ще два простих числа, менших цього (числа не завжди відкриваються у порядку зростання), тому його номер на даний час - 47. Саме воно до відкриття Купера було рекордсменом за розміром.
За відкриття GIMPS отримав премію в 100 тисяч доларів від фонду EFF, обіцяну за відкриття першого простого числа, записаного більш ніж 10 мільйонами знаків. Отримані гроші проект розділив на невеликі премії для заохочення наступних відкриттів - так, Купер з 48-м числом Мерсенна претендує на три тисячі доларів.
Примітно, що з числами Мерсенна пов'язана велика кількість досі невирішених завдань. Наприклад, поки невідомо, чи нескінченна множина простих чисел Мерсенна. На закінчення хочеться згадати ще про одну чудову властивість чисел Мерсенна. Число називається досконалим, якщо воно дорівнює сумі всіх своїх власних (тобто додатних і відмінних від самого числа) дільників, включаючи 1. Наприклад, 6 - досконале, оскільки 6 = 3 + 2 + 1. Ще Евклід виявив, що число виду 2N - 1 (2N - 1) досконале, якщо в дужках стоїть просте число, тобто просте число Мерсенна з показником n. Пізніше Леонард Ейлер довів, що всі парні досконалі числа мають такий вигляд, де в дужках стоїть просте число Мерсенна. На даний момент невідомо жодного непарного досконалого числа, проте існують припущення, що шукати такі числа також слід за допомогою чисел Мерсенна.
Похожие статьи
-
Серед простих чисел особливу роль відіграють прості числа Мерсенна - числа виду 1) МР = 2Р -1, де р - просте число. Вони називаються простими числами...
-
Роль простих чисел у математиці Кожне натуральне число, більше одиниці, ділиться принаймні на два числа: на 1 і на саме себе. Якщо ні на яке інше ціле...
-
Вступ - Арифметичний метод побудови великих простих чисел. Числа Мерсенна
Виникнення чисел у житті не випадковість. Важко уявити собі спілкування без використання чисел. Історія чисел захоплююча й загадкова. Людство встановило...
-
Специфика транспортной задачи позволяет находить новое опорное решение задачи и новый базис по правилу более простому, чем в симплекс-методе. Пусть...
-
Рассмотрим замкнутую сеть массового обслуживания с разнотипными заявками, которая является вероятностной моделью обслуживания заявок в УП "Проектный...
-
Кодирование по методу четности / нечетности - Кодирование информации
Для контроля правильности передачи информации, а также как средство шифрования информации используются различные коды. Коды, использующие для передачи...
-
Среднее число исполнителей Чu, участвующих в разработке рассчитывается по формуле: Чu= , (10) Где Fд - полезный (действительный фонд времени одного...
-
Онлайн исследования в социологии: новые методы анализа данных - Распространение новостной информации
На сегодняшний день анализ социальных сетей и медиа, Интернет-сообществ, пользователей в целом используется в основном в маркетинге. Компания может...
-
10 2 4 8 16 0 0 0 0 0 1 1 1 1 1 2 10 2 2 2 3 11 3 3 3 4 100 10 4 4 5 101 11 5 5 6 110 12 6 6 7 111 13 7 7 8 1000 20 10 8 9 1001 21 11 9 10 1010 22 12 A...
-
Математические методы в управлении - Офисные автоматизированные технологии
Один из мощных инструментов анализа, которым располагают люди, ответственные за управление сложными системами, - моделирование. Модель является...
-
Построение модели сердца, Постановка задачи, Создание нового проекта - Построение модели сердца
Постановка задачи Мы рассмотрим простейшую математическую модель, описывающую процессы, похожие на биение сердца. Эта модель описана двумя...
-
Геймификация Когда рестораны принимают решения встраивать инновационные услуги в свой бизнес для привлечения аудитории, следует учитывать не только...
-
Рассмотрим замкнутую сеть массового обслуживания с разнотипными заявками, которая является вероятностной моделью обслуживания заявок в УП "Проектный...
-
Информационная система крупной организации, как правило, представляет собой исторически сложившуюся совокупность отдельно работающих систем, которые...
-
Висновок - Інтернет, як сучасний метод збору первинної інформації
Отже, роблячи висновок даної курсової роботи, можна запевнити про значну необхідність та ефективність використання первинної інформації при маркетингових...
-
Методы и средства проектирования - Автоматизированные системы обработки экономической информации
Проектирование - процесс создания проекта-прототипа, прообраза предполагаемого или возможного объекта, его состояния. Современная технология создания АИС...
-
До сих пір ми торкалися лише імпортних продуктів в Internet. А як же складаються справи з нашими? Чесно кажучи, поки що туговато. Напрочуд необмежені...
-
Для оценки возможности выполнения проекта имеющимся в распоряжении разработчика штатным составом исполнителей, нужно рассчитать их среднее количество,...
-
Завдання 1. "Основні прийоми та способи побудови тривимірних моделей у графічному редакторі Компас 3D LT 5.11" Завдання 1 А) Побудувати модель втулки,...
-
В цьому розділі я описую яку послідовність необхідно витримати при створенні інтерфейсу головного вікна програми для того, щоб створити форму та...
-
Собственные числа и собственные векторы матрицы Предположим, что среди бесконечного множества одномерных пространств R1 найдутся такие, которые будут...
-
Метод парольной защиты - Защита информации
Законность запроса пользователя определяется по паролю, представляющему собой, как правило, строку знаков. Метод паролей считается достаточно слабым, так...
-
Для построения эффективной системы мониторинга необходимо определить объекты наблюдения, отслеживаемые показатели и сроки их представления, программные...
-
Методы и системы принятия решений
Методы и технологии искусственного интеллекта в управлении. Методы и технологии разработки решений в условиях неопределенности А) Технология управления...
-
Принцип метода линейного предсказания - Вокодеры с линейным предсказанием
Вокодер информация кодирование синтезатор В вокодерах с линейным предсказанием при анализе речевого сигнала в передающем устройстве определяются...
-
Стандарт ЕЦП DSS/DSА - Розробка електронного цифрового підпису
У 1991 р NIST (National Institute of Standards and Technology) запропонував для обговорення проект стандарту ЕЦП DSS (Digital Signature Standard),...
-
Обоснование выбранного метода При дизайне системы согласно требованиям или при оптимизации существующей необходимо ввести модель, позволяющую не только...
-
Функциональные требования: - Поиск и обработка информации в текстовых файлах при появлении файлов в соответствующей директории по запросу администратора...
-
Рассмотрим два программных продукта наиболее схожих по функциям и назначению с программным обеспечением "Программа обработки сложноструктурированных...
-
ИИС "Шлаковые расплавы" позволяет вести моделирование КЭ в нескольких "режимах", с полным набором получаемых свойств. 1. Моделирование комплекса свойств...
-
Актуальность исследования. Компьютерный эксперимент - это исследование математической модели объекта изучения на ЭВМ, состоящее в том, что, по известным...
-
МЕТОДЫ АРХИВАЦИИ - Архивация информации и программы-архиваторы
Несмотря на то, что объемы внешней памяти ЭВМ постоянно растут, потребность в архивации не уменьшается. Это объясняется тем, что архивация необходима не...
-
Таким образом, от общей проблемы математического анализа изображений мы перешли к проблеме проверки на плагиат графической информации. Для этого нами...
-
Прямое использование предсказания позволяет воспроизводить звук, но с плохим качеством. Поэтому этот метод имеет много различных разновидностей,...
-
Физическая среда передачи в локальных сетях - Методы доступа к передающей среде в ЛВС
Весьма важный момент - учет факторов, влияющих на выбор физической среды передачи (в ЛВС - кабельной системы). Среди них можно перечислить следующие:...
-
Шифрование данных традиционно использовалось спецслужбами и оборонными ведомствами; сейчас, в связи с ростом возможностей компьютерной техники, многие...
-
Відомі два підходи до організації інформаційних масивів: файлова організація та організація у вигляді бази даних. Файлова організація передбачає...
-
Управление дорожным движением осуществляется адаптивной компьютерной системой, которая, измеряя реальные потоки транспорта на дороге, оптимизирует...
-
Методика решения задач ЛП графическим методом - Линейное программирование
I. В ограничениях задачи (1.2) заменить знаки неравенств знаками точных равенств и построить соответствующие прямые. II. Найти и заштриховать...
-
Метод определения погрешности - Поверка и калибровка информационно измерительных систем
Метод определения погрешности аналоговых и цифро-аналоговых ИК для случая пренебрежимо малой случайной составляющей погрешности Если проверяемая точка...
Знаходження нового числа Мерсенна - Арифметичний метод побудови великих простих чисел. Числа Мерсенна