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 ] 

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



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

Сейчас этот форум просматривают: нет зарегистрированных пользователей


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

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