Длинная арифметика в С++ - Общие вопросы C/C++

vladina · 29.09.2017, 00:02

что делать, если одну из арифметической операций необходимо применить для огромных чисел, скажем так 1000 знаков или более…

Croessmah · 29.09.2017, 00:08

например, есть boost::multiprecision

ura_111 · 01.10.2017, 23:14

Поищи на форуме - здесь неоднократно поднимался этот вопрос.

Aoizora · 02.10.2017, 13:42

Зачем вообще нужны библиотеки длинной арифметики в традиционном виде? Кому это надо?
В криптографии такая арифметика не нужна. Длинная арифметика для этих целей реализуется иначе. Выбирается фиксированное конечное поле и в этом поле реализуются операции на основании равенств, выполняющихся в этом поле. Получается неуниверсально, зато эффективно за счет использования векторных регистров.

Black Fregat · 02.10.2017, 14:32

Цитата:

Сообщение от Aoizora

Длинная арифметика для этих целей реализуется иначе.

Не могли бы Вы, уважаемый, чем-то подтвердить столь категорические заявления?

Aoizora · 02.10.2017, 14:46

Цитата:

Сообщение от Black Fregat

Не могли бы Вы, уважаемый, чем-то подтвердить столь категорические заявления?

Гугли эффективную реализацию криптоалгоритмов, арифметики в полях Галуа, быстрых мультипликаторов и прочее. Оптимизация на высоком уровне там заключается в выборе базиса, в котором вычисления занимают наименьшее число операций, а на низком уровне используются тождества, выполняющиеся в данном поле, и особенности процессоров (например, неиспользование инструкции adc, поскольку она не позволяет параллельно обрабатывать chunk'и длинных чисел в векторных регистрах).

Aoizora · 02.10.2017, 14:50

Может быть, с RSA не так, но эллиптическая криптография оптимизируется хардкорно. Обычно для криптосистем на эллиптических кривых пишется специальная библиотека длинных чисел - допустим, 256-битные числа, а не числа произвольной длины, и все это оптимизируется на основании теорем алгебры и особенностей железа. Можно добавить, что формулы сложения точек на кривых записываются в проективных координатах, тогда получается очень быстро.

Croessmah · 02.10.2017, 15:35

Цитата:

Сообщение от Aoizora

Зачем вообще нужны библиотеки длинной арифметики в традиционном виде?

Банально - для расчетов.
Еще банальнее - калькулятор.

29.09.2017, 00:02	#1
vladina Новичок Джуниор Регистрация: 28.09.2017 Сообщений: 1	Длинная арифметика в С++ что делать, если одну из арифметической операций необходимо применить для огромных чисел, скажем так 1000 знаков или более…

02.10.2017, 14:50	#7
Aoizora Заблокирован Регистрация: 11.11.2016 Сообщений: 261	Может быть, с RSA не так, но эллиптическая криптография оптимизируется хардкорно. Обычно для криптосистем на эллиптических кривых пишется специальная библиотека длинных чисел - допустим, 256-битные числа, а не числа произвольной длины, и все это оптимизируется на основании теорем алгебры и особенностей железа. Можно добавить, что формулы сложения точек на кривых записываются в проективных координатах, тогда получается очень быстро. Последний раз редактировалось Aoizora; 02.10.2017 в 15:03.

Похожие темы
Тема	Автор	Раздел	Ответов	Последнее сообщение
Длинная арифметика	nimfa1	Общие вопросы Delphi	4	28.06.2012 15:16
Длинная арифметика.	Leshii	Паскаль, Turbo Pascal, PascalABC.NET	4	01.03.2012 11:38
C# Длинная арифметика	_Varyag_	Помощь студентам	23	21.02.2012 19:33
Длинная арифметика	DmT	Помощь студентам	2	06.10.2007 22:43

29.09.2017, 00:08	#2
Croessmah Вредный кошак Участник клуба Регистрация: 14.10.2012 Сообщений: 1,159	например, есть boost::multiprecision

01.10.2017, 23:14	#3
ura_111 Участник клуба Регистрация: 14.05.2016 Сообщений: 1,793	Поищи на форуме - здесь неоднократно поднимался этот вопрос.

02.10.2017, 13:42	#4
Aoizora Заблокирован Регистрация: 11.11.2016 Сообщений: 261	Зачем вообще нужны библиотеки длинной арифметики в традиционном виде? Кому это надо? В криптографии такая арифметика не нужна. Длинная арифметика для этих целей реализуется иначе. Выбирается фиксированное конечное поле и в этом поле реализуются операции на основании равенств, выполняющихся в этом поле. Получается неуниверсально, зато эффективно за счет использования векторных регистров.