1. Основна теорема арифметики
Кожне ціле число n ≥ 2 розкладається в добуток простих чисел єдиним чином (з точністю до порядку множників).
n = p₁^α₁ · p₂^α₂ · … · pₖ^αₖ (канонічний розклад)
Приклади:
12 = 2² · 3
360 = 2³ · 3² · 5
2024 = 2³ · 11 · 23
Кількість дільників: τ(n) = (α₁+1)(α₂+1)…(αₖ+1)
τ(12) = (2+1)(1+1) = 6 → дільники: 1,2,3,4,6,12 ✓
Сума дільників: σ(n) = ∏ (pᵢ^(αᵢ+1)-1)/(pᵢ-1)
σ(12) = (2³-1)/(2-1) · (3²-1)/(3-1) = 7 · 4 = 28
2. Алгоритм Евкліда: НСД і НСК
НСД(a,b) — найбільший спільний дільник
Алгоритм Евкліда:
НСД(a,b) = НСД(b, a mod b) при b ≠ 0
НСД(a,0) = a
Приклад: НСД(252, 105)
252 = 2·105 + 42
105 = 2·42 + 21
42 = 2·21 + 0
→ НСД = 21
Розширений алгоритм (тотожність Безу):
НСД(a,b) = a·u + b·v (знайти u,v)
21 = 105 - 2·42 = 105 - 2·(252-2·105) = 5·105 - 2·252
НСК(a,b) = a·b / НСД(a,b)
НСК(252,105) = 252·105/21 = 1260
3. Функція Ейлера φ(n)
φ(n) = кількість цілих від 1 до n, взаємно простих з n
Формула:
φ(n) = n · ∏(1 - 1/p) по простих p|n
Приклади:
φ(1)=1, φ(2)=1, φ(6)=2, φ(7)=6, φ(12)=4
Для простого p: φ(p) = p-1
Для pᵏ: φ(pᵏ) = pᵏ⁻¹(p-1)
Теорема Ейлера:
aᵠ⁽ⁿ⁾ ≡ 1 (mod n) якщо gcd(a,n)=1
(Мала теорема Ферма — частковий випадок: φ(p)=p-1)
4. RSA-шифрування
RSA (Рівест–Шамір–Едельман, 1977) — перша практична асиметрична криптосистема. Безпека заснована на складності факторизації великих чисел.
Генерація ключів:
1. Вибрати два великі прості p, q (по 1024+ біт)
2. n = p·q (відкритий модуль)
3. φ(n) = (p-1)(q-1)
4. Вибрати e: gcd(e, φ(n))=1, зазвичай e=65537
5. Знайти d: e·d ≡ 1 (mod φ(n)) → розширений Евклід
Відкритий ключ: (n, e)
Приватний ключ: (n, d) (d тримати в таємниці!)
Шифрування: c = mᵉ mod n
Розшифрування: m = cᵈ mod n
Коректність: cᵈ = (mᵉ)ᵈ = m^(ed) = m^(1+k·φ(n)) ≡ m (mod n)
(теорема Ейлера!)
Мікро-RSA (демо, n=55)
p=5, q=11, n=55, φ=40. e=3, d=27 (3·27=81≡1 mod 40).
m=2: c=2³ mod 55=8. Розшифрування: 8²⁷ mod 55=2 ✓
p=5, q=11, n=55, φ=40. e=3, d=27 (3·27=81≡1 mod 40).
m=2: c=2³ mod 55=8. Розшифрування: 8²⁷ mod 55=2 ✓
5. Числа Мерсена і великі прості
Числа Мерсена: Mₙ = 2ⁿ - 1
Необхідна умова: Mₙ просте ⟹ n просте
(але не навпаки: M₁₁ = 2047 = 23×89 — складене)
Відомі прості Мерсена (початок 2026):
M₂=3, M₃=7, M₅=31, M₇=127, M₁₃=8191, …
Найбільше відоме просте (2024): M₁₃₆₂₇₉₈₄₁
(41 024 320 цифр!!) — знайдено GIMPS
Тест Люка–Лемера: Mₙ просте ⟺
S_{n-2} ≡ 0 (mod Mₙ), де S₀=4, Sₖ=Sₖ₋₁²-2
6. Квадратичні лишки та закон взаємності
Символ Лежандра: (a/p) = 1 якщо x²≡a(mod p) має розв'язок
-1 якщо не має
0 якщо p|a
Критерій Ейлера: (a/p) ≡ a^((p-1)/2) (mod p)
Квадратичний закон взаємності Гаусса (1796):
(p/q)·(q/p) = (-1)^((p-1)(q-1)/4)
Для непарних простих p≠q:
якщо хоча б одне з p,q ≡ 1 (mod 4): (p/q)=(q/p)
якщо обидва p,q ≡ 3 (mod 4): (p/q)=-(q/p)
7. Гіпотеза Рімана
Дзета-функція Рімана:
ζ(s) = ∑_{n=1}^∞ 1/nˢ = ∏_p 1/(1-p⁻ˢ) (Re s > 1)
(зв'язок із простими числами через добуток Ейлера!)
Аналітичне продовження: ζ(s) визначена на всьому ℂ \ {1}
Нулі:
Тривіальні: s = -2, -4, -6, … (усі визначені)
Нетривіальні: у критичній смузі 0 < Re(s) < 1
Гіпотеза Рімана (1859):
Всі нетривіальні нулі лежать на критичній прямій
Re(s) = 1/2 (тобто s = 1/2 + it)
Перевірено: перші 10¹³ нулів — всі на Re=1/2
Наслідок: оцінка π(x) ~ Li(x) = ∫₂ˣ dt/ln(t)
(ГР ⟹ |π(x) - Li(x)| ≤ C·√x·ln x)
Гіпотеза Рімана — одна з Задач тисячоліття Клейнівського інституту ($1 000 000 премія). Нерозв'язана вже 165 років.
Про цю статтю
Ця стаття є частиною бази знань calculator.party — освітнього ресурсу, що поєднує теорію з практичними інструментами. Матеріал орієнтований на студентів, учнів і фахівців, що прагнуть глибокого розуміння теми. Тут зібрані ключові концепції, формули та реальні приклади застосування.
Криптографія — математика захисту інформації. RSA, AES, хеш-функції та цифрові підписи забезпечують безпеку кожного HTTPS-з'єднання та банківського переказу.
Навіщо читати цю статтю
Після прочитання ви зможете впевнено пояснити тему, вирішувати практичні задачі та застосовувати знання у навчанні й роботі. Стаття охоплює теоретичне підґрунтя і числові приклади, що полегшують запам'ятовування матеріалу.
Часті запитання (FAQ)
Що таке Теорія чисел: від алгоритму Евкліда до RSA і гіпотези Рімана і чому це важливо знати?
Теорія чисел: від алгоритму Евкліда до RSA і гіпотези Рімана — ключова тема в різних галузей науки. Розуміння її основ дає змогу вирішувати практичні задачі, успішно складати іспити та застосовувати знання в реальних ситуаціях. Стаття розкриває концепцію доступними словами з конкретними прикладами.
Які ключові формули та методи використовуються в теорія чисел: від алгоритму евкліда до rsa і гіпотези рімана?
Основні формули та методи для теорія чисел: від алгоритму евкліда до rsa і гіпотези рімана охоплюють як аналітичні підходи, так і числові алгоритми. У статті наведені всі ключові вирази з поясненням кожного позначення та вказівкою одиниць вимірювання.
Де в реальному житті застосовується теорія чисел: від алгоритму евкліда до rsa і гіпотези рімана?
Сфери застосування теорія чисел: від алгоритму евкліда до rsa і гіпотези рімана надзвичайно широкі: освіті, науці, інженерії та повсякденному житті. Знання цієї теми відкриває кар'єрні можливості в інженерії, науці, фінансах та IT-галузі.
Як розрахувати теорія чисел: від алгоритму евкліда до rsa і гіпотези рімана онлайн?
На calculator.party є безкоштовні онлайн-калькулятори з тематики 'Теорія чисел: від алгоритму Евкліда до RSA і гіпотези Рімана'. Достатньо ввести вхідні дані — і ви миттєво отримаєте точний результат з покроковим поясненням. Це ідеально для перевірки ручних розрахунків.
Яка різниця між теорія чисел: від алгоритму евкліда до rsa і гіпотези рімана та суміжними темами?
Стаття чітко описує межі тематики 'Теорія чисел: від алгоритму Евкліда до RSA і гіпотези Рімана', порівнюючи її з близькими поняттями. Чітке розуміння відмінностей допомагає уникнути типових помилок та плутанини при розв'язанні задач.