Hacker News Digest

RSA-алгоритм изначально использовал функцию Эйлера φ(n), но со временем её заменили на функцию Кармайкла λ(n). Это изменение незаметно для пользователей, но оно важно: λ(n) делит φ(n) и может уменьшить приватный ключ в 2-3 раза, что ускоряет расшифровку. Однако экономия невелика, так как gcd(p-1, q-1) почти всегда равен 2 или 4.

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

Новые методы в алгебраической геометрии возрождают классические задачи, восходящие к древнегреческим математикам вроде Аполлония Пергского. Используя теорию обогащённой схемы — относительно молодой подход, разработанный в последние десятилетия, — исследователи смогли систематически подсчитывать геометрические объекты, удовлетворяющие заданным условиям, например, количество окружностей, касающихся трёх данных. Этот метод позволяет учитывать вырожденные случаи и мультипликативности, которые ранее затрудняли точные вычисления.

Один из ключевых результатов — доказательство того, что на кубической поверхности лежит ровно 27 прямых, а также уточнение числа конических сечений, касающихся пяти заданных. Подход не только даёт строгие ответы на многовековые вопросы, но и открывает пути для решения более сложных проблем, связывая геометрию с алгеброй и теорией чисел. Это показывает, как современные абстракции оживляют древнейшие математические интуиции.

• Участники обсуждают сложность понимания математических концепций из статьи Quanta Magazine, в частности, теории Громова-Виттена и подсчёта линий на кубической поверхности.
• Некоторые пользователи выражают затруднение или полное непонимание темы, отмечая, что даже поиск не прояснил вопрос.
• Один из комментаторов предлагает простое визуальное наблюдение о состояниях круга (2^3=8), но не как доказательство, а как заметку.
• Высказывается мнение, что Quanta Magazine в целом хорошо и точно доносит суть сложных тем, вселяя доверие даже к статьям вне зоны компетенции читателей.
• Поднимается вопрос, сохраняется ли обсуждаемое математическое правило для большего количества точек (4, 5, 10).

План самообразования математика-чистяка (или статистика)

Этап 1

• школьная база
• дискретка, алгебра, анализ начального уровня

Этап 2

• линейная алгебра
• высшая алгебра
• вещественный и комплексный анализ
• диффуры, вероятность и статистика

Этап 3

• анализ, абстрактная алгебра, теория чисел
• топология, диффгеометрия
• по желанию: моделирование, статвывод, стохастика, вычислительная статистика

Этап 4

• фундамент: логика, множества, комбинаторика, криптография
• анализ: функциональный, мера, гармонический
• алгебра: группы, кольца, поля, гомологии
• числа: алгебраическая и аналитическая теория, эллиптические кривые
• геометрия и топология: алгебраическая, риманова, K-теория
• опционально: диффуры в частных, матфизика, вероятность на мере, многомерная статистика, байес, выживание, data mining

Этап 5

• читаем монографии и статьи, выбираем специализацию, делаем исследования

«Как пианист: сначала скучные этюды, потом — музыка» (Терри Тао).

• Классические «дорожные карты» по чистой математике часто выглядят как бесполезные списки книг без объяснения, зачем и в каком порядке их читать.
• Настоящий путь проще: крепкая линейная алгебра и анализ (Шилов, Рудин), дальше — основные учебники по геометрии, алгебре и анализу с доказательствами и наставником.
• Единственный способ стать математиком — публиковать исследования; маршрут любой, лишь бы вам было интересно и вы могли его пройти.
• Споры о «требуемом IQ 145» вызывают бурю критики: IQ не определяет креативность и усердие, а SAT/ACT лишь коррелируют с успехом, но не гарантируют его.
• Проверять стоит не коэффициент интеллекта, а свои реальные успехи в математике: умеете ли вы читать и писать доказательства, получаете ли удовольствие от процесса.

Бог создал действительные числа, а не целые.
16-вековая Италия считала науку знанием о вечном, созданном Богом, а искусство — делом человеческим. Кронекер утверждал: «Бог сотворил целые, всё остальное — дело рук человеческих». Но целые слишком просты и элегантны, чтобы быть «божественными»; природа не стремится к абстрактной простоте. Настоящая «божественная» математика — это иррациональные, «тошнотворные» действительные числа: √2, π и прочие бесконечности, вызывающие у человека головокружение.

Иерархия странности
Вечная природа → природа → люди → человеческие идеи. Чем ближе к вечной природе, тем выше степень странности. Целые числа лежат ближе к человеческим идеям, поэтому кажутся «совершенными»; молоток кажется идеальным инструментом, потому что был изобретён людьми для людей.

Кронекер, Кантор и Бог
Кронекер атаковал бесконечность, чтобы защитить «божественные» целые. Кантор же видел в трансфинитах путь к Богу и полагал, что математика — это Бог, говорящий через него. Гильберт назвал «рай Кантора» неизгладимым.

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

Что такое «Busy Beaver»
Функция Σ(n) показывает максимальное количество 1, которое может оставить на ленте останавливающаяся машина Тьюринга с n состояниями и двумя символами (0 и 1). Аналогично, S(n) — максимальное число шагов до остановки. Оба значения растут быстрее любой вычислимой функции, поэтому уже Σ(5) и S(5) неизвестны без компьютерного перебора.

Новый рекорд: n = 6
Команда «Beaver Hunters» (Scott Aaronson, Shawn Ligocki et al.) доказала:

• S(6) = 36 534 678 263 377 ≈ 3,65 × 10¹³
• Σ(6) = 10 ↑↑ 15
  (15-я степень десятки в стеке степеней: 10^(10^(10^…)))

Это число настолько велико, что его нельзя записать в обычной десятичной форме: для этого потребовалось бы больше атомов, чем во Вселенной.

Как нашли

• Использовали SAT-решатели и распределённые вычисления, чтобы перебрать ~10⁴⁴ машин.
• Для оставшихся «подозрительных» случаев построили индивидуальные доказательства остановки или бесконечного цикла.
• Работа заняла ~2 года и миллионы часов CPU.

Зачем это нужно

• Busy Beaver служит «натуральной» границей между вычислимым и не-вычислимым.
• Новые методы перебора и доказательств могут пригодиться в верификации ПО и теории сложности.
• Следующая цель — n = 7, но она потребует принципиально новых идей и, вероятно, ещё более фантастических чисел.

• Участники обсуждают сверхбольшие конечные числа: Busy Beaver, TREE(3), субкубические графы и быстро-растущие иерархии.
• BB-функция растёт быстрее любой вычислимой функции и не вычислима; для N>549 нельзя доказать в ZFC, что какое-то вычислимое число ≥BB(N).
• Поделились ссылками на видео Numberphile, плейлист Дэвида Мецлера и статью Скотта Ааронсона.
• Появились размышления о том, что делает такие числа интереснее бесконечности, а также о состоянии ленты после остановки BB(5).
• Некоторые критикуют статью Quanta за поверхностное описание экспоненциации и отсутствие объяснения сути BB.