Перебор для факторизации Ферма можно ускорить, анализируя остатки по простым модулям. Значение p*q можно представить разностью квадратов ((p+q)/2)^2 — ((p-q)/2)^2.
Мы хотим представить нечетное N в виде A^2 — B^2. Если N % 4 == 1, то легко убедиться, что A должно быть нечетным, а B — четным. А в случае N % 4 == 3 наоборот: A четное, B нечетное.
Дальше смотрим на N % 3. Если N % 3 == 1, тогда A не кратно 3, B кратно 3. В случае N % 3 == 2 у нас A кратно 3, B не кратно 3.
И дальше, перебирая остатки N по простым модулям, можем ограничить возможные значения A, B по каждому модулю, и собрать по китайской теореме об остатках возможные значения по модулю произведения простых.
Например, по модулю 2*3*5*7 будет меньше 25 возможных значений из 210.
Но это еще не всё! Мы предполагаем, что N — произведение ровно двух простых N = p*q. Тогда из малой теоремы Ферма следует, что для любого x, не кратного p и q, выполняется x^((p-1)*(q-1)/2) % N == 1. Выберем например x = 2. Небольшое преобразование: 2^((N+1)/2) % N == 2^((p+q)/2) % N. Слева известное значение. Справа — неизвестный показатель, то есть свели к дискретному логарифму. Можно использовать небольшую модификацию алгоритма больших и малых шагов. За большой шаг взять произведение маленьких простых, а возможные значения для малых шагов собрать в хеш-таблицу, размер которой мы уменьшили за счет ограничений на (p+q)/2. С таким подходом кажется реальным за несколько минут перебрать значения до abs(p-q) < sqrt((p+q)/2) * 2^64
Ну ping похоже использует функцию inet_addr, а у нее правила парсинга довольно неожиданные. Например, части адреса, начинающиеся с 0, считаются восьмеричными. С этим иногда сюрприз случается — программист значение, введенное пользователем, передает в inet_addr(), а пользователь зачем-то добивает двузначные части адреса нулем слева и в результате обращение идет не к тому адресу, к которому ожидает пользователь.
В линуксе ping работает именно так. Под windows 7 было так же, кажется в 10 переделали. docs.microsoft.com/en-us/windows/win32/api/winsock/nf-winsock-inet_addr
«Ровно из тех же соображений» не получается.
Как это работает для сферы. Сначала берется тонкая сферическая оболочка, и рассматривается точка где-то внутри. Проводится произвольная прямая через нее. Расстояния до двух точек пересечения этой прямой со сферой в общем случае будут разными.
Рассматриваются два противоположных конуса вокруг этой прямой с вершиной в начальной точке. Основания конусов вырезают на сфере фрагменты, площади (и массы) которых пропорциональны квадрату высоты конуса. Ну а поскольку сила притяжения обратно пропорциональна квадрату расстояния и пропорциональна массе, они друг друга компенсируют. Тут подробнее расписано, или здесь.
Так вот, для плоского диска так не получится. Если по аналогии рассмотреть тонкое кольцо, то при таком же построении масса вырезанного сектором фрагмента кольца будет пропорциональна первой степени расстояния, а не квадрату.
А откуда сведения о сферически-симметричном распределении темной материи?
Вот такое получилось на базе последовательностей Люка:
def fib(n):
b = 1 << (n.bit_length() - 1)
f = 1
l = 1
a = 2
while b != 1:
b = b >> 1
f = f * l
l = l ** 2 + a
if n & b != 0:
a = 2
fn = (f + l) >> 1
l = fn + f + f
f = fn
else:
a = -2
return f
А статический массив, отсортированный по ключу, чем плох?
Обычно двоичное дерево полезно тем, что в нем вставка/удаление за log(n). Но если дерево неизменяемое, в чем преимущество перед массивом?
Ну в RSA абсолютно тривиальное умножение по модулю. Негде там закладку спрятать. Нахождение секретной экспоненты сразу дает факторизацию.
Вот про эллиптические кривые есть параноидальные подозрения, что для некоторых классов кривых могут существовать способы быстрого вычисления дискретного логарифма, и кое-кто пытается пропихнуть в стандарты именно такие кривые.
А как переносимо проверять переполнение после? Например, если на какой-то платформе переполнение вызывает прерывание и аварийное завершение программы?
В каком-то языке (не помню каком) так и было определено поведение при переполнении, и на x86 компилятор инструкции into вставлял после арифметических операций.
Мы хотим представить нечетное N в виде A^2 — B^2. Если N % 4 == 1, то легко убедиться, что A должно быть нечетным, а B — четным. А в случае N % 4 == 3 наоборот: A четное, B нечетное.
Дальше смотрим на N % 3. Если N % 3 == 1, тогда A не кратно 3, B кратно 3. В случае N % 3 == 2 у нас A кратно 3, B не кратно 3.
И дальше, перебирая остатки N по простым модулям, можем ограничить возможные значения A, B по каждому модулю, и собрать по китайской теореме об остатках возможные значения по модулю произведения простых.
Например, по модулю 2*3*5*7 будет меньше 25 возможных значений из 210.
Но это еще не всё! Мы предполагаем, что N — произведение ровно двух простых N = p*q. Тогда из малой теоремы Ферма следует, что для любого x, не кратного p и q, выполняется x^((p-1)*(q-1)/2) % N == 1. Выберем например x = 2. Небольшое преобразование: 2^((N+1)/2) % N == 2^((p+q)/2) % N. Слева известное значение. Справа — неизвестный показатель, то есть свели к дискретному логарифму. Можно использовать небольшую модификацию алгоритма больших и малых шагов. За большой шаг взять произведение маленьких простых, а возможные значения для малых шагов собрать в хеш-таблицу, размер которой мы уменьшили за счет ограничений на (p+q)/2. С таким подходом кажется реальным за несколько минут перебрать значения до abs(p-q) < sqrt((p+q)/2) * 2^64
В линуксе ping работает именно так. Под windows 7 было так же, кажется в 10 переделали.
docs.microsoft.com/en-us/windows/win32/api/winsock/nf-winsock-inet_addr
Как это работает для сферы. Сначала берется тонкая сферическая оболочка, и рассматривается точка где-то внутри. Проводится произвольная прямая через нее. Расстояния до двух точек пересечения этой прямой со сферой в общем случае будут разными.
Рассматриваются два противоположных конуса вокруг этой прямой с вершиной в начальной точке. Основания конусов вырезают на сфере фрагменты, площади (и массы) которых пропорциональны квадрату высоты конуса. Ну а поскольку сила притяжения обратно пропорциональна квадрату расстояния и пропорциональна массе, они друг друга компенсируют. Тут подробнее расписано, или здесь.
Так вот, для плоского диска так не получится. Если по аналогии рассмотреть тонкое кольцо, то при таком же построении масса вырезанного сектором фрагмента кольца будет пропорциональна первой степени расстояния, а не квадрату.
А откуда сведения о сферически-симметричном распределении темной материи?
И в Search сравнения?
TypeListSort тоже интересно увидеть
Обычно двоичное дерево полезно тем, что в нем вставка/удаление за log(n). Но если дерево неизменяемое, в чем преимущество перед массивом?
Вот про эллиптические кривые есть параноидальные подозрения, что для некоторых классов кривых могут существовать способы быстрого вычисления дискретного логарифма, и кое-кто пытается пропихнуть в стандарты именно такие кривые.
В каком-то языке (не помню каком) так и было определено поведение при переполнении, и на x86 компилятор инструкции into вставлял после арифметических операций.