Функция Эйлера
HTML-код
- Опубликовано: 9 фев 2025
- Методы вычисления функции Эйлера. Лекция в МЭИ. За кадром осталось вычисление в виде phi(30)=30*(1-1/2)*(1-1/3)*(1-1/5) как пример реализации приведенной в лекции формулы при разложении числа на множители 30=2^1*3^1*5^1. Степени в формулу не входят.
Преподаватель от Бога . . . Спасибо вам большое . . .
Занимаюсь программированием, решил по приколу узнать как шифруются сообщения алгоритмом RSA. Как оказалось, алгоритм имеет внутри формулу Эйлера. Решил посмотреть ваше видео, чтобы узнать как эта функция работает. Все понятно и прекрасно объясняется, но я в очередной раз понял, почему мне не подходит очная форма обучения. В начале, каждые пару минут останавливал видео, чтобы вспомнить что означает тот или иной термин =) (или вовсе переварить информацию, объяснив ее самому себе еще раз). В жизни к сожалению такого не сделаешь, а уточнять такие простые термины как "взаимно простые числа" бывает стыдно. Благодарю за лекцию, пойду дальше изучать алгоритм =)
Замечательный преподаватель, большое спасибо!
45 лет как закончила школу. Послушала лекцию и помолодела. Спасибо.
Это не школьная программа
@@trio9355 школьная...
@@АлександрШандрыгин-ы1й ничего подобного,тфкп нет в школе
241 - 240
247 - 216
251 - 250
253 - 220
257 - 256
259 - 216
Вот некоторые значения функции Эйлера для чисел простых и кажущихся таковыми. 241, 251, 257 есть числа простые. 247, 253 и 259 - кажущиеся простыми.
Интересно, вы сможете отличить числа, являющиеся простыми, от чисел, внешне похожих на простые:
391 397 401 403 407 409
851 853 857 859 863 869 871 877
Если уравнение фи(x)=n имеет решения, то их, как правило, несколько.
Для n=2 x=3; 4; 6.
Для n=4 x=5; 8; 10; 12.
Для n=6 x=7; 9; 14; 18.
Для n=8 x=15; 16; 20; 24; 30.
Число n называется нетотиентным, если для него не существует соответствующего x. Наименьшее чётное - 14.
Не найдено ни одного n, при котором уравнение имеет только один корень - и в то же время не доказано полное отсутствие таковых.
Все простые числа большие 5 делятся на 8 категорий по остатку от деления на 30: 1, 7, 11, 13, 17, 19, 23 и 29.
Нетрудно догадаться, что более 2 простых чисел в одном десятке возможно только в каждом втором из трёх десятков: наибольшая концентрация простых чисел в рамках первой тысячи в десятках 1*, 10*, 19* и 82*.
Только при остатке от деления на 30, равном 11, 23 или 29, можно получить другое простое число путём удвоения с последующим прибавлением единицы (простые числа Софи Жермен и соответствующие им безопасные).
По сути, функция Эйлера от числа n - это количество несократимых правильных дробей со знаменателем n. 97 - простое число, и любая правильная дробь с этим знаменателем несократимая. Не все правильные дроби со знаменателем 91 несократимые: 6/91, 25/91, 57/91, 80/91 есть дроби несократимые. А 26/91, 49/91, 65/91, 77/91 сократить возможно: 2/7, 7/13, 5/7, 11/13.
А если у нас скажем дано последовательность чисел (1,2,3,4,6,8) то как нам здесь можно применить функцию Ейлера для нахождения попарно взаимно простых чисел? Или лучше тогда воспользоваться таблицей простых чисел?
Функция Эйлера для простого числа близка к 100% от этого числа. Функция Эйлера от чётного полупростого числа - к 50%. Если функция Эйлера от числа превышает 50% от него, то это число нечётное.
Функция Эйлера, как и любая другая функция, имеет свой график. Только он точечный: верхняя линия напоминает график y = x-1. Средняя линия - y = x/2 - 1. Между ними точки с нечётными абсциссами, ниже средней линии - с чётными. Но и здесь можно видеть две чёткие линии - скорее всего, это ф(3p) и ф(4p).
Спасибо. Очень любопытно.
Перебирать все числа до 1200 на предмет взаимной простоты с ним? 1200 - число, кратное 30 и не имеющее никаких простых делителей больше 5. Здесь значение можно найти через пропорцию: 1200/30 = х/8. Отсюда х = (1200*8)/30 = 40*8 = 320.
а почему можно использовать пропорцию? мы же не ищем через пропорцию кол-во простых чисел меньших n. Нашли сколько простых меньших 30 и по пропорции вычислили кол-во простых меньших 1200.
По сути, из доказанного факта сперва + fi(p1*p2)=fi(p1)*fi(p2) и выводится общая формула
для двох простих чисел p,q формула phi(pq) = phi(p)phi(q) очевидна:
phi(pq) = pq - (q-1) - (p-1) - 1 = (p-1)(q-1) = phi(p)phi(q)
те саме з останніми двома властивостями:
нехай n=2^k*m, де m непарне
тоді phi(n)=phi(2^k)phi(m)=(2^k-2^{k-1})phi(m)=2^{k-1}phi(m)
отже, якщо k=1, то phi(n)=phi(m); якщо k>1, то phi(n)=2*2^{k-2}phi(m)=2phi(2^{k-1}m)
Есть задача для данного M, найти максимальное x: phi(x)=M и минимальное y: phi(y)=M. Как решать?
Я бы просто перебором решил...
Может ли чётное нетотиентное число соседствовать с простым?
Может. Но только следовать за ним, но никак не предшествовать - любое число, предшествующее простому, является значением фЭ для него.
Учусь в лицее при МЭИ. Мечтаю стать математиком. На каком факультете вы преподаёте?
ЭНМИ (читаю дискр. матем), ИТАЭ (читаю теор.мех), ИРЭ (читаю прикл.механику). Но математика однозначно самая сильная на ИВТИ . Я там раньше читал математическое моделирование. Студенты этого института традиционно побеждают на олимпиадах Москвы и России по математике. Там работают такие выдающиеся математики как А.А. Амосов, Ю.А. Дубинский и др. По математике после ИВТИ идет наш ЭНМИ (проф. Кобрин А.И., Меркурьев И.В., Подалков В.В.). Остальные институты заметно по математике отстают.
если φ(p) = p-1; где p - простое число
верно ли обратное?
что если φ(n) = n-1 => n - простое число
Спасибо. Интересно. Где эта функция имеет применение?
В криптологии, везде, где работают простые числа. Она сама собой возникает в решении. Просто удобно с ней.
φ(18) = φ(2 * 3 * 3) = (2 - 1)(3 - 1)(3 - 1) = 1 * 2 * 2 = 4 А должно быть 6. Почему?
Потому что, чтобы эта формула была действительна, в разложении не должно быть повторяющихся простых множителей (такие числа называются свободными от квадратов).
Поэтому правильно находить так:
фи(18) = фи(2*3^2) = (2 - 1)(3^2 - 3) = 1 * (9 - 3) = 6.
Очень интерестный урок жалко что слишком урезали :(
Да, но мультипликативность функции эйлера не доказана ж ведь
А куда 5 в числовом ряду делось? Оно же простое вроде как
30 делится на 5, вот и не вошло.
Дядька то умный
а почему разделив по формуле фи(4) на фи(2)*фи(2) = 1*1 = 1, получаем фи(4) = 1, но в действительности фи(4) = 2 ?
Потому что эта формула действительна не для любых a и b, а только для взаимно простых!
М... Да уж... А доказательство мультипликативности было? Так чисто... Оно не сложное конечно. Это школьная математика (для нормального прилежного и в меру талантливого школьника)
2*2=4
Дали похожую задачу, при трудоустройстве на работу.
Куда устраивался?
а чем 3 и 5 не угодили?
Функций эйлера - количество ВЗАИМНО ПРОСТЫХ, то есть чисел, не имеющих общих делителей. В случае с 3 и 5 общими делителями будут являться сами числа
это функция так и в жизни мне не пригодилась
И всё же... Для чего нужна эта функция то?
Например, в криптографии. Там все основано на простых числах. А у простых чисел есть важное свойство - они непредсказуемы. Вот и шифры на них надежнее.
@@Kirsanov2011 я как раз разбираю алгоритм шифрования RSA. Но до сих пор не понимаю, для чего он нужен там. С простыми числами это одно, а зачем там нужно находить именно КОЛИЧЕСТВО взаимно простых, я не понимаю. С любым успехом я могу взять рандомно простое число меньше модуля.
Из Википедии (ф-я Эйлера)
На этапе создания пары из секретного и открытого ключей вычисляется
{\displaystyle \varphi (n)=\varphi (p\cdot q)=(p-1)\cdot (q-1),}\varphi(n) = \varphi(p \cdot q) = (p-1) \cdot (q-1),
где {\displaystyle p}p и {\displaystyle q}q - простые. Затем выбираются случайные числа {\displaystyle d,\ e}{\displaystyle d,\ e} так, чтобы
{\displaystyle d\cdot e=1\;{\bmod {\;}}\varphi (n).}d \cdot e = 1 \;\bmod \;\varphi(n).
Затем сообщение шифруется открытым ключом адресата:
{\displaystyle c=m^{e}\;{\bmod {\;}}n.}c = m^e \;\bmod \;n.
После этого расшифровать сообщение может только обладатель секретного ключа {\displaystyle d}d:
{\displaystyle m=c^{d}\;{\bmod {\;}}n.}m = c^d \;\bmod \;n.
Корректность последнего утверждения основывается на теореме Эйлера и китайской теореме об остатках.
Ребята, кто с термехом может помочь?
Я во вторник 4-го февр после 13.30 и до 15 буду в МЭИ, кафедра теор мех (РМДиПМ), Москва, Красноказарменная 13, корп. С, ауд С216. Расскажу беспл.
как можно связаться ватсапе?
Для начала, было-бы здорово, если-бы объяснили понятие (здесь объяснения не видно! И для меня - глупого в математике, всё не так очевидно, как для тех кто "прошарил" тему), а то ряд простых чисел... а где 5, 3? Из объяснения не совсем понятно.
Здесь имеется в виду не "ряд простых чисел", а ВЗАИМНО простые числа, то есть не имеющие с аргументом никаких общих делителей, кроме 1. В примере с phi(30) числа 3 и 5 к взаимно простым с 30 не относятся. А вот в случае с 11 как раз все числа от 1 до 10 будут с ним взаимно простыми (так как само 11 простое и не делится ни на что, кроме 1 и 11). Именно поэтому phi(30) = 8, а скажем phi(29) = 28
Вы говорили фи( n)меньше чем n и пишите фи (1)=1
Це можна сприймати як факт, що phi(1)=1. Або розуміти це так, як те що (1,1)=1, де перша одиниця це наше число, друга одиниця це одиниця з якою порівнюєм, ну і зрозуміло, що НСД(1,1)=1...тобто інакше кажучи 1 це єдине число, яке є взаємно просте само з собою...крім того, функція Ейлера phi(n) вказує кількість взаємно простих чисел менших або рівних n, при n>1,зрозуміло що n не є взаємно просте з собою...