Для чего таблица простых чисел

Что такое Простые числа

Простые числа — это натуральные числа, больше единицы, которые делятся без остатка только на 1 и на само себя. Например: 2, 3, 5, 7, 11, 13, 17, 19, 23. Единица не является ни простым числом, ни составным.

Последовательность простых чисел начинается с 2 и является бесконечной; наименьшее простое число — это 2 (делится на 1 и на самого себя).

Составные числа — это натуральные числа, у которых есть больше двух делителей (1, оно само и например, 2 и/или 3); это противоположность простым числам. Например: 4, 6, 9, 12 (все делятся на 2, на 3, на 1 и на само себя).

Все натуральные числа считаются либо простыми, либо составными (кроме 1).

Натуральные числа — это те числа, которые возникли натуральным образом при счёте предметов; например: 1, 2, 3, 4. (нет ни дробей, ни 0, ни чисел ниже 0).

Зачастую множество простых чисел в математике обозначается буквой P.

Простые числа до 1000

Как определить, является ли число простым?

Очень простой способ понять, является ли число простым — нужно его разделить на простые числа и посмотреть, получится ли целое число. Сначала нужно попробовать его разделить на 2 и/или на 3. Если получилось целое число, то оно не является простым.

Если после первого деления не получилось целого числа, значит нужно попробовать разделить его на другие простые числа: 5, 7, 11 и т. д. (на 9 делить не нужно, т. к. это не простое число и оно делится на 3, а на него вы уже делили).

Более структурированный метод — это решето Эратосфена.

Решето Эратосфена

Это алгоритм поиска простых чисел. Для этого нужно:

Те числа, которые не будут вычеркнуты в конце этого процесса, являются простыми.

Взаимно простые числа

Это натуральные числа, у которых 1 — это единственный общий делитель. Например:

Число Мерсенна

Простое число Мерсенна — это простое число вида:

До 1536 г. многие считали, что числа такого вида были все простыми, пока математик Ульрих Ригер не доказал, что 2 (^11) – 1 = 2047 было составным (23 x 89). Затем появились и другие составные числа (p = 23, 29, 31, 37 и др.).

Например, для p = 23 это 2 (^23) – 1 = 8 388 607; И 47 x 178481 = 8 388 607, значит оно составное.

Почему 1 не является простым числом?

Российские математики Боревич и Шафаревич в своей знаменитой работе «Теория чисел» (1964 г.) определяют простое число как p (элемент кольца D), не равен ни 0, ни 1. И p можно называть простым числом, если его невозможно разложить на множители ab (т.е. p = ab), притом ни один из них не является единицей в D. Так как 1 невозможно представить ни в одном, ни в другом виде, 1 не считается ни простым числом, ни составным.

Почему 4 не является простым числом?

Простое число — это натуральное число, больше единицы, которое делится без остатка на 1 и на само себя. Т. к. 4 можно разделить на 1, на 2 и на 4, из-за деления на 2 оно не является простым.

Самое большое простое число

21 декабря 2018 года Great Internet Mersenne Prime Search (проект, целью которого является открытие новых простых чисел Мерсенна) обнаружил новое самое большое известное простое число:

Новое простое число также именуется M82589933 и в нём более чем на полтора миллиона цифр больше, чем в предыдущем (найденном годом ранее).

Источник

Простые и составные числа, определения, примеры, таблица простых чисел, решето Эратосфена

В статье рассматриваются понятия простых и составных чисел. Даются определения таких чисел с примерами. Приводим доказательство того, что количество простых чисел неограниченно и произведем запись в таблицу простых чисел при помощи метода Эратосфена. Будут приведены доказательства того, является ли число простым или составным.

Простые и составные числа – определения и примеры

Простые и составные числа относят к целым положительным. Они обязательно должны быть больше единицы. Делители также подразделяют на простые и составные. Чтобы понимать понятие составных чисел, необходимо предварительно изучить понятия делителей и кратных.

Составными числами называют целые числа, которые больше единицы и имеют хотя бы три положительных делителя.

Единица не является ни простым ни составным числом. Она имеет только один положительный делитель, поэтому отличается от всех других положительных чисел. Все целые положительные числа называют натуральными, то есть используемые при счете.

Простые числа – это натуральные числа, имеющие только два положительных делителя.

Составное число – это натуральное число, имеющее более двух положительных делителей.

Натуральные числа, которые не являются простыми, называют составными.

Таблица простых чисел

Для того, чтобы было проще использовать простые числа, необходимо использовать таблицу:

Рассмотрим теорему, которая объясняет последнее утверждение.

Наименьший положительный и отличный от 1 делитель натурального числа, большего единицы, является простым числом.

Простых чисел бесконечно много.

Видно, что может быть найдено любое простое число среди любого количества заданных простых чисел. Отсюда следует, что простых чисел бесконечно много.

Решето Эратосфена

Данный способ неудобный и долгий. Таблицу составить можно, но придется потратить большое количество времени. Необходимо использовать признаки делимости, которые ускорят процесс нахождения делителей.

Перейдем к формулировке теоремы.

Данное число простое или составное?

Перед решением необходимо выяснять, является ли число простым или составным. Зачастую используются признаки делимости. Рассмотрим это на ниже приведенных примере.

Доказать что число 898989898989898989 является составным.

Ответ: 11723 является составным числом.

Источник

ТЕХНОЛОГИИ, ИНЖИНИРИНГ, ИННОВАЦИИ

Измеритель диаметра, измеритель эксцентриситета, автоматизация, ГИС, моделирование, разработка программного обеспечения и электроники, БИМ

Магия простых чисел: примеры и неожиданные открытия

Значимость простых чисел, как в повседневном применении, так и во всех отраслях математики, невозможно переоценить. Мы спокойно полагаемся на их особые свойства, используя их как фундамент бесчисленного количества элементов нашего общества, ведь они являются неделимой частью самой ткани природы. Простые числа, устойчивые к любому делению на множители, часто называют «атомами» мира математики. Карл Саган сказал о них так: Очень важен статус простых чисел как фундаментальных строительных блоков всех чисел, которые сами являются строительными блоками нашего понимания Вселенной. В природе и в нашей жизни простые числа используются повсюду: цикады выстраивают по ним свои жизненные циклы, часовщики применяют их для вычисления тиканья, а в авиационных двигателях с их помощью балансируется частота воздушных импульсов. Однако все эти области применения бледнеют на фоне факта, знакомого каждому криптографу: простые числа находятся в самом сердце современной компьютерной безопасности, то есть они напрямую несут ответственность за защиту всего.

