Длинная арифметика на Си

Здравствуйте, форумчане!

Хотелось бы мне начать топик, сообщения в котором я планирую пополнять постоянно (по возможности и уровню занятости, разумеется). Тема топика, как видно из заголовка, длинная арифметика.
Я не хочу подробно описывать, что такое длинная арифметика и зачем она нужна. Об этом любой может прочитать на той же википедии. Но небольшое вступление сделать все таки надо.
В длинной арифметике вычисления производятся над очень большими числами. С точки зрения программирования на языке Си такими числами можно считать любые, которые "не помещаются" в стандартные типы данных, то есть те, которые больше 32-х (64-х) бит. Наиболее популярно применение длинной арифметики, пожалуй, в криптографии.

Я знаю, что очень многим студентам в университетах дают задания на длинную арифметику и надеюсь, что кто-то наткнется на эти сообщения и они ему помогут (сам в свое время мучился).
Под конечной целью буду предполагать создание библиотеки или пакета (набора функций) для работы с длинными числами, возможно реализация каких-либо криптографических алгоритмов для примера.

Начальный план действий будет таков:

• Представление длинных чисел на языке Си
• Основные математические операции

PS. Я нисколько не претендую на специалиста в данной области. В первую очередь создаю топик для самого себя, чтобы изучить данную тему и как следует в ней разобраться. Но я надеюсь, что это заитересует многих. Я знаю, что только начинаю осваивать языки программирования, поэтому очень надеюсь на поддержку наших гуру во всех аспектах задачи.

PPS. За "Библию" в этой теме беру второй том из серии "Искусство программирования" Д. Кнута.

16

Сообщение от fasked Не понял о чем это Вы здесь.

О том, что младший в младшем и старший в младшем (младший байт в младшем, то есть меньшем адресе и старший байт в младшем адресе) - это порядки байт, а у тебя имеет место порядок слов, внутри которых уже имеется порядок байт. И если порядок слов противоположен порядку байт, то в четырёхбайтном двойном слове получаем чередующийся порядок 1032 или 2301. Можно ещё накрутить порядок двойных слов совпадающий с порядком байт: 54761032. И так далее. А теперь прикинь, на что будет похож код.

0

Сообщение от taras atavin О том, что младший в младшем и старший в младшем (младший байт в младшем, то есть меньшем адресе и старший байт в младшем адресе) - это порядки байт, а у тебя имеет место порядок слов, внутри которых уже имеется порядок байт. И если порядок слов противоположен порядку байт, то в четырёхбайтном двойном слове получаем чередующийся порядок 1032 или 2301. Можно ещё накрутить порядок двойных слов совпадающий с порядком байт: 54761032. И так далее. А теперь прикинь, на что будет похож код.

Ага, это да, вот только один момент, каким боком byte order должен влиять на код?

0

Сообщение от Vergil111 Если интересует, могу подбросить пару идей и функций по поводу модульной арифметики, которая так же очень популярна в криптографии. А так же реализацию некоторых популярных алгоритмов шифрования(Эль-Гамаля, RSA), основанных как раз на модульной арифметике и арифметики длинных чисел. Просто очень интересуюсь всякими шифрами и их взламыванием и готов помочь любому в данной теме))

я понимаю что я некропостер, но все же..

Может у Вас ещё осталась реализация RSA? Поделитесь, пожалуйста

fasked, наткнулся на тему в преддверии написания своего подобного пакета, не абы какого, но по-настоящему хорошего и совместимого со встроенными типами C++. Может невнимательно проглядел сообщения, но есть ли где-нибудь Ваш пакет, оформленный в виде zip архива с исходными кодами. Интересно было бы изучить его перед тем, как написать свой "Hello, World". Ну и предать его некоторой критике по возможности)))

Добавлено через 4 минуты
Да вся проблема RSA как раз в том, чтобы управиться с большими циферами, проще написать его самому, он пишется/отлаживается за пару часов))) В том его прелесть в сравнении с остальными лютыми шифрами))

0

Сообщение от fasked Функция-то может и будет проще выглядеть, но как-то возиться со структурами сложнее имхо будет.

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

Сообщение от fasked REALINT переименован в BIGINT

Я не большой знаток, но вроде бы как термин "big" используют для характеристики физических размеров (типа "большой дом"). А для длинных чисел применяют термин "large"

Сообщение от fasked Как всегда жду критики и комментариев. Если кому интересно могу описать алгоритм умножения

Не хватает теоретических выкладок. Думаю, они критичны начинающим. Даже для алгоритма сложения, поскольку не всем очевидно про бит переноса. Такие вещи полезно описывать на примере сложения или умножения столбиком на бумажке.

1