ΠΠ΅ΠΏΡΠΈΠ²ΠΎΠ΄ΠΈΠΌΠΎΡΡΡ Π½Π΅ΠΊΠΎΡΠΎΡΡΡ ΡΡΠΈΠ½ΠΎΠΌΠΎΠ²
Π’Π΅ΠΎΡΠ΅ΠΌΠ° 4. 5. Π°) ΠΠ½ΠΎΠ³ΠΎΡΠ»Π΅Π½ ΡΠ°ΡΠΊΠ»Π°Π΄ΡΠ²Π°Π΅ΡΡΡ Π² ΠΏΡΠΎΠΈΠ·Π²Π΅Π΄Π΅Π½ΠΈΠ΅ Π½Π΅ΠΏΡΠΈΠ²ΠΎΠ΄ΠΈΠΌΡΡ ΠΊΠ²Π°Π΄ΡΠ°ΡΠ½ΠΎΠ³ΠΎ ΠΈ ΠΊΡΠ±ΠΈΡΠ΅ΡΠΊΠΎΠ³ΠΎ ΠΌΠ½ΠΎΠ³ΠΎΡΠ»Π΅Π½ΠΎΠ² ΡΠΎΠ³Π΄Π° ΠΈ ΡΠΎΠ»ΡΠΊΠΎ ΡΠΎΠ³Π΄Π°, ΠΊΠΎΠ³Π΄Π° ΠΈΠ»ΠΈ. ΠΠΎΡΠΏΠΎΠ»ΡΠ·ΠΎΠ²Π°Π²ΡΠΈΡΡ ΡΠ΅Π·ΡΠ»ΡΡΠ°ΡΠ°ΠΌΠΈ, ΠΏΠΎΠ»ΡΡΠ΅Π½Π½ΡΠΌΠΈ Π² ΠΏΡΠ΅Π΄ΡΠ΄ΡΡΠ΅ΠΌ ΠΏΠ°ΡΠ°Π³ΡΠ°ΡΠ΅, Π½Π΅ΡΠ»ΠΎΠΆΠ½ΠΎ Π²ΡΡΡΠ½ΠΈΡΡ, ΠΊΠ°ΠΊΠΈΠ΅ ΠΈΠ· ΡΡΠΈΠ½ΠΎΠΌΠΎΠ² Π²ΠΈΠ΄Π° Π½Π΅ΠΏΡΠΈΠ²ΠΎΠ΄ΠΈΠΌΡ. ΠΠ½ΠΎΠ³ΠΎΡΠ»Π΅Π½ ΡΠ°ΡΠΊΠ»Π°Π΄ΡΠ²Π°Π΅ΡΡΡ Π² ΠΏΡΠΎΠΈΠ·Π²Π΅Π΄Π΅Π½ΠΈΠ΅ Π½Π΅ΠΏΡΠΈΠ²ΠΎΠ΄ΠΈΠΌΡΡ ΠΊΠ²Π°Π΄ΡΠ°ΡΠ½ΠΎΠ³ΠΎ ΠΈ ΠΊΡΠ±ΠΈΡΠ΅ΡΠΊΠΎΠ³ΠΎ ΠΌΠ½ΠΎΠ³ΠΎΡΠ»Π΅Π½ΠΎΠ² ΡΠΎΠ³Π΄Π° ΠΈ ΡΠΎΠ»ΡΠΊΠΎ ΡΠΎΠ³Π΄Π°, ΠΊΠΎΠ³Π΄Π°. Π’Π΅ΠΎΡΠ΅ΠΌΠ° 4.3… Π§ΠΈΡΠ°ΡΡ Π΅ΡΡ >
ΠΠ΅ΠΏΡΠΈΠ²ΠΎΠ΄ΠΈΠΌΠΎΡΡΡ Π½Π΅ΠΊΠΎΡΠΎΡΡΡ ΡΡΠΈΠ½ΠΎΠΌΠΎΠ² (ΡΠ΅ΡΠ΅ΡΠ°Ρ, ΠΊΡΡΡΠΎΠ²Π°Ρ, Π΄ΠΈΠΏΠ»ΠΎΠΌ, ΠΊΠΎΠ½ΡΡΠΎΠ»ΡΠ½Π°Ρ)
ΠΠΎΡΠΏΠΎΠ»ΡΠ·ΠΎΠ²Π°Π²ΡΠΈΡΡ ΡΠ΅Π·ΡΠ»ΡΡΠ°ΡΠ°ΠΌΠΈ, ΠΏΠΎΠ»ΡΡΠ΅Π½Π½ΡΠΌΠΈ Π² ΠΏΡΠ΅Π΄ΡΠ΄ΡΡΠ΅ΠΌ ΠΏΠ°ΡΠ°Π³ΡΠ°ΡΠ΅, Π½Π΅ΡΠ»ΠΎΠΆΠ½ΠΎ Π²ΡΡΡΠ½ΠΈΡΡ, ΠΊΠ°ΠΊΠΈΠ΅ ΠΈΠ· ΡΡΠΈΠ½ΠΎΠΌΠΎΠ² Π²ΠΈΠ΄Π° Π½Π΅ΠΏΡΠΈΠ²ΠΎΠ΄ΠΈΠΌΡ.
Π’Π΅ΠΎΡΠ΅ΠΌΠ° 4.3. ΠΡΡΡΡ ΠΈ. Π’ΠΎΠ³Π΄Π° ΠΌΠ½ΠΎΠ³ΡΠ»Π΅Π½, Π³Π΄Π΅ ΠΈ, Π½Π΅ΠΏΡΠΈΠ²ΠΎΠ΄ΠΈΠΌ, Π·Π° ΠΈΡΠΊΠ»ΡΡΠ΅Π½ΠΈΠ΅ΠΌ ΡΡΠ΅Ρ ΡΠ»ΡΡΠ°Π΅Π², Π² ΠΊΠΎΡΠΎΡΡΡ (mod 3):
- Π°) n1 ΠΈ m1 Π½Π΅ΡΠ΅ΡΠ½Ρ ΠΈ ;
- Π±) ΠΏ1 ΡΠ΅ΡΠ½ΠΎ ΠΈ ;
Π²)m1 ΡΠ΅ΡΠ½ΠΎ ΠΈ .
ΠΠΎ Π²ΡΠ΅Ρ ΡΡΠΈΡ ΡΠ»ΡΡΠ°ΡΡ g (x) ΡΠ²Π»ΡΠ΅ΡΡΡ ΠΏΡΠΎΠΈΠ·Π²Π΅Π΄Π΅Π½ΠΈΠ΅ΠΌ Π½Π΅ΠΊΠΎΡΠΎΡΠΎΠ³ΠΎ Π½Π΅ΠΏΡΠΈΠ²ΠΎΠ΄ΠΈΠΌΠΎΠ³ΠΎ ΠΌΠ½ΠΎΠ³ΠΎΡΠ»Π΅Π½Π° Π½Π° .
ΠΠΎΠΊΠ°Π·Π°ΡΠ΅Π»ΡΡΡΠ²ΠΎ. Π‘Π»ΡΡΠ°ΠΉ, ΠΊΠΎΠ³Π΄Π° n= 2m ΠΈ, ΠΎΡΠ΅Π²ΠΈΠ΄Π΅Π½. ΠΠΎΡΡΠΎΠΌΡ Π±ΡΠ΄Π΅ΠΌ ΡΡΠΈΡΠ°ΡΡ, ΡΡΠΎ-Π»ΠΈΠ±ΠΎ n= 2m ΠΈ, Π»ΠΈΠ±ΠΎ ΠΏ > 2m. Π ΡΠ°ΠΊΠΎΠΌ ΡΠ»ΡΡΠ°Π΅ ΠΊ ΠΌΠ½ΠΎΠ³ΠΎΡΠ»Π΅Π½Ρ ΠΌΠΎΠΆΠ½ΠΎ ΠΏΡΠΈΠΌΠ΅Π½ΠΈΡΡ ΡΠ΅ΠΎΡΠ΅ΠΌΡ 8.1 ΠΈ 8.2. ΠΏΠΎΡΠΊΠΎΠ»ΡΠΊΡ 2n> ΠΏ + m > m ΠΈ Π΅ΡΠ»ΠΈ, Ρ. Π΅. n = 2m, ΡΠΎ. Π ΠΎΠ±ΠΎΠ·Π½Π°ΡΠ΅Π½ΠΈΡΡ ΡΠ΅ΠΎΡΠ΅ΠΌΡ 8.2 ΠΈΠΌΠ΅Π΅ΠΌ:
ΠΈ .Π’Π°ΠΊΠΈΠΌ ΠΎΠ±ΡΠ°Π·ΠΎΠΌ, d2 = 1, Π΅ΡΠ»ΠΈ (mod 3) ΠΈ d2 = 3, Π΅ΡΠ»ΠΈ (mod 3).
Π‘ΠΎΠ³Π»Π°ΡΠ½ΠΎ ΡΠ΅ΠΎΡΠ΅ΠΌΠ΅ 8.2 ΠΊΠΎΡΠ½ΠΈ ΠΈΠ· Π΅Π΄ΠΈΠ½ΠΈΡΡ, ΡΠ²Π»ΡΡΡΠΈΠ΅ΡΡ ΠΎΠ΄Π½ΠΎΠ²ΡΠ΅ΠΌΠ΅Π½Π½ΠΎ ΠΊΠΎΡΠ½ΡΠΌΠΈ ΠΌΠ½ΠΎΠ³ΠΎΡΠ»Π΅Π½Π° g, ΡΠ΄ΠΎΠ²Π»Π΅ΡΠ²ΠΎΡΡΡΡ ΠΎΠ΄Π½ΠΎΠΌΡ ΠΈΠ· ΡΡΠ°Π²Π½Π΅Π½ΠΈΠΉ, ,. ΠΠ΅ΡΠ²ΠΎΠ΅ ΡΡΠ°Π²Π½Π΅Π½ΠΈΠ΅ ΠΈΠΌΠ΅Π΅Ρ Π²ΠΈΠ΄. Π° ΡΡΠ΅ΡΡΠ΅. ΠΡΠ»ΠΈ, ΡΠΎ, Π° Π΅ΡΠ»ΠΈ, ΡΠΎ. ΠΡΡΠ°Π΅ΡΡΡ ΡΠ°ΡΡΠΌΠΎΡΡΠ΅ΡΡ ΡΠ»ΡΡΠ°ΠΉ, ΠΊΠΎΠ³Π΄Π° d2 = 3. Π Π»Π΅ΠΌΠΌΠ΅ 8.2 ΡΠ»ΡΡΠ°ΠΉ (I) ΠΏΡΠΈΠ²ΠΎΠ΄ΠΈΡ ΠΊ ΡΠΎΠΎΡΠ½ΠΎΡΠ΅Π½ΠΈΡΠΌ ΠΈ, Π° ΡΠ»ΡΡΠ°ΠΉ (III) ΠΏΡΠΈΠ²ΠΎΠ΄ΠΈΡ ΠΊ ΡΠΎΠΎΡΠ½ΠΎΡΠ΅Π½ΠΈΡΠΌ ΠΈ. Π ΠΎΠ±ΠΎΠΈΡ ΡΠ»ΡΡΠ°ΡΡ ΠΏΠΎΠ»ΡΡΠ°Π΅ΠΌ, ΠΏΠΎΡΡΠΎΠΌΡ. Π‘Π»ΡΡΠ°ΠΉ (II) ΠΏΡΠΈΠ²ΠΎΠ΄ΠΈΡ ΠΊ ΡΠΎΠΎΡΠ½ΠΎΡΠ΅Π½ΠΈΡΠΌ, , Ρ. Π΅.. Π’Π°ΠΊΠΈΠΌ ΠΎΠ±ΡΠ°Π·ΠΎΠΌ, ΠΈ, Π³Π΄Π΅ (n1, m1) = 1 ΠΈ (mod 3). ΠΠ· ΡΡΠ»ΠΎΠ²ΠΈΡ (n1, m1) = 1 ΡΠ»Π΅Π΄ΡΠ΅Ρ, ΡΡΠΎ Π΄Π»Ρ Π½Π΅ΠΊΠΎΡΠΎΡΡΡ ΡΠ΅Π»ΡΡ ΡΠΈΡΠ΅Π» ΠΈ ΠΈ v. ΠΠΎΡΡΠΎΠΌΡ .
ΠΡΠ»ΠΈ ΡΠΈΡΠ»Π° n1 ΠΈ m1 Π½Π΅ΡΠ΅ΡΠ½Ρ, ΡΠΎ, ΠΏΠΎΡΡΠΎΠΌΡ .
ΠΡΠ»ΠΈ ΡΠΈΡΠ»ΠΎ n1 ΡΠ΅ΡΠ½ΠΎ, ΡΠΎ .
ΠΡΠ»ΠΈ ΡΠΈΡΠ»ΠΎ m1 ΡΠ΅ΡΠ½ΠΎ, ΡΠΎ .
Π‘ΠΎΠ³Π»Π°ΡΠ½ΠΎ ΠΏΡΠΈΠ·Π½Π°ΠΊΡ ΠΠ΅ΡΡΠΎΠ½Π° (ΡΠ΅ΠΎΡΠ΅ΠΌΠ° 7.2 Π½Π° Ρ. 68) ΡΡΠΈΠ½ΠΎΠΌ, Π³Π΄Π΅ ΡΠ΅Π»ΠΎΠ΅ ΡΠΈΡΠ»ΠΎ, Π½Π΅ΠΏΡΠΈΠ²ΠΎΠ΄ΠΈΠΌ. ΠΡΠΈ Π° = 2 ΡΡΠΎΡ ΡΡΠΈΠ½ΠΎΠΌ Π½Π΅ΠΏΡΠΈΠ²ΠΎΠ΄ΠΈΠΌ, Π΅ΡΠ»ΠΈ Ρ Π½Π΅Π³ΠΎ ΠΏΠΎΡ ΠΊΠΎΡΠ½Π΅ΠΉ, ΡΠ°Π²Π½ΡΡ . ΠΡΠ΅ ΡΡΠΈ ΡΡΠ²Π΅ΡΠΆΠ΄Π΅Π½ΠΈΡ Π²Π΅ΡΠ½Ρ ΠΈ Π΄Π»Ρ ΡΡΠΈΠ½ΠΎΠΌΠ° .
ΠΠ΅ΠΏΡΠΈΠ²ΠΎΠ΄ΠΈΠΌΠΎΡΡΡ ΡΡΠΈΠ½ΠΎΠΌΠΎΠ² ΠΈΡΡΠ»Π΅Π΄ΠΎΠ²Π°Π½Π° Π² [Sc1].
Π’Π΅ΠΎΡΠ΅ΠΌΠ° 4.4. ΠΡΡΡΡ ΠΌΠ½ΠΎΠ³ΠΎΡΠ»Π΅Π½, Π³Π΄Π΅ n > Ρ ΠΈ ΡΠΏΡΠΎΡΡΠΎΠ΅ ΡΠΈΡΠ»ΠΎ, ΠΏΡΠΈΠ²ΠΎΠ΄ΠΈΠΌ. Π’ΠΎΠ³Π΄Π° .
Π’Π΅ΠΎΡΠ΅ΠΌΠ° 4. 5. Π°) ΠΠ½ΠΎΠ³ΠΎΡΠ»Π΅Π½ ΡΠ°ΡΠΊΠ»Π°Π΄ΡΠ²Π°Π΅ΡΡΡ Π² ΠΏΡΠΎΠΈΠ·Π²Π΅Π΄Π΅Π½ΠΈΠ΅ Π½Π΅ΠΏΡΠΈΠ²ΠΎΠ΄ΠΈΠΌΡΡ ΠΊΠ²Π°Π΄ΡΠ°ΡΠ½ΠΎΠ³ΠΎ ΠΈ ΠΊΡΠ±ΠΈΡΠ΅ΡΠΊΠΎΠ³ΠΎ ΠΌΠ½ΠΎΠ³ΠΎΡΠ»Π΅Π½ΠΎΠ² ΡΠΎΠ³Π΄Π° ΠΈ ΡΠΎΠ»ΡΠΊΠΎ ΡΠΎΠ³Π΄Π°, ΠΊΠΎΠ³Π΄Π° ΠΈΠ»ΠΈ .
Π±) ΠΠ½ΠΎΠ³ΠΎΡΠ»Π΅Π½ ΡΠ°ΡΠΊΠ»Π°Π΄ΡΠ²Π°Π΅ΡΡΡ Π² ΠΏΡΠΎΠΈΠ·Π²Π΅Π΄Π΅Π½ΠΈΠ΅ Π½Π΅ΠΏΡΠΈΠ²ΠΎΠ΄ΠΈΠΌΡΡ ΠΊΠ²Π°Π΄ΡΠ°ΡΠ½ΠΎΠ³ΠΎ ΠΈ ΠΊΡΠ±ΠΈΡΠ΅ΡΠΊΠΎΠ³ΠΎ ΠΌΠ½ΠΎΠ³ΠΎΡΠ»Π΅Π½ΠΎΠ² ΡΠΎΠ³Π΄Π° ΠΈ ΡΠΎΠ»ΡΠΊΠΎ ΡΠΎΠ³Π΄Π°, ΠΊΠΎΠ³Π΄Π° .