Видите замок в адресной строке браузера? Да, это значит, что используется двухключевое «рукопожатие», основанное на простых числах. Как защищается при покупках ваша кредитная карта? Тоже при помощи криптографии на основе простых чисел.

Однако несмотря на то, что мы постоянно полагаемся на их уникальные свойства, простые числа оставались для нас неуловимыми. На протяжении всей истории математики величайшие умы пытались доказать теорему о предсказании чисел, являющихся простыми, или о том, как далеко друг от друга они должны располагаться. На самом деле, некоторые нерешённые задачи, например задача о числах-близнецах, проблема Гольдбаха, простые числа-палиндромы и гипотеза Римана, связаны с этой общей непредсказуемостью и неопределённостью простых чисел при стремлении к бесконечности.

Разумеется, со времён Евклида мы обнаружили алгоритмы, позволяющие предсказывать расположение некоторых чисел, но общие теоремы ещё не доказаны, а у предыдущих попыток не было инструментов для проверки больших чисел. Однако технологии 21-го века позволяют исследователям проверять предположения на чрезвычайно больших числах, но такая методика сама по себе вызывает споры, ведь проверка грубым перебором не считается надёжным доказательством. Другими словами, простые числа противятся подчиняться какой-либо универсальной формуле или уравнению, а их расположение в природе кажется случайным.

Однако, одному человеку случайными каракулями удалось доказать, что они как минимум не полностью случайны…

От закорючек к подсказке — скатерть Улама

Одно из величайших доказательств того, что расположение простых чисел не является чистым совпадением, появилось самым маловероятным образом: из бездумных и случайных каракуль одного заскучавшего слушателя лекций.

Схема скатерти Улама

Как гласит история, польский математик Станислав Улам обнаружил этот графический паттерн во время семинара в 1963 году. Рисуя сетку из линий, он решил пронумеровать пересечения по квадратно-спиральному паттерну и начал обводить те числа в спирали, которые были простыми. К его удивлению, обведённые простые числа приходились на диагональные прямые линии, или, как чуть строже сформулировал Улам, «проявляли сильно неслучайное поведение». Скатерть Улама, или спираль простых чисел — это получившееся в результате графическое отображение размеченных в квадратной спирали множества простых чисел. Изначально скатерть была опубликована и получила широкую известность в рубрике «Математические игры» Мартина Гарднера в Scientific American.

Скатерть Улама размером 377×377 (числа примерно до 142 тысяч)

Показанная выше визуализация очевидно выявляет примечательные паттерны, особенно по диагоналям. Но возможно, мы обманываем себя? Часто утверждают, что скатерть Улама — это просто трюк нашего мозга, пытающегося находить паттерны в случайности. К счастью, мы можем использовать две разные методики, чтобы убедиться, что это не так. И визуальное сравнение, и логический анализ с определённостью говорят нам, что паттерн не случаен. Во-первых, мы сравним скатерть Улама, заданную матрицей размером NxN, с матрицей того же размера, содержащей случайно заданные точки. Во-вторых, мы можем воспользоваться своими знаниями о многочленах, чтобы понять, почему нужно ожидать появления некоторого паттерна при графическом отображении простых чисел.

Как говорилось выше, скорее всего, наиболее интуитивно понятным подтверждением неслучайности паттерна будет непосредственное сравнение со скатертью Улама. Для этого нужно создать скатерть Улама и квадратную спираль со случайными расположениями того же размера. Ниже показаны две разные матрицы 200×200, представляющие числовые спирали:

При визуальном сравнении становится достаточно очевидно, что скатерть Улама содержит потрясающие паттерны, особенно вдоль диагональных осей; кроме того, в ней почти нет скоплений точек. С другой стороны, случайное расположение точек не создаёт никаких сразу же заметных паттернов и приводит к скоплению точек в разных направлениях. Несомненно, такой методике не достаёт строгости традиционных доказательств; однако в визуализации спиралей простых чисел есть нечто безупречное: это случайно обнаруженная методика, позволяющая создать график, стимулирующий логику и привлекательный эстетически.

Если подходить к природе простых чисел в более логической и традиционной манере, то вполне разумно ожидать появления паттернов в таких визуализациях. Как сказано выше, линии в диагональных, горизонтальных и вертикальных направлениях, похоже, содержат подсказку. Некоторые из этих линий, не являющихся простыми числами, можно объяснить обычными квадратными многочленами, исключающими возможность появления простых чисел — например, одна из диагональных линий, соответствующая уравнению y = x², очевидно, исключает простые чила. С другой стороны, известно, что некоторые квадратные многочлены, называемые формулами простых чисел (о них мы поговорим ниже), создают высокую плотность простых чисел, например, многочлен генерации простых чисел Эйлера: x² — x — 41; это ещё одна линия, отражающаяся как паттерн в спирали (хотя на показанной выше схеме сложно найти разрывы).

Визуальное сравнение указывает на наличие паттернов, а логический анализ подтверждает существование ожидаемых паттернов. Разумеется, мы ещё далеки от универсальной формулы для нахождения всех простых чисел, но скатерть Улама без сомнений прекрасна, и как символ нашего знания, и как шедевр природного искусства.

Спираль Сакса

Как и во многих областях математики, после появления оригинальной идеи идущая по следам армия коллег-математиков начала делать попытки внести свой вклад в новую тему. Логично, что скатерть Улама вдохновила поколения математиков, стремившихся развить его потрясающую находку. В 1994 году инженер по разработке ПО Роберт Сакс решил использовать свои навыки программиста для визуализации простых чисел различными способами.

Почти как и в случае со скатертью Улама, Сакс решил структурировать свою схему при помощи другой спиральной плоскости. Аналогично показанной выше квадратной спирали, спиральные плоскости отказываются при задании точек от традиционной декартовой числовой системы, потому что являются системой однополярного позиционирования. Просто зная число, можно узнать его расположение в спирали, его позицию относительно всех других чисел в спирали, а также расстояние от него до предыдущего и следующего квадрата числа. Однако вместо квадратной спирали Сакс попытался найти паттерны при помощи целых чисел, наложенных на архимедову спираль со следующими полярными координатами:

