2014 dxdy logo

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

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


Правила форума


В этом разделе нельзя создавать новые темы.



Начать новую тему Ответить на тему
 
 Растолкуйте пожалуста свойство псевдопростых чисел.
Сообщение28.07.2010, 09:30 


27/11/08
111
Читаю книжку

Курс теории чисел и криптографии (Коблиц)

Нашол интересное свойство псевдопростых чисел

Изображение

образование у меня плохое

обясните мне пожалуста! что означают выражения

[*] группа (Z/nZ)*
[*] порядок b в группе (Z/nZ)

 Профиль  
                  
 
 Re: Растолкуйте пожалуста свойство псевдопростых чисел.
Сообщение28.07.2010, 09:37 
Супермодератор
Аватара пользователя


29/07/05
8248
Москва
В каком объеме Вы вообще знакомы с теорией групп? Термин "порядок элемента в группе" Вам вообще ни о чем не говорит?

 Профиль  
                  
 
 Re: Растолкуйте пожалуста свойство псевдопростых чисел.
Сообщение28.07.2010, 09:42 


27/11/08
111
PAV в сообщении #341272 писал(а):
В каком объеме Вы вообще знакомы с теорией групп? Термин "порядок элемента в группе" Вам вообще ни о чем не говорит?


ничего :) будем читать

 Профиль  
                  
 
 Re: Растолкуйте пожалуста свойство псевдопростых чисел.
Сообщение28.07.2010, 09:49 
Аватара пользователя


06/03/09
240
Владивосток
там же в скобках написано, что такое порядок :?
а о группе $\mathbb{Z} /n \mathbb{Z}$ можно немного прочитать сдесь:

(Оффтоп)

http://ru.wikipedia.org/wiki/Полная_система_вычетов#.D0.A1.D0.B8.D1.81.D1.82.D0.B5.D0.BC.D1.8B_.D0.B2.D1.8B.D1.87.D0.B5.D1.82.D0.BE.D0.B2

 Профиль  
                  
 
 Re: Растолкуйте пожалуста свойство псевдопростых чисел.
Сообщение28.07.2010, 10:08 


27/11/08
111
осталось только доказать (мой интерес) что делители псевдослучайного числа n по основанию b
можно представить в виде

$d*x+1$

где
[*] d - порядок b в группе Z/nZ
[*] x - какоето целое положительное число больше нуля

может это как в книге пишется очевидно? :)

 Профиль  
                  
 
 Re: Растолкуйте пожалуста свойство псевдопростых чисел.
Сообщение28.07.2010, 12:11 


27/11/08
111
Ascar в сообщении #341277 писал(а):
осталось только доказать (мой интерес) что делители псевдослучайного числа n по основанию b
можно представить в виде

$d*x+1$

где
[*] d - порядок b в группе Z/nZ
[*] x - какоето целое положительное число больше нуля

может это как в книге пишется очевидно? :)


неверное утверждение
нашол нехороший пример
$n=73555$ псевдопростое по основанию 4
опытным путем найдено
$d=1794$ -порядок b(=4) в группе $Z/_{73555}Z$

имеем разложение $73555 = 235 * 313$
$235=d*(9/69)+1=d*(3/23)+1$
$313=d*(12/69)+1=d*(4/23)+1$

вернее будет так


делители псевдослучайного числа n по основанию b
можно представить в виде

$d*(x/y)+1$

где
[*] d - порядок b в группе Z/nZ
[*] x - целое положительное число больше нуля
[*] y - целое положительное число больше нуля, такое что отношение $d/y$ - целое; для каждого из делителей является константой

остается только доказать что имеет место быть $d/y>2$ (мои интерес)

вообщем ценности никакой :)

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

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



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

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


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

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