2014 dxdy logo

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

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




Начать новую тему Ответить на тему На страницу Пред.  1, 2, 3, 4, 5, 6, 7  След.
 
 Re: Re:
Сообщение06.08.2012, 18:50 


29/05/12
239
megamix62 в сообщении #581528 писал(а):
maxal в сообщении #75435 писал(а):

Цитата:
Ну, например, если 17 делит решение $2^n\equiv 3\pmod{n}$, то $\frac{n}{17}\equiv 14\pmod{16}.$ При этом, $n$ обязано делиться на gcd(14,16)=2, но этого быть не может. Поэтому 17 не может делить решения $2^n\equiv 3\pmod{n}$.



Обясните популярно пожалуйста на примере:
Если 485 делит решение $2^n\equiv 3\pmod{n}$, то $n\equiv 19\pmod{48}$ :oops:

 Профиль  
                  
 
 Re: новое решение сравнения 2^n = 3 (mod n)
Сообщение06.08.2012, 21:10 
Модератор
Аватара пользователя


11/01/06
5702
megamix62 в сообщении #603522 писал(а):
Обясните популярно пожалуйста на примере:
Если 485 делит решение $2^n\equiv 3\pmod{n}$, то $n\equiv 19\pmod{48}$ :oops:

Так как $485=5\cdot 97$ делит $n$, то в частности имеем $2^n\equiv 3\pmod{97}$. Ну а решением последнего сравнения является $n\equiv 19\pmod{48}$ (если непонятны детали - см. в википедии).

 Профиль  
                  
 
 Re: новое решение сравнения 2^n = 3 (mod n)
Сообщение09.08.2012, 14:07 


29/05/12
239
maxal в сообщении #75396 писал(а):
У меня значения вычислены для всех подходящих простых . Могу выложить - в архиве это весит 2.5GB Если это много, могу уменьшить верхнюю границу, например, до .

Вот для затравки все тройки в пределах :



Можно для $p$ в пределах $10^6-10^7$

или в архиве ( 2.5GB)

 Профиль  
                  
 
 Re:
Сообщение27.08.2012, 18:01 


22/08/12
127
Руст в сообщении #40022 писал(а):
Я не понял, имеет ли решение такого сравнения хоть какое то применение.

Конечно имеет. Ведь это сравнение частный случай задачи дискретного логарифмирования, которая формулируется следующим образом:
$A^X\equiv B \pmod{P}$, где P - большое простое число; A такое, что (A, P)=1.
Требуется найти число X.

Если взять A=2, X=P=n, B=3 и (2, n)=1, то видим, что это задача дискретного логарифмирования.
Данная задача, как и задача факторизации и задача логарифмирования на эллиптической кривой, имеет широкое применение в криптографии и защите информации.

 Профиль  
                  
 
 Re: новое решение сравнения 2^n = 3 (mod n)
Сообщение03.09.2012, 15:30 


29/05/12
239
Число Ферма $F({32})$ - не простое !

$n=2^{32}; $
$2^n +1$ not is prime !

$2^n +1 ==0 (mod 25409026523137)$

 !  Предупреждение за дублирование сообщений и оффтопик!

 Профиль  
                  
 
 Re: Re:
Сообщение03.09.2012, 17:02 
Заслуженный участник


09/02/06
4397
Москва
hazzo в сообщении #611285 писал(а):
Конечно имеет. Ведь это сравнение частный случай задачи дискретного логарифмирования, которая формулируется следующим образом:
$A^X\equiv B \pmod{P}$, где P - большое простое число; A такое, что (A, P)=1.
Требуется найти число X.

Если взять A=2, X=P=n, B=3 и (2, n)=1, то видим, что это задача дискретного логарифмирования.
Данная задача, как и задача факторизации и задача логарифмирования на эллиптической кривой, имеет широкое применение в криптографии и защите информации.

В дискретном логарифмировании Р - заданное известное число, а здесь Р=Х неизвестное, соответственно задача решается совсем другими алгоритмами и ничего общего.

megamix62 в сообщении #614205 писал(а):
Число Ферма $F({32})$ - не простое !

$n=2^{32}; $
$2^n +1$ not is prime !

$2^n +1 ==0 (mod 25409026523137)$

Насколько я знаю не простота F(32) была известна давно. А простой делитель вы сами нашли?

 Профиль  
                  
 
 Re: новое решение сравнения 2^n = 3 (mod n)
Сообщение04.09.2012, 05:14 
Модератор
Аватара пользователя


11/01/06
5702
megamix62 в сообщении #614205 писал(а):
Число Ферма $F({32})$ - не простое !

$n=2^{32}; $
$2^n +1$ not is prime !

$2^n +1 ==0 (mod 25409026523137)$

Сие давно известно - см. http://www.prothsearch.net/fermat.html
И вообще, в данной теме это оффтопик.

 Профиль  
                  
 
 Re: новое решение сравнения 2^n = 3 (mod n)
Сообщение08.09.2012, 00:10 
Модератор
Аватара пользователя


11/01/06
5702
maxal в сообщении #75396 писал(а):
Пусть $2^n\equiv 3\pmod{n}.$ При этом если простое $p$ делит $n,$ то $n$ с необходимостью удовлетворяет некоторому сравнению $n\equiv a\pmod{m},$ где $m$ делится на $p\cdot\mathop{ord}_p(2)$ (и поэтому в среднем имеет порядок $p^2$).
Руст выше написал примерную идею вычисления пары $(a,m)$.

