Добавил:
Upload Опубликованный материал нарушает ваши авторские права? Сообщите нам.
Вуз: Предмет: Файл:

Spektorsky_diskretka

.pdf
Скачиваний:
5
Добавлен:
12.05.2015
Размер:
1.73 Mб
Скачать

6.3. ƒà㯠¯÷¤áâ -®¢®ª

„®¢¥¤¥--ï. ’¢¥à¤¦¥--ï ⥮६¨ õ ¯à®á⨬ - á«÷¤ª®¬ «¥¬¨ 6.3. „÷©á-

-®, ¬ âà¨æî ¤«ï §®¡à ¦¥--ï ¯÷¤áâ -®¢ª¨ c =

µj

¬®¦- §¬÷-î¢ â¨

 

i

 

 

«¨è¥ ¯¥à¥áâ ¢«¥--ï¬ á⮢¯æ÷¢, ⮡⮠§ áâ®á㢠--ï¬ ¤® ¯¥à¥áâ -®¢®ª i

â

j ¤®¢÷«ì-®ù ¯÷¤áâ -®¢ª¨ c0:

 

 

 

i

(i)

 

 

 

c0

 

 

c = µj= µc0(j):

 

Ÿªé® c0 õ âà -ᯮ§¨æ÷õî, ¯ à-÷áâì ¯¥à¥áâ -®¢®ª i â c0(i) à÷§- («¥-

¬

6.3). €«¥ ¯ à-÷áâì ¯¥à¥áâ -®¢®ª j â

c0(j) â ª®¦ à÷§- , ⮡⮠¯ à-÷áâì

 

i

c0(i)

 

¯÷¤áâ -®¢®ª µjâ

µc0(j)(â®ç-÷è¥, à÷§-¨å §®¡à ¦¥-ì ®¤-÷õù ¯÷¤áâ -

-®¢ª¨ c) ®¤- ª®¢ .

 

 

 

“ § £ «ì-®¬ã ¢¨¯ ¤ªã, ª®«¨ c0 õ ¤®¢÷«ì-®î ¯÷¤áâ -®¢ª®î - ¬-®¦¨-÷

A = f1; 2; : : : ; ng, ¤®áâ â-ì® §®¡à §¨â¨ c0 ã ¢¨£«ï¤÷ ª®¬¯®§¨æ÷ù âà -ᯮ§¨-

æ÷© (ä ªâ¨ç-® ®âਬãîç¨ ¬ âà¨æî µc0(j)÷§ ¬ âà¨æ÷

µj§ ¤¥ª÷«ìª

c0(i)

 

i

ªà®ª÷¢, - ª®¦-®¬ã ªà®æ÷ ¬÷-ïîç¨ ¬÷áæﬨ «¨è¥ ¤¢

á⮢¯æ÷).

•à¨ª« ¤ 6.25. •®§£«ï-¥¬® ¯÷¤áâ -®¢ªã c = µ2

3

1. •¥à¥áâ -®¢-

1

2

3

ª i = (1; 2; 3) õ ¯ à-®î (-¥ ¬÷áâ¨âì ÷-¢¥àá÷©), ¯¥à¥áâ -®¢ª j = (2; 3; 1)

â ª®¦ õ ¯ à-®î (¬÷áâ¨âì ¤¢÷ ÷-¢¥àá÷ù: f2; 1g ÷ f3; 1g). Žâ¦¥, ¢¨å÷¤- ¯÷¤-

áâ -®¢ª

 

c = µjõ ¯ à-®î, ®áª÷«ìª¨ ¯¥à¥áâ -®¢ª¨

i =

(1; 2; 3) â

 

 

i

 

 

 

 

 

 

 

j = (2; 3; 1) ¬ îâì ®¤- ª®¢ã ¯ à-÷áâì.

 

 

 

®áâ --÷©

’¥¯¥à ã ¬ âà¨æ÷ µ2

3

1¯®¬÷-ïõ¬® ¬÷áæﬨ ¯¥à訩 â

 

 

1

2

3

 

 

 

 

 

á⮢¯æ÷, ®âਬ ¢è¨ ÷-è¥ §®¡à ¦¥--ï ¤«ï ¯÷¤áâ -®¢ª¨ c:

 

 

 

 

 

c = µ1

3

2:

 

 

 

 

 

 

 

3

2

1

 

 

 

‡£÷¤-® § ⥮६®î 6.5, ¯ à-÷áâì ¯÷¤áâ -®¢ª¨ c

-¥ ¬ õ § «¥¦ ⨠¢÷¤

¢¨¡®àã ¬ âà¨æ÷ ¤«ï ùù §®¡à ¦¥--ï. „÷©á-®, ã æ쮬㠢¨¯ ¤ªã ¬ õ¬®: ¯¥-

à¥áâ -®¢ª

e

 

 

 

 

f

g

 

áâ -®¢ª

 

 

 

 

 

 

 

i = (3; 2; 1) -¥¯

à- (âਠ÷-¢¥àá÷ù: f3; 2g, f3; 1g, f2; 1g); ¯¥à¥-

 

e

 

 

(®¤- ÷-¢¥àá÷ï:

3; 2 ); ®â¦¥, ¬ âà¨-

 

j = (1; 3; 2) â ª®¦ -¥¯ à-

129

 

 

•®§¤÷« 6.

…«¥¬¥-⨠⥮à÷ù £àã¯

æï

µj

