ReSQL.ru
     
powered by simpleCommunicator - 2.0.59     © 2025 Programmizd 02
Мобильная версия    Контакт    Правила    FAQ    Помощь
Целевая тема:
Создать новую тему:
Автор:
Закрыть
Цитировать
Доб. в избранное | Игнор. тему | Прикреп. тему | Пометить прочит. / непрочит. | Фильтр
Форумы / C++ [игнор отключен] [закрыт для гостей] / Длинные сдвиги
25 сообщений из 50, страница 1 из 2
  1  все
Длинные сдвиги
    #39601500
Dimitry Sibiryakov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dimitry Sibiryakov
Участник
Среди intrinsic-ов (или подобных трюков) есть возможность быстрых сдвигов нескольких
последовательных целых? Что-нибудь быстрее, чем цикл из
Код: sql
1.
arr[i+1] = arr[i+1] >> 1 | arr[i] << 31



PS: В старом добром ассемблере DEC была идеально подходящая для этого команда сдвига через
флаг переноса...
Posted via ActualForum NNTP Server 1.5
...
Рейтинг: 0 / 0
13.02.2018, 23:16
| Ответить | Цитировать | Написать  
Длинные сдвиги
    #39601514
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
Похоже не сдвиг а ротация.
...
Рейтинг: 0 / 0
14.02.2018, 00:58
| Ответить | Цитировать | Написать  
Длинные сдвиги
    #39601592
rdb_dev
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
rdb_dev
Участник
Dimitry Sibiryakov, чуть быстрее только ассемблерной вставкой операциями сдвига через CF, если сдвиг на 1.
...
Рейтинг: 0 / 0
14.02.2018, 09:22
| Ответить | Цитировать | Написать  
Длинные сдвиги
    #39601651
kealon(Ruslan)
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
kealon(Ruslan)
Участник
Dimitry Sibiryakov,

наверное, только ассемблером, на x86 тоже есть такая команда RCL
...
Рейтинг: 0 / 0
14.02.2018, 11:19
| Ответить | Цитировать | Написать  
Длинные сдвиги
    #39601738
jmp_original
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
jmp_original
Гость
Есть ещё shld / shrd. Они, возможно(!), быстрее.
...
Рейтинг: 0 / 0
14.02.2018, 13:01
| Ответить | Цитировать | Написать  
Длинные сдвиги
    #39602028
Barlone
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Barlone
Участник
https://msdn.microsoft.com/ru-ru/library/5az7sk38.aspx
...
Рейтинг: 0 / 0
14.02.2018, 21:02
| Ответить | Цитировать | Написать  
Длинные сдвиги
    #39602690
д0кХ
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
д0кХ
Гость
Dimitry SibiryakovСреди intrinsic-ов (или подобных трюков) есть возможность быстрых сдвигов нескольких
последовательных целых? Что-нибудь быстрее, чем цикл из
Код: sql
1.
arr[i+1] = arr[i+1] >> 1 | arr[i] << 31



PS: В старом добром ассемблере DEC была идеально подходящая для этого команда сдвига через
флаг переноса...


Загадочная и неоднозначная постановка.
Оптимизировать нужно не сам сдвиг, там особо нечего оптимизировать.
а что то другое внутри цикла, то зачем вам нужны значения 0 или 1
в позицих битовой маски.

Попробуйте посмотреть на задачу не в лоб, а с боку.
Например кардинально сократить количестов итераций цикла .
...
Рейтинг: 0 / 0
16.02.2018, 02:11
| Ответить | Цитировать | Написать  
Длинные сдвиги
    #39602936
Dimitry Sibiryakov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dimitry Sibiryakov
Участник
д0кХОптимизировать нужно не сам сдвиг, там особо нечего оптимизировать.
а что то другое внутри цикла, то зачем вам нужны значения 0 или 1
в позицих битовой маски.

Хорошая идея. Тогда вопрос: есть ли трюк, позволяющий найти остаток от деления двух
длинных чисел быстрее, чем за M-N вычитаний, где M и N - число бит в делимом и делителе
соответственно? Именно для этого мне нужна матрица из 32-х (64-х) сдвинутых чисел.

PS: Да, это RSA. Нет, пользоваться готовой библиотекой не так прикольно.
Posted via ActualForum NNTP Server 1.5
...
Рейтинг: 0 / 0
16.02.2018, 13:36
| Ответить | Цитировать | Написать  
Длинные сдвиги
    #39602963
kealon(Ruslan)
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
kealon(Ruslan)
Участник
Dimitry Sibiryakov,

тогда какая разница сколько оно будет выполняться? это же при инициалиации делаться будет, так?
...
Рейтинг: 0 / 0
16.02.2018, 13:55
| Ответить | Цитировать | Написать  
Длинные сдвиги
    #39602972
