2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки


Правила форума


Посмотреть правила форума



Начать новую тему Ответить на тему
 
 "малая теорема Ферма" для составных чисел
Сообщение22.01.2020, 18:09 


27/11/08
111
Наткнулся на метод. (случайно)
Если знать составные части числа K, то можно найти степень M для которого будет верно утверждение

$2^M \mod K = 1$

Например
37*89*199=655307
K=655307
M=199440025800840449116009037576736768

$2^{199440025800840449116009037576736768} \mod 655307 = 1$

долго объяснять как получается M
но я подумал наверное эта тема известна
Практического смысла от этого нет, факторизация числа не решается эта задача :)
Знающие люди может посоветуют, что можно почитать по этой теме?
Наверное это простая задача на самом деле, и степень наверное не такая большая должна быть

-- Ср янв 22, 2020 19:14:37 --

31*43*83*149=16485211
K=16485211
M=10422861155466402260340116655075422344733340627169947648000

$2^{10422861155466402260340116655075422344733340627169947648000} \mod 16485211 = 1$

 Профиль  
                  
 
 Re: "малая теорема Ферма" для составных чисел
Сообщение22.01.2020, 18:26 
Заслуженный участник


20/12/10
9062
Самое простое --- это теорема Эйлера (в качестве показателя берется значение функции Эйлера от модуля). Она естественным образом обобщает малую теорему Ферма.

 Профиль  
                  
 
 Re: "малая теорема Ферма" для составных чисел
Сообщение22.01.2020, 18:49 


27/11/08
111
nnosipov в сообщении #1436396 писал(а):
Самое простое --- это теорема Эйлера (в качестве показателя берется значение функции Эйлера от модуля). Она естественным образом обобщает малую теорему Ферма.


Спасибо, действительно
но моим методом получается быстрее можно наити степень содержащую в себе значение функции Эйлера :)))
Тоесть зная все делители можно както БЫСТРО вычислить функцию Эйлера
по этой теме нужны материалы

У простого числа понятно - функция эйлера равна простому числу минус один
Зная все делители числа можно вычислить функцию Эйлера быстро? вот тогда такой вопрос :)

 Профиль  
                  
 
 Re: "малая теорема Ферма" для составных чисел
Сообщение22.01.2020, 19:50 
Заслуженный участник
Аватара пользователя


21/11/12
1968
Санкт-Петербург
Ascar в сообщении #1436391 писал(а):
$2^M \mod K = 1$
Например
37*89*199=655307
K=655307
M=199440025800840449116009037576736768
$2^{199440025800840449116009037576736768} \mod 655307 = 1$

А наименьшее общее кратное кратное не пробовали брать? $\operatorname{lcm}(\varphi(37),\varphi(89),\varphi(199))=\operatorname{lcm}(36,88,198)=792.$
$a^{792}=1\mod655307$ верно для любого $a$ вз.пр. с модулем.
Ascar в сообщении #1436391 писал(а):
долго объяснять как получается M... что можно почитать по этой теме?

Даже писать долго. См. Функция Кармайкла и учебники по теории чисел.
Ascar в сообщении #1436404 писал(а):
Зная все делители числа можно вычислить функцию Эйлера быстро? вот тогда такой вопрос :)

$\varphi(M)=M\left ( \dfrac{p_1-1}{p_1} \cdot \dfrac{p_2-1}{p_2} \cdot ...  \cdot \dfrac{p_n-1}{p_n} \right ),$ где $p_1,p_2,...,p_n$ — список простых делителей $M.$

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 4 ] 

Модераторы: Модераторы Математики, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: VanD


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group