â ª®¦ ¢¨§- ç õ ¯ à-ã ¯÷¤áâ -®¢ªã (¯¥à¥áâ -®¢ª¨ i â

j ¬ îâì

 

e

 

 

 

 

i

 

e

e

®¤- ª®¢ã ¯ à-÷áâì { ®¡¨¤¢÷ -¥¯ à-÷).

 

e

 

 

 

Ž§- ç¥--ï 6.14 (¤à㣥 ®§- ç¥--ï ¯ à-®áâ÷ ¯÷¤áâ -®¢ª¨). •÷¤-

áâ -®¢ªã - §¨¢ îâì ¯ à-®î, ïªé® ùù §®¡à ¦ãîâì ã ¢¨£«ï¤÷ ª®¬¯®§¨æ÷ù

¯ à-®ù ª÷«ìª®áâ÷ âà -ᯮ§¨æ÷©, ÷ -¥¯ à-®î, ïªé® ùù §®¡à ¦ãîâì ã ¢¨£«ï¤÷

ª®¬¯®§¨æ÷ù -¥¯ à-®ù ª÷«ìª®áâ÷ âà -ᯮ§¨æ÷©.

 

 

 

‡ §- 稬®, é® ¥ª¢÷¢ «¥-â-÷áâì ®§- ç¥-ì 6.13 â

6.14,

§¢÷¤á¨ ÷ ª®-

४â-÷áâì ®§- ç¥--ï 6.14 (-¥§ «¥¦-÷áâì ¢÷¤ ᯮᮡ㠧®¡à ¦¥--ï ¯÷¤áâ -

-®¢ª¨ ã ¢¨£«ï¤÷ ª®¬¯®§¨æ÷ù âà -ᯮ§¨æ÷©), ®¤à §ã ¢¨¯«¨¢ õ § १ã«ìâ â÷¢

¢¯à ¢¨ 6.9.

4

3

1, ïª õ ¯ à-

•à¨ª« ¤ 6.26. •®§£«ï-¥¬® ¯÷¤áâ -®¢ªã c = µ2

1

2

3

4

-®î ¢ á¥-á÷ ®§- ç¥--ï 6.13 (¯¥à¥áâ -®¢ª¨ (1; 2; 3; 4) â

(2; 4; 3; 1) ®¡¨¤¢÷

¯ à-÷).

 

 

 

„«ï § áâ®á㢠--ï ®§- ç¥--ï 6.14 §®¡à §¨¬® ¯÷¤áâ -®¢ªã c ã ¢¨£«ï¤÷

ª®¬¯®§¨æ÷ù âà -ᯮ§¨æ÷©:

 

 

 

1

2

3

4

µ2

4

3

1= (2; 1) ± (2; 4):

Š÷«ìª÷áâì âà -ᯮ§¨æ÷© ¢ ®âਬ -®¬ã §®¡à ¦¥--÷ ¯ à- , ®â¦¥, ¯÷¤-

áâ -®¢ª

c

õ ¯ à-®î ÷ ¢ á¥-á÷ ®§- ç¥--ï 6.14.

•а®¤¥¬®-бвагх¬® - ¯а¨ª« ¤ч ¯ч¤бв -®¢ª¨ c ª®à¥ªâ-÷áâì ®§- ç¥--

6.14, ⮡⮠¢¨¯¨è¥¬® ¤«ï c ª÷«ìª ÷-è¨å ᯮᮡ÷¢ ஧ª« ¤ --ï ¢

ª®¬¯®§¨æ÷î âà -ᯮ§¨æ÷©:

1

2

3

4

 

c = µ2

4

3

1= (1; 4)±(1; 2) = (2; 4)±(1; 4) = (2; 1)±(2; 3)±(2; 3)±(2; 4):

Ÿª ¡ 稬®, ¢ ãá÷å -

¢¥¤¥-¨å ஧ª« ¤ å ª÷«ìª÷áâì âà -ᯮ§¨æ÷© § «¨-

и хвмбп ¯ а-®о (е®з

á ¬ ª÷«ìª÷áâì ¬®¦¥ §¬÷-î¢ â¨áï).

•à¨ª« ¤ 6.27. Ž¡ç¨á«¨¬® ¯ à-÷áâì ¯÷¤áâ -®¢®ª ã £à㯠å S2 â S3.

ƒàã¯

S2 ¬÷áâ¨âì â®â®¦-ã ¯÷¤áâ -®¢ªã e ÷ âà -ᯮ§¨æ÷î t = (1; 2)

(¤¨¢. ¯à¨ª«. 6.14). ’ ª¨¬ ç¨-®¬, S2 ¬÷áâ¨âì ®¤-ã ¯ à-ã (â®â®¦-ã) ¯÷¤-

áâ -®¢ªã e â

®¤-ã -¥¯ à-ã ¯÷¤áâ -®¢ªã (âà -ᯮ§¨æ÷î) t.

130

6.3. ƒà㯠¯÷¤áâ -®¢®ª

ƒà㯠S3 ¬÷áâ¨âì â®â®¦-ã ¯÷¤áâ -®¢ªã e, âਠâà -ᯮ§¨æ÷ù c1, c2, c3,

â ª®¦ ¤¢ 横«¨ ¤®¢¦¨-®î 3: f1 â f2 (¤«ï ¯÷¤áâ -®¢®ª £à㯨 S3 ¢¨ª®à¨áâ õ¬® ¯®§- ç¥--ï § ¯à¨ª«. 6.14). Žâ¦¥, S3 ¬÷áâ¨âì âਠ¯ à-÷ ¯÷¤-

áâ -®¢ª¨ (横«¨ -¥¯ à-®ù ¤®¢¦¨-¨ e, f1, f2) ÷ âਠ-¥¯ à-÷ ¯÷¤áâ -®¢ª¨ (âà -ᯮ§¨æ÷ù c1, c2, c3).

Š®¦- § ஧£«ï-ãâ¨å £à㯠S2

â S3

¬÷áâ¨âì ®¤- ª®¢ã ª÷«ìª÷áâì ¯ à-

-¨å ÷ -¥¯ à-¨å ¯÷¤áâ -®¢®ª (®¤-

¯ à-

© ®¤- -¥¯ à-

¢ S2, ÷ âਠ¯ à-÷

â âਠ-¥¯ à-÷ ¢ S3). „ «÷ (¯÷¤à®§¤. 6.12) ¡ã¤¥ ¤®¢¥¤¥-® ¡÷«ìè § £ «ì-

-¨© ä ªâ: ª®¦- £à㯠Sn ¯à¨ n ¸ 2

¬÷áâ¨âì n!

n!

 

2 ¯ à-¨å â 2 -¥¯ à-¨å

¯÷¤áâ -®¢®ª.

 

 

 

 

‡ ¢¥аигоз¨ ¯ч¤а®§¤ч«, - ¢¥¤¥¬® ®¤¨- ¯а¨ª« ¤ ¢¨ª®а¨бв --п в¥®ачщ ¯ч¤бв -®¢®ª г «ч-ч©-ч© «£¥¡ач.

•à¨ª« ¤ 6.28. ‡ ªãàáã «÷-÷©-®ù «£¥¡à¨ (- ¯à¨ª« ¤, [10]) ¤®¡à¥ ¢÷- ¤®¬® ä®à¬ã«ã ¤«ï ®¡ç¨á«¥--ï ¢¨§- ç-¨ª ¬ âà¨æ÷:

¯a2;1 a2;2 : : : a2;n

¯

=

 

( 1)k(c) a c

(1)

 

a

c

(2)

: : : a

c

¯: : : : : : : : : : : : : : : : : : :¯

 

 

 

 

 

1;

 

 

2;

 

n; (n)

¯

a1;1

a1;2

: : : a1;n

¯

 

 

 

 

 

 

 

 

 

 

 

 

 

 

a

 

: : : a

 

 

c Sn

¡

 

¢

 

 

¢

 

 

 

 

 

¯a

 

 

¯

 

X

 

 

 

 

 

 

 

 

 

 

 

¯

 

 

 

 

 

¯

 

 

 

 

 

 

 

 

 

 

 

 

 

¯

 

 

 

 

 

¯

 

2

 

 

 

 

 

 

 

 

 

 

 

(¯ч¤б㬮¢говмбп¯

¤®¤ -ª¨ ¤«ï¯

¢á÷å c

 

Sn; k(c), ïª ÷ à -÷è¥, ¯®§- ç õ

¯

n;1

 

n;2

 

n;n

¯

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

2

 

 

 

 

 

 

 

 

 

¯ à-÷áâì ¯÷¤áâ -®¢ª¨ c).

•®§£«ï-¥¬® ª®-ªà¥â-÷ ¢¨¯ ¤ª¨ ¤«ï n = 1; 2; 3.

1. ƒà㯠S1 ¬÷áâ¨âì ®¤-ã (â®â®¦-ã) ¯÷¤áâ -®¢ªã e. Žâ¦¥, ®âਬãõ¬®

X

ka1;1k = (¡1)k(c)a1;c(1) = (¡1)k(e)a1;e(1) = a1;1:

c2S1

2. ƒà㯠S2 ¬÷áâ¨âì ¤¢÷ ¯÷¤áâ -®¢ª¨ { â®â®¦-ã ¯÷¤áâ -®¢ªã e ÷ âà -á- ¯®§¨æ÷î c = (1; 2). Žâ¦¥, ®âਬãõ¬®

 

¯

a1;1

a1;2

¯

X

 

 

k c

k(e)

¯

 

a2;2

¯

= c

 

k(t)

 

( )a1;c(1)a2;c(2) =

 

¯a2;1

¯

2

S2

(¡1)

 

a1¯;e(1)a2;e(2)

 

 

 

 

 

 

= (¡1)

¯+ (¡1)

 

a1;t(1)a2;t(2) = a1;1a2;2 ¡ a1;2a2;1:

131

 

 

 

 

 

 

 

 

 

 

 

 

 

•®§¤÷« 6. …«¥¬¥-⨠⥮à÷ù £àã¯

3. ƒàã¯

S3 ¬÷áâ¨âì â®â®¦-ã ¯÷¤áâ -®¢ªã e, âਠâà -ᯮ§¨æ÷ù c1, c2,

c3, â ª®¦ ¤¢

横«¨ ¤®¢¦¨-®î 3: f1 â f2 (¯®§- ç¥--ï § ¯à¨ª«. 6.9).

Žâ¦¥, ¤«ï ¢¨§- ç-¨ª

¯®à浪ã 3 ®âਬãõ¬®

 

¯

a1;1

 

a1;2

a1;3

¯

X

 

 

 

 

 

 

 

 

¯

k(e)

 

 

¯

 

 

 

 

 

 

k(c1)

 

 

¯a2;1

 

a2;2

a2;3

¯

=

(

¡

1)k(c)a1;c(1)a2;c(2)a3;c(3) =

 

¯a3;1

 

a3;2

a3;3

¯

c2S3

 

 

 

 

 

 

= (

¡¯

 

 

 

 

¯

a3;e(3) + (

¡

1)

 

a1;c1(1)a2;c1(2)a3;c1(3)+

¯1)

 

a1;e(1)a2;e(2)¯

 

 

+(¡1)k(c2)a1;c2(1)a2;c2(2)a3;c2(3) + (¡1)k(c3)a1;c3(1)a2;c3(2)a3;c3(3)+

+(¡1)k(f1)a1;f1(1)a2;f1(2)a3;f1(3) + (¡1)k(f2)a1;f2(1)a2;f2(2)a3;f2(3) =

 

 

 

= a1;1a2;2a3;3 ¡ a1;1a2;3a3;2 ¡ a1;3a2;2a3;1¡

 

 

 

 

¡a1;2a2;1a3;3 + a1;2a2;3a3;1 + a1;3a2;1a3;2:

„¥â «ì-÷è¥

¯à® £àã¯ã Sn (§®ªà¥¬ , ¯à® ஧ª« ¤ --ï ¯÷¤áâ -®¢-

ª¨ ¢ ª®¬¯®§¨æ÷î -¥§ «¥¦-¨å 横«÷¢)

¬®¦- ¯à®ç¨â â¨, - ¯à¨ª« ¤,

ã [7, 10, 14]. „¥ïª÷

«£®à¨â¬÷ç-÷

 

ᯥªâ¨ £à㯨 ¯÷¤áâ -®¢®ª ¢¨á¢÷â-

«¥-® ¢ [15].

 

 

 

 

 

 

 

 

 

 

 

 

 

 

6.4.€¤¨â¨¢- â ¬ã«ì⨯«÷ª ⨢- £à㯨 ª« á÷¢ «¨èª÷¢

6.4.1. Œ-®¦¨- ª« á÷¢ «¨èª÷¢

“ æ쮬㠯÷¤à®§¤÷«÷ ¡ã¤¥ ஧£«ï-ãâ®

¤¨â¨¢-ã â ¬ã«ì⨯«÷ª ⨢-ã

§ ¢÷¤-®è¥--ï¬ ¥ª¢÷¢ «¥-â-®áâ÷ (mod n±)(, ¤¥ n { ä÷ªá®¢ -¥ - âãà «ì-¥

£à㯨, ¯®¢'ï§ -÷ § ä ªâ®à-¬-®¦¨-®î Z

mod n) ¬-®¦¨-¨ æ÷«¨å ç¨á¥« Z

ç¨á«®.

‚÷¤-®è¥--ï ¥ª¢÷¢ «¥-â-®áâ÷ (mod n) (§ ¬®¤ã«¥¬ n) ¤®á¨âì ¤¥â «ì-

-® ஧£«ï-ãâ® ¢ ஧¤. 3, ¯à¨ª«. 3.20. • £ ¤ õ¬®, é® ä ªâ®à-¬-®¦¨-

(mod n) ¬ õ ¢¨£«ï¤

 

 

 

¤¥

 

 

 

Œ-

Z

±

 

 

 

 

 

 

 

 

 

 

 

 

= fnm + k : m 2 Zg:

 

( mod n) = f0; 1; : : : ; k; : : : ; n ¡ 1g;

 

 

k

 

®¦¨-¨ (ª« ᨠ¥ª¢÷¢ «¥-â-®áâ÷)

 

 

(

0 · k · n ¡ 1

) - §¨¢ îâì ª« -

 

 

 

 

 

 

 

 

 

 

k

 

 

á ¬¨ «¨èª÷¢ § ¬®¤ã«¥¬ n. Žç¥¢¨¤-®, ª®¦¥- ª« á k бª« ¤ хвмбп § жч«¨е з¨б¥«, ¯чб«п ¤ч«¥--п ª®¦-®£® § пª¨е - n ®¤¥à¦ãîâì ®áâ çã k.

132

6.4. €¤¨â¨¢- â ¬ã«ì⨯«÷ª ⨢- £à㯨 ª« á÷¢ «¨èª÷¢

ªâ®à-¬-®¦¨-ã (mod n) ¯®§- ç îâì ç¥à¥§ Zn:

Zn = Z±(mod n) = f0; 1; : : : ; k; : : : ; n ¡ 1g; ¤¥ k = fnm + k : m 2 Zg:

™¥ à § - £®«®á¨¬®, é® ¥«¥¬¥-â ¬¨ ¬-®¦¨-¨ Zn õ ª« ᨠ«¨èª÷¢, ⮡-

â® -¥ ®ªà¥¬÷ æ÷«÷ ç¨á« , ¬-®¦¨-¨ ç¨á¥«. ‚ ¦«¨¢® â ª®¦ ¯ ¬'ïâ â¨, é® ¢¨à § k ¬ õ á¥-á ¤«ï ¤®¢÷«ì-®£® k 2 Z (-¥ â÷«ìª¨ ¤«ï 0 · k · n ¡ 1).

•à®â¥, ã ¬-®¦¨-÷ Zn ¬÷áâ¨âìáï à÷¢-® n à÷§-¨å ª« á÷¢, ÷ æ¥ á ¬¥ ª« ᨠk ¯à¨ 0 · k · n ¡1; ª« ᨠk § -®¬¥à ¬¨ k ¸ n â k < 0 §¡ч£ овмбп § ®¤-¨¬

÷§ ª« á÷¢ k ¯à¨ 0 · k · n ¡ 1:

n = 0; n + 1 = 1; ¡ 1 = n ¡ 1; : : : :

‚§ £ «÷, «¥£ª® ¯®¡ ç¨â¨, é® k = k mod n. • £ ¤ õ¬®, é® k mod n õ

§ £ «ì-®¯à¨©-ï⨬ ¯®§- ç¥--ï¬ ¤«ï ®áâ ç÷ ¢÷¤ ¤÷«¥--ï k -

n, ⮡â®

ç¨á«® k0 = k mod n ®¤-®§- з-® ¢¨§- з хвмбп 㬮¢ ¬¨:

 

0 · k0 · n ¡ 1;

(6.3)

k = n ¢ m + k0 ¤«ï ¤¥ïª®£® m 2 Z:

(6.4)

‡ §- 稬®, é® ç¨á«® m = k div n в ª®¦ ¢¨§- з хвмбп 㬮¢ ¬¨ (6.3)

÷ (6.4) ®¤-®§- ç-®:

m = maxfp 2 Z: k ¸ n ¢ pg:

•à¨ª« ¤ 6.29. •®§£«ï-¥¬® ¬-®¦¨-¨ Z1, Z2 â Z3.

1. Œ-®¦¨- Z1 = f0g бª« ¤ хвмбп § ®¤-®£® ¥«¥¬¥-в 0 = Z (¡ã¤ì-瘟 æ÷«¥ ç¨á«® ¤÷«¨âìáï - 1 ¡¥§ ®áâ ç÷). –¥© ¢¨¯ ¤®ª -¥æ÷ª ¢¨© ÷ ©®£®, ïª

¯à ¢¨«®, -¥ ஧£«ï¤ îâì.

2. Œ-®¦¨- Z2 = f0; 1g ¬÷áâ¨âì ¤¢ ¥«¥¬¥-⨠{ ¬-®¦¨-ã 0 ¯ à-¨å ç¨á¥« ÷ ¬-®¦¨-ã 1 -¥¯ à-¨å ç¨á¥«. “ æ쮬㠢¨¯ ¤ªã

(

k = k mod 2 = 0; ïªé® k ¯ à-¥; 1; ïªé® k -¥¯ à-¥:

‡®ªà¥¬ : 0 = 2 = ¡ 2 = 4 = ¡ 4; 1 = ¡ 1 = 3 = ¡ 3.

3.Œ-®¦¨- Z3 = f0; 1; 2g бª« ¤ хвмбп § вам®е ¥«¥¬¥-вч¢:

²¬-®¦¨-¨ 0 з¨б¥«, пªч ¤ч«пвмбп - 3 ¡¥§ ®áâ ç÷;

133

•®§¤÷« 6. …«¥¬¥-⨠⥮à÷ù £àã¯

² ¬-®¦¨-¨ 1 з¨б¥«, пªч ¤ч«пвмбп - 3 § ®áâ ç¥î 1;

²¬-®¦¨-¨ 2 з¨б¥«, пªч ¤ч«пвмбп - 3 § ®áâ ç¥î 2.

æ쮬㠢¨¯ ¤ªã, §®ªà¥¬ , ¬ õ¬®:

0 = 3 = ¡ 3 = 6 = ¡ 6; 1 = ¡ 2 = 4; 2 = ¡ 1 = 5:

6.4.2. €¤¨â¨¢- £à㯠Zn

‡ ä÷ªáãõ¬® n 2 N.

¬-®¦¨-÷ Zn = f0; 1; : : : ; n ¡ 1g

a + b = a + b;

¢¨§- 稬® ®¯¥à æ÷î «+»:

a; b 2 Z:

• ¢¥¤¥-¥ ®§- ç¥--ï ¯®âॡãõ ®¡óàã-â㢠--ï ª®à¥ªâ-®áâ÷: âॡ ¤®- ¢¥áâ¨, é® à¥§ã«ìâ â ®¯¥à æ÷ù a + b -¥ § «¥¦¨âì ¢÷¤ ¢¨¡®à㠯।áâ ¢-¨ª÷¢

§ ª« á÷¢ a â b.

‹¥¬ 6.4 (ª®à¥ªâ-÷áâì ®¯¥à æ÷ù «+» - Zn). •¥å © a1 = a, b1 = b. ’®¤÷ a1 + b1 = a + b.

„®¢¥¤¥--ï. „«ï ¤®¢¥¤¥--ï à÷¢-®áâ÷ a1 + b1 = a + b ¤®áâ â-ì® ¯¥à¥¢÷-

à¨â¨, é® ((a1 + b1) ¡ (a + b)) mod n = 0.

Žáª÷«ìª¨ a1 = a, b1 = b, ¬ õ¬®

a1 = a + m1n; b1 = b + m2n ¤«ï ¤¥ïª¨å m1; m2 2 Z:

€«¥ ⮤÷ ®âਬãõ¬®

(a1 + b1) ¡ (a + b) = (a1 ¡ a) + (b1 ¡ b) = m1n + m2n = (m1 + m2)n;

⮡⮠((a1 + b1) ¡ (a + b)) mod n = 0, é® ¤®¢®¤¨âì ⢥द¥--ï «¥¬¨.

Žâ¦¥, ¯®¡ã¤®¢ -® § ¬ª-¥-ã «£¥¡à¨ç-ã áâàãªâãàã hZn; +i. ‹¥£ª® ¤®-

¢¥áâ¨, é® â ª áâàãªâãà õ ¡¥«¥¢®î £à㯮î, ®áª÷«ìª¨ £à㯮¢÷ ¢« áâ¨- ¢®áâ÷ ( á®æ÷ ⨢-÷áâì, ª®¬ãâ ⨢-÷áâì, - ï¢-÷áâì -¥©âà «ì-®£® ¥«¥¬¥-- â e, â ª®¦ ÷á-㢠--ï ®¡¥à-¥-®£® x¡1;+ ¤«ï ª®¦-®£® x 2 Z) ®¤à §ã

¢¨¯«¨¢ îâì § - «®£÷ç-¨å £à㯮¢¨å ¢« á⨢®á⥩ ¤«ï áâàãªâãਠhZ; +i.

’ ª, ã áâàãªâãà÷ hZn; +i -¥©âà «ì-¨© ¥«¥¬¥-â e = 0, ®¡¥à-¥-¨© ¥«¥¬¥-â

(a)¡1;+ = ¡ a = n ¡ a.

134

6.4. €¤¨â¨¢- â ¬ã«ì⨯«÷ª ⨢- £à㯨 ª« á÷¢ «¨èª÷¢

‚¯à ¢ 6.10. •à®¢¥á⨠¯®¢-¥ ¤®¢¥¤¥--ï ä ªâã, é® áâàãªâãà hZn; +i õ ¡¥«¥¢®î £à㯮î.

ƒàã¯ã hZn; +i - §¨¢ îâì ¤¨â¨¢-®î £àã¯®î ª« á÷¢ «¨èª÷¢ § ¬®- ¤ã«¥¬ n. „«ï æ÷õù £à㯨 ç áâ® ¢¦¨¢ îâì ᪮à®ç¥-¥, ¡¥§ 㪠§ --ï ®¯¥-

à æ÷ù, ¯®§- ç¥--ï Zn; ïªé® ¢¨-¨ª õ ¬®¦«¨¢÷áâì ª®-ä«÷ªâã ¯®§- ç¥-ì,

§ áâ®á®¢ãîâì - §¢ã « ¤¨â¨¢- £à㯠Zn», é® ¢ª §ãõ - ®¯¥à æ÷î «+» (¤¨¢. § ã¢. 6.5).

•à¨ª« ¤ 6.30. •®§£«ï-¥¬® £à㯨 Z2 â

Z3.

1. • ¢¥¤¥¬® â ¡«¨æî Š¥«÷ ¤«ï ¤¨â¨¢-®ù £à㯨 Z2 (â ¡«. 6.3).

’ ¡«¨æï 6.3. ’ ¡«¨æï Š¥«÷ ¤«ï

¤¨â¨¢-®ù £à㯨 Z2

+ 0 1

0 0 1

11 0

Žç¥¢¨¤-®, ®¡¥à-¥-÷ ¥«¥¬¥-⨠¢ Z2 ¬ îâì ¢¨£«ï¤

(0)¡1;+ = 0; (1)¡1;+ = 1:

2. • ¢¥¤¥¬® â ¡«¨æî Š¥«÷ ¤«ï ¤¨â¨¢-®ù £à㯨 Z3 (â ¡«. 6.4).

’ ¡«¨æï 6.4. ’ ¡«¨æï Š¥«÷ ¤«ï ¤¨â¨¢-®ù £à㯨 Z3

+

0

 

1

 

2

 

 

 

 

 

 

 

 

 

 

 

 

 

 

0

 

0

1

2

 

1

 

 

 

1

 

 

2

 

0

 

22 0 1

‹¥£ª® ¯¥à¥¢÷à¨â¨, é® ®¡¥à-¥-÷ ¥«¥¬¥-⨠¢ Z3 ¬ îâì ¢¨£«ï¤

(0)¡1;+ = 0; (1)¡1;+ = ¡ 1 = 2; (2)¡1;+ = ¡ 2 = 1:

‡ 㢠¦¥--ï 6.13. €¤¨â¨¢- £à㯠Zn õ ¯à¨ª« ¤®¬ § £ «ì-®£® ⨯ã áâàãªâãà { â ª §¢ -¨å ä ªâ®à-£àã¯, ïª÷ ¡ã¤¥ ஧£«ï-ãâ® ¢ ¯÷¤à®§¤. 6.12.

135

e = 1.

•®§¤÷« 6. …«¥¬¥-⨠⥮à÷ù £àã¯

6.4.3. Œã«ì⨯«÷ª ⨢- £à㯠Zp¤

‡ ä÷ªáãõ¬® p 2 N.

• ¬-®¦¨-÷ Zp = f0; 1; : : : ; p ¡ 1g ¢¨§- 稬® ®¯¥à æ÷î ¬-®¦¥--ï «¢»:

a ¢ b = ab; a; b 2 Z:

Ÿª ÷ ã ¢¨¯ ¤ªã ®¯¥à æ÷ù «+», ®§- ç¥--ï ®¯¥à æ÷ù «¢» â ª®¦ ¯®âॡãõ ®¡óàã-â㢠--ï ª®à¥ªâ-®áâ÷.

‹¥¬ 6.5 (ª®à¥ªâ-÷áâì ®¯¥à æ÷ù «¢» - Zp). •¥å © a1 = a, b1 = b. ’®¤÷ a1 ¢ b1 = ab.

„®¢¥¤¥--ï. „«ï ¤®¢¥¤¥--ï à÷¢-®áâ÷ a1 ¢ b1 = ab ¤®áâ â-ì® ¯¥à¥¢÷à¨â¨,

é® (a1b1 ¡ ab) mod p = 0.

Žáª÷«ìª¨ a1 = a, b1 = b, ¬ õ¬®

a1 = a + m1p; b1 = b + m2p ¤«ï ¤¥ïª¨å m1; m2 2 Z:

€«¥ ⮤÷ ®âਬãõ¬®

a1b1 ¡ ab = a1b1 ¡ a1b + a1b ¡ ab = a1(b1 ¡ b) + b(a1 ¡ a) = a1m2p + bm1p;

⮡⮠(a1b1 ¡ ab) mod p = 0, é® ¤®¢®¤¨âì ⢥द¥--ï «¥¬¨.

Žâ¦¥, ¯®¡ã¤®¢ -® § ¬ª-¥-ã «£¥¡à¨ç-ã áâàãªâãàã hZp; ¢i. ‹¥£ª® ¤®¢¥-

áâ¨, é® æï áâàãªâãà õ ª®¬ãâ ⨢-¨¬ ¬®-®ù¤®¬, ®áª÷«ìª¨ -¥®¡å÷¤-÷ ¢« - á⨢®áâ÷ ( á®æ÷ ⨢-÷áâì, ª®¬ãâ ⨢-÷áâì ÷ - ï¢-÷áâì -¥©âà «ì-®£® ¥«¥- ¬¥-â ) ®¤à §ã ¢¨¯«¨¢ îâì § - «®£÷ç-¨å ¢« á⨢®á⥩ ¤«ï ¬®-®ù¤ hZ; ¢i.

’ ª, ã áâàãªâãà÷ hZp; ¢i -¥©âà «ì-¨© ¥«¥¬¥-â

Ž¤- ª áâàãªâãà hZp; ¢i, ïª ÷ hZ; ¢i (¤¨¢. ¯à¨ª«. 6.5), § ¦®¤-®£® p ¸ 2 -¥ õ £à㯮î, ®áª÷«ìª¨ ¤«ï ¥«¥¬¥-â 0 ã æ쮬ã à §÷ -¥ ÷á-ãõ ®¡¥à-¥-®£®.

„«ï ¯®¡ã¤®¢¨ ¬ã«ì⨯«÷ª ⨢-®ù £à㯨 - ¬-®¦¨-÷ ª« á÷¢ «¨èª÷¢ ¡ã¤¥¬® ¤®¤ ⪮¢® ¢¨¬ £ â¨, 鮡 p 2 N ¡ã«® ¯à®á⨬ ç¨á«®¬1. Šà÷¬ ⮣®,

£àã¯ã ¡ã¤ã¢ ⨬¥¬® - «¬-®¦¨-÷ ¡¥§ -ã«ï»:

Zp¤ = Zp n f0g = f1; 2; : : : ; p ¡ 1g:

1ö-®¤÷ ¢ «÷â¥à âãà÷, ®á®¡«¨¢® ¢ ¤¥ïª¨å èª÷«ì-¨å ¯÷¤àãç-¨ª å, ç¨á«® 1 ¢¢ ¦ îâì

¯à®á⨬. ’ã⠡㤥¬® ¢¢ ¦ â¨, é® ¯à®á⥠ç¨á«® ¯®¢¨--® ¬ ⨠à÷¢-® ¤¢ à÷§-÷ - âã- à «ì-÷ ¤÷«ì-¨ª¨, ⮡⮠ç¨á«® 1 -¥ õ ¯à®á⨬.

136

6.4. €¤¨â¨¢- â ¬ã«ì⨯«÷ª ⨢- £à㯨 ª« á÷¢ «¨èª÷¢

’¥®à¥¬ 6.6. €«£¥¡à¨ç- áâàãªâãà hZp¤; ¢i ¤«ï ¯à®á⮣® p 2 N õ ¡¥«¥¢®î £à㯮î.

„®¢¥¤¥--ï. •¥àè § ¢á¥, ¯®âà÷¡-® ¤®¢¥á⨠§ ¬ª-¥-÷áâì áâàãªâãਠhZp¤; ¢i, ®áª÷«ìª¨ ¯à æîõ¬® -¥ - ¢á÷© ¬-®¦¨-÷ ª« á÷¢ «¨èª÷¢. „«ï æ쮣®

-¥®¡å÷¤-® ¤®¢¥áâ¨, é® a ¢ b 2 Zp¤ ¯à¨ a; b 2 Zp¤, â®¡â® é® a ¢ b 6= 0 ¤«ï

a =6 0, b =6 0.

•à¨¯ãáâ÷¬®, é® a ¢ b = 0. –¥ ®§- ç õ, é® ab mod p = 0, ⮡⮠¤®¡ã⮪ ab ¤÷«¨âìáï - p ¡¥§ ®áâ ç÷. €«¥ ⮤÷, ®áª÷«ìª¨ ç¨á«® p õ ¯à®á⨬, ®¤-¥ §

ç¨á¥« a ç¨ b ¬ õ ¤÷«¨â¨áï - p ¡¥§ ®áâ ç÷, é® á㯥à¥ç¨âì 㬮¢÷ a; b =6 0.

Žâ¦¥, § ¬ª-¥-÷áâì áâàãªâãਠhZp¤; ¢i ¤®¢¥¤¥-®.

€á®æ÷ ⨢-÷áâì ÷ ª®¬ãâ ⨢-÷áâì áâàãªâãਠhZp¤; ¢i ¢¨¯«¨¢ õ § - «®-

£÷ç-¨å ¢« á⨢®á⥩ ã áâàãªâãà÷ hZp; ¢i. •¥©âà «ì-¨¬ ¥«¥¬¥-⮬ ã áâàãªâãà÷ hZp¤; ¢i õ ª« á 1 (§ §- 稬®, é® 1 6= 0).

• à¥èâ÷, ¤®¢¥¤¥¬® ÷á-㢠--ï ®¡¥à-¥-®£® ¥«¥¬¥-â ¤«ï ¤®¢÷«ì¤-®£® a =6 0 ¢÷¤-®á-® ®¯¥à æ÷ù ¬-®¦¥--ï (⮡⮠¢ ¬¥¦ å áâàãªâãਠhZp ; ¢i).

‡ ä÷ªáãõ¬® ç¨á«® a, â ª¥, é® 1 · a · p ¡ 1, ÷ ஧£«ï-¥¬® - ¡÷à ª« á÷¢

«¨èª÷¢:

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

(6.5)

a ¢ 1; a ¢ 2;

: : : ; a ¢ (p ¡ 1):

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

ö§ ¢¨é¥¤®¢¥¤¥-®ù § ¬ª-¥-®áâ÷

¤

 

¢¨¯«¨¢ õ,

é®

 

 

 

 

¯à¨

; ¢i

ak

6= 0

 

 

 

 

 

 

hZp

 

 

¤

.

 

 

1 · k · p ¡ 1, ⮡⮠- ¡÷à ª« á÷¢ (6.5) «¥¦¨âì ã Zp

 

 

 

 

 

 

 

„®¢¥¤¥¬® ¤ «÷, é® ¢á÷ ª« ᨠ(6.5) ¯®¯ à-® à÷§-÷, ⮡⮠ak1 6= ak2 ¯à¨ 1 · k1 < k2 · p ¡ 1. •à¨¯ãá⨢è¨, é® ak1 = ak2, ®âਬãõ¬®

(ak2 ¡ ak1) mod p = 0; ⮡⮠(a ¢ (k2 ¡ k1)) mod p = 0:

‡¢÷¤á¨ ¢¨¯«¨¢ õ, é® ¬-®¦-¨ª a ¡® ¬-®¦-¨ª (k2 ¡ k1) ¬ õ ¤÷«¨â¨áï ¡¥§ ®áâ ç÷ - ¯à®á⥠ç¨á«® p, é® á㯥à¥ç¨âì 㬮¢ ¬ 1 · (k2 ¡ k1) · p ¡ 1

â 1 · a · p ¡ 1.

Žâ¦¥, ãá÷ ª« ᨠ¢ - ¡®à÷ (6.5) ¯®¯ à-® à÷§-÷, ⮡⮠- ¡÷à (6.5) ¬÷á- â¨âì p ¡ 1 ª« á÷¢ «¨èª÷¢, ª®¦¥- § ïª¨å «¥¦¨âì ã Zp¤. €«¥ Zp¤ â ª®¦

¬÷áâ¨âì p ¡ 1 ¥«¥¬¥-â÷¢, ⮡⮠-¥ ¬®¦¥ ¬÷áâ¨â¨ ª« á÷¢, ïª÷ -¥ ¢å®¤ïâì:

¤®

- ¡®àã (6.5). –¥ ®§- ç õ, é® - ¡÷à (6.5) §¡ч£ хвмбп § ¬-®¦¨-®о Zp¤

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

f1; 2; : : : ; p ¡ 1g = fa ¢ 1; a ¢ 2; : : : ; a ¢ (p ¡ 1)g:

 

‡÷ §¡÷£ã - ¢¥¤¥-¨å ¬-®¦¨- ¢¨¯«¨¢ õ, é® ®¤¨- § ¥«¥¬¥-â÷¢ ¬-®¦¨-¨ fa ¢ 1; a ¢ 2; : : : ; a ¢ (p ¡ 1)g ¬ õ ¤®à÷¢-î¢ â¨ 1; ¯®§- 稬® 楩 ¥«¥¬¥-â ç¥-

१ a ¢ ka, ¤¥ 1 · ka · p ¡ 1. €«¥ ⮤÷ ª« á «¨èª÷¢ ka 2 Zp¤ ¢¨§- ç õ

137

•®§¤÷« 6. …«¥¬¥-⨠⥮à÷ù £àã¯

¥«¥¬¥-â, ®¡¥à-¥-¨© ¤® a, ®áª÷«ìª¨ § ¯®¡ã¤®¢®î

a ¢ ka = a ¢ ka = 1:

’¢¥à¤¦¥--ï ⥮६¨ ¯®¢-÷áâî ¤®¢¥¤¥-®.

ƒàã¯ã hZp¤; ¢i (¤«ï ¯à®á⮣® ç¨á« p) - §¨¢ îâì ¬ã«ì⨯«÷ª ⨢- -®î £àã¯®î ª« á÷¢ «¨èª÷¢ § ¬®¤ã«¥¬ p; ¤«ï æ÷õù £à㯨 ç áâ® ¢¦¨¢ îâì ᪮à®ç¥-¥, ¡¥§ 㪠§ --ï ®¯¥à æ÷ù, ¯®§- ç¥--ï Zp¤; ïªé® ¢¨-¨ª õ ¬®¦- «¨¢÷áâì ª®-ä«÷ªâã ¯®§- ç¥-ì, § áâ®á®¢ãîâì - §¢ã «¬ã«ì⨯«÷ª ⨢- £à㯠Zp¤», é® ¢ª §ãõ - ®¯¥à æ÷î «¢» (¤¨¢. § ã¢. 6.5).

•à¨ª« ¤ 6.31. • ¢¥¤¥¬® â ¡«¨æî Š¥«÷ ¤«ï £à㯨 Z5¤ (â ¡«. 6.5).

’ ¡«¨æï 6.5. ’ ¡«¨æï Š¥«÷ ¤«ï ¬ã«ì⨯«÷ª ⨢-®ù £à㯨 Z5¤

£

1

 

2

 

3

 

4

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

1

1

2

3

4

 

 

2

 

 

2

 

4

 

1

 

3

 

 

3

 

 

3

 

1

 

4

 

2

 

44 3 2 1

‹¥£ª® ¯¥à¥¢÷à¨â¨, é® ®¡¥à-¥-÷ ¥«¥¬¥-⨠¢ Z5¤ ¬ îâì â ª¨© ¢¨£«ï¤:

(1)¡1 = 1; (2)¡1 = 3; (3)¡1 = 2; (4)¡1 = 4:

6.5. •®-ïââï ¯÷¤£à㯨. Šà¨â¥à÷© ¯÷¤£à㯨

•¥å © hG; ¤i { ¤®¢÷«ì- £à㯠.

Ž§- ç¥--ï 6.15. •÷¤£àã¯®î £à㯨 hG; ¤i - §¨¢ îâì ¯÷¤¬-®¦¨-ã

H ½ G, ïª

õ £àã¯®î § â÷õî á ¬®î ®¯¥à æ÷õî, é® ÷ £à㯠hG; ¤i (⮡â®

áâàãªâãà

hH; ¤i õ £à㯮î).

‡ 㢠¦¥--ï 6.14. 1. Š®«¨ ஧£«ï¤ îâì £àã¯ã hG; ¤i, á«÷¤ ¢ª § ⨠-¥ â÷«ìª¨ ¬-®¦¨-ã G, «¥ © ®¯¥à æ÷î «¤»; ª®«¨ ¦ ¡¥àãâì ¤® ஧£«ï¤ã ¯÷¤- £àã¯ã H ½ G, ¬®¦- -¥ ¢ª §ã¢ ⨠®¯¥à æ÷î «¤», ïª , § ®§- ç¥--ï¬ ¯÷¤£à㯨, ¬ õ §¡÷£ â¨áï § ®¯¥à æ÷õî £à㯨 hG; ¤i.

2. ‚ ®§- з¥--ч ¯ч¤£г¯¨ -¥ ¢¨¬ £ хвмбп, й®¡ -¥©ва «м-¨© ¥«¥¬¥-в e1 ¯÷¤£à㯨 H §¡÷£ ¢áï § -¥©âà «ì-¨¬ ¥«¥¬¥-⮬ e £à㯨 G, ®áª÷«ìª¨ 楩

138

Соседние файлы в предмете [НЕСОРТИРОВАННОЕ]