Полярные координаты спирали Архимеда/Сакса

При такой методике архимедова спираль центрирована относительно нуля, а квадраты всех натуральных чисел (1,4,9,16,25) расположены на пересечениях спирали и полярной оси (расположенной к востоку от точки начала координат).

Структура спирали Архимеда/Сакса

Подготовив эту схему, мы будем заполнять точки между квадратами вдоль спирали (против часовой стрелки), нанося их на равном расстоянии друг от друга. А в конце, как и в примере со скатертью Улама, мы выделим простые числа, содержащиеся в получившейся спирали.

Числовая спираль Сакса, впервые опубликованная онлайн в 2003 году, привлекательна и визуально, и интеллектуально. Кроме того, как мы вскоре убедимся, она даёт нам более глубокое понимание паттернов простых чисел, чем хорошо известная скатерть Улама, потому что она объединяет разорванные линии псевдоспирали Улама:

Архимедова спираль с отмеченными простыми числами, она же спираль Сакса.

Получившийся график снова демонстрирует заметные паттерны. Почти сразу становится понятно, что есть чистая белая линия, проходящая из центра и растянувшаяся горизонтально на восток. Обратившись к нашей схеме, мы можем убедиться, что это просто линия, содержащая все квадраты целых чисел (r = n^(.5)). Второе наблюдение: паттерн пометок, в отличие от прямых линий скатерти Улама, здесь больше напоминает кривые линии. Оказывается, эти кривые, также известные как кривые произведений, возвращают нас к многочленам, объясняющим паттерны, возникающие в предыдущей спирали. Но прежде чем мы обратимся к ним, ради единства снова сравним спираль Сакса со спиралью случайных значений:

Многочлены и кривые произведений

Работа Роберта Сакса, последовавшая за этим открытием, целиком была сосредоточена на этих кривых произведений, начинающихся в центре спирали или рядом с ним, и под разными углами пересекающихся с витками спирали. Кривые почти прямы, но более типично для них то, что они выполняют частичные, полные или многократные повороты по часовой стрелке (против движения самой спирали) вокруг точки начала координат перед тем, как выпрямиться на определённом смещении от оси «восток-запад». Один из самых поразительных аспектов числовой спирали Сакса заключается в преобладании таких кривых произведений в западном полушарии (в противоположной от квадратов чисел стороне).

Сакс описал кривые произведений как представляющие «произведения множителей с постоянной разностью между ними». Другими словами, каждую кривую можно представить квадратным уравнением (многочленом второй степени), что опять-таки не является простым совпадением, учитывая превалирование квадрата натурального числа в спирали Сакса. Возможно, эти кривые произведений могут привести нас к выводу, что спираль Сакса значительно полезнее в нашем пути к пониманию простых чисел, чем скатерть Улама. Хотя скатерть Улама указала нам на паттерны и возможное существование уравнений, спираль Сакса даёт точки опоры в поиске формул простых чисел — их кривизна и целостность постоянны, а значит, их гораздо проще будет обнаружить. Например, показанная ниже спираль Сакса содержит помеченные линии и относящуюся к ним формулу простых чисел, записанную в стандартном виде. Как я и обещал, знаменитая формула Эйлера для генерации простых чисел снова нам встретилась (последняя запись: n² + n +41):

Благодаря этой числовой спирали Сакс смог сделать потрясающее заявление о том, чем является простое число: положительным целым, лежащим только на одной кривой произведений. Поскольку спираль может раскручиваться бесконечно, сами кривые произведений тоже можно считать бесконечными; теоретически, эти кривые произведений, возможно, могут предсказывать расположение достаточно больших чисел — по крайней мере, такие числа стоят более внимательного изучения.

В целом, спираль Сакса без сомнений подтолкнула нас к более глубокому пониманию простых чисел, предложив более удобные формулы простых чисел.

Значение всего этого

Итак, мы проанализировали и скатерть Улама, и спираль Сакса. Благодаря этим примерам расширилось наше понимание природы, лежащей в основе простых чисел. В частности, спираль Сакса познакомила нас с кривыми произведений, которые по сути являются множеством квадратных уравнений, известных как формулы простых чисел. Оба графика, и Улама, и Сакса, оказались неожиданными и эстетичными, они стимулируют наше любопытство и проливают свет на одну из сложных для всего мира задач.

Какой же урок можно извлечь из всего этого?

Никогда нельзя отказываться от пересмотра кажущихся неразрешимыми проблем, даже если вы занимаетесь этим из чистого любопытства и скуки; открытия может делать каждый и часто они возникают как результат совершенно необычных процессов. Изменив точку зрения на знаменитую задачу благодаря визуализации, Станислав Улам на один шаг приблизил нас к пониманию простых чисел: кто знает, на какие ещё неожиданные открытия мы наткнёмся?

Понравилась статья? Тогда поддержите нас, поделитесь с друзьями и заглядывайте по рекламным ссылкам!

Источник

Глава 7 Для чего нужны простые числа

Для чего нужны простые числа

Поиск простых чисел — по крайней мере больших простых чисел — довольно сложная задача, потому что еще никому не удалось найти формулу или алгоритм, позволяющий генерировать любые простые числа. Но может возникнуть логичный вопрос: «Для чего нужно генерировать простые числа?»

На этот вопрос можно дать два ответа. Первый из них имеет теоретическое значение. Попытки генерации простых чисел ведут к появлению новых интересных инструментов для расчетов, особенно для компьютерных вычислений. Кроме того, наличие большого списка простых чисел позволяет проверять теоремы, которые еще не доказаны. Если кто-то выдвигает гипотезу относительно простых чисел, но оказывается, что одно из миллионов чисел нарушает ее, то вопрос снимается. Это стимулирует поиск простых чисел различных видов: простых чисел Мерсенна, чисел-близнецов и так далее. Иногда такой поиск превращается в соревнование, в котором устанавливаются мировые рекорды и за победы присуждаются большие призы.

Но есть и другая, более практическая причина, связанная с так называемым шифрованием. Электронная почта, банковские операции, кредитные карты и мобильная телефонная связь — все это защищено секретными кодами, непосредственно основанными на свойствах простых чисел.

Простые числа в криптографии

