Кіріспе

Модульдік арифметика тұжырымдамасы

Модульдік арифметикада g саны n модулі бойынша түпнұсқа түбір болып есептеледі, егер n-мен өзара жайлы болатын әрбір a саны g санының n модулі бойынша дәрежесіне конгруэнтті болса. Яғни, g саны n модулі бойынша түпнұсқа түбір болып есептеледі, егер n-мен өзара жайлы болатын әрбір a бүтін саны үшін gk ≡ a (mod n) болатын кейбір k бүтін саны табылатын болса. Мұндай k мәні a-ның g негізіндегі n модулі бойынша индексі немесе дискретті логарифмі деп аталады. Осылайша, g саны n модулі бойынша түпнұсқа түбір болып табылады, егер және ғана егер g саны n модулі бойынша бүтін сандардың көбейту тобының генераторы болса.

Гаусс «Disquisitiones Arithmeticae» (1801) еңбегінің 57-бабында түпнұсқа түбірлерді анықтады, онда ол осы терминді ойлап тапқан Эйлер екенін айтты. 56-бабында ол Ламберт пен Эйлер оларды білгенін, бірақ алғашқы түпнұсқа түбірлердің бар екенін қатаң түрде дәлелдегені – өзі екенін мәлімдеді. Шындығында, «Disquisitiones» екі дәлелдеме ұсынады: 54-баптағы дәлелдеме конструктивті емес, ал 55-баптағы дәлелдеме конструктивті. Түпнұсқа түбір тек қана егер n 1, 2, 4, pk немесе 2pk болса ғана бар, мұнда p – тақ сан, ал k > 0. n-нің басқа барлық мәндері үшін n модулі бойынша бүтін сандардың көбейту тобы циклдік емес. Бұл тұңғыш рет Гаусспен дәлелденді.

Анықтама

Егер n оң бүтін сан болса, 1-ден n-ге дейінгі (немесе эквивалентті түрде, n-ге өзіндік жай сандар) бүтін сандар n-ге өзіндік болатын сандар тобын құрайды, көбейту модулі n операциясы бойынша; ол деп белгіленеді және n модулі бойынша бірліктер тобы немесе n модулі бойынша бастапқы сыныптар тобы деп аталады. «Бүтін сандардың көбейту тобы модулі n» мақаласында түсіндірілгендей, бұл көбейту тобы циклдік болады, егер және тек қана n 2, 4, немесе 2-ге тең болса, мұнда – тақ жай санның дәрежесі. Бұл топ циклдік болғанда (және тек қана) осы циклдік топтың генераторы n модулі бойынша бастапқы түбір деп аталады (немесе толық тілмен, n модулі бойынша бірліктің бастапқы түбірі, оның X - 1 сақинасындағы бірлік полиномдық теңдеулердің түбірлерінің негізгі шешімі ретіндегі рөлін атап өту), немесе жай ғана бастапқы элемент. циклдік емес болғанда, мұндай бастапқы элементтер mod n болмайды. Оның орнына, n-нің әрбір жай компонентінің өзіндік бастапқы түбірлері болады (төмендегі мысалдардағы 15-ке қараңыз). Кез келген n үшін (циклдік болсын, болмасын), тобының реті Ойлердің φ(n) тотиенттік функциясымен беріледі. Содан кейін Ойлер теоремасы былай дейді: n-ге өзіндік болатын әрбір a үшін, a-ның 1-ге модуль n бойынша сәйкес келетін ең төменгі дәрежесі a-ның n модулі бойынша көбейту реті деп аталады. Атап айтқанда, a-ның n модулі бойынша бастапқы түбір болуы үшін, a-ның 1-ге модуль n бойынша сәйкес келетін ең кіші дәрежесі болуы керек.

Төменгі шектер

Фридландер (1949) және Салье (1950) криптографияны, оның ішінде Диффи-Хеллман кілт алмасу схемасын дәлелдеді. Дыбыс диффузорлары примитивті түбірлер және квадраттық қалдықтар сияқты сандық теориялық ұғымдарға негізделген.