Евклид алгоритмы

Евкли́д алгори́тмы — ике бөтөн һандың иң ҙур уртаҡ бүлеүсеһен (йәки ике киҫектең уртаҡ үлсәмен) табыу өсөн эффектив алгоритм. Алгоритм уны беренсе башлап «Башланғыстар»ҙың VII һәм X китаптарында һүрәтләгән грек математигы Евклид хөрмәтенә шулай аталған. Иң ябай осраҡта Евклид алгоритмы ыңғай бөтөн һандар парына ҡулланыла һәм, бәләкәй һандан һәм ҙур һан менән бәләкәй һандың айырмаһынан торған яңы пар барлыҡҡа килтерә. Ошо процесс һандар тигеҙ булғанға тиклем дауам итә. Табылған һан бирелгән парҙың иң ҙур уртаҡ бүлеүсеһе була ла инде.

Алгоритмдың беренсе тасуирламаһы Евклидтың «Башланғыстар» китабында (б.э.т. яҡынса300 йыл) бирелгән, ул бөгөнгө көндә лә ҡулланылған иң боронғо һанлы алгоритм. Алгоритмдың оригиналы тик натураль һандар һәм геометрик оҙонлоҡтар (ысын һандар) өсөн тәҡдим ителгән була. Ләкин XIX быуатта ул Гаусстың бөтөн һандары кеүек башҡа типтағы һандарға һәм бер үҙгәреүсәнле полиномдарға дөйөмләштерелә. Был хәҙергә дөйөм алгебрала евклид балдағы тигән төшөнсә барлыҡҡа килтерҙе. Һуңғараҡ Евклид алгоритмы төйөндәр һәм күп үлсәмле полиномдар кеүек башҡа математик структуралар өсөн дә дөйөмләштерелә. Был алгоритм өсөн күп теоретик һәм практик ҡулланылыш бар. Айырып әйткәндә, ул электрон коммерцияла киң таралған асыҡ асҡыслы RSA криптографик алгоритм өсөн нигеҙ булып тора. Алгоритмдар шулай уҡ һыҙыҡлы диофант тигеҙләмәләрен сығарғанда, өҙлөкһөҙ кәсерҙәр төҙөгәндә, Штурм методында ҡулланылалар. Евклид алгоритмы дүрт квадраттың суммаһы тураһында Лагранж теоремаһы, арифметиканың төп теоремаһы һ.б. кеүек хәҙергә һандар теорияһы теоремаларын иҫбат итеү өсөн төп инструмент булып тора.

Тарих

Боронғо грек математиктары был алгоритмды ἀνθυφαίρεσις йәки ἀνταναίρεσις — «үҙ-ара алыу» тип атайҙар. Был алгоритм Евклид тарафынан асылмаған, сөнки ул Аристотель Топигында телгә алына. Евклид «Башланғыстарында» ул ике тапҡыр — VII китапта ике натураль һандың иң ҙур уртаҡ бүлеүсеһен[1] табыу өсөн һәм X китапта ике бер төрлө дәүмәлдең иң ҙур уртаҡ үлсәмен табыу өсөн телгә алына. Ике осраҡта ла, ике киҫектең «дөйөм үлсәмен» табыу өсөн, алгоритмдың геометрик тасуирламаһы бирелә.

Математика тарихсылары фаразлауынса, тап Евклид алгоритмы (эҙмә-эҙ үҙ-ара алыу процедураһы) ярҙамында сағыштырғыһыҙ булған дәүмәлдәрҙең (квадраттың яғы һәм диагонале, төҙөк бишмөйөштөң яҡтары һәм диагоналдәре) булыуы асыҡланған. Әйтергә кәрәк, был фараздың етерлек документаль раҫламаһы юҡ. Ике натураль һандың иң ҙур уртаҡ бүлеүсеһен эҙләү алгоритмы боронғо ҡытайҙың туғыҙ китаптан торған Математика трактатының I китабында ла тасуирланған.

Тасуирлама

Бөтөн һандар өсөн Евклид алгоритмы

$a$ и $b$ — бер үк ваҡытта нулгә тигеҙ булмаған бөтөн һандар булһын, ти, һәм

$a>b>r_{1}>r_{2}>r_{3}>r_{4}>\cdots >r_{n}$ һандар эҙмә-эҙлелеге