В 1975 г. Уитфилду Диффи и Мартину Хеллману, в то время работавшим в Стэнфордском университете, пришла в голову идея асимметричного шифрования, или «шифрования с открытым ключом». Эта система основана на специальных математических функциях, называемых «односторонними функциями с потайным входом», которые позволяют зашифровывать текст, но делают расшифровку практически невозможной без знания используемого кода. Идея состоит в том, что каждый пользователь имеет пару ключей: открытый и закрытый. Если мы хотим отправить кому-то сообщение, мы зашифровываем это сообщение с помощью открытого ключа — то есть ключа, известного всем. Но только человек, имеющий соответствующий закрытый ключ, может расшифровать это сообщение. Одним из преимуществ такого метода является то, что закрытый ключ никогда не передается и поэтому его не нужно постоянно менять в целях безопасности. Идея метода не совсем проста, но мы можем пояснить ее с помощью аналогии. Представьте себе большой магазин, где продаются сотни тысяч банок с краской разного цвета. Возьмем две любые банки и смешаем краску в разных количествах. Пока все просто. Теперь, если мы покажем кому-нибудь получившийся цвет и попросим «расшифровать», какое количество каких красок использовалось изначально, на такой вопрос будет очень трудно ответить.

Именно так работают односторонние функции с потайным входом, которые легко применить в одном направлении, но практически невозможно — в обратном.

Схема, иллюстрирующая алгоритм Диффи — Хеллмана. Имеются два абонента, Алиса и Боб, желающие общаться втайне. Они открыто договариваются о двух числах (простое число р и другое число g, имеющие определенные свойства). И Алиса, и Боб выполняют некоторые операции с этими числами и с еще одним целым числом, которое они держат в секрете, а затем открыто посылают друг другу результаты. Теперь и Алиса, и Боб выполняют с полученным результатом еще одну операцию и получают один и тот же ответ, который будет для них секретным кодом. Потенциальный шпион, перехвативший результаты, посланные Алисой и Бобом, не может сгенерировать секретный код, имея лишь эту информацию.

Предположим теперь, что вместо банок с краской в магазине находятся простые числа. Возьмем любые два, например, 7 и 13, и перемножим их (аналогично смешиванию краски). В результате мы получим 7 х 13 = 91.

Тогда возникает вопрос: можно ли узнать, какие простые числа были перемножены, чтобы в результате получилось 91? Для ответа на него надо взять список простых чисел и проделать несколько проверок. Казалось бы, простое решение, как и в случае определения цвета красок, если в магазине было всего около десятка основных цветов.

Но с простыми числами все намного сложнее.

Например, ни у кого не хватит терпения проверить, что число 1409 305 684 859 является результатом умножения простых чисел 705 967 и 1996 277, особенно если учесть, что эти два простых числа взяты из списка простых чисел между 1 и 2000000, а там таких «всего лишь» 148933. Однако мы живем в эпоху высоких технологий, и, конечно, эту задачу можно довольно быстро решить с помощью хорошей программы и мощного компьютера. Хотя все зависит от того, насколько большой этот магазин красок. Не следует также забывать, что количество простых чисел не просто очень большое, а бесконечное.

Пара простых чисел в приведенном выше примере содержит лишь несколько цифр. Если мы возьмем простые числа, каждое из которых содержит сотни цифр, то время, которое потребуется компьютерной программе на простой перебор всех возможных вариантов — метод «грубой силы», как говорят криптографы, — будет больше, чем предполагаемое время существования Земли.

Простые числа повсеместно используются в нашей повседневной жизни, например, в кредитных картах и персональных компьютерах, поэтому постоянно существует потребность в новых простых числах (чем больше, тем лучше) для генерации секретных кодов. Таким образом, имеется спрос на простые числа, но контроль качества так же важен, как и их производство. Чтобы большому числу присвоить статус простого, его должна проверить специальная организация.

Шифр RSA был опубликован в 1978 г., но повсеместно начал использоваться в качестве метода шифрования лишь в конце 1990 гг. в связи с ростом сети интернет. Поиск больших простых чисел прежде требовал специального программного обеспечения, которое, как правило, можно было купить лишь в специализированных фирмах или в университетах, занимающихся такими исследованиями. Однако экспоненциальный рост вычислительных мощностей и появление более совершенных алгоритмов изменили рынок простых чисел и сделали их гораздо более доступными.

В апреле 1994 г. шифр RSA-129 потерпел полное фиаско. Он был построен на числе, содержащем 129 цифр, о чем объявили авторы этой системы шифрования, предложив желающим взломать его. Около 600 математиков с помощью 1600 добровольцев, найденных через интернет, работали над проблемой, и в конце концов им удалось разложить это число на множители. Однако было подсчитано, что если все компьютеры в мире будут работать параллельно, чтобы взломать код из 1024 цифр, им потребуется время, равное возрасту Вселенной (13,7 миллиарда лет). А теперь представьте себе, что в шифровании с открытым ключом используются числа, содержащие 128,1024 и даже 2048 цифр! Чем больше цифр использует система шифрования, тем устойчивее она к атакам, хотя это, конечно, замедляет процесс расшифровки.

Эпоха высоких технологий

Появление логарифмов позволило значительно сэкономить время при выполнении вычислений. Позже появились логарифмическая линейка и первые вычислительные машины, которые использовали вращающиеся цилиндры для выполнения операций сложения и умножения.

Тем не менее, именно компьютеры смогли делать вычисления, выходящие за пределы возможностей человеческого мозга. Машины могли даже имитировать дедуктивные рассуждения — одно из свойств математического мышления. В этот момент некоторые ученые почувствовали, что компьютеры достигли рубежа, к которому до сих пор ни одна машина не подходила. Был ли это правильный путь?

Экспоненциальный рост информационных технологий привел к изменению системы воззрений, сложившейся на протяжении веков. Начали появляться первые вычислительные алгоритмы, способные доказывать теоремы.

Противники компьютерных доказательств приводят два основных аргумента.

Во-первых, такие доказательства невозможно проверить, так как компьютерная программа содержит этапы, которые никакой математик никогда не сможет проконтролировать. Во-вторых, в процессе возможны ошибки из-за сбоев как в аппаратном, так и в программном обеспечении. В большинстве случаев эти ошибки случайны. Одним из способов предотвращения таких ошибок является использование различных программ на разных машинах (чтобы сравнить полученные результаты).

