Циполлас алгоритмі - Cipollas algorithm - Wikipedia

Жылы есептеу сандарының теориясы, Циполланың алгоритмі шешуге арналған әдіс үйлесімділік форманың

қайда , сондықтан n квадраты х, және қайда болып табылады тақ қарапайым. Мұнда ақырлықты білдіреді өріс бірге элементтер; . The алгоритм есімімен аталады Мишель Циполла, an Итальян математик оны 1907 жылы кім ашқан.

Алғашқы модульдерден басқа, Сиполланың алгоритмі қарапайым дәрежедегі квадрат түбірлерді қабылдай алады.[1]

Алгоритм

Кірістер:

  • тақ тақ,
  • , бұл квадрат.

Шығарулар:

  • , қанағаттанарлық

1-қадам - ​​табу осындай шаршы емес. Мұндай ан табу үшін белгілі алгоритм жоқ , қоспағанда сынақ және қателік әдіс. Жай таңдау керек және есептеу арқылы Legendre символы не екенін көруге болады шартты қанағаттандырады. Кездейсоқ мүмкіндік қанағаттандырады . Бірге бұл жеткілікті үлкен .[2] Сондықтан лайықты таппас бұрын күтілетін сынақтар саны шамамен 2.

2-қадам - ​​есептеу х есептеу арқылы өріс ішінде . Бұл х қанағаттандыратын болады

Егер , содан кейін ұстайды. Содан бері б тақ, . Сондықтан шешім болған сайын х табылды, әрқашан екінші шешім бар, -x.

Мысал

(Ескерту: екінші қадамға дейінгі барлық элементтер. Элементі ретінде қарастырылады және екінші қадамдағы барлық элементтер -дің элементтері ретінде қарастырылады ).

Барлығын табу х осындай

Алгоритмді қолданбас бұрын оны тексеру керек бұл шынымен де квадрат . Демек, Легендра символы 1-ге тең болуы керек. Мұны пайдаланып есептеуге болады Эйлер критерийі; Бұл 10-дың квадрат екендігін растайды, сондықтан алгоритмді қолдануға болады.

  • 1-қадам: Ан а осындай шаршы емес. Жоғарыда айтылғандай, бұл сынақ пен қателік арқылы жасалуы керек. Таңдау . Содан кейін 7. Легендра белгісі болады -1 болуы керек. Тағы да мұны Эйлер критерийі арқылы есептеуге болады. Сонымен үшін қолайлы таңдау болып табылады а.
  • 2-қадам: Есептеу

Сонымен шешім болып табылады, сонымен қатар Әрине, және

Дәлел

Дәлелдің бірінші бөлігі - оны тексеру бұл шынымен де өріс. Белгілеудің қарапайымдылығы үшін, ретінде анықталады . Әрине, квадраттық қалдық емес, сондықтан жоқ шаршы түбір жылы . Бұл шамамен күрделі санға ұқсас деп санауға болады мен Өріс арифметикасы айқын. Қосу ретінде анықталады

.

Көбейту сонымен қатар әдеттегідей анықталады. Мұны ескере отырып , ол болады

.

Енді өрістің қасиеттерін тексеру керек, қосу және көбейту кезінде жабу қасиеттері, ассоциативтілік, коммутативтілік және тарату оңай көрінеді. Себебі, бұл жағдайда өріс өрісіне ұқсайды күрделі сандар (бірге аналогы бола отырып мен).
Қоспа жеке басын куәландыратын болып табылады , немесе ресми түрде : Рұқсат етіңіз , содан кейін

.

Мультипликативті сәйкестік , немесе ресми түрде :

.

Жалғыз нәрсе қалды өріс болу - бұл аддитивті және мультипликативті болу инверстер. Қосымшасының кері екендігі оңай көрінеді болып табылады , бұл элемент , өйткені . Шын мәнінде, бұл - қосымшасының кері элементтері х және ж. Әр нөлге тең емес элементті көрсеткені үшін мультипликативті кері, жазыңыз және . Басқа сөздермен айтқанда,

.

Сонымен екі теңдік және ұстау керек. Бөлшектерді пысықтау өрнектер береді және , атап айтқанда

,
.

Өрнектерінде көрсетілген кері элементтер және бар, өйткені бұл элементтер . Осымен дәлелдеудің бірінші бөлігі аяқталады өріс.