шулай билдәләнгән, һәр $r_{k}$ — алдағынан алдағы һанды алдағы һанға бүлеүҙән ҡалдыҡ, әһуңғыһынан алдағы һуңғыһына ҡалдыҡһыҙ бүленә, йәғни:

$a=bq_{0}+r_{1},$

$b=r_{1}q_{1}+r_{2},$

$r_{1}=r_{2}q_{2}+r_{3},$

$\cdots$

$r_{k-2}=r_{k-1}q_{k-1}+r_{k},$

$\cdots$

$r_{n-2}=r_{n-1}q_{n-1}+r_{n},$

$r_{n-1}=r_{n}q_{n}.$

Ул саҡта ИҘУБ(a, b), a һәм b-ның иң ҙур уртаҡ бүлеүсеһе, r_n-ға, был эҙмә-эҙлелектең һуңғы нулдән айырмалы быуынына, тигеҙ.

Шундай r₁, r₂, ..., r_n-ҙың булыуы, йәғни теләһә ниндәй бөтөн m һәм бөтөн n ≠ 0 өсөн m-ды n-ға ҡалдыҡлы бүлеү мөмкин икәнлеге, m буйынса индукция ярҙамында иҫбатлана.

Был алгоритмдың урынлы булыуы түбәндәге ике раҫлауҙан килеп сыға:

• a = b⋅q + r булһын, ул саҡта ИҘУБ(a, b) = ИҘУБ(b, r).

Иҫбатлау  

1. k — a һәм b һандарының мотлаҡ иң ҙур түгел, ә теләһә ниндәй уртаҡ бүлеүсеһе булһын,ти. Ул саҡта a = t₁⋅k и b = t₂⋅k, бындаt₁ и t₂ — билдәләмә буйынса бөтөн һандар. Ул саҡта k һаны ла b һәм r һандарының уртаҡ бүлеүсеһе була, Сөнки b k-ға билдәләмә буйынса бүленә, ә r = a - b⋅q = (t₁ - t₂⋅q)⋅k (йәйә эсендәге аңлатма бөтөн һан, ошонан сығып, k r-ны ҡалдыҡһыҙ бүлә).
2. Кире раҫлау ҙа дөрөҫ һәм 2 пунктҡа оҡшаш иҫбатлана: b һәм r-ның теләһә ниндәй бүлеүсеһе шулай уҡ a һәм b-ның бүлеүсеһе була.
3. Ошонан сығып, (a, b) һәм (b, r) һандар парҙарының бөтә уртаҡ бүлеүселәре тап килә.совпадают. Икенсе төрлө әйткәндә, (a, b) һандар парының , (b, r) һандар парының бүлеүсеһе булмаған уртаҡ бүлеүселәре юҡ, һәм киреһенсә.
4. Шул иҫәптән, иң ҙур уртаҡ бүлеүселә шул уҡ ҡала.

Шуны иҫбат итергә һоралғайны ла инде.

• Нулдән айырмалы теләһә ниндәй r өсөн ИҘУБ(r, 0) = r (сөнки 0 нулдән башҡа теләһә ниндәй бөтөн һанға бүленә).

Геометрик Евклид алгоритмы

Оҙонлоҡтары a һәм b булған ике киҫек бирелһен, ти.Ҙур киҫектән бәләкәйен алабыҙ һәм ҙур киҫекте килеп сыҡҡан айырма менән алмаштырабыҙ. Был операцияны, киҫектәр тигеҙ булғанға тиклем, ҡабатлайбыҙ. Әгәр был хәл тыуһа, бирелгән киҫектәр үлсәнмәле, һуңғы табылған киҫек уларҙың иң ҙур уртаҡ үлсәме була. Әгәр уртаҡ үлсәм булмаһа, процесс сикһеҙ дауам итә. Ошондай күренештә алгоритм Евклид тарафынан тасуирланған һәм циркуль һәм линейка ярҙамында башҡарыла.

Миҫал

Евклид алгоритмын һүрәтләү өсөн a = 1071 һәм b = 462 һандарының ИҘУБ табыуҙы ҡарайбыҙ. Тәүҙә 1071-ҙән 462-нең тапҡырлы ҡиммәтен, айырма 462-нән кәм булғанға тиклем, алабыҙ. Беҙ ике тапҡыр 462-не алабыҙ (q₀ = 2), 147 ҡалдығы килеп сыға:

1071 = 2 × 462 + 147.

Бынан һуң 462-нән 147-нең тапҡырлы ҡиммәтен, ҡалдыҡ 147-нән кәмерәк булғансы, алабыҙ. Беҙ 147-не өс тапҡыр (q₁ = 3)) алырға тейешбеҙ, ҡалдыҡ 21 килеп сыға:

462 = 3 × 147 + 21.

Аҙаҡ 147-нән 21-ҙең тапҡырлы ҡиммәтен, ҡалдыҡ 21-ҙән кәмерәк булғанға тиклем, алабыҙ. Беҙ 21-ҙе ете тапҡыр (q₂ = 7 алырға тейешбеҙ, ҡалдыҡ ҡалмай:

147 = 7 × 21 + 0.

Шулай итеп a > b > r₁ > r₂ > r₃ > … > r_n эҙмә-эҙлелеге был конкрет осраҡта ошолай булып күренә:

1071 > 462 > 147 > 21.

Һуңғы ҡалдыҡ нулгә тигеҙ булғас, алгоритм 21 һаны менән тамамлана һәм ИҘУБ(1071, 462) = 21.

Аҙымдар таблица формаһында түбәндәгесә:

Аҙым k	Тигеҙлек	Бүлендек һәм ҡалдыҡ
0	1071 = q0 462 + r0	q0 = 2 и r0 = 147
1	462 = q1 147 + r1	q1 = 3 и r1 = 21
2	147 = q2 21 + r2	q2 = 7 и r2 = 0; алгоритм тамам

Ҡулланылышы

Евклидтың киңәйтелгән алгоритмы һәм Безу нисбәте

$r_{i}$ өсөн формулаларҙы ошолай итеп күсереп яҙырға була:

$r_{1}=a+b(-q_{0})$

$r_{2}=b-r_{1}q_{1}=a(-q_{1})+b(1+q_{1}q_{0})$

$\vdots$

ИҘУБ $(a,b)=r_{n}=as+bt$

Бында s һәм t бөтөн һандар. Иң ҙур уртаҡ бүлеүсене күрһәтеү Безу нисбәте тип атала, ә s һәм t һандары — Безу коэффициенттары . Безу нисбәте Евклид леммаһын һәм арифметиканың төп теоремаһын иҫбатлағанда төп урынды алып тора..

Сылбырлы кәсерҙәр

Евклид алгоритмы сылбырлы кәсерҙәр менән тығыҙ бәйләнгән. a/b сағыштырмаһын сылбырлы кәсер рәүешендә күрһәтергә мөмкин:

${\frac {a}{b}}=[q_{0};q_{1},q_{2},\cdots ,q_{n}]$.

Бында һуңғы быуынынан башҡа сылбырлы кәсер минус тамғаһы менән алынған Безу коэффициентына t/s тигеҙ:

$[q_{0};q_{1},q_{2},\cdots ,q_{n-1}]=-{\frac {t}{s}}$.

Евклид алгоритмын биргән һуңғы тигеҙлекте ошо формала яҙырға мөмкин:

${\begin{aligned}{\frac {a}{b}}&=q_{0}+{\frac {r_{0}}{b}}\\{\frac {b}{r_{0}}}&=q_{1}+{\frac {r_{1}}{r_{0}}}\\{\frac {r_{0}}{r_{1}}}&=q_{2}+{\frac {r_{2}}{r_{1}}}\\&{}\ \vdots \\{\frac {r_{k-2}}{r_{k-1}}}&=q_{k}+{\frac {r_{k}}{r_{k-1}}}\\&{}\ \vdots \\{\frac {r_{N-2}}{r_{N-1}}}&=q_{N}\end{aligned}}$

Тигеҙлектең уң яғындағы һуңғы ҡушылыусы һәр ваҡыт артабанғы тигеҙләмәнең һул яғының кире ҡиммәтенә тигеҙ. Шуға күрә тәүге ике тигеҙләмәне ошолай берләштерергә мөмкин:

${\frac {a}{b}}=q_{0}+{\cfrac {1}{q_{1}+{\cfrac {r_{1}}{r_{0}}}}}$

Өсөнсө тигеҙлек r₁/r₀ аңлатмаһының знаменателен алмаштырыу өсөн ҡулланылырға мөмкин. Табабыҙ:

${\frac {a}{b}}=q_{0}+{\cfrac {1}{q_{1}+{\cfrac {1}{q_{2}+{\cfrac {r_{2}}{r_{1}}}}}}}$

Һуңғы ҡалдыҡтар сағыштырмаһы r_k/r_k−1 һәр ваҡыт эҙмә-эҙлелектәге артабанғы тигеҙлекте ҡулланып алмаштырылырға мөмкин, һәм шулай һуңғы тигеҙләмәгә тиклем.Һөҙөмтәлә сылбырлы кәсер килеп сыға:

${\frac {a}{b}}=q_{0}+{\cfrac {1}{q_{1}+{\cfrac {1}{q_{2}+{\cfrac {1}{\ddots +{\cfrac {1}{q_{N}}}}}}}}}=[q_{0};q_{1},q_{2},\ldots ,q_{N}]$

Юғарыла килтерелгән #миҫалда миҫалда ИҘУБ(1071, 462) иҫәпләнде һәм ярашлы рәүештә 2, 3 һәм 7-гә тигеҙ булған q_k бүлендектәр табылды. Шуға күрә 1071/462 бүлендеге ошолай яҙылырға мөмкин:

${\frac {1071}{462}}=2+{\cfrac {1}{3+{\cfrac {1}{7}}}}=[2;3,7]$

Һыҙыҡлы диофант тигеҙләмәләр

Диофант тигеҙләмәһе — ул бөтөн һанлы коэффициентлы һәм бер йәки бер нисә үҙгәреүсәнле тигеҙләмә, шуның менән бергә уның тик бөтөн тамырҙарын ғына табыу маҡсаты ҡуйыла. Ундай тигеҙләмәнең сикһеҙ күп сығарылышы булырға, сикле һанда сығарылышы булырға йәки бөтөнләй сығарылышы булмаҫҡа мөмкин. Иң ябай диофант тигеҙләмәһе - ике үҙгәреүсәнле һыҙыҡлы тигеҙләмә:

$a\cdot x+b\cdot y=c,$

бында a, b, c — бөтөн һандар. Евклид алгоритмы ярҙамында бындай типтағы тигеҙләмәнең тулы сығарылышын табырға мөмкин. Иң тәүҙә был алгоритм ярҙамында d = ИҘУБ(a, b) табырға була. Аҙаҡ, Евклидтың киңәйтелгән алгоритмын ҡулланып, шундай k һәм l табыла:

$a\cdot k+b\cdot l=d.$

Йәғни x = k һәм y = l - тигеҙләмәнең c = d булғандағы сығарылышы. Әгәр c = q⋅d, ул саҡта x = q⋅k, y = q⋅l - бирелгән тигеҙләмәнең сығарылышы булыуы килеп сыға, сөнки:

$a\cdot x+b\cdot y=a\cdot (q\cdot k)+b\cdot (q\cdot l)=q\cdot (a\cdot k+b\cdot l)=q\cdot d=c.$

Киреһенсә, әгәр тигеҙләмәнең бер генә булһа ла сығарылышы булһа, ул саҡта c d-ға бүленә. Был шунан килеп сыға, d a-ны ла, һәм b-ны ла бүлә (тимәк бөтә һул яғын), шуға күрә c-ны ла (уң яғын) бүлергә тейеш. Шулай итеп, һыҙыҡлы диофант тигеҙләмәһенең бер генә булһа ла сығарылышы шул саҡта һәм тик шул саҡта була, әгәр c ИҘУБ(a, b)-нә бүленһә.

Вариациялар һәм дөйөмләштереү

Евклид балдағы

Евклид алгоритмын ҡулланып булған балдаҡтар евклид балдаҡтары тип атала. Уларға бөтөн һандар балдаҡтары һәм күпбыуындар балдаҡтары инә.

Күпбыуындар өсөн дөйөмләштерелгән Евклид алгоритмы

Евклид алгоритмы һәм киңәйтелгән Евклид алгоритмы тәбиғи рәүештә ирекле k яланында бер үҙгәреүсәнле k[x] күпбыуындар балдағында дөйөмләштерелә, сөнки ундай күпбыуындар өсөн ҡалдыҡлы бүлеү ғәмәле билдәләнгән. Күпбыуындар өсөн Евклид алгоритмын башҡарғанда, бөтөн һандарға Евклид алгоритмын ҡулланғандағыға оҡшаш рәүештә, полиномиаль ҡалдыҡтар (PRS) эҙмә-эҙлелеге килеп сыға.

Z[x]  

Билдәләмә буйынса cont(f) — Z[x] — күпбыуындың йөкмәткеһенән f(x) күпбыуынының коэффициенттарының ИҘУБ-ы булһын, ти. . f(x)-тың cont(f)-ҡабүлендеге f(x)күпбыуынының примитив өлөшө тип атала һәм primpart(f(x)) тип тамғалана. Был билдәләмәләр Z[x]балдағында ике p₁(x) һәм p₂(x)күпбыуындарының ИҘУБ-ын тапҡанда кәрәк була. Бөтөн һандар өҫтөндә күпбыуындар өсөн түбәндәге дөрөҫ:

$cont($НОД$\{p_{1}(x),p_{2}(x)\})=$НОД$\{cont(p_{1}(x)),cont(p_{2}(x))\},$

$primpart($НОД$\{p_{1}(x),p_{2}(x)\})=$НОД$\{primpart(p_{1}(x)),primpart(p_{2}(x))\}.$

Шулай итеп, ике ирекле күпбыуындың ИҘУБ-ын табыу примитив полиномдарҙың ИҘУБ-ын табыуға ҡайтып ҡала.

p1(x) һәм p2(x)  Z[x]-тан, уларҙың дәрәжәләре өсөн  deg(p1(x)) = m һәм deg(p2(x)) = n, m > n нисбәте үтәлгән ике примитив күпбыуын булһын, ти. Күпбыуындарҙы ҡалдыҡлы бүлеү бүленеүсенең өлкән коэффициентының бүлеүсенең өлкән коэффициентына теүәл бүленеүен талап итә, дөйөм осраҡта ҡалдыҡлы бүлеүҙе башҡарыу мөмкин түгел. Шуға күрә псевдобүлеү алгоритмын индерәләр, был бөтөн һандар өҫтөндә күпбыуындар күмәклегенә ингән псевдобүлендек һәм псевдоҡалдыҡ табырға мөмкинлек бирә. 

Псевдобүлеүҙе ошолай аңларға кәрәк: бүлеүҙән алда $p_{1}(x)$ полиномы $(lc(p_{2}(x)))^{m-n+1}$ полиномына ҡабатлана, йәғни:

$lc(p_{2}(x))^{m-n+1}p_{1}(x)=p_{2}(x)q(x)+r_{2}(x),\deg(r(x))<\deg(p_{2}(x)),$

бында $q(x)$ һәм $r(x)$ — ярашлы рәүештә псевдобүлендек һәм псевдоҡалдыҡ.

Шулай итеп, $p_{1}(x),p_{2}(x)\in Z[x]$, шуның менән бергә $\deg(p_{1})=n_{1}\geq \deg(p_{2})=n_{2}$. Ул саҡта Евклид алгоритмы түбәндәге аҙымдарҙан тора:

1. Йөкмәткеләрҙең ИҘУБ-ын иҫәпләү:

$c:=$НОД$\{cont(p_{1}),cont(p_{2})\}$.

2. Примитив өлөштәрен иҫәпләү:

$p_{1}'(x):=primpart(p_{1}(x));$

$p_{2}'(x):=primpart(p_{2}(x)).$

3. Полиномиаль ҡалдыҡтар эҙмә-эҙлелеген төҙөү:

$p_{1}'(x),$

$p_{2}'(x),$

$p_{3}(x):=prem(p_{1}'(x),p_{2}'(x)),$

$p_{4}(x):=prem(p_{2}'(x),p_{3}(x)),$

$p_{5}(x):=prem(p_{3}(x),p_{4}(x)),$

$...$

$p_{h}(x):=prem(p_{h-2}(x),p_{h-1}(x)).$

4. Һөҙөмтәне кире ҡайтарыу:

Әгәр $\deg(p_{h}(x))=0$ булһа, ул саҡта $c$-ны кире ҡайтарырға, кире осраҡта $c\cdot primpart(p_{h}(x))$-ны кире ҡайтарырға.

Алгоритмдың тиҙләтелгән версиялары

• Бөтөн һанлы Евклид алгоритмын тиҙләтеү ысулдарының береһе булып симметрик ҡалдыҡ ҡулланыу тора:

$r_{i}\equiv r_{i-2}{\pmod {r_{i-1}}},$

бында

$-{\frac {r_{i-1}}{2}}\leq r_{i}\leq {\frac {r_{i-1}}{2}}.$

• Полиномдар өсөн тиҙләтелгән Евклид алгоритмы версияларының береһе, алгоритмдың аралағы ҡиммәттәре, нигеҙҙә, юғары дәрәжәгә бәйле булыуына нигеҙләнгән. «Бүлгеслә һәм идара ит» стратегияһын ҡулланыу алгоритмдың асимптотик ҡатмарлылығын

кәметергә мөмкинлек бирә.

Әҙәбиәт

• Евклид башланғыстары / ғәрәп теленән тәржемә һәм комм. Д. Д. Мордухая-Болтовский Выгодский М. Я. и Веселовский И. Н. редакцияһы. — ГИТТЛ, 1949. — Т. 2. — 511 с.
• Виноградов И. М. Һандар теорияһы нигеҙҙәре. — М.-Л.: ГИТТЛ, 1952. — 180 с. — ISBN 978-5-811-40535-0.
• Курант Р., Роббинс Г. Глава I, § 4-кә өҫтәлмә. // Нимә ул математика? — 3-e изд., испр. и доп. — М., 2001. — 568 с. — ISBN 5-900916-45-6.
• Абрамов С. А. Самый знаменитый алгоритм (урыҫ) // Квант / под ред. И. К. Кикоин, Ю. Осипьян, В. В. Козлов, А. Л. Семенов, А. Гайфуллин — МИАН, 1985. — вып. 11. — С. 44—46. — ISSN 0130-2221
• Кнут Д. Э. Программалаштырыу сәнғәте. — Вильямс, 2001. — Т. 2. — 829 с. — ISBN 5-8459-0081-6.
• Menezes A., van Oorschot P., Vanstone S. Handbook of Applied Cryptography. — CRC-Press, 1996. — 816 с. — (Discrete Mathematics and Its Applications). — ISBN 0-8493-8523-7.
• von zur Gathen J., Gerhard J. Modern Computer Algebra. — Cambridge University Press, 2013. — 808 с. — ISBN 978-1-107-03903-2.
• Панкратьев Е. В. Компьютерлы алгебра элементтары. — ИНТУИТ, 2007. — 217 с. — ISBN 978-5-955-60099-4.
• Тихомиров В. М. Боронғо бөйөк математиктәр һәм уларҙың бөйөк теоремалары. — 2-е изд., испр. — МЦНМО, 2003. — 16 с. — ISBN 5-94057-110-7.
• Калужин Л. А. Арифметиканың төп теоремаһы. — Математика буйынса популяр лекциялар. — М.: Наука, 1969. — 33 с.
• Хассе Г. Һандар теорияһы буйынса лекциялар. — Сит ил әҙәбиәте нәшриәте. — 527 с.
• Энгелер Э. Элементар математиканың метаматематикаһы. — М.: Мир, 1987. — 128 с.
• Цейтен Г. Г. Боронғо һәм урта быуаттарҙағы математика тарихы. — ГТТИ, 1932. — 232 с.
• Курош А. Г. Лекции по общей алгебре (урыҫ) / под ред. О. Н. Головин — 2-е изд. — М.: Наука, 1973. — 400 с. — ISBN 978-5-8114-0617-3

Һылтанмалар

• Евклид алгоритмы методын тасуирлау һәм программалар коды [1].
• Евклид алгоритмын нигеҙләү 2016 йыл 7 март архивланған.
• e-maxx.ru-ла Евклид алгоритмы
• C# киңәйтелгән Евклид алгоритмын тормошҡа ашырыу 2016 йыл 1 июль архивланған.