НГУ

Форумы НГУ
Текущее время: Ср авг 21, 2019 2:08 am

Часовой пояс: UTC + 7 часов




Начать новую тему Ответить на тему  [ Сообщений: 4 ] 
Автор Сообщение
СообщениеДобавлено: Вт июн 12, 2007 2:58 am 
Не в сети
Редкий гость

Зарегистрирован: Вт июн 12, 2007 2:54 am
Сообщения: 2
есть такая задача:

Доказать что для чисел Блюма(n конгруэнтно 3(mod4)) верно: если n - сильно псевдопростое число, то оно псевдопростое Эйлера.

Я над этой задачей думал почти весь семестр и никак :((
Буду рад любой помощи, а если кто знает решение то ваше супер...
Если можете посоветовать книгу по этому вопросу, буду очень рад (только желательно ссылку на электронный вариант)


Вернуться к началу
 Профиль  
 
 Заголовок сообщения:
СообщениеДобавлено: Вт июн 12, 2007 9:56 am 
Не в сети
Непрерывный писатель

Зарегистрирован: Пт июн 18, 2004 10:34 pm
Сообщения: 4435
Откуда: Сергей Подзоров
Ну надо же: числа Блюма! Напридумывают терминов!! Блюм --- он(она) что, первый, кто тройку или семёрку на четыре с остатком поделил?

А что такое псевдопростое число? И что такое псевдопростое число Эйлера?

_________________
Don't let the sun blast your shadow
Don't let the milk float ride your mind


Вернуться к началу
 Профиль  
 
 Заголовок сообщения:
СообщениеДобавлено: Вт июн 12, 2007 10:10 pm 
Не в сети
Редкий гость

Зарегистрирован: Вт июн 12, 2007 2:54 am
Сообщения: 2
n псевдопростое Эйлера по основанию х:
(x/n)(modn)=x^((n-1)/2)

где (x/n)-символ Якоби
n=p(1)^k(1)*...*p(m)^k(m) , где p(i)-простые //p(i)-p с индексом i
(а/n)=((a/p(1))^k(1))*...*((a/p(n))^k(n))
р-простое, тогда:
(a/p)=1, a(mod(p)) принадлежит Qp(множество квадратических вычетов)
-1, a(mod(p)) принадлежит Zp\{0}\Qp //Zp={0,1,2,...,p-1}
0, p делит а.

n сильнопсевдопростое по основанию х, если:
n-1=(2^s)*t, t-нечётное u: либо (x^t)(modn)=+-1
либо в последовательности y(0),y(1),...,y(s-1) существует -1, где у(0)=(x^t)(modn), y(i)=(y(i-1))(modn).

Только тут знаниями самих определений не обойтись, нужно еще владеть всей сопутствующей теорией....


Вернуться к началу
 Профиль  
 
 Заголовок сообщения:
СообщениеДобавлено: Ср авг 01, 2007 6:08 am 
Не в сети
Частый гость

Зарегистрирован: Вт июл 26, 2005 4:27 pm
Сообщения: 31
s-e-r-g-e-y писал(а):
n сильнопсевдопростое по основанию х, если:
n-1=(2^s)*t, t-нечётное u: либо (x^t)(modn)=+-1
либо в последовательности y(0),y(1),...,y(s-1) существует -1, где у(0)=(x^t)(modn), y(i)=(y(i-1))(modn).

Во-первых, воспользуйтесь тем, что для n=3(mod 4) с необходимостью получается s=1 и t=(n-1)/2. И поэтому условие сильной псевдопростоты сводится к тому, что x^((n-1)/2) = +-1 (modn).

Во-вторых, заметьте что в разложение n на простые входит нечетное число степеней pm^km таких, что pm = 3 (mod 4) и km - нечетно.

В-третьих, докажите, что если НОД(x^a + 1, x^b - 1) > 1, то b обязано быть четно.

Отсюда все получится.


Вернуться к началу
 Профиль  
 
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 4 ] 

Часовой пояс: UTC + 7 часов


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

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


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

Найти:
Перейти:  
Создано на основе phpBB® Forum Software © phpBB Group
Русская поддержка phpBB