https://play-sweet-bonanza.top/play слот sweet bonanza свит бонанза играть.

Простые числа

Простым называется целое число, большее единицы, единственными множителями которого является 1 и оно само: оно не делится ни на одно другое число. Два - это простое число. Простыми являются и 73, 2521, 2365347734339 и 2756839-1. Существует бесконечно много простых чисел. Криптография, особенно криптография с открытыми ключами, часто использует большие простые числа (512 бит и даже больше).

Евангелос Кранакис (Evangelos Kranakis) написал отличную книгу по теории чисел, простым числам и их применению в криптографии [896]. Паула Рибенбойм (Paula Ribenboim) написала две отличных справочных работы по простым числам вообще [1307, 1308].

Наибольший общий делитель

Два числа называются взаимно простыми, если у них нет общих множителей кроме 1. Иными словами, если наибольший общий делитель a и n равен 1. Это записывается как:

НОД(a,n)=1

Взаимно просты числа 15 и 28. 15 и 27 не являются взаимно простыми, а 13 и 500 - являются. Простое число взаимно просто со всеми другими числами, кроме чисел, кратных данному простому числу.

Одним из способов вычислить наибольший общий делитель двух чисел является алгоритм Эвклида. Эвклид описал этот алгоритм в своей книге, Элементы, написанной в 300 году до нашей эры. Он не изобрел его. Историки считают, что этот алгоритм лет на 200 старше. Это самый древний нетривиальный алгоритм, который дошел до наших дней, и он все еще хорош. Кнут описал алгоритм и его современные модификации в [863]. На языке C:

/* возвращает НОД (gcd) x и y */

int gcd (int x, int y) {

int g;

if (x < 0)

x = -x;

if (y < 0)

y = -y;

if (x + y == 0 )

ERROR ;

g = y;

while (x > 0) {

g = x;

x = y % x;

y = g;

}

return g;

}

Этот алгоритм можно обобщить для получения НОД массива m чисел:

/* возвращает НОД (gcd) xl, x2...xm */

int multiple_gcd (int m, int *x) {

slze_t i;

int g;

if (m < 1)

return 0;

g = x [0];

for (i=l; i<m; ++i) {

g = gcd(g, x[i]);

/* оптимизация, так как для случайных x[i], g==l в 60% случаев: */

if (g == 1)

return 1;

}

return g;

}