новое решение сравнения 2^n = 3 (mod n)

[megamix62]

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}$

[maxal]

megamix62 в сообщении #603522 писал(а):

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

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

[megamix62]

maxal в сообщении #75396 писал(а):

У меня значения вычислены для всех подходящих простых . Могу выложить - в архиве это весит 2.5GB Если это много, могу уменьшить верхнюю границу, например, до .

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

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

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

[hazzo]

Руст в сообщении #40022 писал(а):

Я не понял, имеет ли решение такого сравнения хоть какое то применение.

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

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

[megamix62]

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

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

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

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

[Руст]

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) была известна давно. А простой делитель вы сами нашли?

[maxal]

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
И вообще, в данной теме это оффтопик.

[maxal]

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 архиве) для тех, кто просил.

[megamix62]

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


$n=115\cdot 85646133749028084594317465224249$

-- 02.10.2012, 08:25 --

Цитата:

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

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

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

[maxal]

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 писал(а):

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

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

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

[megamix62]

? n=115*85646133749028084594317465224249
%1 = 9849305381138229728346508500788635
? Mod(2,n)^n -
%2 = Mod(8564613374902808459431746522424903, 9849305381138229728346508500788635)
115*85646133749028084594317465224249= 9849305381138229728346508500788635

[maxal]

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}$ не получится.

[megamix62]

Руст в сообщении #614290 писал(а):

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

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

[megamix62]

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)$
Что интересно, из значений $(p,a,m)$ вычисленых для всех подходящих простых $\leq 10^{10}$, на каждые $2 \cdot10^{6}$ значений $p$ приходится только около $8000$ подходящих значений $a$.

[dmd]

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