Dimitry Sibiryakov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dimitry Sibiryakov
Участник
kealon(Ruslan)тогда какая разница сколько оно будет выполняться? это же при инициалиации делаться будет,
так?

Не совсем так: в приложении используются несколько разных ключей. Но подготовить их все
заранее, а не при каждом шифровании как сейчас, это действительно отличная идея. Спасибо.
Posted via ActualForum NNTP Server 1.5
...
Рейтинг: 0 / 0
16.02.2018, 14:02
| Ответить | Цитировать | Написать  
Длинные сдвиги
    #39603262
Dimitry Sibiryakov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dimitry Sibiryakov
Участник
Кстати, чисто по сабжу: в конечном итоге таки победила конструкция
Код: sql
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
static void SHR(uintptr_t* Value, const size_t n)
{
     uintptr_t carry = 0;
     for (int i = n - 1; i >= 0; i--)
     {
         uintptr_t new_carry = (Value[i] & 1) != 0? (uintptr_t)1 << ((sizeof(uintptr_t) * 
8) - 1): 0x00;
         Value[i] = Value[i] >> 1 | carry;
		carry = new_carry;
     }
}


оказавшаяся в 64-х битном исполнении в четыре раза быстрее чем
Код: sql
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
static void SHR_asm(uintptr_t* Value, size_t n)
{
	Value += n - 1;
	asm volatile (R"asm(
		pushf
		mov	%%rsi, %%rdi
		clc
		std
Shift%=:
		lodsq
		rcr		%%rax
		stosq
		loop Shift%=
		popf
)asm"
}


Хоть и порождает ассемблерный код на порядок длиннее. Снимаю шляпу перед неестественным
интеллектом современного GCC.

PS: На 32-х битах разница "всего" в полтора раза.
Posted via ActualForum NNTP Server 1.5
...
Рейтинг: 0 / 0
16.02.2018, 17:58
| Ответить | Цитировать | Написать  
Длинные сдвиги
    #39603307
д0kХ
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
д0kХ
Гость
Dimitry Sibiryakovд0кХОптимизировать нужно не сам сдвиг, там особо нечего оптимизировать.
а что то другое внутри цикла, то зачем вам нужны значения 0 или 1
в позицих битовой маски.

Хорошая идея. Тогда вопрос: есть ли трюк, позволяющий найти остаток от деления двух
длинных чисел быстрее, чем за M-N вычитаний, где M и N - число бит в делимом и делителе
соответственно? Именно для этого мне нужна матрица из 32-х (64-х) сдвинутых чисел.

PS: Да, это RSA. Нет, пользоваться готовой библиотекой не так прикольно.


ИМХО для ключей RSA

не подходят числа за M-N вычитаний, где M и N - число бит в делимом и делителе
соответственно

потому как при использовании НЕ RSA чисел
вы даете зеленый свет на оптимизацию взлома вашей реализации
RSA алгоритма брутфорсом.
...
Рейтинг: 0 / 0
16.02.2018, 19:42
| Ответить | Цитировать | Написать  
Длинные сдвиги
    #39603312
Dimitry Sibiryakov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dimitry Sibiryakov
Участник
д0kХвы даете зеленый свет на оптимизацию взлома вашей реализации RSA алгоритма брутфорсом.

О чём ты? За M-N итераций делятся любые два числа. Это первый класс, деление в столбик.
Posted via ActualForum NNTP Server 1.5
...
Рейтинг: 0 / 0
16.02.2018, 19:48
| Ответить | Цитировать | Написать  
Длинные сдвиги
    #39603319
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dima T
Участник
Dimitry SibiryakovЭто первый класс, деление в столбик.

Деление в столбик это третий класс :)
...
Рейтинг: 0 / 0
16.02.2018, 20:03
| Ответить | Цитировать | Написать  
Длинные сдвиги
    #39603321
д0kХ
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
д0kХ
Гость
Dimitry Sibiryakovд0kХвы даете зеленый свет на оптимизацию взлома вашей реализации RSA алгоритма брутфорсом.

О чём ты? За M-N итераций делятся любые два числа. Это первый класс, деление в столбик.


Ну да, я ж как раз об этом :)
M-N для RSA чисел у вас будет 0 ,1 или 2 .
...
Рейтинг: 0 / 0
16.02.2018, 20:06
| Ответить | Цитировать | Написать  
Длинные сдвиги
    #39603324
kealon(Ruslan)
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
kealon(Ruslan)
Участник
д0kХ,

он об асимптотической сложности, хотя она в данном случае будет O(N^2)
...
Рейтинг: 0 / 0
16.02.2018, 20:14
| Ответить | Цитировать | Написать  
Длинные сдвиги
    #39603327
д0kХ
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
д0kХ
Гость
kealon(Ruslan)д0kХ,

