2014 dxdy logo

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

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




На страницу Пред.  1, 2
 
 
Сообщение31.07.2008, 00:44 
Аватара пользователя
Руст в сообщении #136427 писал(а):
При выполнении обобщённой гипотезы Римана достаточно перебирать простые а

Это Вы про что, простите? Перебирать для чего?

 
 
 
 
Сообщение31.07.2008, 09:15 
Это при проверке является а свидетелем псевдопростоты $n=2^st+1$ или нет.
Пробегаем по простым a от 2 до $2(\ln n)^2$ и вычисляем $b=a^t\mod n$.
Если это число 1, то а свидетель, если нет проверяем $b,b^2,..,b^{2^{s-1}}\mod n$. Если среди этих чисел есть -1(или то же самое n-1), то а свидетель, иначе n - составное.
Согласно ОГР для простоты n достаточно проверить по a от 2 до $N=2(\ln n)^2$, На самом деле для проверенных чисел до $10^{15}$ число N существенно меньше достаточно проверять для a=2,3,5,7,11,13.

 
 
 
 
Сообщение01.08.2008, 18:04 
Аватара пользователя
Руст, а числа $s,t,a$ как-то находятся? Просто не понятно, как их определять. Или такое представление единственно? Расскажите, пожалуйста, или дайте ссылку, где про это можно почитать.

 
 
 
 
Сообщение01.08.2008, 18:30 
Spook писал(а):
Руст, а числа $s,t,a$ как-то находятся? Просто не понятно, как их определять. Или такое представление единственно? Расскажите, пожалуйста, или дайте ссылку, где про это можно почитать.

Проверяется на простоту нечётное число n. Соответственно n-1 чётное. Делим это число на 2 до тех пор, пока не получится в результате нечётное число и обозначим это через t. Число s равно количеству делений на 2.

 
 
 
 
Сообщение01.08.2008, 18:54 
Аватара пользователя
Руст, спасибо, понял.

Материала набрал много, осталось поразбираться. Вопрос решен, всем спасибо.

 
 
 [ Сообщений: 20 ]  На страницу Пред.  1, 2


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group