У меня получилось сжать переведённую "Войну и Мир" обычным RLE вне зависимости от числа повторений, попробуйте Энтропийное кодирование для потока битовых флагов.
Вот код. Вроде бы и немного (21+18 строк), но он довольно таки ёмок на математику, легко допустить ошибку. Если будет несложно дополните статью, так она станет гораздо информативнее.
Максимально дубовая реализация монтгомери вместе с делением по Лемиру улучшила мой результат с 27,223 до 21,820 . Даже обидно как-то, получается раньше я вообще не в ту сторону смотрел. Но теперь до первых мест рукой подать, скорее всего можно те же вызовы _mullo_epi32 в два раза реже делать (у меня на 1 mulmod 3 simd умножения, из которых только два полноценное, и одно урезанное), или от бранча для переполнения вычитания как-то отказаться, его обработка съедает четверть всего времени. Теоретически можно оптимально распланировать умножения по битам степени, и вместо маскировки делать их только тогда когда нужно, это тоже может дать до трети всего времени (умножаем только на половину всех битов).
Да, проверяю по 4 числа одновременно. Главное заранее отсекать большую часть работы (5/6) проверкой на делимость на маленькие делители, довольно красиво сделано, но видимо можно сделать лучше, я использовал для больших libdivide_u32_do_vec256, а для маленьких (2,3,5,7) сообразил трюк с _mm256_shuffle_epi8. Тоже в восторге от результатов первой тройки. Ах да, еще нужно чтение через mmap организовать, в справке от сайта есть пример.
Все так говорят (на один символ отправка 8 байт если между ними меньше ~20ms), пробежал по коду и не вижу ничего противоречащего этому. Тестить правда лень, если хотите оспорить — wireshark/tcpdump вам в помощь.
подмешивается немного мусора
Действительно в прошлом году появился патч и опция в конфиге, мне интересно, а в вашем дистрибутиве есть эта опция? (проще всего проверить man ssh_config; /Obf)
Презентация про ssh, тут статья. Текст об этом на хабре, но я не рекомендую ни комментарии ни статью: там какая-то отсебятина про visual feedback.
Но в таком случае происходит утечка данных не только о тайминге нажатий, но и о количестве клавиш, что соответствует длине пароля
Вместе с таймингом утекает и длина пароля, ответных пакетов со стороны сервера не нужно.
В комментариях тоже какая-то дичь, например: (проблема не в комментарии или в комментаторе, а в том что его никто не поправил, так и висит).
в SSH автоматически включается Nagel's и передаваемые символы начинают группироваться и объединяться, что портит хакерам весь праздник
/* Informs that the current session is interactive. Sets IP flags for that. */
void
ssh_packet_set_interactive(struct ssh *ssh, int interactive, int qos_interactive, int qos_bulk)
{
...
set_nodelay(state->connection_in);
...
}
/* disable nagle on socket */
void
set_nodelay(int fd)
{
...
if (setsockopt(fd, IPPROTO_TCP, TCP_NODELAY, &opt, sizeof opt) == -1)
error("setsockopt TCP_NODELAY: %.100s", strerror(errno));
}
Статья про анализ серверного "пинга" со стороны собеседника в IM.
Напишу на тот случай если кто-то не понимает какую конкретно безопасность обеспечивает E2EE и для/от кого. Для любого мессенджера с моментальной доставкой сообщений и без серьёзного "замусоривания" траффика легко понять кто с кем общается используя глобальное наблюдение (без MitM) и элементарные корреляции.
Пусть пользователь A, B живут в стране, где некие вредоносные агенты Е установили специальное оборудование сохраняющее метаданные всего оконечного трафика на всех провайдерах связи. Пусть агенты E знают A, но не знают B, про B известно что он один из множества U.
Теперь каждый раз когда A пишет сообщение B, он инициирует обмен сетевым трафиком с серверами напрямую (Telegram), через peer-to-peer сеть(Tor), либо даже с использованием туннеля с дополнительным шифрованием ( Wireguard или OpenVPN). Но во всех популярных любительских сценариях использования (за редким исключением вроде i2p) размеры пакетов меняются крайне предсказуемо, а то и не меняются вовсе. Теперь E, зная паттерны трафика нового сообщения (а в случае push уведомлений можно опираться и на ip-подсеть как на показатель пуша), запоминает текущее время.
Затем это сообщение должно прийти B, где ситуации повторится. Так как множество людей из U могут получить подобный трафик случайно, E может лишь ограничить размер множества U - даже для довольно таки большого окна доставки в минуты (типично для пуш-уведомлений) с каждым сообщением размер U будет сокращаться в разы, если не в десятки. Для однозначного установления B потребуется около 27 бит информации (|U|~=1.4e8), что вполне себе достижимо при регулярном общении. Даже если утекать будут малые доли бита (т.е. агенты E очень не уверены в том что произошло общение), из того что нам их нужно собрать буквально десятки, при достаточном количестве сообщений легко вычислить весь граф общения.
Эту картину не меняет даже вменяемый false-positive (пусть например фоном запущенный ютуб раз в 15 секунд даёт картину похожую на сообщение, тогда мы должны учесть шанс того что A ничего не отправлял). В таком случае мы не выкидываем кандидатов из U, а честно обновляем ожидания по Байесу. Если проделать подобное в итоге получатся что граф общения оказывается (ребро между вершинами если они общаются) равен попарной временной корреляции "интересного" трафика относительно U.
Подправив параметры можно узнать например на какие каналы в youtube вы подписаны не залезая в шифрованный трафик, достаточно посмотреть корреляцию жирного потока на сервера гугла с расписанием публикации новых видео, (если вы конечно открываете их сразу по уведомлению).
Да, это вычислительно сложная задача, но явно не сложнее подсчета условного PageRank-a для поискового индекса с MapReduce, естественно считать в лоб (O(|U|^2)) нельзя.
Слайды про утечку пользователя по паролю при наборе его используя SSH (не совсем в тему, но идея похожая)
Определение местоположения пользователя популярных "защищенных" мессенджеров
Тут исследователи не пользуются глобальным мониторингом траффика, смотрят только на раундтрипы оповещения о доставке.
P.S. Задумался над тем что бы комментарий до статьи добить, но об подобном на хабре уже писали еще в 2011 (в контексте Tor, Tarzan и Morphmix).
Еще я сомнительным способом генерировал случайное целое, uniform_uint64() % (HI-LO) + LO В районе 10^18 там уже значительный перекос в пользу меньших чисел.
Было бы любопытно узнать, как график ведёт себя на бесконечности
Прогнал Монте-Карло на равномерных неупорядоченных парах, (это не точно учтёт пары где x=y, но так как их немного, погрешность должна быть небольшой).
Просто взял p:=cnt_good/cnt_iters; estimate:=81*10^{d-2}*p/2;
Скорость симуляции получилась около 5 миллиардов итераций в секунду, что не впечатляет. Пришлось немного попотеть что бы правильно работать с 36-значными числами.
@cuda.jit
def cuda_run_core(A, oA, oB, B):
B0 = B // BASE
pos = cuda.grid(1)
if pos + 1 < A.size:
b_lo = A[pos]
b_hi = A[pos + 1]
for b in range(b_lo, b_hi):
if b % BASE == 0:
continue
rb = rev(b)
a0 = uint64(math.ceil(rb * 1.0 * B / b))
for a in range(a0, a0 + BASE):
if not (B0 <= a < B):
continue
ra = rev(a)
err = uint64(a * b - rb * B)
if err == ra:
oA[pos] = a
oB[pos] = b
if err > B:
break
Проверяет все до m=12 за минуту на видюшке. Посмотрим что будет с m=14 через пару часов.
Hidden text
@cuda.jit(device=True)
def cuda_rev(x):
r = uint64(0)
while x > 0:
r = r * BASE + x % BASE
x = x // BASE
return uint64(r)
def run_cuda(d):
# 10 -> 0.638
# 11 -> 6.601
# 12 -> 68.787
# 13 -> 775.907
num = 2**18
A = np.linspace(pow(BASE, d - 1), pow(BASE, d), num).astype(np.uint64)
oA, oB = np.zeros_like(A), np.zeros_like(A)
threadsperblock = 2**9
blockspergrid = (A.size - 1 + (threadsperblock - 1)) // threadsperblock
A, oA, oB = cuda.to_device(A), cuda.to_device(oA), cuda.to_device(oB)
cuda_run_core[blockspergrid, threadsperblock](A, oA, oB, uint64(pow(BASE, d)))
A, oA, oB = A.copy_to_host(), oA.copy_to_host(), oB.copy_to_host()
for x, y in zip(oA, oB):
if x:
print(x, '*', y, '=', rev(y), rev(x))
def main():
for d in range(8, 16):
t0 = time.perf_counter()
run_cuda(d)
t1 = time.perf_counter()
print(f'{d} -> {t1-t0:.3f}')
Эксперты компании по отслеживанию космического мусора LeoLabs говорят, что обломки будут находиться на орбите еще долго, и возникнет «потенциальный риск столкновения с большинством спутников на низкой околоземной орбите в течение следующих нескольких лет или десятилетий».
Очень сомнительное ограничение в 56 на путь, так-то змейка на карте в 60x60 что-то порядка 1700 дает. В мире плюсов аллокацию из библиотеки можно избежать output iterator-ом, там такое на шаблонах бесплатно, в го так не выйдет.
Ого. Ходил еще школьником на его курс по питону 14-15 лет назад, жалко не имел подходящий mindset для этих занятий в то время. Вроде бы делали рисовалку на pygame. Действительно многому научил.
Помню через несколько лет уже в МФТИ сокурсники удивлялись этому факту когда мы учили курс по ОСям по его учебнику.
"Основы вычислимости и теории сложности" - крайне полезный курс в CS, думаю что большинству программистов стоит с ним ознакомится.
А по сути дела статья какая-то дичь:
Зададим некоторое количество натурально пронумерованных действительных чисел
Какое отношение имеют действительные числа к теории сложности?
Распределение которых может иметь произвольный характер
Ну и зачем нам тут случайные величины? Правда чуть ниже что-то похожее на определение Мартингала.
Если, найдётся такая последовательность, что для неё строго не обнаружиться
Определение классов скопировано правильно, но сразу после этого идет без каких либо пояснений переформулировка на язык последовательностей. Я так и не понял как может быть связана одна последовательность с языком.
оперативно-количественном весеm(WhT) - условно определяется через время за которое с точностью в 100%, без методов аппроксимирования
Фу, ужас, отвратительно.
Ощущение что вы даже свой список литературы не открывали, по первой же ссылке весьма грамотно замечают:
С сожалением приходится констатировать, что проблема эта стала даже слишком популярной. Не будет большим преувеличением сказать, что ферматисты XXI века доказывают, что . Работы с такими "доказательствами" публикуются регулярно и, как правило, несут на себе печать "синдрома непризнанного гения": безудержное самовосхваление, претензии на какие-то выдающиеся открытия, позволяющие одним махом решить все мировые проблемы, и, главное, отсутствие корректных определений и доказательств
Могу посоветовать начать с задач попроще, заодно разберётесь с определениями. Например могу предложить доказать (задача которую студенты получают буквально на втором занятии по ТС) что "для всякого языка из P существует недетерминированная машина Тьюринга разрешающая его за время P". Ну или хотя бы что P лежит в NP.
У меня получилось сжать переведённую "Войну и Мир" обычным RLE вне зависимости от числа повторений, попробуйте Энтропийное кодирование для потока битовых флагов.
Вот код. Вроде бы и немного (21+18 строк), но он довольно таки ёмок на математику, легко допустить ошибку. Если будет несложно дополните статью, так она станет гораздо информативнее.
Максимально дубовая реализация монтгомери вместе с делением по Лемиру улучшила мой результат с
27,223до21,820. Даже обидно как-то, получается раньше я вообще не в ту сторону смотрел. Но теперь до первых мест рукой подать, скорее всего можно те же вызовы_mullo_epi32в два раза реже делать (у меня на 1 mulmod 3 simd умножения, из которых только два полноценное, и одно урезанное), или от бранча для переполнения вычитания как-то отказаться, его обработка съедает четверть всего времени. Теоретически можно оптимально распланировать умножения по битам степени, и вместо маскировки делать их только тогда когда нужно, это тоже может дать до трети всего времени (умножаем только на половину всех битов).Да, проверяю по 4 числа одновременно. Главное заранее отсекать большую часть работы (5/6) проверкой на делимость на маленькие делители, довольно красиво сделано, но видимо можно сделать лучше, я использовал для больших libdivide_u32_do_vec256, а для маленьких (2,3,5,7) сообразил трюк с _mm256_shuffle_epi8. Тоже в восторге от результатов первой тройки. Ах да, еще нужно чтение через mmap организовать, в справке от сайта есть пример.
О, я примерно тем же путём шел когда решал https://highload.fun/tasks/10
Правда у меня в итоге векторизованная где-то в 2 раза быстрее не векторизованной, но и другие трюки использовал. Обязательно поделитесь результатом.
Все так говорят (на один символ отправка 8 байт если между ними меньше ~20ms), пробежал по коду и не вижу ничего противоречащего этому. Тестить правда лень, если хотите оспорить — wireshark/tcpdump вам в помощь.
Действительно в прошлом году появился патч и опция в конфиге, мне интересно, а в вашем дистрибутиве есть эта опция? (проще всего проверить
man ssh_config; /Obf)Презентация про ssh, тут статья. Текст об этом на хабре, но я не рекомендую ни комментарии ни статью: там какая-то отсебятина про visual feedback.
Вместе с таймингом утекает и длина пароля, ответных пакетов со стороны сервера не нужно.
В комментариях тоже какая-то дичь, например: (проблема не в комментарии или в комментаторе, а в том что его никто не поправил, так и висит).
Статья про анализ серверного "пинга" со стороны собеседника в IM.
Напишу на тот случай если кто-то не понимает какую конкретно безопасность обеспечивает E2EE и для/от кого. Для любого мессенджера с моментальной доставкой сообщений и без серьёзного "замусоривания" траффика легко понять кто с кем общается используя глобальное наблюдение (без MitM) и элементарные корреляции.
Пусть пользователь A, B живут в стране, где некие
вредоносныеагенты Е установили специальное оборудование сохраняющее метаданные всего оконечного трафика на всех провайдерах связи. Пусть агенты E знают A, но не знают B, про B известно что он один из множества U.Теперь каждый раз когда A пишет сообщение B, он инициирует обмен сетевым трафиком с серверами напрямую (Telegram), через peer-to-peer сеть(Tor), либо даже с использованием туннеля с дополнительным шифрованием ( Wireguard или OpenVPN). Но во всех популярных любительских сценариях использования (за редким исключением вроде i2p) размеры пакетов меняются крайне предсказуемо, а то и не меняются вовсе. Теперь E, зная паттерны трафика нового сообщения (а в случае push уведомлений можно опираться и на ip-подсеть как на показатель пуша), запоминает текущее время.
Затем это сообщение должно прийти B, где ситуации повторится. Так как множество людей из U могут получить подобный трафик случайно, E может лишь ограничить размер множества U - даже для довольно таки большого окна доставки в минуты (типично для пуш-уведомлений) с каждым сообщением размер U будет сокращаться в разы, если не в десятки. Для однозначного установления B потребуется около 27 бит информации (
|U|~=1.4e8), что вполне себе достижимо при регулярном общении. Даже если утекать будут малые доли бита (т.е. агенты E очень не уверены в том что произошло общение), из того что нам их нужно собрать буквально десятки, при достаточном количестве сообщений легко вычислить весь граф общения.Эту картину не меняет даже вменяемый false-positive (пусть например фоном запущенный ютуб раз в 15 секунд даёт картину похожую на сообщение, тогда мы должны учесть шанс того что A ничего не отправлял). В таком случае мы не выкидываем кандидатов из U, а честно обновляем ожидания по Байесу. Если проделать подобное в итоге получатся что граф общения оказывается (ребро между вершинами если они общаются) равен попарной временной корреляции "интересного" трафика относительно U.
Подправив параметры можно узнать например на какие каналы в youtube вы подписаны не залезая в шифрованный трафик, достаточно посмотреть корреляцию жирного потока на сервера гугла с расписанием публикации новых видео, (если вы конечно открываете их сразу по уведомлению).
Да, это вычислительно сложная задача, но явно не сложнее подсчета условного PageRank-a для поискового индекса с MapReduce, естественно считать в лоб (O(|U|^2)) нельзя.
Слайды про утечку пользователя по паролю при наборе его используя SSH (не совсем в тему, но идея похожая)
Определение местоположения пользователя популярных "защищенных" мессенджеров
Тут исследователи не пользуются глобальным мониторингом траффика, смотрят только на раундтрипы оповещения о доставке.
P.S.
Задумался над тем что бы комментарий до статьи добить, но об подобном на хабре уже писали еще в 2011 (в контексте Tor, Tarzan и Morphmix).
Еще я сомнительным способом генерировал случайное целое,
uniform_uint64() % (HI-LO) + LOВ районе 10^18 там уже значительный перекос в пользу меньших чисел.Прогнал Монте-Карло на равномерных неупорядоченных парах, (это не точно учтёт пары где
x=y, но так как их немного, погрешность должна быть небольшой).Просто взял
p:=cnt_good/cnt_iters; estimate:=81*10^{d-2}*p/2;Скорость симуляции получилась около 5 миллиардов итераций в секунду, что не впечатляет. Пришлось немного попотеть что бы правильно работать с 36-значными числами.
Monte-Carlo
Относительная точность падает при уменьшении p, поэтому оценку для d=18 получилось посчитать с точностью
±0.3%Hidden text
Попробовал ваш алгоритм на видяшке, работает 4.5 секунды для
n=6.Заодно и осилил
n=7Лобовой подсчет без каких-либо алгоритмов на видяшке работает 4 секунды! (задача с парами). Если не лень ждать 16 часов сможете узнать ответ для n=7.
Hidden text
Ничего не нашлось, а пятнадцать нужно 16 часов ждать. Расширил пространство на несколько порядков, вдруг пригодится потомкам.
Другие основания, из не указанного выше
Проверяет все до
m=12за минуту на видюшке. Посмотрим что будет сm=14через пару часов.Hidden text
Чет медленно. Сейчас сделаю побыстрее.
WTF! В каком это месте он рекурсивный? В целом почти все алгоритмы поиска кратчайшего пути нерекурсивные.
Визуализация показала обширное облако обломков после уничтожения советского спутника
Очень сомнительное ограничение в 56 на путь, так-то змейка на карте в 60x60 что-то порядка 1700 дает. В мире плюсов аллокацию из библиотеки можно избежать output iterator-ом, там такое на шаблонах бесплатно, в го так не выйдет.
А где про это можно почитать на русском?
Ого. Ходил еще школьником на его курс по питону 14-15 лет назад, жалко не имел подходящий mindset для этих занятий в то время. Вроде бы делали рисовалку на pygame. Действительно многому научил.
Помню через несколько лет уже в МФТИ сокурсники удивлялись этому факту когда мы учили курс по ОСям по его учебнику.
"Основы вычислимости и теории сложности" - крайне полезный курс в CS, думаю что большинству программистов стоит с ним ознакомится.
А по сути дела статья какая-то дичь:
Какое отношение имеют действительные числа к теории сложности?
Ну и зачем нам тут случайные величины? Правда чуть ниже что-то похожее на определение Мартингала.
Определение классов скопировано правильно, но сразу после этого идет без каких либо пояснений переформулировка на язык последовательностей. Я так и не понял как может быть связана одна последовательность с языком.
Фу, ужас, отвратительно.
Ощущение что вы даже свой список литературы не открывали, по первой же ссылке весьма грамотно замечают:
Могу посоветовать начать с задач попроще, заодно разберётесь с определениями. Например могу предложить доказать (задача которую студенты получают буквально на втором занятии по ТС) что "для всякого языка из P существует недетерминированная машина Тьюринга разрешающая его за время P". Ну или хотя бы что P лежит в NP.