Но компьютеры могут работать только с кодами из единиц и нулей. Это накладывает некоторые ограничения, так как для чисел, которые не могут быть выражены в двоичной системе счисления, приходится использовать приближенные значения, что ведет к возможным ошибкам. В 1991 г. Дэвид Стаутмайер провел 18 экспериментов, доказав, что вычисления с помощью компьютерных программ могут дать неверные результаты.

Именно поэтому многие считают, что новые вычислительные методы исследований можно применять лишь в экспериментальной науке, а не в математике. Однако никто и не говорит, что в математике может быть использован лишь один метод.

Подсчитано, что у суперкомпьютера Cray на каждую тысячу часов работы приходится лишь одна ошибка.

«Традиционные» математические подходы тоже никогда не были свободны от ошибок. В ряде случаев неверные результаты считались правильными в течение многих

лет. Кроме того, в наши дни математика достигла такого высокого уровня разнообразия и сложности, что проверка доказательства теоремы может занять годы, или доказательство будет понятно в лучшем случае лишь нескольким специалистам.

Наконец, некоторые эксперты считают, что использование компьютера в качестве инструмента исследования и проверки теорем означает новое отношение к математике. Вполне разумно предположить, что гипотеза Римана в один прекрасный день может быть доказана с помощью компьютера. В любом случае, никто не ставит под сомнение правомерность того, что вычислительные методы используются для поиска и проверки простых чисел. В области вычислительной алгебры часто звучат такие термины, как детерминированный и вероятностный полиномиальные алгоритмы, которые совершенно непонятны для непосвященных. Хотя к нашей теме это не имеет прямого отношения, было бы полезно пояснить эти понятия.

Когда говорят о полиномиальном времени, имеют в виду время, необходимое компьютеру для выполнения некоего алгоритма. Предположим, что у нас есть входная переменная п. Если алгоритм использует полиномиальные выражения, например, n 3 + 2n + 1, его называют полиномиальным алгоритмом (алгоритмом класса сложности Р). Если же выражение экспоненциальное, то говорят о неполиномиальном алгоритме (алгоритме класса сложности NP). В общих чертах идея состоит в том, что полиномиальные алгоритмы имеют приемлемое время работы, в отличие от неполиномиальных.

Р в сравнении с NP

Некоторые вычислительные задачи не могут быть решены с помощью детерминированного подхода — другими словами, с помощью процессов, выдающих уникальный и предполагаемый результат. Именно такими являются полиномиальные алгоритмы, работающие за полиномиальное время и выполняющие, например, операции сложения, умножения или решения систем уравнений. В большинстве случаев при использовании подходящих алгоритмов решение может быть найдено за разумное время. Задачи, которые могут быть решены таким образом, называются задачами класса сложности Р. С другой стороны, задачи класса сложности NP, для которых используются недетерминированные алгоритмы, решаются несколькими разными способами без гарантии получения одинакового результата.

Время, необходимое для решения такого рода проблем, намного больше чем для задач класса Р. Ясно, что любая проблема, которая допускает детерминированное решение за полиномиальное время, может быть также решена способом быстрой проверки. Другими словами, любая задача класса Р является также задачей класса NP. Однако на этом этапе нам следует уточнить понятие алгоритма.

Алгоритм можно сравнить с кулинарным рецептом. Он состоит из последовательности кристально ясных инструкций. Например, чтобы решить уравнение вида х — 2 = 8, можно использовать следующий алгоритм.

1. Отделить х (перенеся все члены, не содержащие х, в правую часть).

2. Выполнить сложение в правой части: 8 + 2 = 10.

3. Записать решение: х = 10.

Это задача класса Р, которую можно решить за полиномиальное время: она

очень проста и быстро решается.

Конечно, мы могли бы просто подставить значение, например х = 3, х = —2 и так далее, и времени на вычисления потребовалось бы меньше, так как единственное, что программа должна делать, — это подставлять значение вместо х и проверять равенство. Такой метод не является детерминированным, потому что всегда есть вероятность того, что решение будет неверным. (Мы предполагаем, что у нас есть определенные критерии для выбора диапазона возможных решений, например, условие, что все они должны находиться между 9 и 11.)

Можно поставить и обратный вопрос. Если у нас есть недетерминированный алгоритм, например, подстановки и проверки, можно ли гарантировать, что существует полиномиальный алгоритм, который позволяет решить задачу детерминировано? Другими словами, можем ли мы быть уверены в существовании алгоритма, решающего задачу за полиномиальное время?

Этот вопрос был поставлен независимо друг от друга Стивеном Куком и Леонидом Левиным в 1971 г.: если любая задача класса Р является также задачей класса NP, существуют ли задачи класса NP, которые не являются задачами класса Р?

Этот вопрос считается самой важной проблемой современной информатики и является одной из семи задач тысячелетия, за решение каждой из которых математическим институтом Клэя назначен приз в 1000 000 долларов США.

СЕМЬ ЗАДАЧ ТЫСЯЧЕЛЕТИЯ

Математический институт Клэя — частная некоммерческая организация, основанная Лэндоном Клэем, мультимиллионером и бизнесменом из Бостона. Цель института заключается в развитии и распространении математических знаний.

25 мая 2000 г. институт опубликовал список задач тысячелетия — наиболее сложных проблем математики XX в., за решение которых в общей сложности будет выплачено семь миллионов долларов. Задачи можно решать по одной; за решение каждой будет выдаваться приз в миллион долларов (это больше, чем Нобелевская премия). Институт не накладывает никаких ограничений на сроки решения и возраст кандидатов. Вот эти семь задач.

1. Равенство классов Р и NP.

3. Теория Янга-Миллса.

4. Уравнения Навье-Стокса.

5. Гипотеза Бёрча-Свиннертон-Дайера.

7. Гипотеза Пуанкаре.

Учитывая сложность и важность предложенных задач, финансовые консультанты господина Клэя сомневались в том, что Институту когда-нибудь придется выплачивать эти призы. Тем не менее, в 2006 г. российский математик Григорий Перельман к удивлению всего мира решил седьмую задачу, доказав гипотезу Пуанкаре. Однако по личным причинам он отказался от медали Филдса, присужденной ему на 25-м Международном конгрессе математиков в Мадриде. Он также отказался от награды института Клэя.

Генерация простых чисел

Очень часто случается так, что кто-нибудь, не имея специальной математической подготовки, вдруг решает, что он нашел (как правило, в интернете) систему или формулу, с помощью которой можно получить простое число, следующее за некоторым натуральным числом n. Однако следует иметь в виду, что такая новость не останется незамеченной. Тот, кто найдет магическую формулу, сразу попадет на первые страницы всех газет и журналов мира.