У меня значения $(p,a,m)$ вычислены для всех подходящих простых $p\leq 10^{10}$. Могу выложить - в архиве это весит 2.5GB


Вот выложил этот файлик (в bzip2 архиве) для тех, кто просил.

 Профиль  
                  
 
 Re: новое решение сравнения 2^n = 3 (mod n)
Сообщение02.10.2012, 09:20 


29/05/12
239
Отыскал новое решение сравнения $2^n=3\pmod{n}.$ А именно:


$n=115\cdot 85646133749028084594317465224249$

-- 02.10.2012, 08:25 --

Цитата:
Вот выложил этот файлик (в bzip2 архиве) для тех, кто просил.


Спасибо за файлик .

Можно вопросик - с каким СУБД работаете ?

 Профиль  
                  
 
 Re: новое решение сравнения 2^n = 3 (mod n)
Сообщение02.10.2012, 14:02 
Модератор
Аватара пользователя


11/01/06
5702
megamix62 в сообщении #625976 писал(а):
Отыскал новое решение сравнения $2^n=3\pmod{n}.$ А именно:


$n=115\cdot 85646133749028084594317465224249$

Это не решение:
Код:
? n=115*85646133749028084594317465224249
%1 = 9849305381138229728346508500788635
? Mod(2,n)^n
%2 = Mod(8564613374902808459431746522424903, 9849305381138229728346508500788635)


megamix62 в сообщении #625976 писал(а):
Спасибо за файлик .

Можно вопросик - с каким СУБД работаете ?

Ни с какими. Это просто заархивированный текстовый файлик.

 Профиль  
                  
 
 Re: новое решение сравнения 2^n = 3 (mod n)
Сообщение02.10.2012, 16:46 


29/05/12
239
? n=115*85646133749028084594317465224249
%1 = 9849305381138229728346508500788635
? Mod(2,n)^n - :?:
%2 = Mod(8564613374902808459431746522424903, 9849305381138229728346508500788635)
115*85646133749028084594317465224249= 9849305381138229728346508500788635 :?:

 Профиль  
                  
 
 Re: новое решение сравнения 2^n = 3 (mod n)
Сообщение02.10.2012, 18:23 
Модератор
Аватара пользователя


11/01/06
5702
megamix62
И что?
$$8564613374902808459431746522424903 \not\equiv 3\pmod{9849305381138229728346508500788635}$$
То есть результат возведения 2 в степень $n$ по модулю $n$ не равен 3.

-- Tue Oct 02, 2012 10:28:44 --

Для $m=85646133749028084594317465224249$ у вас получилось такое сравнение:
$$2^{115m}\equiv 3\pmod{m},$$
но извлечь отсюда решение сравнения $2^n\equiv 3\pmod{n}$ не получится.

 Профиль  
                  
 
 Re: новое решение сравнения 2^n = 3 (mod n)
Сообщение22.11.2012, 07:35 


29/05/12
239
Руст в сообщении #614290 писал(а):
Насколько я знаю не простота F(32) была известна давно. А простой делитель вы сами нашли?


простой делитель я сам нашел
пока программа ищет $2^n\equiv 3\pmod{n}$ , решил заодно проверить простоту F(32) ...
Спасибо всем за помощь, :idea:
то иногда почитываешь книги по математике 100 - летней давности, и отстаешь от прогресса :oops:

 Профиль  
                  
 
 Re: новое решение сравнения 2^n = 3 (mod n)
Сообщение06.12.2012, 18:17 


29/05/12
239
maxal в сообщении #616059 писал(а):
maxal в сообщении #75396 писал(а):
Пусть $2^n\equiv 3\pmod{n}.$ При этом если простое $p$ делит $n,$ то $n$ с необходимостью удовлетворяет некоторому сравнению $n\equiv a\pmod{m},$ где $m$ делится на $p\cdot\mathop{ord}_p(2)$ (и поэтому в среднем имеет порядок $p^2$).
Руст выше написал примерную идею вычисления пары $(a,m)$.

У меня значения $(p,a,m)$ вычислены для всех подходящих простых $p\leq 10^{10}$. Могу выложить - в архиве это весит 2.5GB


Вот выложил этот файлик (в bzip2 архиве) для тех, кто просил.


Перелопатил $130\cdot10^{6}$ записей вида $(p,a,m)$ , нашел
из известных только три, которые были равны $a$, т.е $(4700063497, 3468371109448915 , 10991007971508067)$ :cry:
Что интересно, из значений $(p,a,m)$ вычисленых для всех подходящих простых $\leq 10^{10}$, на каждые $2 \cdot10^{6}$ значений $p$ приходится только около $8000$ подходящих значений $a$.

 Профиль  
                  
 
 Re: новое решение сравнения 2^n = 3 (mod n)
Сообщение06.12.2012, 18:33 


16/08/05
1153
Программой, которую выкладывал выше, подходящие были проверены до $10^{11}$.

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 91 ]  На страницу Пред.  1, 2, 3, 4, 5, 6, 7  След.

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



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

Сейчас этот форум просматривают: YandexBot [bot]


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

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