Математика для гиков - Рафаель Роузен

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

2 – простое число.

3 – простое число.

4 = 2 × 2

5 – простое число.

6 = 2 × 3

7 – простое число.

8 = 2 × 2 × 2

9 = 3 × 3

10 = 2 × 5

11 – простое число.

12 = 2 × 2 × 3

13 – простое число.

И так далее.

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

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

1. Во-первых, помните, что каждое число – это простое число или же получено путем перемножения ряда простых чисел.

2. Во-вторых, мы будем использовать особый вид способа доказательств под названием reduction ad absurdum (доведение до абсурда): мы попробуем доказать противоположное тому, что мы пытаемся доказать. Если мы докажем, что это противоположное не может быть правдой, тогда мы будем знать, что противоположное ему утверждение – то, что мы изначально хотели доказать, – будет истиной.

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

Шаг первый: давайте изобретем число и назовем его «Джордж». Скажем, что мы можем получить Джорджа, если перемножим все простые числа, от первого до последнего, а потом прибавим к результату 1. (Не забывайте, что мы предполагаем, что существует ограниченное количество простых чисел.) Мы знаем, что Джордж должен быть простым числом или должен быть получен в результате умножения простых чисел. Мы сразу же можем увидеть, что если Джордж является простым числом, то мы доказали, что есть простое число – Джордж! – которое не входило в наш изначальный список. Теперь мы можем остановиться и похлопать себя по спине, так как наш результат будет актуален для любого количества простых чисел.

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

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

Числа Ферма

Некоторые простые числа экзотичнее других. Числа Ферма, например, имеют вид 22n + 1 и являются простыми. Однако единственными известными числами Ферма являются те, где n = 0, 1, 2, 3 и 4 и равны 3, 5, 17, 257 и 65537 соответственно.

Забудьте об электронной почте и социальных сетях. Тогда наиболее глубокое влияние Интернета на мир могут оказывать интернет-магазины. Но онлайн-коммерция таит в себе опасности. Когда вы вбиваете номер своей кредитной карты на такие сайты, как Amazon, и кликаете «Купить», что останавливает киберворов от перехвата этой информации и кражи номера?

Обратимся к математике. Безопасность работы в Интернете и криптография с открытым ключом в целом основаны на простых числах, особом виде чисел, которые делятся только на себя и на 1. (Для сравнения: число 10 делится на себя, 1, 2 и 5 и простым не является.) Примерами простых чисел являются 1, 3, 5, 7 и 11, но их существует бесконечное множество и соответственно могут расти на огромные расстояния. Существует математическое доказательство того, почему простых чисел бесконечное множество, но это уже другая история (см. главу 4.2).

Когда вы вбиваете номер своей кредитной карты онлайн, вы пользуетесь так называемым алгоритмом RSA. Он был назван в честь создателей – Рональда Ривеста (Rivest), Ади Шамира (Shamir) и Леонарда Адлемана (Adleman). Алгоритм был создан в 1977 году и является системой шифрования, которая основывается на огромных простых числах. В сущности, система обеспечивает безопасность ваших личных данных путем преобразования номера вашей кредитки в другой, чрезвычайно длинный номер, который получен в результате умножения двух длинных случайных простых чисел. Вы могли бы превратить этот новый номер обратно в номер своей карточки, если бы знали два простых числа, но безопасность ваших данных обеспечивается еще одним математическим фактом: крайне тяжело разложить большое число на простые числа. На самом деле, для очень длинного числа могут понадобиться сотни и тысячи лет для того, чтобы сеть суперкомпьютеров смогла найти два правильных простых числа.

Хотя в последнее время появилась информация, что система RSA не такая надежная, как думалось. Целостность системы зависит от генерации случайных простых чисел, но программы, которые этим занимаются – известные как генераторы случайных чисел, – кажется, не всегда создают такие уж случайные числа. Такое несоответствие оставляет место для мошенников, которые могут определить эти два простых числа и украсть конфиденциальную информацию.

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

Биткойны

Любой, кто использует биткойны – виртуальную валюту, изобретенную в 2008 году, – должен иметь какой-то электронный кошелек, который находится в безопасности от криптографии с открытым ключом. На самом деле биткойн – это первая валюта, которая основывается на криптографии. Чтобы получить доступ к своим биткойнам, у вас должно быть два ключа: один публичный, а другой секретный, как пин-код или пароль. Два ключа математически связаны.

Все видели знак бесконечности: цифра восемь, лежащая на боку (∞). Но что такое бесконечность и как она связана с математикой?