он об асимптотической сложности, хотя она в данном случае будет O(N^2)

На этом и построена математическая суть RSA алгоритма.
Поэтому он медленный, но криптостойкий
и простой с точки зрения процедур обмена ключами.
...
Рейтинг: 0 / 0
16.02.2018, 20:20
| Ответить | Цитировать | Написать  
Длинные сдвиги
    #39603328
д0kХ
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
д0kХ
Гость
 
ИМХО пятничный офтопик

Попытка алгоритмически ускорить RSA
приведет к уязвимости алгоритма к атакам.
Атакующий точно также будет иметь возможность соптимизировать атаку.

Бессмысленно пытаться обманывать математику при игре на ее поле.

...
Рейтинг: 0 / 0
16.02.2018, 20:28
| Ответить | Цитировать | Написать  
Длинные сдвиги
    #39603331
Dimitry Sibiryakov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dimitry Sibiryakov
Участник
д0kХM-N для RSA чисел у вас будет 0 ,1 или 2 .

Если они генерировались согласно "лучшим рекомендациям", то у них M вдвое больше чем N.
Posted via ActualForum NNTP Server 1.5
...
Рейтинг: 0 / 0
16.02.2018, 21:04
| Ответить | Цитировать | Написать  
Длинные сдвиги
    #39603341
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
д0kХ,

На ниве копания крипто валют мы уже несколько лет наблюдаем гонку вооружения. Остаётся только гадать когда же себестоимость транзакции станет
такой дорогой чтобы самые рьяные сторонники просто успокоились и доверились обыкновенным платежным системам.
...
Рейтинг: 0 / 0
16.02.2018, 21:57
| Ответить | Цитировать | Написать  
Длинные сдвиги
    #39603348
д0кХ
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
д0кХ
Гость
Dimitry Sibiryakovд0kХM-N для RSA чисел у вас будет 0 ,1 или 2 .

Если они генерировались согласно "лучшим рекомендациям", то у них M вдвое больше чем N.



А о какой части алгоритма мы говорим ?
я не телепат.
...
Рейтинг: 0 / 0
16.02.2018, 22:26
| Ответить | Цитировать | Написать  
Длинные сдвиги
    #39603350
д0кХ
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
д0кХ
Гость
maytonд0kХ,

На ниве копания крипто валют мы уже несколько лет наблюдаем гонку вооружения. Остаётся только гадать когда же себестоимость транзакции станет
такой дорогой чтобы самые рьяные сторонники просто успокоились и доверились обыкновенным платежным системам.
Так это сразу было понятно,
что себестоимость будет расти чуть ли не геометрической прогрессии к количеству.
...
Рейтинг: 0 / 0
16.02.2018, 22:30
| Ответить | Цитировать | Написать  
Длинные сдвиги
    #39603354
jmp_original
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
jmp_original
Гость
Dimitry Sibiryakovоказавшаяся в 64-х битном исполнении в четыре раза быстрее
...
PS: На 32-х битах разница "всего" в полтора раза.

Судя по всему они в итоге соптимизировали только movs, а lods/stos так и остались на микрокоде прошлого века.
Вот так и живём.
...
Рейтинг: 0 / 0
16.02.2018, 22:33
| Ответить | Цитировать | Написать  
Длинные сдвиги
    #39603355
Dimitry Sibiryakov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dimitry Sibiryakov
Участник
д0кХА о какой части алгоритма мы говорим ?

Повторяю медленно:
Dimitry Sibiryakov Тогда вопрос: есть ли трюк, позволяющий найти остаток от деления
двух длинных чисел быстрее, чем за M-N вычитаний, где M и N - число бит в делимом и
делителе соответственно?
Posted via ActualForum NNTP Server 1.5
...
Рейтинг: 0 / 0
16.02.2018, 22:33
| Ответить | Цитировать | Написать  
Длинные сдвиги
    #39603368
д0кХ
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
д0кХ
Гость
Dimitry Sibiryakovд0кХА о какой части алгоритма мы говорим ?

Повторяю медленно:
Dimitry Sibiryakov Тогда вопрос: есть ли трюк, позволяющий найти остаток от деления
двух длинных чисел быстрее, чем за M-N вычитаний, где M и N - число бит в делимом и
делителе соответственно?


Для RSA за счет создания уязвимости.
...
Рейтинг: 0 / 0
16.02.2018, 23:18
| Ответить | Цитировать | Написать  
25 сообщений из 50, страница 1 из 2
  1  все
Форумы / C++ [игнор отключен] [закрыт для гостей] / Длинные сдвиги
Найденые пользователи ...
Разблокировать пользователей ...
Читали тему (0):
Читали форум (0):
Пользователи онлайн (0):
x
x
Закрыть


Просмотр
0 / 0
Close
Debug Console [Select Text]