Сайт о программировании, математике и моделировании
Записи с метками длинная арифметика
Простые числа в криптографии
3 Декабрь
Все используемые сегодня криптосистемы с открытым ключом опираются на один из следующих типов необратимых преобразований:
Разложение больших чисел на простые множители и работа с простыми числами
Вычисление логарифма в конечном поле.
Вычисление корней алгебраических уравнений.
Таким образом, простые числа являются одной из неотъемлемых частей современных асимметричных криптосистем, то есть систем, использующих два ключа: открытый и секретный. Для того, чтобы криптосистема была стойкой к вскрытию, в ней необходимо использовать простые числа большой длины ( и выше).
Для того, чтобы использовать большие простые числа, их необходимо сначала построить. Читать дальше >
Описание лабораторного практикума по длинной арифметике
3 Декабрь
Материал был изложен не в рамках одной лабораторной работы, а в цикле из сем
и лабораторных:
- Лабораторная работа №1. Сложение, вычитание и сравнение длинных чисел.
- Лабораторная работа №2. Умножение длинных чисел.
- Лабораторная работа №3. Возведение в квадрат длинных чисел.
- Лабораторная работа №4. Вычисление остатка длинных чисел.
- Лабораторная работа №5. Модулярное умножение.
- Лабораторная работа №6. Возведение длинных чисел в степень.
- Лабораторная работа №7. Вычисление обратного по модулю.
Подобное изложение должно поспособствовать более качественному усвоению материала. Каждая лабораторная работа включает в себя цель, теоретическую часть с подробным описанием идей и примерами, контрольные вопросы и список практических заданий. В седьмой лабораторной работе по окончанию изучения курса «длинной» арифметики предложены темы для исследований. Читать дальше >
Программа, реализующая модулярное умножение
3 Декабрь
Операцию умножения по модулю можно выполнять следующим образом. Если А и В < Р, то С = (А Ч В) (mod P) вычисляется так:
D:=A Ч B;
С := D mod P. Читать дальше >
Программа деления длинного числа
3 Декабрь
Приведем алгоритм деления длинного числа на цифру. За эту операцию отвечает процедура ShortDiv. Деление С = А/х и вычисление остатка r = A mod x (х-цифра)
void ShortDiv(
DIGIT *C, /* результат */
const DIGIT A[ ], /* делимое */
DIGIT x, /* делитель (1 цифра) */
DIGIT *pr, /* остаток */
int n) /* длина делимого */ Читать дальше >
Программа возведения в квадрат длинного числа
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;
}
Сложение длинных чисел
3 Декабрь
За операцию сложения отвечает процедура ADD
DIGIT Аdd(
DIGIT C[ ], // результат
const DIGIT A[ ], // первое слагаемое
const DIGIT B[ ], // второе слагаемое
int n) // длина слагаемых Читать дальше >
