Справочник по математике
Изучите целые числа, простые числа, модульную арифметику, генераторы циклических групп, квадратичные остатки, диофантовы уравнения и RSA с формулами и примерами.
Последовательные степени 3 посещают каждый ненулевой остаток, прежде чем вернуться к 1.
Возведение в квадрат ненулевых остатков дает только 1, 2 и 4.
55 терминов
Целые числа и основы
Integer
ℤЦелое число, которое может быть отрицательным, нулевым или положительным.
Используйте целые числа для подсчета с направлением, индексов, разностей и точных дискретных вычислений.
-4, 0 и 27 - целые числа.Целые числа и основы
Natural number
ℕНатуральное число; включено ли ноль, зависит от используемой конвенции.
Укажите определение натуральных чисел перед их использованием в доказательстве, спецификации или программе.
В некоторых книгах натуральные числа начинаются с 1, поэтому всегда проверяйте определение.
This guide uses ℕ = {0, 1, 2, 3, ...}.Целые числа и основы
Absolute value
|a|Неотрицательное расстояние от целого числа до нуля на числовой прямой.
Используйте это для выражения величины, расстояния, ошибки и симметричных границ.
|-7| = 7 and |5 - 12| = 7.Целые числа и основы
Parity
n mod 2Свойство целого числа быть четным или нечетным.
Используйте четность для ветвления, чередующихся шаблонов, доказательств, контрольных сумм и логики на уровне битов.
18 mod 2 = 0, so 18 is even.Целые числа и основы
Division algorithm
a = bq + rДля целых чисел a и положительного b, существуют единственные целые числа q и r, такие что 0 ≤ r < b.
Используйте это в качестве основы для алгоритмов частного деления, остатка, алгоритма Евклида и модульной арифметики.
29 = 6 × 4 + 5, so q = 4 and r = 5.Делимость
Divisor
d | nЦелое число d является делителем n, когда n = dk для некоторого целого числа k.
Используйте делители для анализа структуры факторов, общих факторов и точной делимости.
6 | 42 because 42 = 6 × 7.Делимость
Multiple
n = dkЧисло, полученное путем умножения целого числа на другое целое число.
Используйте кратные значения для расписаний, общих периодов, циклических систем и выравнивания знаменателей.
Множители 5 включают 0, 5, 10, 15 и 20.Делимость
Divisibility test
n mod d = 0Правило, определяющее, делится ли одно целое число на другое без выполнения деления.
Используйте это для быстрых проверок, устного счета, проверки входных данных и обучения структуре разрядной системы.
7,452 is divisible by 3 because 7 + 4 + 5 + 2 = 18.Делимость
Greatest common divisor
gcd(a, b)Наибольшее положительное целое число, которое делит оба целых числа без остатка.
Используйте это для сокращения дробей, проверки взаимной простоты, решения сравнений и вычисления отношений.
gcd(84, 30) = 6.Делимость
Least common multiple
lcm(a, b)Наименьшее положительное целое число, которое является кратным обоих ненулевых целых чисел.
Используйте это для синхронизации циклов, объединения дробей и вычисления повторяющихся расписаний.
lcm(12, 18) = 36.Делимость
GCD-LCM identity
gcd(a,b)lcm(a,b)=|ab|Отношение, связывающее наибольший общий делитель и наименьшее общее кратное двух ненулевых целых чисел.
Используйте это для эффективного вычисления одного значения, когда другое уже известно.
gcd(12,18)=6, so lcm(12,18)=|12×18|/6=36.Делимость
Euclidean algorithm
gcd(a,b)=gcd(b,a mod b)Рекурсивный алгоритм для нахождения наибольшего общего делителя.
Используйте это для быстрой вычисления GCD, даже когда входные целые числа велики.
gcd(252,105) = gcd(105,42) = gcd(42,21) = 21.Делимость
Extended Euclidean algorithm
ax + by = gcd(a,b)Расширение алгоритма Евклида, которое также находит коэффициенты Безву x и y.
Используйте это для вычисления обратных величин по модулю и решения линейных диофантовых уравнений.
35×(-1) + 12×3 = 1, следовательно, -1 является коэффициентом для 35.Делимость
Coprime integers
gcd(a,b)=1Два целых числа взаимно просты, когда их наибольший общий делитель равен 1.
Используйте взаимную простоту для определения обратимости по модулю n и для применения теоремы Эйлера.
8 и 15 - взаимно простые числа, даже если ни одно из них не является простым.Простые числа и разложение
Prime number
pЦелое число больше 1, положительные делители которого - это только 1 и само число.
Используйте простые числа в качестве основных строительных блоков факторизации целых чисел и криптографии с открытым ключом.
2, 3, 5, 7 и 11 - простые числа.Простые числа и разложение
Composite number
n = abЦелое число больше 1, имеющее положительный делитель, отличный от 1 и самого себя.
Используйте это для различения целых чисел, которые можно разложить на множители, от простых чисел.
21 is composite because 21 = 3 × 7.Простые числа и разложение
Prime factorization
n=∏pᵢ^aᵢЗапись целого числа в виде произведения степеней простых чисел.
Используйте это для вычисления делителей, GCD, LCM и арифметических функций.
360 = 2^3 × 3^2 × 5.Простые числа и разложение
Fundamental theorem of arithmetic
n=∏pᵢ^aᵢКаждое целое число, большее 1, имеет единственное (с точностью до порядка множителей) разложение на простые множители.
Используйте это для обоснования алгоритмов и доказательств, основанных на простых степенях.
72 = 2^3 × 3^2 - это единственное разложение числа 72 на простые множители.Простые числа и разложение
Sieve of Eratosthenes
Алгоритм, который перечисляет простые числа до заданного предела, многократно отмечая кратные каждого найденного простого числа.
Используйте это, когда многие запросы на простые числа имеют один и тот же умеренный верхний предел.
Чтобы найти простые числа до 30, отметьте кратные 2, 3 и 5.Простые числа и разложение
Primality test
Алгоритм, который определяет, является ли данное целое число простым.
Используйте прямое деление для небольших входных данных и вероятностные тесты, такие как тест Миллера-Рабина, для больших входных данных.
Тест на простоту может потребовать нескольких раундов или определенного базового набора для заданного диапазона целых чисел.
Проверка делимости требует только кандидатов-делителей до √n.Модульная арифметика
Congruence
a ≡ b (mod n)Два целых числа конгруэнтны по модулю n, когда n делит их разность.
Используйте это для замены целых чисел эквивалентными остатками в циклических вычислениях.
29 ≡ 5 (mod 12), потому что 12 делит 29 - 5.Модульная арифметика
Residue class
[a]ₙМножество всех целых чисел, конгруэнтных фиксированному целому по модулю n.
Используйте это для рассуждений о модульных значениях как об классах эквивалентности, а не об отдельных числах.
[2]₅ = {..., -8, -3, 2, 7, 12, ...}.Модульная арифметика
Modulo operation
a mod nОперация, возвращающая представительный остаток после деления на n.
Используйте это для обертывания индексов, часов, корзин хеш-таблиц и периодических состояний.
(23 + 5) mod 24 = 4.Модульная арифметика
Modular arithmetic
ℤ/nℤАрифметика, выполняемая над классами остатков с результатами, приведенными по модулю n.
Используйте это в криптографии, теории кодирования, циклических буферах и расчетах календаря.
(17 × 19) mod 12 = 11.Модульная арифметика
Modular inverse
a⁻¹ mod nЗначение x, удовлетворяющее уравнению ax ≡ 1 (mod n); оно существует только тогда, когда НОД(a,n)=1.
Используйте это для деления в модульной арифметике, решения сравнений и реализации криптографических алгоритмов.
Не пытайтесь выполнять деление по модулю, не проверив, что делитель взаимно прост с модулем.
3⁻¹ mod 7 = 5 because 3 × 5 ≡ 1 (mod 7).Модульная арифметика
Modular exponentiation
a^k mod nВычисление степени по модулю n без предварительного построения потенциально огромной полной степени.
Используйте метод возведения в квадрат для криптографии, тестов на простоту и задач с большими степенями.
3^13 mod 7 = 3 using repeated squaring.Модульная арифметика
Linear congruence
ax ≡ b (mod n)Взаимно-простое уравнение, которое ищет целые числа x, удовлетворяющие линейному модульному уравнению.
Используйте условия GCD и модульные обратные для определения и вычисления решений.
3x ≡ 4 (mod 7) дает x ≡ 6 (mod 7).Модульная арифметика
Chinese remainder theorem
x ≡ aᵢ (mod nᵢ)Теорема, которая объединяет совместимые сравнения, давая единственное решение по модулю произведения, когда модули попарно взаимно просты.
Используйте это для объединения независимых циклических ограничений и ускорения вычислений с большими целыми числами.
x ≡ 2 (mod 3), x ≡ 3 (mod 5) дает x ≡ 8 (mod 15).Модульная арифметика
Euler's totient function
φ(n)Количество целых чисел от 1 до n, которые взаимно просты с n.
Используйте это в теореме Эйлера, для вычислений ключей RSA и для систем вычетов по модулю.
φ(12) = 4, потому что 1, 5, 7 и 11 взаимно просты с 12.Модульная арифметика
Euler's theorem
a^φ(n) ≡ 1 (mod n)Если a и n взаимно просты, то a в степени φ(n) дает 1 по модулю n.
Используйте это для уменьшения степеней, доказательства модульных тождеств и объяснения RSA.
gcd(3,10)=1 and φ(10)=4, so 3^4 ≡ 1 (mod 10).Модульная арифметика
Fermat's little theorem
a^(p-1) ≡ 1 (mod p)Для простого числа p и числа a, не делящегося на p, a в степени p-1 сравнимо с 1 по модулю p.
Используйте это для вычисления обратных величин по модулю простого числа и для проверки на простоту.
Прохождение теста Ферма не доказывает, что число является простым, поскольку существуют псевдопростые числа.
2^6 ≡ 1 (mod 7).Циклические группы и генераторы
Group
(G, *)Множество с ассоциативной операцией, единичным элементом и обратным элементом для каждого элемента.
Используйте группы для описания арифметических структур, в которых операции могут быть составлены и обращены.
Целые числа образуют группу относительно операции сложения, с нейтральным элементом 0 и обратным элементом -a для числа a.Циклические группы и генераторы
Abelian group
a*b=b*aГруппа, в которой операция коммутативна.
Используйте ее для модульного сложения, векторного сложения и многих арифметических групп, где порядок операций не имеет значения.
(ℤ/nℤ, +) - абелева группа.Циклические группы и генераторы
Additive group modulo n
(ℤ/nℤ, +)Классы остатков по модулю n с выполнением операции сложения по модулю n.
Используйте ее для моделирования циклических счетчиков, периодических состояний и классов сравнения по сложению.
In ℤ/5ℤ, 3+4=2.Циклические группы и генераторы
Multiplicative group of units
(ℤ/nℤ)×Классы остатков, взаимно простые с n, с умножением по модулю n.
Используйте ее для изучения модульных обратных элементов, первообразных корней, теоремы Эйлера и криптографии с открытым ключом.
(ℤ/8ℤ)×={1,3,5,7}.Циклические группы и генераторы
Cyclic group
G=⟨g⟩Группа, в которой каждый элемент является степенью или повторной суммой одного элемента.
Используйте ее для сведения операции группы к арифметическим операциям над показателями или целыми кратным.
Аддитивная группа ℤ/6ℤ порождается числами 1 и 5.Циклические группы и генераторы
Generator
⟨g⟩=GЭлемент, многократное применение групповой операции которого генерирует каждый элемент циклической группы.
Используйте ее для перечисления циклических групп и определения криптографических операций на основе показателей.
Всегда указывайте группу и операцию, потому что элемент может генерировать одну структуру, но не другую.
Степени 3 по модулю 7 дают 3,2,6,4,5,1, следовательно, 3 генерирует (ℤ/7ℤ)×.Циклические группы и генераторы
Order of an element
ord(g)Наименьшее положительное целое число k, для которого g^k является нейтральным элементом.
Используйте ее для проверки, является ли элемент генератором, и для определения длины цикла.
По модулю 7, ord(2)=3, потому что 2^3≡1 и ни один меньший положительный показатель не работает.Циклические группы и генераторы
Primitive root
ordₙ(g)=φ(n)Генератор мультипликативной группы единиц по модулю n.
Используйте примитивные корни для представления ненулевых остатков в виде степеней и для формулирования дискретных логарифмов.
3 является первообразным корнем по модулю 7, потому что его порядок равен φ(7)=6.Циклические группы и генераторы
Primitive root existence
Примитивные корни по модулю n существуют только для n=1, 2, 4, p^k или 2p^k, где p - простое число.
Используйте этот критерий перед поиском примитивного корня по модулю составного числа.
Не существует первообразного корня по модулю 8, поскольку число 8 не имеет требуемых свойств.Циклические группы и генераторы
Discrete logarithm
g^x=hЕсли дан генератор g и элемент группы h, то задача дискретного логарифма заключается в поиске показателя x, удовлетворяющего g^x=h.
Используйте ее для понимания безопасности протоколов Diffie-Hellman, ElGamal и кривых Эллиптических кривых.
Дискретный логарифм может быть легко вычислен для небольших или плохо выбранных групп и сложен только при определенных параметрах.
По модулю 7 с генератором 3, log₃(5)=5, потому что 3^5≡5.Циклические группы и генераторы
Carmichael function
λ(n)Наименьшая положительная степень m, такая что a^m ≡ 1 (mod n) для любого a, взаимно простого с n.
Используйте ее для получения более точного универсального показателя, чем φ(n), для анализа модульных степеней и RSA.
λ(8)=2, потому что каждое нечетное число a удовлетворяет условию a²≡1 (mod 8).Квадратичные остатки
Quadratic residue
x²≡a (mod n)Остаток a, для которого конгруэнтность x²≡a modulo n имеет решение.
Используйте ее для анализа модульных квадратных корней, тестов на простоту и криптографии на основе квадратичных остатков.
2 является квадратичным остатком по модулю 7, потому что 3²≡2.Квадратичные остатки
Quadratic nonresidue
Ненулевой остаток, для которого уравнение x²≡a modulo n не имеет решения.
Используйте ее для классификации остатков и построения тестов или криптографических параметров с известным квадратичным характером.
3 является квадратичным не-остатком по модулю 7.Квадратичные остатки
Modular square root
x=√a mod nРешение x уравнения x²≡a modulo n.
Используйте ее в декомпрессии точек, алгоритмах теории чисел и криптографии на основе остатков.
Квадратные корни числа 2 по модулю 7 равны 3 и 4.Квадратичные остатки
Legendre symbol
(a/p)Для простого нечетного числа p, значение 0, 1 или -1, указывающее делимость на p или статус квадратичного остатка по модулю p.
Используйте ее для тестирования квадратичного характера и компактного изложения критерия Эйлера и закона взаимности.
(2/7)=1, потому что 2 является квадратичным остатком по модулю 7.Квадратичные остатки
Jacobi symbol
(a/n)Мультипликативное расширение символа Лежандра на положительные нечетные составные знаменатели.
Используйте ее для эффективных вычислений характеристик и алгоритмов, которые не требуют предварительного факторизации n.
Символ Якоби, равный 1, не гарантирует, что a является квадратичным остатком по модулю составного числа n.
(5/21)=(5/3)(5/7)=1.Квадратичные остатки
Euler's criterion
a^((p-1)/2)≡(a/p) (mod p)Критерий, определяющий статус квадратичного остатка по модулю простого нечетного числа с использованием возведения в степень по модулю.
Используйте ее для вычисления символа Лежандра без перечисления всех квадратов.
Для p=7, 3^3≡-1 (mod 7), следовательно, 3 является невычислительным квадратичным остатком.Квадратичные остатки
Quadratic reciprocity
(p/q)(q/p)=(-1)^((p-1)(q-1)/4)Теорема, связывающая вопрос о том, является ли одно простое нечетное число квадратичным остатком по модулю другого.
Используйте ее для сведения больших вычислений символа Лежандра к меньшим.
Поскольку 3 и 11 оба дают 3 по модулю 4, (3/11)=-(11/3).Квадратичные остатки
Supplementary laws
(-1/p), (2/p)Формулы, определяющие квадратичный характер -1 и 2 по модулю простого числа.
Используйте их вместе с квадратичной взаимностью для завершения вычислений символа Лежандра.
(2/p)=1, когда p≡1 или 7 (mod 8), и -1, когда p≡3 или 5 (mod 8).Квадратичные остатки
Tonelli-Shanks algorithm
Алгоритм для нахождения модульного квадратного корня квадратичного остатка по модулю простого нечетного числа.
Используйте это, когда модуль является простым числом, и простое сокращение p≡3 (mod 4) не применяется.
Для p=13, метод Тонелли-Шенкс находит x=6 или 7 для x²≡10 (mod 13).Квадратичные остатки
Square roots modulo a composite
Модульные квадратные корни находятся по модулю простых степеней и объединяются с китайской теоремой об остатках.
Используйте ее для анализа систем типа Рабина и сравнений с составными модулями.
Для произведения различных нечетных простых чисел один остаток может иметь несколько квадратных корней, поэтому выбор предполагаемого корня требует дополнительной информации.
Решите x²≡1 по модулям 3 и 5, затем объедините выборы знаков по модулю 15.Целочисленные уравнения
Diophantine equation
Уравнение, для которого ищутся только решения, являющиеся целыми числами.
Используйте делимость, GCD, конгруэнтности и границы для определения, существуют ли целочисленные решения.
3x + 5y = 17 has the integer solution x = 4, y = 1.Целочисленные уравнения
Linear Diophantine equation
ax + by = cЛинейное уравнение, в котором неизвестные должны быть целыми числами; решения существуют только тогда, когда НОД(a,b) делит c.
Используйте это для точного распределения, задач с монетами, расписаний и ограничений решетки.
6x + 9y = 30 имеет решение, потому что НОД(6,9)=3 делит 30.Применения
RSA arithmetic
c ≡ m^e (mod n)Арифметика с открытым ключом, основанная на модульном возведении в степень и сложности факторизации произведения больших простых чисел.
Используйте это для понимания того, как теория чисел поддерживает шифрование и цифровые подписи.
Примеры значений предназначены только для обучения; для реальной RSA требуется стандартизированная защита, безопасные размеры ключей и проверенные библиотеки.
Используя тестовые значения n=55, e=3 и m=7, c=7^3 mod 55=13.