Сайт о программировании, математике и моделировании
Записи с метками длинная арифметика
Актуальность применения «длинной» арифметики
6 Февраль
Для представления чисел в компьютере имеются стандартные типы данных. Однако возникает вопрос: что делать, если число очень большое и не помещается в рамки ни одного из существующих типов данных? Вот в этом случае как раз и используется «длинная» арифметика, суть которой заключается в представлении таких чисел в виде массива и проведении соответствующих арифметических операций над ними уже в преобразованном состоянии.
В настоящее время работа с длинными числами осуществляется во многих областях. Ярким примером может послужить криптография, где вся секретная часть спрятана не в знании кода алгоритма, а в наличии ключа, длинного случайного числа, подданного на «вход» алгоритма вместе с защищаемыми данными. И чем длиннее этот ключ, тем надежнее шифрование. Не вдаваясь в подробности отметим, что минимально разумной длиной ключа на данный момент считается 128 бит. Читать дальше >
Простые числа в криптографии
29 Январь
Все используемые сегодня криптосистемы с открытым ключом опираются на один из следующих типов необратимых преобразований:
Разложение больших чисел на простые множители и работа с простыми числами
Вычисление логарифма в конечном поле.
Вычисление корней алгебраических уравнений.
Таким образом, простые числа являются одной из неотъемлемых частей современных асимметричных криптосистем, то есть систем, использующих два ключа: открытый и секретный. Для того, чтобы криптосистема была стойкой к вскрытию, в ней необходимо использовать простые числа большой длины ( и выше).
Для того, чтобы использовать большие простые числа, их необходимо сначала построить. Читать дальше >
Описание лабораторного практикума по длинной арифметике
23 Январь
Материал был изложен не в рамках одной лабораторной работы, а в цикле из сем
и лабораторных:
- Лабораторная работа №1. Сложение, вычитание и сравнение длинных чисел.
- Лабораторная работа №2. Умножение длинных чисел.
- Лабораторная работа №3. Возведение в квадрат длинных чисел.
- Лабораторная работа №4. Вычисление остатка длинных чисел.
- Лабораторная работа №5. Модулярное умножение.
- Лабораторная работа №6. Возведение длинных чисел в степень.
- Лабораторная работа №7. Вычисление обратного по модулю.
Подобное изложение должно поспособствовать более качественному усвоению материала. Каждая лабораторная работа включает в себя цель, теоретическую часть с подробным описанием идей и примерами, контрольные вопросы и список практических заданий. В седьмой лабораторной работе по окончанию изучения курса «длинной» арифметики предложены темы для исследований. Читать дальше >
Программа деления длинного числа
28 Август
Приведем алгоритм деления длинного числа на цифру. За эту операцию отвечает процедура ShortDiv. Деление С = А/х и вычисление остатка r = A mod x (х-цифра)
void ShortDiv(
DIGIT *C, /* результат */
const DIGIT A[ ], /* делимое */
DIGIT x, /* делитель (1 цифра) */
DIGIT *pr, /* остаток */
int n) /* длина делимого */ Читать дальше >
Программа, реализующая модулярное умножение
9 Август
Операцию умножения по модулю можно выполнять следующим образом. Если А и В < Р, то С = (А Ч В) (mod P) вычисляется так:
D:=A Ч B;
С := D mod P. Читать дальше >
Программа возведения в квадрат длинного числа
3 Декабрь
За операцию возведения в квадрат методом «треугольника» отвечает процедура SquareTri./ Вычисление квадрата длинного числа С = А2 методом «треугольника»
void SquareTri(
DIGIT C[ ], /* результат длины 2n цифр */
const DIGIT A[ ], /* основание длины n цифр */
int n) /* длина основания */ Читать дальше >
Программа умножения длинного числа на цифру
3 Декабрь
Приведем листинг программы, выполняющей умножение длинного числа на цифру.
/* Умножение длинного числа на цифру С = АЧх */
void ShortMul(
DIGIT C[ ], /* результат длины n+1 цифра */
const DIGIT A[ ], /* сомножитель длины n цифр */
DIGIT x, /* сомножитель длины 1 цифра*/
int n) /* длина A */ Читать дальше >
Реализация алгоритма вычитания длинных чисел
3 Декабрь
За операцию вычитания отвечает процедура Sub
/* Вычитание длинных чисел длины n цифр C=A-B.
В качестве результата возвращаем заем старшего разряда d */ Читать дальше >
Сложение длинного числа
3 Декабрь
Приведем реализацию алгоритма сложения, а также ввод и вывод длинного числа на Паскале.
{основная программа}
Var A, B, C : Tlong;
Begin
Assign(Input, ‘Input.txt’); Reset(Input);
ReadLong(A); ReadLong(B) ;
Close(Input);
SumLongTwo(A, B, C); Читать дальше >
Сравнение «длинных» чисел длины n
3 Декабрь
Сравнение «длинных» чисел длины n цифр А==В */
int Cmp(
const DIGIT A[ ], /* первое число */
const DIGIT B[ ], /* второе число */
int n) /* длина чисел */
{
int i;
for(i=n-1; (i>=0)&&(A[i]==B[i]); i—);
if (i<0) return 0;
if(A[i]>B[i]) return +1;
return -1;
}
