Евклид алгоритмы
From Wikipedia, the free encyclopedia
Евкли́д алгори́тмы — ике бөтөн һандың иң ҙур уртаҡ бүлеүсеһен (йәки ике киҫектең уртаҡ үлсәмен) табыу өсөн эффектив алгоритм. Алгоритм уны беренсе башлап «Башланғыстар»ҙың VII[1] һәм X[2] китаптарында һүрәтләгән грек математигы Евклид хөрмәтенә шулай аталған. Иң ябай осраҡта Евклид алгоритмы ыңғай бөтөн һандар парына ҡулланыла һәм, бәләкәй һандан һәм ҙур һан менән бәләкәй һандың айырмаһынан торған яңы пар барлыҡҡа килтерә. Ошо процесс һандар тигеҙ булғанға тиклем дауам итә. Табылған һан бирелгән парҙың иң ҙур уртаҡ бүлеүсеһе була ла инде.
Алгоритмдың беренсе тасуирламаһы Евклидтың «Башланғыстар» китабында (б.э.т. яҡынса300 йыл) бирелгән, ул бөгөнгө көндә лә ҡулланылған иң боронғо һанлы алгоритм[3]. Алгоритмдың оригиналы тик натураль һандар һәм геометрик оҙонлоҡтар (ысын һандар) өсөн тәҡдим ителгән була. Ләкин XIX быуатта ул Гаусстың бөтөн һандары кеүек башҡа типтағы һандарға һәм бер үҙгәреүсәнле полиномдарға дөйөмләштерелә. Был хәҙергә дөйөм алгебрала евклид балдағы тигән төшөнсә барлыҡҡа килтерҙе. Һуңғараҡ Евклид алгоритмы төйөндәр һәм күп үлсәмле полиномдар кеүек башҡа математик структуралар өсөн дә дөйөмләштерелә. Был алгоритм өсөн күп теоретик һәм практик ҡулланылыш бар. Айырып әйткәндә, ул электрон коммерцияла киң таралған асыҡ асҡыслы RSA[4] криптографик алгоритм өсөн нигеҙ булып тора. Алгоритмдар шулай уҡ һыҙыҡлы диофант тигеҙләмәләрен сығарғанда[5], өҙлөкһөҙ кәсерҙәр төҙөгәндә[6], Штурм методында[7] ҡулланылалар. Евклид алгоритмы дүрт квадраттың суммаһы тураһында Лагранж теоремаһы[8], арифметиканың төп теоремаһы[9] һ.б. кеүек хәҙергә һандар теорияһы теоремаларын иҫбат итеү өсөн төп инструмент булып тора.