Гость
Войти | Профиль | Очистить
Целевая тема:
Создать новую тему:
Автор:
Действия ...
Форумы / C++ [игнор отключен] [закрыт для гостей] / Длинные сдвиги / 25 сообщений из 50, страница 1 из 2
  1  все
13.02.2018, 23:16
    #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
| Ответить | Цитировать | Написать  
14.02.2018, 00:58
    #39601514
mayton
mayton
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Длинные сдвиги
Похоже не сдвиг а ротация.
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
14.02.2018, 09:22
    #39601592
rdb_dev
rdb_dev
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Длинные сдвиги
Dimitry Sibiryakov, чуть быстрее только ассемблерной вставкой операциями сдвига через CF, если сдвиг на 1.
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
14.02.2018, 11:19
    #39601651
kealon(Ruslan)
kealon(Ruslan)
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Длинные сдвиги
Dimitry Sibiryakov,

наверное, только ассемблером, на x86 тоже есть такая команда RCL
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
14.02.2018, 13:01
    #39601738
jmp_original
jmp_original
Гость
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Длинные сдвиги
Есть ещё shld / shrd. Они, возможно(!), быстрее.
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
14.02.2018, 21:02
    #39602028
Barlone
Barlone
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Длинные сдвиги
https://msdn.microsoft.com/ru-ru/library/5az7sk38.aspx
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
16.02.2018, 02:11
    #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, 13:36
    #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:55
    #39602963
kealon(Ruslan)
kealon(Ruslan)
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Длинные сдвиги
Dimitry Sibiryakov,

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

Не совсем так: в приложении используются несколько разных ключей. Но подготовить их все
заранее, а не при каждом шифровании как сейчас, это действительно отличная идея. Спасибо.
Posted via ActualForum NNTP Server 1.5
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
16.02.2018, 17:58
    #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, 19:42
    #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:48
    #39603312
Dimitry Sibiryakov
Dimitry Sibiryakov
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Длинные сдвиги
д0kХвы даете зеленый свет на оптимизацию взлома вашей реализации RSA алгоритма брутфорсом.

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

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

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


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

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

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

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

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

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

...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
16.02.2018, 21:04
    #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:57
    #39603341
mayton
mayton
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Длинные сдвиги
д0kХ,

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

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



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

На ниве копания крипто валют мы уже несколько лет наблюдаем гонку вооружения. Остаётся только гадать когда же себестоимость транзакции станет
такой дорогой чтобы самые рьяные сторонники просто успокоились и доверились обыкновенным платежным системам.
Так это сразу было понятно,
что себестоимость будет расти чуть ли не геометрической прогрессии к количеству.
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
16.02.2018, 22:33
    #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, 23:18
    #39603368
д0кХ
д0кХ
Гость
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Длинные сдвиги
Dimitry Sibiryakovд0кХА о какой части алгоритма мы говорим ?

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


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


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