Поклингтонның алгоритмі шешуге арналған әдіс үйлесімділік форманың
![{ displaystyle x ^ {2} equiv a { pmod {p}},}](https://wikimedia.org/api/rest_v1/media/math/render/svg/9010d7b9e12f7d5f41a6e03daa23dd3ac547fd6f)
қайда х және а бүтін сандар және а Бұл квадраттық қалдық.
Алгоритм - мұндай үйлесімділікті шешудің алғашқы тиімді әдістерінің бірі. Ол сипатталған Х.С. Поклингтон 1917 ж.[1]
Алгоритм
(Ескерту: барлығы
деген мағынада қабылданады
, егер басқаша көрсетілмесе.)
Кірістер:
- б, тақ қарапайым
- а, квадраттық қалдық болатын бүтін сан
.
Шығарулар:
- х, қанағаттандыратын бүтін сан
. Егер болса х шешім болып табылады, -х шешім де, содан бері де бар б тақ,
. Сондықтан әрқашан бір шешім табылған кезде екінші шешім болады.
Шешім әдісі
Поклингтон 3 түрлі жағдайды бөледі б:
Бірінші жағдай, егер
, бірге
, шешім
.
Екінші жағдай, егер
, бірге
және
, шешім
.
, 2 - қалдық емес (квадрат)
. Бұл дегеніміз
сондықтан
шешімі болып табылады
. Демек
немесе, егер ж тақ,
.
Үшінші жағдай, егер
, қой
, сондықтан шешілетін теңдеу болады
. Енді сынақ және қате арқылы табыңыз
және
сондай-ақ
квадраттық қалдық емес. Сонымен қатар, рұқсат етіңіз
.
Қазір келесі теңдіктер сақталады:
.
Мұны б формада болады
(егер бұл дұрыс болса б формада болады
), Д. квадраттық қалдық болып табылады және
. Енді теңдеулер
![t_1 equiv t_ {p-1} t_1 + D u_ {p-1} u_1 quad mbox {and} quad u_1 equiv t_ {p-1} u_1 + t_1 u_ {p-1}](https://wikimedia.org/api/rest_v1/media/math/render/svg/4b99472bbd10f1cad7f58e686eba1cc8755977d1)
шешім беріңіз
.
Келіңіздер
. Содан кейін
. Бұл дегеніміз де
немесе
бөлінеді б. Егер ол болса
, қой
және сол сияқты жалғастырыңыз
. Әрқайсысы емес
бөлінеді б, үшін
емес. Іс
бірге м тақ мүмкін емес, өйткені
ұстап тұрса, бұл дегеніміз
квадраттық қалдыққа сәйкес келеді, бұл қайшылық. Сонымен, бұл цикл қашан тоқтайды
нақты үшін л. Бұл береді
және, өйткені
квадраттық қалдық, л біркелкі болуы керек. Қойыңыз
. Содан кейін
. Сондықтан
сызықтық сәйкестікті шешу арқылы алынады
.
Мысалдар
Төменде Поклингтон формулаларын бөлген 3 түрлі жағдайларға сәйкес 4 мысал келтірілген б. Барлық
бірге алынады модуль мысалда.
Мысал 0
![{ displaystyle x ^ {2} equiv 43 { pmod {47}}.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/8969dcb441670b771f8481742727ff181dab3158)
Алгоритм бойынша бұл бірінші жағдай,
, бірақ содан кейін
43 емес, сондықтан біз алгоритмді мүлдем қолданбауымыз керек. Алгоритмнің қолданылмауының себебі, a = 43 p = 47 үшін квадраттық қалдық емес.
1-мысал
Сәйкестікті шешіңіз
![x ^ 2 equiv 18 pmod {23}.](https://wikimedia.org/api/rest_v1/media/math/render/svg/fd7d189237e6e96cdb3bae26028e2f9b2d3e0cb0)
Модуль - 23. Бұл
, сондықтан
. Шешім болуы керек
, бұл шынымен де дұрыс:
.
2-мысал
Сәйкестікті шешіңіз
![x ^ 2 equiv 10 pmod {13}.](https://wikimedia.org/api/rest_v1/media/math/render/svg/97ac38487ba2c5567de9c643a1cac1d991ed528a)
Модуль - 13. Бұл
, сондықтан
. Қазір тексерілуде
. Мәселен, шешім
. Бұл шынымен де шындық:
.
3-мысал
Сәйкестікті шешіңіз
. Ол үшін жазыңыз
. Алдымен а
және
осындай
квадраттық емес қалдық болып табылады. Мысалға алайық
. Енді табыңыз
,
есептеу арқылы
![{ displaystyle t_ {2} = t_ {1} t_ {1} + 13u_ {1} u_ {1} = 9-13 = -4 equiv 13 { pmod {17}},}](https://wikimedia.org/api/rest_v1/media/math/render/svg/4d2b3c0f13c3d9a871ecdb7a508273de031fc4b7)
![{ displaystyle u_ {2} = t_ {1} u_ {1} + t_ {1} u_ {1} = 3 + 3 equiv 6 { pmod {17}}.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/4220f1dcff25bb0533845721eda7c68464a34045)
Және сол сияқты
осындай ![{ displaystyle t_ {8} = - 68 equiv 0 { pmod {17}}, u_ {8} = 42 equiv 8 { pmod {17}}.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/d7bec922012d2296311b889360da389bb4534486)
Бастап
, теңдеу
бұл теңдеуді шешуге әкеледі
. Мұның шешімі бар
. Әрине,
.
Әдебиеттер тізімі
- Леонард Евгений Диксон, «Сандар теориясының тарихы» 1 том 222 б., Челси баспасы 1952 ж.
- ^ Х.С. Поклингтон, Кембридж философиялық қоғамының еңбектері, 19 том, 57–58 беттер