Путь от 0 --> RSA

06.03.2011, 14:17

cel1697i845

Постоянный

Регистрация: 22.11.2008

Сообщений: 395

С нами: 9192803

Репутация: 776

Эту часть можно не читать.

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

Необходимо для работы:

1. Начальные знания языка C#.

2. Начальные знания математики(умножать, делить, и т.д.),

Предварительные знания(функции)

Модуль числа.

Модуль числа - обозначается число-1 mod(число-2) (оператор % в C#) вычисляет остаток после деления первого операнда на второй.

Пример:

Цитата:

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

5 mod(1) = 0 , так как 5 делим на 1, остаток 0
5 mod(2) = 1 , так как 5 делим на 2, остаток 1
5 mod(3) = 2 , так как 5 делим на 3, остаток 2
5 mod(4) = 1 , так как 5 делим на 4, остаток 1
5 mod(5) = 0 , так как 5 делим на 5, остаток 0

Теперь проделаем то же самое в C# (с выводом результатов на экран)

Пример C#:

Код:

Console.WriteLine("{0} mod({1}) = {2} , так как {0} делим на {1}, остаток {2}", 5, 1, 5 % 1);
Console.WriteLine("{0} mod({1}) = {2} , так как {0} делим на {1}, остаток {2}", 5, 2, 5 % 2);
Console.WriteLine("{0} mod({1}) = {2} , так как {0} делим на {1}, остаток {2}", 5, 3, 5 % 3);
Console.WriteLine("{0} mod({1}) = {2} , так как {0} делим на {1}, остаток {2}", 5, 4, 5 % 4);
Console.WriteLine("{0} mod({1}) = {2} , так как {0} делим на {1}, остаток {2}", 5, 5, 5 % 5);

Простое число.

Простое число- число которое делится только на единицу и на саму себя.

Ниже приведен пример поиска простого числа от 1 до 10.

Пример:

Цитата:

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

1 простое число, т.к. делиться только на саму себя и 1
2 простое число, т.к. делиться только на саму себя и 1
3 простое число, т.к. делиться только на саму себя и 1
4 НЕпростое число, т.к. делиться на саму себя и 1, 2
5 простое число, т.к. делиться только на саму себя и 1
6 НЕпростое число, т.к. делиться на саму себя и 1, 2, 3
7 простое число, т.к. делиться только на саму себя и 1
8 НЕпростое число, т.к. делиться на саму себя и 1, 2, 4
9 НЕпростое число, т.к. делиться на саму себя и 1, 3
10 НЕпростое число, т.к. делиться на саму себя и 1, 2, 5

Пример C#:

Код:

bool b1 = true;
for (int i = 1; i  b)
    {
	c2 = a;
	c1 = b;
    }
    else
    {
	c1 = b;
	c2 = a;
    }
    uint r = 1;
    while (r != 0)
    {
	r = c2 % c1;
	c2 = c1;
	c1 = r;
    }
    return c2;
}

Обратный элемент.

Теория.

Обратный элемент a группы G, это элемент b, при котором соблюдается условие a * b = e, где e единичный элемент.

Практика нахождения обратных элементов руками.

Пример: G = 19

Найдем вспомогательные элементы (по принципу 1+19+..+19)

1, 20, 39, 58, 77, 96, 115, 134, 153.(если этих значений не хватит, то продолжим список позже)

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

элемент 0 не учитывается, элементам 1-му и последнему присваиваем обратный элемент такой же как и сам элемент.

1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18

1, 10, 13, 5, 4, 16, 11, 12, 17, 2, 7, 8, 3 , 15, 14, 6, 9, 18

теперь объясню на первом значение почему обратный элемент равен 10

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

2*2=4 неподходит

2*3=6 неподходит

2*4=8 неподходит

2*5=10 неподходит

2*6=12 неподходит

2*7=14 неподходит

2*8=16 неподходит

2*9=18 неподходит

2*10=20 подходит число 20 присутствует в вспомогательных элементах, значит это и есть обратный элемент.

Пример C#:

[CODE]
static uint inverse(uint e, uint N)
{
uint n = 1;
uint d = 0;
while (n b)
{
c2 = a;
c1 = b;
}
else
{
c1 = b;
c2 = a;
}
uint r = 1;
while (r != 0)
{
r = c2 % c1;
c2 = c1;
c1 = r;
}
return c2;
}

/* входные параметры:
1. число для поиска с ним взаимо простых
*/
static uint[] Eiler(uint a)
{
uint n = 1;
uint k = 0;
uint[] K1 = new uint[a];
while (n b)
{
c2 = a;
c1 = b;
}
else
{
c1 = b;
c2 = a;
}
uint r = 1;
while (r != 0)
{
r = c2 % c1;
c2 = c1;
c1 = r;
}
return c2;
}

static uint[] Eiler(uint a)
{
uint n = 1;
uint k = 0;
uint[] K1 = new uint[a];
while (n

𝕏 Twitter Reddit Telegram Копировать ссылку