ΠΠ°Π·Π²Π°Π½ΠΈΠ΅ ΠΊΠΎΠ΄ΠΎΠ² ΠΏΡΠΎΠΈΠ·ΠΎΡΠ»ΠΎ ΠΎΡ ΠΈΡ
ΡΠ²ΠΎΠΉΡΡΠ²Π°, Π·Π°ΠΊΠ»ΡΡΠ°ΡΡΠ΅Π³ΠΎΡΡ Π² ΡΠΎΠΌ, ΡΡΠΎ ΠΊΠ°ΠΆΠ΄Π°Ρ ΠΊΠΎΠ΄ΠΎΠ²Π°Ρ ΠΊΠΎΠΌΠ±ΠΈΠ½Π°ΡΠΈΡ ΠΌΠΎΠΆΠ΅Ρ Π±ΡΡΡ ΠΏΠΎΠ»ΡΡΠ΅Π½Π° ΠΏΡΡΠ΅ΠΌ ΡΠΈΠΊΠ»ΠΈΡΠ΅ΡΠΊΠΎΠΉ ΠΏΠ΅ΡΠ΅ΡΡΠ°Π½ΠΎΠ²ΠΊΠΈ ΡΠΈΠΌΠ²ΠΎΠ»ΠΎΠ² ΠΊΠΎΠΌΠ±ΠΈΠ½Π°ΡΠΈΠΈ, ΠΏΡΠΈΠ½Π°Π΄Π»Π΅ΠΆΠ°ΡΠ΅ΠΉ ΡΡΠΎΠΌΡ ΠΆΠ΅ ΠΊΠΎΠ΄Ρ. ΠΡΠΎ Π·Π½Π°ΡΠΈΡ, ΡΡΠΎ Π΅ΡΠ»ΠΈ, Π½Π°ΠΏΡΠΈΠΌΠ΅Ρ, ΠΊΠΎΠΌΠ±ΠΈΠ½Π°ΡΠΈΡ Π°0 Π°Π³ Π°2 … Π°"_! ΡΠ²Π»ΡΠ΅ΡΡΡ ΡΠ°Π·ΡΠ΅ΡΠ΅Π½Π½ΠΎΠΉ, ΡΠΎ ΠΊΠΎΠΌΠ±ΠΈΠ½Π°ΡΠΈΡ Π°ΠΏ_Π° Π°0Π°1Π°2 … Π°ΠΏ_2 ΡΠ°ΠΊΠΆΠ΅ ΡΠ²Π»ΡΠ΅ΡΡΡ ΡΠ°Π·ΡΠ΅ΡΠ΅Π½Π½ΠΎΠΉ. Π¦ΠΈΠΊΠ»ΠΈΡΠ΅ΡΠΊΠΈΠ΅ ΠΊΠΎΠ΄Ρ ΠΎΠ±ΡΡΠ½ΠΎ ΠΈΠΌΠ΅ΡΡ ΠΏΠΎΠ»ΠΈΠ½ΠΎΠΌΠΈΠ°Π»ΡΠ½ΠΎΠ΅ ΠΏΡΠ΅Π΄ΡΡΠ°Π²Π»Π΅Π½ΠΈΠ΅, ΠΎΠ·Π½Π°ΡΠ°ΡΡΠ΅Π΅, ΡΡΠΎ Π±ΠΈΠ½Π°ΡΠ½ΡΠ΅ ΡΠ»Π΅ΠΌΠ΅Π½ΡΡ ΠΊΠΎΠ΄ΠΎΠ²ΠΎΠ³ΠΎ ΡΠ»ΠΎΠ²Π° Π°"_Π° Π°ΠΏ_2 … Π°2 Π‘Π¦ Π°0 ΠΈΠ½ΡΠ΅ΡΠΏΡΠ΅ΡΠΈΡΡΡΡΡΡ ΠΊΠ°ΠΊ ΠΊΠΎΡΡΡΠΈΡΠΈΠ΅Π½ΡΡ ΠΏΠΎΠ»ΠΈΠ½ΠΎΠΌΠ° ΠΎΡ Π½Π΅ΠΊΠΎΡΠΎΡΠΎΠΉ ΡΠΈΠΊΡΠΈΠ²Π½ΠΎΠΉ ΠΏΠ΅ΡΠ΅ΠΌΠ΅Π½Π½ΠΎΠΉ Ρ
: Π°ΠΏ_1Ρ
ΠΏ~1 + Π°ΠΏ_2Ρ
ΠΏ'2 + … + Π°2Π₯2 + a^x + Π°0.
ΠΠ°ΠΏΡΠΈΠΌΠ΅Ρ, ΠΊΠΎΠ΄ΠΎΠ²ΠΎΠ΅ ΡΠ»ΠΎΠ²ΠΎ 11 010 ΠΏΡΠ΅Π΄ΡΡΠ°Π²Π»ΡΠ΅ΡΡΡ Π² Π²ΠΈΠ΄Π΅ ΠΏΠΎΠ»ΠΈΠ½ΠΎΠΌΠ° Ρ
4 + Ρ
3 + Ρ
.
ΠΠ°ΠΈΠ±ΠΎΠ»ΡΡΠ°Ρ ΡΡΠ΅ΠΏΠ΅Π½Ρ Ρ
Π² ΡΠ»Π°Π³Π°Π΅ΠΌΠΎΠΌ Ρ Π½Π΅Π½ΡΠ»Π΅Π²ΡΠΌ ΠΊΠΎΡΡΡΠΈΡΠΈΠ΅Π½ΡΠΎΠΌ Π½Π°Π·ΡΠ²Π°Π΅ΡΡΡ ΡΡΠ΅ΠΏΠ΅Π½ΡΡ ΠΏΠΎΠ»ΠΈΠ½ΠΎΠΌΠ°. Π’Π°ΠΊΠΈΠΌ ΠΎΠ±ΡΠ°Π·ΠΎΠΌ, Π² ΠΏΠΎΠ»ΠΈΠ½ΠΎΠΌΠ΅ ΡΡΠ΅ΠΏΠ΅Π½ΠΈ ΠΏ — 1 ΡΡΠ°ΡΡΠΈΠΉ ΠΊΠΎΡΡΡΠΈΡΠΈΠ΅Π½Ρ Π°ΠΏ_Π³ ΡΠ°Π²Π΅Π½ 1.
ΠΠ΅ΠΉΡΡΠ²ΠΈΡ Π½Π°Π΄ ΠΊΠΎΠ΄ΠΎΠ²ΡΠΌΠΈ ΠΊΠΎΠΌΠ±ΠΈΠ½Π°ΡΠΈΡΠΌΠΈ ΡΠ²ΠΎΠ΄ΡΡΡΡ ΠΊ Π΄Π΅ΠΉΡΡΠ²ΠΈΡΠΌ Π½Π°Π΄ ΠΏΠΎΠ»ΠΈΠ½ΠΎΠΌΠ°ΠΌΠΈ. ΠΡΠΈΡΠ΅ΠΌ ΠΎΠΏΠ΅ΡΠ°ΡΠΈΡ ΡΠ»ΠΎΠΆΠ΅Π½ΠΈΡ ΠΏΡΠΎΠΈΠ·Π²ΠΎΠ΄ΠΈΡΡΡ ΠΏΠΎ ΠΌΠΎΠ΄ΡΠ»Ρ 2. ΠΠ½ΠΎΠΆΠ΅ΡΡΠ²ΠΎ ΡΠ°ΠΊΠΈΡ
ΠΏΠΎΠ»ΠΈΠ½ΠΎΠΌΠΎΠ² ΠΈ Π΄Π΅ΠΉΡΡΠ²ΠΈΠΉ Π½Π°Π΄ Π½ΠΈΠΌΠΈ ΠΎΠ±ΡΠ°Π·ΡΡΡ ΡΠ°ΠΊ Π½Π°Π·ΡΠ²Π°Π΅ΠΌΠΎΠ΅ ΠΏΠΎΠ»Π΅ ΠΠ°Π»ΡΠ° ΠΏΠΎΡΡΠ΄ΠΊΠ° 2 (ΠΎΠ±ΠΎΠ·Π½Π°ΡΠ°Π΅ΡΡΡ GF ( 2)).
Π¦ΠΈΠΊΠ»ΠΈΡΠ΅ΡΠΊΠΈΠΉ ΡΠ΄Π²ΠΈΠ³ ΠΊΠΎΡΡΡΠΈΡΠΈΠ΅Π½ΡΠΎΠ² ΠΏΠΎΠ»ΠΈΠ½ΠΎΠΌΠ° ΡΡΠ΅ΠΏΠ΅Π½ΠΈ ΠΏ — 1 ΠΌΠΎΠΆΠ½ΠΎ Π²ΡΠΏΠΎΠ»Π½ΠΈΡΡ, ΡΠΌΠ½ΠΎΠΆΠ°Ρ ΠΏΠΎΠ»ΠΈΠ½ΠΎΠΌ Π½Π° Ρ
Ρ ΠΎΠ΄Π½ΠΎΠ²ΡΠ΅ΠΌΠ΅Π½Π½ΡΠΌ ΡΠ»ΠΎΠΆΠ΅Π½ΠΈΠ΅ΠΌ Ρ Π΄Π²ΡΡΠ»Π΅Π½ΠΎΠΌ Ρ
ΠΏ + 1. ΠΠ΅ΠΉΡΡΠ²ΠΈΡΠ΅Π»ΡΠ½ΠΎ, ΠΏΡΡΡΡ /(Ρ
) = 1-Ρ
" -1 + Π°"_2Ρ
" -2 +…+Π°2Ρ
2 +Π°1Ρ
+ Π°0. ΠΠΎΡΡΡΠΈΡΠΈΠ΅Π½ΡΡ ΠΏΠΎΠ»ΠΈΠ½ΠΎΠΌΠ° ΠΡ
) Π·Π°ΠΏΠΈΡΠ΅ΠΌ Π² Π²ΠΈΠ΄Π΅ ΠΊΠΎΡΡΠ΅ΠΆΠ° {1,ΡΠ¦-2>—->Π°2>Π°1>Π°ΠΎ}' .
ΠΡΠΏΠΎΠ»Π½ΠΈΠΌ Π½Π°Π΄ ΠΏΠΎΠ»ΠΈΠ½ΠΎΠΌΠΎΠΌ ΠΎΠΏΠ΅ΡΠ°ΡΠΈΡ ΡΠΌΠ½ΠΎΠΆΠ΅Π½ΠΈΡ Π½Π° Ρ
ΠΈ ΡΠ»ΠΎΠΆΠ΅Π½ΠΈΡ Ρ Π΄Π²ΡΡΠ»Π΅Π½ΠΎΠΌ Ρ
" +1. Π’ΠΎΠ³Π΄Π°.
ΠΠΎΡΡΠ΅ΠΆ ΠΊΠΎΡΡΡΠΈΡΠΈΠ΅Π½ΡΠΎΠ² Π½ΠΎΠ²ΠΎΠ³ΠΎ ΠΏΠΎΠ»ΠΈΠ½ΠΎΠΌΠ° Π²ΡΠ³Π»ΡΠ΄ΠΈΡ ΡΠ°ΠΊ: {Π°ΠΏ_2,…, Π°2, Π°1, Π°0, 1}. Π’Π°ΠΊΠΈΠΌ ΠΎΠ±ΡΠ°Π·ΠΎΠΌ, ΠΌΡ ΡΠ±Π΅Π΄ΠΈΠ»ΠΈΡΡ, ΡΡΠΎ ΡΠΊΠ°Π·Π°Π½Π½Π°Ρ ΠΎΠΏΠ΅ΡΠ°ΡΠΈΡ ΡΠΊΠ²ΠΈΠ²Π°Π»Π΅Π½ΡΠ½Π° ΡΠΈΠΊΠ»ΠΈΡΠ΅ΡΠΊΠΎΠΌΡ ΡΠ΄Π²ΠΈΠ³Ρ ΠΊΠΎΡΡΡΠΈΡΠΈΠ΅Π½ΡΠΎΠ².
Π‘Π»Π΅Π΄ΠΎΠ²Π°ΡΠ΅Π»ΡΠ½ΠΎ, Π΅ΡΠ»ΠΈ Π² ΠΊΠ°ΡΠ΅ΡΡΠ²Π΅ ΠΈΡΡ
ΠΎΠ΄Π½ΠΎΠ³ΠΎ Π²Π·ΡΡΡ Π½Π΅ΠΊΠΎΡΠΎΡΡΠΉ ΠΏΠΎΠ»ΠΈΠ½ΠΎΠΌ g (x), ΡΠΎ ΠΏΡΠΎΡΠ΅ΡΡ ΠΏΠΎΠ»ΡΡΠ΅Π½ΠΈΡ ΡΠ°Π·ΡΠ΅ΡΠ΅Π½Π½ΡΡ
ΠΊΠΎΠ΄ΠΎΠ²ΡΡ
ΠΊΠΎΠΌΠ±ΠΈΠ½Π°ΡΠΈΠΉ ΠΌΠΎΠΆΠ½ΠΎ ΠΏΡΠ΅Π΄ΡΡΠ°Π²ΠΈΡΡ Π² ΡΠ»Π΅Π΄ΡΡΡΠ΅ΠΌ Π²ΠΈΠ΄Π΅:
ΠΡΠΈ ΡΠ°ΠΊΠΎΠΌ ΡΠΏΠΎΡΠΎΠ±Π΅ ΠΏΠΎΡΡΡΠΎΠ΅Π½ΠΈΡ ΠΏΠΎΠ»ΠΈΠ½ΠΎΠΌ g (x) Π½Π°Π·ΡΠ²Π°Π΅ΡΡΡ ΠΏΠΎΡΠΎΠΆΠ΄Π°ΡΡΠΈΠΌ (ΠΈΠ½ΠΎΠ³Π΄Π° ΠΈΡΠΏΠΎΠ»ΡΠ·ΡΡΡ ΡΠ΅ΡΠΌΠΈΠ½ ΠΏΡΠΎΠΈΠ·Π²ΠΎΠ΄ΡΡΠΈΠΉ ΠΏΠΎΠ»ΠΈΠ½ΠΎΠΌ). ΠΡΠ»ΠΈ ΠΏΠΎΡΡΠ΅Π±ΠΎΠ²Π°ΡΡ, ΡΡΠΎΠ±Ρ ΠΏΠΎΡΠΎΠΆΠ΄Π°ΡΡΠΈΠΉ ΠΏΠΎΠ»ΠΈΠ½ΠΎΠΌ g (x) Π±ΡΠ» Π΄Π΅Π»ΠΈΡΠ΅Π»Π΅ΠΌ Π΄Π²ΡΡΠ»Π΅Π½Π° (Ρ
" + 1), ΡΠΎ Π²ΡΠ΅ ΡΠ°Π·ΡΠ΅ΡΠ΅Π½Π½ΡΠ΅ ΠΊΠΎΠΌΠ±ΠΈΠ½Π°ΡΠΈΠΈ ΠΏΡΠΈΠΎΠ±ΡΠ΅ΡΠ°ΡΡ ΡΠ²ΠΎΠΉΡΡΠ²ΠΎ Π΄Π΅Π»ΠΈΠΌΠΎΡΡΠΈ Hag (x). ΠΠ· ΡΡΠΎΠ³ΠΎ ΡΠ»Π΅Π΄ΡΠ΅Ρ, ΡΡΠΎ ΠΌΠΎΠΆΠ½ΠΎ Π»Π΅Π³ΠΊΠΎ ΠΏΡΠΎΠ²Π΅ΡΠΈΡΡ, ΡΠ²Π»ΡΠ΅ΡΡΡ Π»ΠΈ ΠΊΠΎΠΌΠ±ΠΈΠ½Π°ΡΠΈΡ ΡΠ°Π·ΡΠ΅ΡΠ΅Π½Π½ΠΎΠΉ, Π΄Π»Ρ ΡΡΠΎΠ³ΠΎ Π΄ΠΎΡΡΠ°ΡΠΎΡΠ½ΠΎ ΠΏΡΠΎΠ²Π΅ΡΠΈΡΡ Π΅Π΅ Π΄Π΅Π»ΠΈΠΌΠΎΡΡΡ Π½Π° ΠΏΠΎΠ»ΠΈΠ½ΠΎΠΌ g (x).
ΠΡΠ½ΠΎΠ²Π½ΡΠ΅ ΡΠ²ΠΎΠΉΡΡΠ²Π° ΡΠΈΠΊΠ»ΠΈΡΠ΅ΡΠΊΠΈΡ
ΠΊΠΎΠ΄ΠΎΠ².
- 1. Π ΡΠΈΠΊΠ»ΠΈΡΠ΅ΡΠΊΠΎΠΌ (ΠΏ, /Ρ)-ΠΊΠΎΠ΄Π΅ ΠΊΠ°ΠΆΠ΄ΡΠΉ ΠΊΠΎΠ΄ΠΎΠ²ΡΠΉ ΠΏΠΎΠ»ΠΈΠ½ΠΎΠΌ Π΄ΠΎΠ»ΠΆΠ΅Π½ ΠΈΠΌΠ΅ΡΡ ΡΡΠ΅ΠΏΠ΅Π½Ρ Π½Π΅ Π±ΠΎΠ»Π΅Π΅ ΠΏ — 1.
- 2. ΠΠ»Ρ ΠΊΠ°ΠΆΠ΄ΠΎΠ³ΠΎ ΡΠΈΠΊΠ»ΠΈΡΠ΅ΡΠΊΠΎΠ³ΠΎ ΠΊΠΎΠ΄Π° ΡΡΡΠ΅ΡΡΠ²ΡΠ΅Ρ ΡΠΎΠ±ΡΡΠ²Π΅Π½Π½ΡΠΉ Π΅Π΄ΠΈΠ½ΡΡΠ²Π΅Π½Π½ΡΠΉ ΠΏΠΎΠ»ΠΈΠ½ΠΎΠΌ g (x) ΡΡΠ΅ΠΏΠ΅Π½ΠΈ (ΠΏ — ΠΊ) Π²ΠΈΠ΄Π°
Π½Π°Π·ΡΠ²Π°Π΅ΠΌΡΠΉ ΠΏΠΎΡΠΎΠΆΠ΄Π°ΡΡΠΈΠΌ ΠΏΠΎΠ»ΠΈΠ½ΠΎΠΌΠΎΠΌ ΠΊΠΎΠ΄Π°.
- 3. ΠΠ°ΠΆΠ΄ΡΠΉ ΡΠ°Π·ΡΠ΅ΡΠ΅Π½Π½ΡΠΉ ΠΊΠΎΠ΄ΠΎΠ²ΡΠΉ ΠΏΠΎΠ»ΠΈΠ½ΠΎΠΌ Ρ (Ρ
) ΡΠ²Π»ΡΠ΅ΡΡΡ ΠΊΡΠ°ΡΠ½ΡΠΌ g (x), Ρ. Π΅. ΠΈ (Ρ
) = q (x) β’ g (x).
- 4. ΠΠΎΡΠΎΠΆΠ΄Π°ΡΡΠΈΠΉ ΠΏΠΎΠ»ΠΈΠ½ΠΎΠΌ g (x) ΡΠ²Π»ΡΠ΅ΡΡΡ Π΄Π΅Π»ΠΈΡΠ΅Π»Π΅ΠΌ Π΄Π²ΡΡΠ»Π΅Π½Π° (Ρ
,! + 1).