Некоторые основные свойства целых чисел, которые используются в криптографии:

• Свойства делимости. 1 Например, если два числа делятся на целое число b ≠ 0, то их сумма и разность также делятся на число b. 1 Если в произведении целых чисел один из множителей делится на целое число b ≠ 0, то и произведение также делится на число b. 1
• Простые и составные числа. 2 Если число не имеет делителей, кроме самого себя и единицы, то оно называется простым, а если у числа есть ещё делители, то составным. 2 В криптографии используются большие простые числа длиной более 80–90 десятичных знаков. 1
• Факторизация целых чисел. 1 Факторизацией натурального числа называется разложение этого числа в произведение простых сомножителей. 1 Один из самых популярных методов криптографии с открытым ключом, метод RSA, основан на трудоёмкости задачи факторизации длинных целых чисел. 1
• Взаимно простые числа и функция Эйлера. 2 Два числа называются взаимно простыми, если они не имеют ни одного общего делителя кроме единицы. 2 Для криптографии формула Эйлера важна тем, что она позволяет легко получить число φ(n) для простых и некоторых других чисел. 2