Давным-давно в 1637 году Пьер Ферма имел глупость написать на полях «Арифметики» Диофанта следующее: «… невозможно разложить куб на два куба, биквадрат на два биквадрата и вообще никакую степень, большую квадрата, на две степени с тем же показателем. Я нашел этому поистине чудесное доказательство, но поля книги слишком узки для него».

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

Несмотря на это, она была полностью доказана лишь в 1995 году, используя теории эллиптических кривых.

Недавно сразу несколько достаточно авторитетных по местным меркам новостных порталов взорвала новость: Узбекский математик разгадал теорему Ферма — Математик из Ташкента Борис Пономарев утверждает, что отыскал «простое оригинальное доказательство» Великой теоремы Ферма — загадки, над которой ученые всего мира бьются вот уже 350 лет (например, здесь, здесь и здесь). В одной из них даже было приведено доказательство.

В соответствии со стандартами C и C++, если выполнение программы приводит к переполнению знаковой целой переменной, или к любому из сотен других «неопределённых действий» (undefined behaviour, UB), то результат выполнения программы может быть любым: она может запостить на Твиттер непристойности, может отформатировать вам диск…
Увы, в действительности «пасхальные яйца», которые бы заставляли программу в случае UB делать что-то из ряда вон выходящее, не встречались со времён GCC 1.17 — та запускала nethack, когда встречала в коде программы неизвестные #pragma. Обычно же результат UB намного скучнее: компилятор просто оптимизирует код для тех случаев, когда UB не происходит, не придавая ни малейшего значения тому, что этот код будет делать в случае UB — ведь стандарт разрешает сделать в этом случае что угодно!
В качестве иллюстрации того, как изобилие UB в стандарте позволяет компилятору выполнять неочевидные оптимизации, Реймонд Чен приводит такой пример кода:

int table[4];
bool exists_in_table(int v)
{
    for (int i = 0; i <= 4; i++) {
        if (table[i] == v) return true;
    }
    return false;
}

В условии цикла мы ошиблись на единицу, поставив <= вместо <. В итоге exists_in_table() либо должна вернуть true на одной из первых четырёх итераций, либо она прочтёт table[4], что является UB, и в этом случае exists_in_table() может сделать всё что угодно — в том числе, вернуть true! В полном соответствии со стандартом, компилятор может соптимизировать код exists_in_table() до

int table[4];
bool exists_in_table(int v)
{
    return true;
}

Такие оптимизации иногда застают программистов врасплох.

Старая математика ломает постквантовые шифры



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

Проблема в том, что современные алгоритмы вроде RSA и Диффи-Хеллмана (в том числе на эллиптических кривых) не способны противостоять квантовым атакам. Поэтому в июле 2022 года Национальный институт стандартов и технологий США (NIST) опубликовал набор алгоритмов шифрования, потенциально способных противостоять взлому на квантовых компьютерах — так называемые «постквантовые шифры».

Один из «постквантовых» шифров сразу взломали. Но самое интересное — метод, который применили исследователи.