LINUX.ORG.RU

Реализация библиотеки для работы с большими числами в С


0

0

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

Re: Реализация библиотеки для работы с большими числами в С

Если скорость работы и "красота кода" не критична, то храни десятичные числа в обычных строках, а операции над ними выполняй как на бумажке столбиком. Всё что сложнее +-/* - реализуй через +-/*. Дёшево и сердито =).

Deleted ()

Re: Реализация библиотеки для работы с большими числами в С

В том то и дело что разрядность чисел 96 знаков, а выполнить надо три действия: НОД(алгорит Евклида)-сликом уж много получится вычитаний, два возведения в степень по модулю. Думаю это может затянутся на долгое время...

hoggor ()

Re: Реализация библиотеки для работы с большими числами в С

объясни преподавателю, что in real life за изобретение таких велосипедов больно бьют по лицу, и бери gmp

guest-3484-2009 ()

Re: Реализация библиотеки для работы с большими числами в С

вообще, насчет строк идея, на мой взгляд, самая удачная в твоем случае.
Не понимаю 2 момента:
1. какая разница твоему преподу на сторонние либы
2. кто тебе запрщал посмотреть различного рода реализации в сторонних либах и скопировать код себе? :)

vitroot ★★ ()

Re: Реализация библиотеки для работы с большими числами в С

> объясни преподавателю, что in real life за изобретение таких велосипедов больно бьют по лицу, и бери gmp

В вузе за такие отмазки больно бьют по лицу, а особо упорствующих отчисляют куда подальше.

const86 ★★★★★ ()

Re: Реализация библиотеки для работы с большими числами в С

> Буду рад услышать любые идеи и предложения.

Д. Кнут высказывал по этому поводу очень хорошие идеи во втором томе "Искусства программирования". Читай соответсвующие главы и переводи примеры на C.

const86 ★★★★★ ()

Re: Реализация библиотеки для работы с большими числами в С

> какая разница твоему преподу на сторонние либы

Сказано же, сам алгоритм несложный. То есть если разрешить юзать gmp, то курсач обернётся лабой.

const86 ★★★★★ ()

Re: Реализация библиотеки для работы с большими числами в С

В том то и дело что преподу надо обязательно свою реализацию, еще и гуевую. Мало того, курсач на С, консольный и под линухом, так это уже будет на бал оценка ниже. Кнута посмотрю, модулярную арифметику тоже. Самое странное что нигде нет реализации данного крипто-алгоритма.Хорошо было бы взять gmp и не изобретать колесо, но это не мой случай...

hoggor ()

Re: Реализация библиотеки для работы с большими числами в С

> Сказано же, сам алгоритм несложный. То есть если разрешить юзать gmp, то курсач обернётся лабой.

тогда почему не поковырять mpg и обернуть его курсачем? :)

// wbr

klalafuda ★☆☆ ()

Re: Реализация библиотеки для работы с большими числами в С

>> объясни преподавателю, что in real life за изобретение таких велосипедов больно бьют по лицу, и бери gmp

>В вузе за такие отмазки больно бьют по лицу, а особо упорствующих отчисляют куда подальше.

In real life такие люди редко что создают нового.

dave ★★★★★ ()

Re: Реализация библиотеки для работы с большими числами в С

> Сам алгоритм не сложный, только вот встала проблема работы с большими числами.

Тоже мне проблема... По-моему преподаватель прав.

dave ★★★★★ ()

Re: Реализация библиотеки для работы с большими числами в С

> In real life такие люди редко что создают нового.

Как можно создать что-то новое, когда не знаешь, как устроено старое??

const86 ★★★★★ ()

Re: Реализация библиотеки для работы с большими числами в С

Помню видел когда-то в интернетах варианты реализации длинных чисел,
один из них был - представление в виде связного списка, навроде

struct longnum
{
  int number;
  struct longnum * next;
};

в принципе должно работать :)

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

Cy6erBr4in ★★★ ()

Re: Реализация библиотеки для работы с большими числами в С

> В том то и дело что разрядность чисел 96 знаков, а выполнить надо три действия: НОД(алгорит Евклида)-сликом уж много получится вычитаний, два возведения в степень по модулю. Думаю это может затянутся на долгое время...

Сколько примерно простых действий (+-/*) тебе нужно выполнить? Пару сотен на современных процессорах ты вряд-ли заметишь.

Deleted ()

Re: Реализация библиотеки для работы с большими числами в С

>> In real life такие люди редко что создают нового.

>Как можно создать что-то новое, когда не знаешь, как устроено старое??

Ты не понял. Люди, которые всегда отдают предпочтение тому, что уже есть, редко создают что-то новое. Не Творцы они. Тип людей не тот.

Кстати, иногда бывает полезно _не_ знать старое, чтобы не повторить уже совершенные кем-то ошибки, а эти ошибки не всегда осознаются (!!). Но это - сложная и спорная тема. Не хочу ее развивать.

dave ★★★★★ ()

Re: Реализация библиотеки для работы с большими числами в С

> вообще, насчет строк идея, на мой взгляд, самая удачная в твоем случае.

Память расходуется неэффективно. Лучше строки в формате BCD, там в байте вмещаются сразу 2 десятичных цифры.

> кто тебе запрщал посмотреть различного рода реализации в сторонних либах и скопировать код себе?

+1

Den_Zurin ()

Re: Реализация библиотеки для работы с большими числами в С

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

А те, кто велосипедит на низкоуровневых языках не/недореализованные там мелочи - это нисколько не Творцы, а обычные быдлокодеры на низкоуровневых языках.

guest-3484-2009 ()

Re: Реализация библиотеки для работы с большими числами в С

Нужно разобраться с представлением чисел и только потом с реализацией базовых численных операций. Когда-то давно в студенчестве мутил такое от нечего делать (только мне это было нужно для реализации системы Эль-Гамаля). В "Получисленных алгоритмах" у Кнута описаны все необходимые нюансы. Там же есть и разные варианты алгоритмов численных операций (сложение, вычитание, умножение, деление, возведение в степень, модулярная арифметика). Скажу лишь, что из представленных там алгоритмов умножения наиболее прост в реализации метод Карацубы. При этом он не особо проигрывает методу, использующему дискретное преобразование Фурье.

С возведением в степень особо мутить не нужно. Конечно, можно (и даже нужно) извращаться с построением аддитивных цепочек, чтобы сократить количество умножений. Но это на самом деле не критично. Особенно когда начинаешь разбираться с курсовой в мае.

А строки - это не вариант. Скорость уж больно ужасная.

Для ускорения собственной работы проще сразу смотреть исходники. Причем не gmp, а какого-нибудь простенького bc. Там тоже всё это есть, причем в приличном виде.

twosev ★★ ()

Re: Реализация библиотеки для работы с большими числами в С

>НОД(алгорит Евклида)-сликом уж много получится вычитаний

Берите остаток от деления вместо того, чтобы вычитать. По сути то же, но гора-аздо быстрее!

Возведение в степень тоже разгоняется:
x^2n = x^n * x^n;
x^2^k сл-но требует k операций умножения
x^137 = x^128 * x^8 * x^1 итого всего 11 умножений.

lodin ★★★★ ()

Re: Реализация библиотеки для работы с большими числами в С

Мне кажется, что наиболее правильно использовать следующую стратегию: двухсотпятидесятиричную двоичнокодированная система счисления - это фактически число, записанное парами шестнадцатеричными цифр - по две две цифры на байт. Таким образом, никаких потерь памяти при хранении нет, все операции очень просто реализуются, работая чисто с байтами. Более того, при таком подходе работает деление на степень двойки методом сдвига всего массива чисел на соответствующее число бит! А основные операции - сравнение, сложение, вычитание, умножение и деление просто реализуются. Например, сложение будет выражаться как-то так: С = A + B carry = 0 for( i = 0, i < len, i++) { ci` = ai + bi + carry; ci = ci` % 0xFF; carry = ci` / 0xFF; } ci = carry; Остальные операции будут не многим сложнее. Фактически везде реализуется школьные алгоритм столбика. А для вычисления НОД я бы рекомендовал использовать бинарный алгоритм Евклида. В таком случае для него не надо будет реализовывать алгоритм деления, который из всей этой группы будет наиболее сложным. Если надо линейное представление нода (например для вычисления мультипликативно обратного) - расширенный бинарный алгоритм Евклида. Для него тоже деление не надо. В итоге мне кажется, что такую арифметику - сравнение, сложение, вычетание и умножение + бинарный евклид - можно реализовать за день, если не торопиться.

ЗЫ почему-то бинарный расширенный алгоритм евклида оказался редкостью, я его довольно долго гуглил. Если понадобится, могу дать - он у меня на диске валяется.

codergeneration ()

Re: Реализация библиотеки для работы с большими числами в С

>Берите остаток от деления вместо того, чтобы вычитать. По сути то же, но гора-аздо быстрее!

Это просто верх маразма. Ты когда-нибуть видел блоки аппаратного деления под микроскопом на risc ? Это большая редкость и занимает половину всего кристалла. Деление - одна из самых затратных простых операций.

Топикстартер - посмотри софтовую реализацию библиотеки для работы с многобайтными данными от любого 8-битного микроконтроллера - там все просто, главное нужны элементарные знания двоичной арифметики. Вообще достаточно одной операции сложения - вычитание - это сложение с двоичным дополнением, человеческий мозг кстати только складывать умеет. Все остальные операции - производные. Сейчас разве этому не обучают ?

imhotep ()

Re: Реализация библиотеки для работы с большими числами в С

Я такие вещи в школе писал, на олимпиадах по программированию. Делов на пару вечеров.

Не понимаю, о каких строках может идти речь. std::string в си? А char* - это в данном случае не строка, а массив unsigned char'ов. Длину и знак хранить отдельно.

+-*/ реализуй по школьным правилам "в столбик". Хорошие алгоритмы можно прикрутить позже, если останется время перед сдачей (преждевременная оптимизация - корень всех зол).