Существует много геометрических моделей для поиска простых чисел. Иногда они могут ввести в заблуждение неопытных новичков, так как представлены в виде формул, по которым можно найти все простые числа. Но в действительности эти модели являются не более чем решетом Эратосфена или другим представлением решета с помощью геометрических методов. Хотя некоторые из них действительно гениальны.

Одна из самых интересных моделей была разработана российскими математиками Юрием Матиясевичем и Борисом Стечкиным с использованием параболы (см. ниже). Две ветви параболы разделены горизонтальной осью, на которой отмечена последовательность натуральных чисел. Затем проводятся перпендикуляры к оси в точках, соответствующих квадратам натуральных чисел. Например, в точке +4 проведен перпендикуляр, и точки его пересечения с ветвями параболы обозначены числом 2. Геометрический смысл перпендикуляра состоит в том, что он представляет собой произведение 2 x 2. Аналогично мы проводим другой перпендикуляр в точке 9, представляющий собой произведение 3 x 3, и так далее вдоль оси.

Когда все квадраты чисел на оси будут таким образом представлены точками на параболе, каждая точка на одной ветви параболы соединяется со всеми точками на другой ветви, то есть точка 2 верхней ветви параболы соединяется с точками 2, 3, 4, 5 и так далее на нижней. Каждый из этих отрезков пересечет ось в точке, соответствующей произведению двух соединенных чисел: например, отрезок, соединяющий числа 2 и 3, пересекает ось в точке 6. В конце концов натуральные точки на оси, через которые не проходит ни один из таких отрезков, будут являться простыми числами. Это очень показательный пример геометрического решета.

Алгебраические реализации решета более полезны для разработки быстрых вычислительных алгоритмов. Одной из таких реализаций является решето Аткина, предложенное Артуром Аткиным и Дэниелом Бернштейном. Этот алгоритм позволяет найти все простые числа, меньшие или равные данному натуральному числу.

Геометрическое решето, разработанное Юрием Матиясевичем и Борисом Стечкиным для поиска простых чисел (они отмечены серыми точками на рисунке). Обратите внимание: через них не проходит ни один отрезок.

В некотором смысле это улучшенная версия решета Эратосфена. Когда мы говорим «улучшенная», мы на самом деле имеем в виду «обновленная», так как решето Аткина, строго говоря, уступает решету Эратосфена. Эта версия устраняет числа, кратные не простым числам, а только квадратам простых чисел.

Конечно, в идеале хотелось бы получить формулу, которая связывает каждое натуральное число n с n-м простым числом. Мы видели, что математики пытались найти эту формулу на протяжении по крайней мере 3000 лет. Функции, которые у нас имеются, позволяют вычислять простые числа практическим способом. Например, доказано (теорема Вильсона), что р является простым числом тогда и только тогда, когда (р — 1)! —1 (mod р). Однако, как мы упоминали выше, любая формула, содержащая факториал, является недопустимой для компьютерных алгоритмов, потому что быстрый рост функции будет сильно замедлять вычисления.

Существуют также многочлены для «генерации» простых чисел, подобные тем, что использовал Эйлер, чтобы получить список 40 простых чисел с помощью функции f(х) = х 2 + х + 41, которая генерирует простые числа для каждого значения х.

Однако формула не работает начиная со значений 41 и 42, при подставлении которых получаются составные числа:

х = 41; f(41) = 1681 + 41 + 41 = 1763;

х = 42; f(42) = 1764 + 42 + 42 = 1848.

Эйлер продолжил изучение этого многочлена и пришел к выводу, что многочлен более общего вида, х 2 — х + q, будет генерировать простые числа для значений х между 0 и q — 2. Существуют также многочлены, открытые Джонсом, Сато, Вада и Вьенсом в 1976 г., которые генерируют только простые числа при подставлении значений их переменных. Эти довольно сложные многочлены содержат 28 переменных. Они не представляют большой практической пользы: если получается положительное значение, оно является простым числом, но в большинстве случаев (почти всегда) результат является отрицательным числом.

В настоящее время большинство известных простых чисел (мы всегда имеем в виду большие простые числа) являются так называемыми простыми числами Мерсенна. Причина этого — в наличии теста простоты Люка-Лемера, который эффективно работает для чисел такого типа. Напомним, что число Мерсенна имеет вид 2 n — 1. Когда такое число является простым, оно называется «простым числом Мерсенна». На момент 14 апреля 2011 г. известно только 47 простых чисел Мерсенна. Самым большим из них является число 2 43112609 —1, которое имеет почти 13 млн цифр.

ПРОЕКТ GIMPS

Широкомасштабный интернет-проект по поиску простых чисел Мерсенна (GIMPS — Great Internet Mersenne Prime Search) начался по инициативе Джорджа Вольтмана и использует сеть соединенных через интернет персональных компьютеров добровольцев (любой желающий может зарегистрироваться). Эти компьютеры работают параллельно и в совокупности представляют собой вычислительные мощности, превосходящие возможности любого суперкомпьютера. Каждый доброволец устанавливает соответствующее программное обеспечение, и его компьютер выполняет вычисления в периоды простоя. Проект был запущен в 1997 г., а к августу 2009 г. было найдено в общей сложности 12 новых простых чисел Мерсенна. Фонд Электронных Рубежей (EFF — Electronic Frontier Foundation) предложил приз в 150 тысяч долларов США за нахождение простого числа, состоящего по меньшей мере из 10 миллионов десятичных цифр. 23 августа 2008 г. приз был присужден Эдсону Смиту из Калифорнийского университета за нахождение числа 2 43112609 — 1.

Логотип Фонда Электронных Рубежей.

Как определить, является ли число простым

