ch
Feedback

不要被骗子欺骗!Telemetrio 会找到并标记这些频道 👉 如果想查看标记,请订阅

Математические байки

Математические байки

前往频道在 Telegram

Рассказы про разную математику. Архив: http://dev.mccme.ru/~merzon/mirror/mathtabletalks/

显示更多
4 360
订阅者
无数据24 小时
+117 天
+4030 天
帖子存档
photo content
07 4月 2020, 06:11

И находим делители —
07 4月 2020, 06:10

photo content
07 4月 2020, 06:10

Находим A и B:
07 4月 2020, 06:10

photo content
07 4月 2020, 06:10

Оказывается, что взяв три небольших k=2,3,7, мы уже видим (mod 2)-линейную зависимость между векторами степеней:
07 4月 2020, 06:10

Игрушечный пример: факторизуем число 64643.
07 4月 2020, 06:07

Вот мы и получили совпадение: построенное произведение a_{k_j} будет и настоящим полным квадратом в обычных целых числах (так что A — обычный корень из этого произведения), и будет по модулю n сравнимо с квадратом произведения (m+k_j) — соответственно, B это произведение (m+k_j).
07 4月 2020, 06:06

И когда мы, просто увеличивая k, наберём достаточно много гладких чисел (больше, чем простых в базе Base) — то вектора степеней разложения (координаты соответствуют простым из базы) начнут быть зависимыми по модулю 2. И произведение соответствующих a_{k_j} будет полным квадратом, и мы будем знать, чьим.
07 4月 2020, 06:05

Понятно, что если мы раскладываем на множители, скажем, 100-значное число n — то a_k будут порядка корня из n, то есть 50-значными. И раскладывать каждое из них на множители это опять та ещё задача. Но — мы выберем некоторый набор Base "не слишком больших" простых (который называется базой ). Скажем — первую сотню тысяч, или миллион. И если какое-то a_k не раскладывается в произведение простых из Base — то просто выбросим его. А если раскладывается — запомним (и назовём такое число " гладким ").
07 4月 2020, 06:04

Но, во-вторых (и это ключевой шаг), можно попробовать найти произведение a_k, которое будет полным квадратом. А именно — предположим, что у какой-то их части оказались одни и те же простые делители. Тогда, чтобы произведение каких-то a_{k_j} было полным квадратом, достаточно их перемножить так, чтобы все степени простых оказались чётными.
07 4月 2020, 06:03

Тогда, во-первых, любое a_k по модулю n является квадратом известного нам вычета (m+k).
07 4月 2020, 06:02

photo content
07 4月 2020, 06:02

Итак, идея. Берём числа, примерно равные корню из n, и посмотрим на их квадраты по модулю n:
07 4月 2020, 06:01

Остаётся такие нетривиальные пары (A,B) найти. Наверное, если бы мы искали B по данному A, то никакого выигрыша без факторизации мы бы не получили — кажется, задача просто равносильна факторизации. Но можно искать именно пару — не зная, ни какое получится A, ни B.
07 4月 2020, 06:01

А основан он на том, что если A^2=B^2 mod n, то либо A=B mod n, либо A=-B mod n, либо и (A+B), и (A-B) имеют нетривиальные общие делители с n. И если первый и второй варианты неинтересны, то последний как раз (алгоритмом Евклида) и приводит к факторизации.
07 4月 2020, 06:00

Мы уже видели метод Ленстры факторизации с помощью эллиптических кривых — который для больших чисел третий по эффективности. Удивительным образом, второй по эффективности метод, метод квадратичного решета, заметно проще и продвинутую науку не использует.
07 4月 2020, 05:59

Добрый день! Я собираюсь продолжить рассказ про работы Маргулиса и геометрию решёток, но сначала — чтобы немного переключаться между сюжетами — вернёмся ненадолго к криптографии и к задаче факторизации.
07 4月 2020, 05:58

Вот. Рассказ получился не самым простым — но и работа меньше, чем 15-летней давности!
06 4月 2020, 12:31

И это и есть то самое место, где применяется теория автоморфных форм и вообще техника. А дальше — если мы рассмотрим T-образ разницы I_A-I_B, то матожидание его квадрата не больше, чем 2a. И складывая это с оценкой на дисперсию T(I_B) — опять получаем линейную по a оценку на дисперсию T(I_A)=T(I_A-I_B)+T(I_B). Значит, T(I_A) опять обращается в 0 с вероятностью, не большей C/a. И значит, с вероятностью не больше C/m(A) случайная решётка не пересекает A.
06 4月 2020, 12:29