Основание системы счисления бери 10. Когда отладишь, можешь увеличить до 2^32-1 (изменив тип "цифр" на unsigned int), но учти, в каком виде будешь выводить. Человекам удобнее в 10м или 16ом.

legolegs ★★★★★ ()

Re: Реализация библиотеки для работы с большими числами в С

Ты счас только что предложил свой велосипед под названием двоично-кодированный int :) тогда как про bcd уже давно говорили и этим г-ом кроме интела никто не увлекается. Ни о какой оптимизации с таким подходом и речи быть не может - можно сразу забыть про быстрое умножение/деление при помощи сдвигов. Тогда как в любом процессоре есть специальные команды для работы с многобайтными числами - сложение с переносом и вычитание с учетом заема на предыдущей операции, сдвиги через флаг переноса.

imhotep ()

Re: Реализация библиотеки для работы с большими числами в С

Какой вуз? ))

NTL/Miracl если не хочешь gmp

vasily_pupkin ★★★★★ ()

Re: Реализация библиотеки для работы с большими числами в С

>> In real life такие люди редко что создают нового.

>Как можно создать что-то новое, когда не знаешь, как устроено старое??


Когда слишком хорошо знаешь старое, невольно начинаешь мыслить шаблонами, от того и врят ли сможешь что-то новое создать на уже казалось бы отшлифованном подспорье.

Deleted ()
Вы не можете добавлять комментарии в эту тему. Тема перемещена в архив.