Дәлелдеудің екінші және орта бөлігі әрбір элемент үшін көрсетілген .Анықтама бойынша шаршы емес . Эйлердің критерийі содан кейін айтады

.

Осылайша . Бұл, бірге Ферманың кішкентай теоремасы (мұны айтады барлығына ) және білімдері сипаттамалық б теңдеу ұстайды, кейде деп аталатын қатынастар Бірінші курстың арманы, қажетті нәтижені көрсетеді

.

Дәлелдеудің үшінші және соңғы бөлігі - егер екенін көрсетсе , содан кейін .
Есептеу

.

Бұл есептеудің өткенін ескеріңіз , сондықтан бұл . Бірақ Лагранж теоремасы, нөлге тең емес екенін көрсете отырып көпмүшелік дәрежесі n ең көп дегенде n кез-келген саладағы тамырлар Қжәне бұл туралы білім 2 тамыры бар , бұл түбірлер барлық тамырлар болуы керек . Бұл жай ғана көрсетілді және тамырлары жылы , сондықтан солай болуы керек .[3]

Жылдамдық

Сәйкесін тапқаннан кейін а, алгоритмге қажетті амалдар саны көбейту, сомалар, қайда м саны цифрлар ішінде екілік ұсыну туралы б және к бұл осы өкілдіктегі саны. Табу а сынақ пен қателік бойынша Легендра таңбасын есептеудің болжамды саны - 2. Бірақ бірінші сынақтан сәттілікке жетуге болады, ал екіншісіне 2-ден артық әрекет қажет болуы мүмкін. Өрісте , келесі екі теңдік орындалады

қайда алдын-ала белгілі. Бұл есептеу үшін 4 көбейту және 4 қосынды қажет.

қайда және . Бұл операцияға 6 көбейту және 4 қосынды қажет.

Мұны қарастырсақ (жағдайда , тікелей есептеу әлдеқайда жылдам) .ның екілік өрнегі бар оның цифрлары к бір. Сонымен есептеу үшін а қуаты , бірінші формуланы қолдану керек рет және екінші рет.

Ол үшін Cipolla алгоритмі қарағанда жақсы Tonelli – Shanks алгоритмі егер және егер болса , бірге бөлетін максималды қуаттың 2 болуы .[4]

Негізгі қуат модульдері

Диксонның «Сандар тарихы» бойынша Циполланың келесі формуласы квадрат түбірлердің жай дәреже күштерінің модулін табады:[5][6]

қайда және
қайда , осы мақаланың мысалындағыдай

Уики мақаласынан мысал келтіре отырып, жоғарыдағы формула шын мәнінде квадрат түбірлердің негізгі күштерін алатындығын көреміз.


Қалай

Енді шешіңіз арқылы:

Енді және (Қараңыз Мұнда жоғарыдағы есептеуді көрсететін математикалық код үшін бұл жерде күрделі модульдік арифметикаға жақын нәрсе болатынын еске түсіру)

Тап мұндай:

және

және соңғы теңдеу:

бұл жауап.

Пайдаланылған әдебиеттер

  1. ^ «Сандар теориясының тарихы» 1 том, Леонард Евгений Диксон, 218-бетИнтернетте оқыңыз
  2. ^ R. Crandall, C. Pomerance қарапайым сандары: Есептеу перспективасы Springer-Verlag, (2001) б. 157
  3. ^ М.Бейкер Циполланың квадрат түбірлерін табудың алгоритмі mod p
  4. ^ Гонсало Торнариа Шаршы түбірлер модулі p
  5. ^ «Сандар теориясының тарихы» 1 том, Леонард Евгений Диксон, 218, Челси баспасы 1952Интернетте оқыңыз
  6. ^ Мишель Сиполла, Rendiconto dell 'Accademia delle Scienze Fisiche e Matematiche. Наполи, (3), 10,1904, 144-150

Дереккөздер

  • Э.Бах, Дж. Шаллит Алгоритмдік сандар теориясы: тиімді алгоритмдер MIT Press, (1996)
  • Леонард Евгений Диксон Сандар теориясының тарихы 1 том p218 [1]
  1. ^ «Сандар теориясының тарихы» 1 том, Леонард Евгений Диксон, p218, Челси баспасы 1952url =https://archive.org/details/historyoftheoryo01dick