Единственный способ узнать наверняка — это разделить данное число на все предшествующие ему числа. Если оно не делится ни на одно из них, то оно является простым. Как мы видели в предыдущей главе, извлечение квадратного корня из числа может значительно сократить количество работы. Это хороший метод для небольших чисел и вычислений вручную. Например, мы хотим узнать, является ли число 101 простым или составным. Знание правил делимости может помочь нам избежать ненужной работы. Очевидно, что 101 не делится на 2, так как в противном случае его последняя цифра была бы четной или нулем. Не делится оно и на 3, так как сумма его цифр не делится на 3 (1 + 0 + 1 = 2). Также 101 не делится на 5, иначе оно оканчивалось бы на 0 или на 5. Мы также можем отбросить 4, 6 и 9, так как они кратны 2 или 3. Если мы попытаемся разделить 101 на 7, мы получим 14 и остаток 3. Значит, оно не делится и на 7. Следующее число, которое стоит проверить, — 11 (101, очевидно, не делится на 10). Деление на 11 дает 9 и остаток 2. Здесь мы можем остановиться и сказать, что 101 является простым числом, так как квадратный корень из 101 составляет примерно 10. Это означает, что наше число уже не будет делиться на любые другие оставшиеся числа, меньшие 101.

Этот метод называется перебором делителей и является самым простым и самым надежным. Проблема заключается в том, что он не оправдывает себя в случае очень больших чисел, даже если используется компьютер. Заметим, что для числа из 50 цифр потребуется проверка всех чисел длиной до 25 цифр, что более или менее соответствует корню из данного числа. Компьютеру, который способен выполнять миллиард операций деления в секунду, потребуется более 300 млн лет, чтобы закончить проверку, а к тому времени, вполне вероятно, человечество исчезнет с лица Земли!

Во всяком случае, этот метод работает достаточно хорошо для составного числа, если один из его делителей не является слишком большим. Следует иметь в виду, что для любого числа n вероятность того, что число 2 является одним из его делителей, составляет 50 %, а вероятность того, что делителем является число 3, составляет 33 % и так далее.

С другой стороны, скорость и объем памяти современных компьютеров значительно выросли, так что поиск простого числа в длинном списке иногда более эффективен, чем сложный процесс определения, является ли данное число простым.

В тестах простоты наиболее часто используется малая теорема Ферма. Напомним, что эта теорема гласит: «Если р — простое число, то не существует такого числа а у меньшего р (а и р взаимно просты), что a p-1 —1 дает при делении на р отличный от нуля остаток».

Теорема имеет ограничения, поскольку, как мы видели, она дает необходимое, но не достаточное условие. Например, если взять р = 7, мы видим, что З 6 — 1 делится на 7. Нет никакой гарантии, что 7 — простое число (мы-то знаем, что это простое число, потому что взяли для примера небольшие числа, но мы должны представить, что имеем дело с большими числами). Однако если взять р = 8, мы видим, что при делении З 7 — 1 на 8 получается 273,25, а значит, остаток не ноль. Теперь мы уверены, что 8 — не простое число (не находя его делителей).

Мы знаем точно, что любое число, которое не проходит тест с данным основанием а у является составным.

С другой стороны, если число проходит тест и является простым, мы называем основание «ложным». И продолжаем тестирование. Вероятность обнаружения «ложных» чисел уменьшается на 1/2 с каждым тестом, так что вероятность того, что число является простым, продолжает расти.

Число р, которое, не являясь простым, проходит тест с основанием а, называется псевдопростым для этого основания. Можно дать более общее определение псевдопростого числа: число называется псевдопростым, если оно проходит тест простоты, но оказывается составным.

Дело обстоит сложнее для чисел, которые проходят тесты с любым основанием, но не являются простыми. Например, число 561 проходит тест простоты с любым основанием и все же является составным (561 = 3 х 11 х 17). Такие числа, открытые американским математиком Робертом Кармайклом (1879–1967), называются числами Кармайкла. Сегодня известно 2163 числа Кармайкла, и они находятся среди первых 25 млрд натуральных чисел. Все они имеют по крайней мере три простых делителя.

Существует 16 чисел Кармайкла, меньших 100 000, а именно:

561,1105,1729, 2465, 2821, 6601, 8911,10585,15841, 29341, 41041, 46657, 52633, 62745, 63973, 75361.

Числа Кармайкла также называют абсолютными псевдопростыми числами.

Сегодня существует два типа алгоритмов, используемых для определения, является ли число простым: детерминированный полиномиальный и вероятностный полиномиальный.

Первый из них точно устанавливает, является ли число простым, но требует много времени. Второй метод быстрее, но при его применении существует некоторая неопределенность результата.

6 августа 2002 г. три исследователя из технологического института в Канпуре (Индия), Маниндра Агравал, Нирадж Каял и Нитин Саксена, опубликовали полиномиальный детерминированный тест простоты на основе обобщения малой теоремы Ферма:

Несмотря на это, наиболее часто используемым методом по-прежнему является вероятностный полиномиальный алгоритм — в силу своего быстродействия.

Большинство веб-браузеров включает алгоритм шифрования, который может использовать такой метод для поиска больших простых чисел до 2048 битов.

Сегодня используются три криптографических системы: RSA, DSA (Digital Signature Algorithm, алгоритм цифровой подписи), и ECDSA (Elliptical Curve Digital Signature Algorithm, алгоритм цифровой подписи на эллиптических кривых). Ни один эксперт не сомневается в безопасности, предоставляемой каждой из этих трех систем. Разница между ними заключается в кодах, которые они используют: безопасность, которую обеспечивают 2048-битные коды в первых двух, эквивалентна использованию 224 битов в третьей, при этом время вычислений значительно уменьшается. В то время как в первых двух используются субэкспоненциальные алгоритмы, в третьей применяется экспоненциальный тип, что дает лучшие результаты.

Число 313 изображено на номерном знаке автомобиля Дональда Дака. Оно обладает любопытным свойством палиндрома: его можно читать слева направо и справа налево как в десятичной системе счисления, так и в двоичной. Это единственное трехзначное простое число с таким свойством: 313 (в десятичной системе) = 100111001 (в двоичной системе). Кроме того, число 100111001 в десятичной системе счисления является простым.

Существует много простых чисел со странными свойствами. Например, «репьюниты» (от repeated unit — «повторенная единица»), которые состоят из длинных последовательностей единиц. Число 11111111111111111111111 (двадцать три единицы) является простым. В принципе, это просто диковинки, хотя в один прекрасный день эти числа могут стать частью теоремы или гипотезы, имеющей некую ценность в математике. Еще одна любопытная последовательность основана на числе 91, которое является составным (91–13 x 7). Если в середину этого числа вставлять последовательности нулей и девяток, то полученные числа чередуются, являясь то простыми, то составными:

К сожалению, следующее число 999999999990000000001 также является составным!

