Поиск простых чисел

[dmd]

Интересно, почему так? Для простого $p$ и $M=2^p-1$, $s=\frac{M-1}{2p}$ примерно в 90% случаев выполняется $2^s \equiv 2^z \pmod s$, где $z$ - некое натуральное $<p$.

sz()=
{
forprime(p=5, 500,
 M= 2^p-1;
 s= (M-1)/2/p;
 t= lift(Mod(2,s)^s);
 print(p,"    ",factorint(t))
)
};

[Руст]

dmd в сообщении #613322 писал(а):

Интересно, почему так? Для простого $p$ и $M=2^p-1$, $s=\frac{M-1}{2p}$ примерно в 90% случаев выполняется $2^s \equiv 2^z \pmod s$, где $z$ - некое натуральное $<p$.

Почему 90%? все 100.
$s|M-1=2^p-2=2(2^{p-1}-1}$ значит 2 имеет период $p-1$ по модулю s, т.е. $2^x=2^z\mod s, 0\le z<p-1$.

[dmd]

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

Почему 90%? все 100.

Проверочный код, который я привёл выше, показывает, что не все 100%.

[Руст]

Значит вы неправильно находите $z=s\mod p-1$. Точнее надо брать по модулю $ord_s(2)$, но это как частное решение так же годится.

[megamix62]

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

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

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

[Droog_Andrey]

Это было известно ещё в 1963 году: http://www.prothsearch.net/fermat.html

[megamix62]

Droog_Andrey в сообщении #614265 писал(а):

Это было известно ещё в 1963 году: http://www.prothsearch.net/fermat.html

1963 - C. P. Wrathall
$k=149041,n= 32 $ - нето

[Someone]

Почему "не то"? Оно самое: $1479\cdot 2^{34}+1=25409026523137$.

-- Пн сен 03, 2012 20:28:08 --

Вы не в ту строчку посмотрели.

32       1479       34             1963       C. P. Wrathall 

[megamix62]

Сорри , уже разобрался

[anwior]

Дайте пожалуйста ссылку на он-лайн програмку извлечения квадр. корня из больших чисел.
Заранее благодарю!

[Someone]

Wolfram Alpha

[anwior]

Someone
За хорошую, должно быть, ссылку огромное спасибо.
За незнанием англ. перепробовал по всякому, в том числе и переходами на внутренние страницы, однако, безрезультатно. Так в работе и не увидел эту программу.

[Someone]

Господи, да она же открывается с примером вычисления квадратного корня. Вместо указанного там числа напишите своё.

[anwior]

Someone в сообщении #662574 писал(а):

Вместо указанного там числа напишите своё.

Это первым и пришло мне в голову, .. что я и сделал. Затем нажал справа (рядом с младшим разрядом) на кнопку: $=$. Выждал минут 5-7. Реакции - нет.
Ту же процедуру проделывал с других внутренних страниц сайта и результат одинаков.
Подскажите, что я не предусмотрел\упускаю.
Благодарю за терпение.

[Jnrty]

Хм... Я попробовал, у меня работает, если
1) щёлкнуть левой кнопкой мыши по знаку "=" (иногда приходится щёлкнуть несколько раз, прежде чем сработает, но эта проблема, скорее всего, гнездится у меня);
2) поместить курсор в окошко ввода вычисляемого выражения и нажать клавишу "Enter".

anwior в сообщении #662587 писал(а):

Это первым и пришло мне в голову, .. что я и сделал.

А слово "sqrt" в самом начале выражения, часом, не стёрли? Это слово - команда извлечь квадратный корень.