Этот баннер — требование Роскомнадзора для исполнения 152 ФЗ.
«На сайте осуществляется обработка файлов cookie, необходимых для работы сайта, а также для анализа использования сайта и улучшения предоставляемых сервисов с использованием метрической программы Яндекс.Метрика. Продолжая использовать сайт, вы даёте согласие с использованием данных технологий».
Политика конфиденциальности
|
|
|
Длинные сдвиги
|
|||
|---|---|---|---|
|
#18+
д0кХДля RSA за счет создания уязвимости. Сила RSA не в медленном делении, а в большом количестве простых чисел в промежутке от p до q. При его брутфорсе вообще деление не используется. Posted via ActualForum NNTP Server 1.5 ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 17.02.2018, 00:12 |
|
||
|
Длинные сдвиги
|
|||
|---|---|---|---|
|
#18+
Dimitry Sibiryakov, попробуй: 1. Выровнять начало массива на размер cache line (обычно 128 байт) 2. Оперировать четырьмя регистрами (rax, rdx, rbx, rcx) над разными частями сдвигаемого массива 3. Использовать инструкцию сдвига SHRD m64,r64,1 Быстрее этого справятся только инструкции из расширенных наборов MMX/SSE ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 17.02.2018, 03:25 |
|
||
|
Длинные сдвиги
|
|||
|---|---|---|---|
|
#18+
Dimitry SibiryakovТогда вопрос: есть ли трюк, позволяющий найти остаток от деления двух длинных чисел быстрее, чем за M-N вычитаний, где M и N - число бит в делимом и делителе соответственно? можно заменить операцию нахождения остатка на 2 умножения и 1 вычитание асимптотически будет быстрее, чем реализация через вычитание столбиком (O(N^2)) Код: plaintext 1. 2. 3. 4. 5. 6. 7. по умножению уже точно есть алгоритмы до O(N*ln(N)) включительно вычитание O(N) ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 17.02.2018, 06:26 |
|
||
|
Длинные сдвиги
|
|||
|---|---|---|---|
|
#18+
тьфу 15 * Q = 210 |удаляем 2 последних разряда| -> 2 умножаем на 7 -> 14 наш остаток: 15 - 14 = 1 ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 17.02.2018, 08:37 |
|
||
|
Длинные сдвиги
|
|||
|---|---|---|---|
|
#18+
kealon(Ruslan)асимптотически будет быстрее, чем реализация через вычитание столбиком (O(N^2)) Почему (O(N^2))? b111111 mod b100 = 111111 - 100000 - 10000 - 1000 - 100 = 11. Posted via ActualForum NNTP Server 1.5 ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 17.02.2018, 12:54 |
|
||
|
Длинные сдвиги
|
|||
|---|---|---|---|
|
#18+
Dimitry Sibiryakov, а у тебя есть команда которая, например, при 512-битном ключе сразу разницу находит? это вычитание даёт O1(N/32), и сделать их нужно в общем случае (2N-N) раз вот и выходит O(N^2) ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 17.02.2018, 20:23 |
|
||
|
Длинные сдвиги
|
|||
|---|---|---|---|
|
#18+
kealon(Ruslan)Q = 100 / 7 = 14 Насколько я понимаю, чтобы не напороться на ошибки округления, надо брать "100" с большим запасом: не меньше чем квадрат делителя. А это автоматически приводит к удвоению разрядности "15 * Q". Надо будет потестить... Posted via ActualForum NNTP Server 1.5 ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 18.02.2018, 22:16 |
|
||
|
Длинные сдвиги
|
|||
|---|---|---|---|
|
#18+
Dimitry Sibiryakov, ага, по идее так, не проверял т.е. если если модуль 512-битный, то множитель нужен 2*512 битный возможно стоит дробную часть не отсекать, там как раз остаток от деления, но не весь 210 -> 10 -> 10*7 = 070 -> 1 ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 19.02.2018, 07:16 |
|
||
|
Длинные сдвиги
|
|||
|---|---|---|---|
|
#18+
Dimitry SibiryakovСреди intrinsic-ов (или подобных трюков) есть возможность быстрых сдвигов нескольких последовательных целых? Что-нибудь быстрее, чем цикл из Код: sql 1. PS: В старом добром ассемблере DEC была идеально подходящая для этого команда сдвига через флаг переноса... Пробовал _mm_slli_si128() + _mm_slli_epi64() + _mm_srli_epi64() + _mm_or_si128() ? Если сдвиг больше, чем на 64 бита, то 2 инструкции, а если меньше, то 4 инструкции. http://coliru.stacked-crooked.com/a/a9dbd34a8940082b ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 19.02.2018, 14:19 |
|
||
|
Длинные сдвиги
|
|||
|---|---|---|---|
|
#18+
Barlone https://ru.wikipedia.org/wiki/Алгоритм_Монтгомери ну раз пошла такая пьянка :) по тынцуОсновное свойство: наибольший общий делитель {\displaystyle m} m и {\displaystyle n} n делится на любой общий делитель этих чисел. Пример: для чисел 12 и 18 наибольший общий делитель равен 6 ; он делится на все общие делители этих чисел: 1, 2, 3, 6. Следствие 1: множество общих делителей {\displaystyle m} m и {\displaystyle n} n совпадает с множеством делителей НОД(m, n). Следствие 2: множество общих кратных {\displaystyle m} m и {\displaystyle n} n совпадает с множеством кратных НОК(m, n). ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 20.02.2018, 14:06 |
|
||
|
Длинные сдвиги
|
|||
|---|---|---|---|
|
#18+
Barlone https://ru.wikipedia.org/wiki/Алгоритм_Монтгомери от же, ещё чуть-чуть и мы бы его переоткрыли ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 20.02.2018, 16:37 |
|
||
|
Длинные сдвиги
|
|||
|---|---|---|---|
|
#18+
kealon(Ruslan)Barlone https://ru.wikipedia.org/wiki/Алгоритм_Монтгомери от же, ещё чуть-чуть и мы бы его переоткрыли Напомню новую вводную Dimitry Sibiryakov найти остаток от деления двух длинных чисел быстрее, чем за M-N вычитаний, ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 20.02.2018, 19:57 |
|
||
|
Длинные сдвиги
|
|||
|---|---|---|---|
|
#18+
kealon(Ruslan)Barlone https://ru.wikipedia.org/wiki/Алгоритм_Монтгомери от же, ещё чуть-чуть и мы бы его переоткрыливажно не путать открытия с откупориваниями (с) ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 20.02.2018, 23:31 |
|
||
|
Длинные сдвиги
|
|||
|---|---|---|---|
|
#18+
д0kХ, авторнайти остаток от деления двух длинных чисел быстрее, чем за M-N длинных вычитаний, уже нашли 21203765 ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 21.02.2018, 07:01 |
|
||
|
Длинные сдвиги
|
|||
|---|---|---|---|
|
#18+
kealon(Ruslan)д0kХ, авторнайти остаток от деления двух длинных чисел быстрее, чем за M-N длинных вычитаний, уже нашли 21203765 У меня есть сомнения в истинной этой серебрянности этой пули авторОднако вычисление n' и перевод чисел в n-остатки и обратно — трудоёмкие операции, вследствие чего применять алгоритм Монтгомери при однократном вычислении произведения двух чисел представляется неразумным. анекдот К уже переодевшемуся в спортивный костюм и с довольной рожей наслаждаюшемуся сигаретой Иосифу возле вагона поезда Москва - Одесса подходят цыгане и предлагают купить богатый золотой перстень за 40 долларов. Йося долго торгуется и они сходятся на 30 . Йося дает им сотку, получает сдачу полтинник и двадцатку. Йося уезжает в Одессу с фальшивым кольцом и настоящими долларами, А довольные цигане остаются с фальшивой соткой. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 21.02.2018, 19:54 |
|
||
|
Длинные сдвиги
|
|||
|---|---|---|---|
|
#18+
д0kХУ меня есть сомнения в истинной этой серебрянности этой пули авторОднако вычисление n' и перевод чисел в n-остатки и обратно — трудоёмкие операции, вследствие чего применять алгоритм Монтгомери при однократном вычислении произведения двух чисел представляется неразумным. всё нормально, алгоритм из разряда немного поднапрячься зато сразу долететь что для RSA и нужно ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 22.02.2018, 00:27 |
|
||
|
Длинные сдвиги
|
|||
|---|---|---|---|
|
#18+
kealon(Ruslan)всё нормально, алгоритм из разряда немного поднапрячься зато сразу долететь что для RSA и нужно Обычно RSA наоборот используют чисто для разовых вещей типа зашифровать сессионный ключ, подписать документ и т.п. Posted via ActualForum NNTP Server 1.5 ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 22.02.2018, 01:19 |
|
||
|
Длинные сдвиги
|
|||
|---|---|---|---|
|
#18+
Dimitry Sibiryakov, в RSA взятие модуля составляет половину алгоритма и выполняется в цикле, вынеси получение n' из основного цикла и используй в цикле уже готовое ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 22.02.2018, 09:12 |
|
||
|
Длинные сдвиги
|
|||
|---|---|---|---|
|
#18+
kealon(Ruslan)в RSA взятие модуля составляет половину алгоритма и выполняется в цикле А, ну да, на приватной стороне. На публичной с e=3 достаточно одного-двух. Posted via ActualForum NNTP Server 1.5 ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 22.02.2018, 12:59 |
|
||
|
Длинные сдвиги
|
|||
|---|---|---|---|
|
#18+
Как же я не люблю баги в компиляторах... Код: sql 1. 2. 3. 4. 5. 6. 7. 8. 9. 10. 11. 12. 13. 14. 15. 16. 17. 18. 19. 20. 21. 22. 23. 24. 25. 26. 27. 28. 29. 30. 31. 32. 33. TDM-GCC 5.1 с -О[1-3] выдаёт "0 ffffffff ffffffff ffffffff 0" вместо правильного "0 0 0 0 1" (MS VC - результат правильный). Может кто-нибудь проверить на версии 5.3 или выше? Posted via ActualForum NNTP Server 1.5 ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 23.02.2018, 21:32 |
|
||
|
Длинные сдвиги
|
|||
|---|---|---|---|
|
#18+
Dimitry SibiryakovМожет кто-нибудь проверить на версии 5.3 или выше?5.3.0 - полет нормальный. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 24.02.2018, 00:22 |
|
||
|
Длинные сдвиги
|
|||
|---|---|---|---|
|
#18+
Dimitry Sibiryakovkealon(Ruslan)в RSA взятие модуля составляет половину алгоритма и выполняется в цикле А, ну да, на приватной стороне. На публичной с e=3 достаточно одного-двух. e=3 плохой выбор https://en.wikipedia.org/wiki/Coppersmith's_attack ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 26.02.2018, 15:15 |
|
||
|
Длинные сдвиги
|
|||
|---|---|---|---|
|
#18+
эти интрисики появились в 5.0, новенькие баги AFAIK gcc надо использовать стабильные ветки https://gcc.gnu.org/develop.html#timeline -4.8.5 -4.9.4 -5.5 -6.4 7 - экспериментальная пока - было много принципиальных изменений по оптимизатору ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 26.02.2018, 20:35 |
|
||
|
|

start [/forum/topic.php?fid=57&msg=39605949&tid=2017960]: |
0ms |
get settings: |
11ms |
get forum list: |
16ms |
check forum access: |
4ms |
check topic access: |
4ms |
track hit: |
157ms |
get topic data: |
11ms |
get forum data: |
3ms |
get page messages: |
62ms |
get tp. blocked users: |
2ms |
| others: | 289ms |
| total: | 559ms |

| 0 / 0 |
