Растолкуйте пожалуста свойство псевдопростых чисел.

[Ascar]

Читаю книжку

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

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



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

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

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

[PAV]

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

[Ascar]

PAV в сообщении #341272 писал(а):

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

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

[BapuK]

там же в скобках написано, что такое порядок
а о группе $\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

[Ascar]

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

$d*x+1$

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

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

[Ascar]

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$ (мои интерес)

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