Наш исследователь @YoussefElHousn3 только что опубликовал новую статью: "Быстрые кубические корни в Fp2 через алгебраический торус." Давайте разберем это на что-то более усваиваемое.

Представьте, что вы находитесь в Южном Париже и вам нужно добраться до ресторана в Северном Париже. До сих пор стандартным методом было ехать прямо через центр города (Fp2) - «сложный мир», где каждое вычисление стоит ~3× больше из-за светофоров и остановок. Прямо в центр города? Это медленно, дорого и неэффективно.

Юсеф выбирает другой маршрут: périphérique (кольцевая дорога). Математически он проецирует проблему на алгебраический тор T2(Fp), структура, след которой полностью находится в Fp - "простом мире". Там он использует последовательности Лукаса для вычисления кубического корня, где каждый шаг - это одна дешевая операция вместо трех. Обходя центр города, вы экономите время, деньги и повышаете эффективность.

Теперь интересная часть: найти точный ресторан. В конце вам нужно будет свернуть на правильный выход с кольцевой дороги. Это шаг восстановления. Вы комбинируете кубический корень нормы N(x) и ваше положение на торе (оба вычислены в Fp), чтобы восстановить точные координаты обратно в Fp2. Вычисление кубического корня N(x) в Fp не дёшево. Но Юсеф вычисляет его почти бесплатно во время проекции тора и сохраняет для последующего использования. Так что это похоже на запоминание вашего выхода в тот момент, когда вы входите на кольцевую дорогу.

Так что же это на самом деле дает? С помощью этого подхода Юсеф ускоряет вычисление кубического корня до 2,1× — основной операции, используемой в декомпрессии точек ZK, хешировании в кривую и постквантовых изогенных протоколах.