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
5660
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
4382
Москва
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
5660
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
5660
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
5660
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
5660
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
1146
Программой, которую выкладывал выше, подходящие были проверены до $10^{11}$.

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

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



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

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


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

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