Мы видели, как математики, такие как Мерсенн, Ферма, а иногда даже сам Эйлер, искали практические инструменты для работы с числами. Это в некоторой степени подрывало становление строгой теории. Доказательства едва упоминались, но результаты продолжали использоваться. Гаусс начал новую эру в истории математики, настояв на том, что приведение строгих доказательств должно быть главной целью.

Тем не менее с простыми числами мы снова, казалось бы, опираемся на эмпирический подход. Мы используем недоказанные теоремы и полагаемся на результаты, если знаем, что вероятность ошибки очень мала. Мы действуем как Ферма, но даже не пытаемся прятать гипотетические доказательства. Мы можем так делать, потому что, во-первых, имеем огромные возможности благодаря компьютерным алгоритмам, а во-вторых — огромную потребность в больших простых числах.

В чисто теоретическом смысле можно сказать, что простые числа продолжают сопротивляться усилиям математиков. История их исследований в значительной степени является историей неудач. Наибольший успех был с дзета-функцией Римана, но мы все-таки понимаем, что это лишь частичный успех. Эйлер, который был великим математическим провидцем, не испытывал особенно оптимистичных чувств по поводу наших шансов понять эти неуловимые числа: «Математики уже давно тщетно пытаются найти закономерности в последовательности простых чисел, но у меня есть основания полагать, что это тайна, в которую человеческий разум никогда не сможет проникнуть».

Читайте также

Глава 2 Простые числа: ускользающие правила

Глава 2 Простые числа: ускользающие правила Как мы уже говорили, простые числа представляют из себя одну из важных тем, которые возвращают нас к самым истокам математики, а затем по пути возрастающей сложности приводят на передний край современной науки. Таким образом,

Глава 4 Логарифмы и простые числа

Глава 4 Логарифмы и простые числа Когда мы исследуем объект, приборы, которые мы используем, тоже влияют на результаты наблюдений. Например, развитие астрономии было тесно связано с совершенствованием телескопов, а микробиология — с микроскопами. Оборудование для

Подбери пару (Что для чего)

Подбери пару (Что для чего) Цель. Расширять представления детей о предметах домашнего обихода – посуде, форме и пропорциях предметов посуды. Закреплять умение составлять целый предмет из отдельных частей, называть его части. Учить объединять предметы по назначению,

Глава 1 Числа

Глава 1 Числа Альберт! Перестань указывать Богу, что Ему делать! Нильс Бор — Альберту Эйнштейну Вначале были число и фигура. Когда человек попытался овладеть ими, родилась наука, и человек начал познавать окружающий мир. Развитие науки часто сопровождалось забавными,

ГЛАВА 2 ПРОСТЫЕ ЧИСЛА

ГЛАВА 2 ПРОСТЫЕ ЧИСЛА § 1. Простые и составные числа Должно быть, одним из первых свойств чисел, открытых человеком, было то, что некоторые из них могут быть разложены на два или более множителя, например,6 = 2 • 3, 9 = 3 • 3, 30 = 2 • 15 = 3 • 10,в то время как другие, например,3, 7, 13, 37,не

§ 1. Простые и составные числа

§ 1. Простые и составные числа Должно быть, одним из первых свойств чисел, открытых человеком, было то, что некоторые из них могут быть разложены на два или более множителя, например,6 = 2 • 3, 9 = 3 • 3, 30 = 2 • 15 = 3 • 10,в то время как другие, например,3, 7, 13, 37,не могут быть разложены

§ 2. Простые числа Мерсенна

§ 2. Простые числа Мерсенна В течение нескольких столетий шла погоня за простыми числами. Многие математики боролись за честь стать открывателем самого большого из известных простых чисел. Разумеется, можно было бы выбрать несколько очень больших чисел, не имеющих таких

§ 3. Простые числа Ферма

§ 3. Простые числа Ферма Существует также еще один тип простых чисел с большой и интересной историей. Они были впервые введены французским юристом Пьером Ферма (1601–1665), который прославился своими выдающимися математическими работами. Первыми пятью простыми числами

§ 2. Взаимно простые числа

§ 2. Взаимно простые числа Число 1 является общим делителем для любой пары чисел а и b. Может случиться, что единица будет единственным их общим делителем, т. е.d0 = D(a, b) = 1. (4.2.1)В этом случае мы говорим, что числа а и b взаимно простые.Пример. (39, 22) = 1.Если числа имеют общий

§ 1. Числа

§ 1. Числа «Все есть число» — учили древние пифагорейцы[8]. Однако количество чисел, которыми они пользовались, ничтожно по сравнению с фантастической пляской цифр, окружающих нас сегодня в повседневной жизни. Огромные числа появляются, когда считаем мы, и тогда, когда

Глава 4. Длины и числа

Глава 4. Длины и числа Длина отрезка есть некое соотнесённое с отрезком число. Из теоремы о несоизмеримости немедленно следует, что длина диагонали единичного квадрата, то есть квадрата со стороной длины единица, не может быть выражена ни целым, ни дробным числом. Таким

ЧИСЛА, ЧИСЛА, ЧИСЛА…

ЧИСЛА, ЧИСЛА, ЧИСЛА… — Есть такая книга, — начал Мате, — «Диалоги о математике». Написал ее выдающийся венгерский математик нашего века Альфред Реньи. Форма диалога выбрана им не случайно, как не случайно, вероятно, обратился к ней когда-то Галилео Галилей.Жанр диалога

Глава 0 Быстрые трюки: простые (и впечатляющие) вычисления

Глава 0 Быстрые трюки: простые (и впечатляющие) вычисления Далее вы узнаете, как быстро выполнять математические действия в уме. После непродолжительной практики и освоения методов этой книги ваша способность работать с числами значительно улучшится. После более

47. Три числа

47. Три числа Какие три целых числа, если их перемножить, дают столько же, сколько получается от их

47. Три числа

Глава 1. Что такое анализ бесконечно малых и для чего он нужен

Глава 1. Что такое анализ бесконечно малых и для чего он нужен Анализ бесконечно малых — это область математики, которая имеет огромное значение для науки и техники. Чтобы понять, из чего состоит эта сложная и тонкая дисциплина, наверное, следует начать с рассказа о

Источник

• Популярная книга Круть доступна для чтения прямо сейчас на нашем сайте boochi.ru. Скачать книгу в формате FB2, TXT, PDF, EPUB бесплатно без регистрации. →