Тотиент Эйлера и малая теорема Ферма

Теорема Тотанса Эйлера

Теорема Эйлера гласит:
Если n положительно, функция Totient подсчитывает количество натуральных чисел меньше n, взаимно простых с n.

Φ (n) = Totient (n) = {Количество целых чисел ‹n И взаимно простых с n}

Например,
Φ (10) = 4 (1,3,7,9 - числа ‹10 и взаимно просты с 10)
Φ (7) = 6 (1,2,3,4,5 , 6 - числа ‹6 и взаимно просты с 6)

Базовый подход к нахождению счетчика заключается в переходе от 1 к n-1 и проверке, равен ли это НОД с n единицей или нет.

Что будет иметь временную сложность: - O (n log n). n для перехода от i к n и log n для поиска gcd (как? может быть не более log i цифр для каждого i).

Можем ли мы сделать лучше?
Существует формула произведения Эйлера, которая гласит, что значение общих функций меньше произведения по всем простым множителям p из n.

То есть
Φ (n) = n * (1–1 / a) * (1–1 / b) *….
где, a, b, .. - простые множители n.

Здесь мы также можем удалить вычисления с плавающей запятой. Это можно сделать, посчитав все простые множители и их кратные и вычтя это количество из n, чтобы получить значение общей функции.

Эта теорема составляет основу алгоритмов RSA.
А также обобщает теорему Ферма.

Маленькая теорема Ферма

Теорема Ферма утверждает, что если p - простое число, то a ^ p-a делится на a. Где, 1≤a≤p.
a ^ p-1 ≡ 1 mod p.

Маленькая теорема Ферма является основой для проверки простоты Ферма, также мы будем использовать ее для нахождения обратного по модулю в следующих случаях.

Если вы тоже любите числа, как и я, то вам стоит проверить Великую теорему Ферма, тест на простоту Ферма, лживые числа (которые не проходят тест Ферма, даже если оно простое) и числа Кармайкла (которые проходят тест Ферма. тест, даже если он непростой), которые действительно являются умопомрачительными фактами🤩.

Ускорители мозга🧠: -

  1. Φ (p) = p-1.
    Если p - простое число. (почему? НОД, если любое число с простыми числами равно 1.)
  2. Φ (a * b) = Φ (a) * Φ (b).
    Если gcd (a, b) = 1.
  3. Φ (p * q) = Φ (p) * Φ (q).
    Если p и q - простые числа. Это свойство используется в алгоритме RSA.
  4. Сумма значений общих функций всех делителей n равна n.
    Σ Φ (d) = n, где, d | n.
  5. a ^ Φ (p) ≡ 1 mod n
    Если     gcd (a, n) = 1 и a ‹n. Здесь функция Φ.

Ссылка🔗: -

Https://www.geeksforgeeks.org/eulers-totient-function/

Вот и все. В следующем блоге я расскажу о модульном возведении в степень и модульном обратном умножении.
Следите за обновлениями ... Спасибо ...