Модулна степенуване - на ринга, SIB съветски
На как да се изгради редица много голяма степен на модулната аритметика и не висеше на компютъра, днес аз ще ви кажа.
Така че, първите математика. Тогава няма да има алгоритъм и код в питона.
Ние ще работим на ринга - това е такава специална алгебрична структура. Това не означава непременно знаете, най-важното, за да се използва специален имот, но първо нека да поговорим за нотация: стандарт написано по този $ 7 ^ 4 \ pmod $ - което означава, 7 в 4-та степен по модул 13, т 7 да издигне 4 и намери остатъка от деление с 13 ( грубо казано, тогава математиката може да ми се карат). И изразяването на 7 $ ^ 4 \ екв 9 \ pmod $ е средство 7 в четвъртия степен се равнява на 9 модул 13, в действителност, ако се изгради 7 до четвъртото степен и намиране на остатък деление на 13 ние ще се свържем 9, но може да записва всяко число от които е намирането на баланс също ще даде 9, да речем $ 7 ^ 4 \ екв 100 \ pmod $ също е вярно - както виждаме като клас от еквивалентни номера - той ще използва (тя използва RSA).
За по-кратко означение:
$ 7 ^ 4 \ pmod $ ще бъдат обозначени с помощта на стила неописан тук алгебрични понятия "пръстен" по следния начин: $ [7] $ ^ 4_, и си позволяваме да Brazen свободи вместо $ \ екв $ ще използват $ = $.
Помислете първо предложеният алгоритъм например, тогава в общ вид. Да предположим, че имаме нужда за изграждане на броя на 7 градуса. хм. 45 модул 5. След това направете следното:
$$
[7] ^ _ = [7] _ * [7] ^ _ = [7] * _ [49] _ ^ = [7] _ * [4] ^ _
$$
С поглед към формулата по-горе, ние вече можем да предполагам алгоритъма)))) Това, което сме направили тук, и това е само един поглед на определен имот ми се възползвали. Нека стъпка по стъпка:
- Първо, ние научихме множител за да получите chotnuyu степен - това е възможно, ние сме в "пръстен"
- Тогава той понижава нивото чрез повишаване на броя в полето (обикновено не изисква голям брой)
- Освен това, само помни, че в модула, ние имаме голям брой еквивалентни числа, добре, просто намери от получения брой - 49 остатъка от деление от 5 - е 4 (защото те са еквивалентни в пръстена). и продължаваме да работим с него (така че ние не се измъкнем от квадрата на модула, в този случай 5)
За съжаление, примерът не е много добър, но кратко (бързо приключи, 1 на 11-ия степен е 1). и така в крайна сметка може да получим например такъв списък:
$$
[7] _ * [4] _ * [3] _ * [2] _ * [1] _ * [2] _
$$
В този случай те са по двойки размножават и след всяко умножение намери остатък, например:
$ [7] _ * [4] _ = [3] _ $
Сега, повече или по-малко общо описание на алгоритъма:
- Веднага намали първоначалното експресията, например: $ [7] _ = [2] _ $
- Постигане дори степен от премахването на фактор и да го добавите към списъка (когато е добавен към списъка на вентилатора, можете да спестите до елементи и след това по двойки за умножение или да се оптимизира и при добавяне на елемент да изглежда, ако има вече един там, ние просто се размножават се добавя към наличните и пишат останалата част, като се раздели на устройството - по този начин "списък" никога няма да растат повече от един елемент, а не да се превърне в "списъка" по същество)
- Повторете предишната точка на необходимия брой пъти
- Умножете всеки други елементи от списъка (ефективно, т.е. чрез използване на свойствата, използвани по-горе), а останалите елемент в списъка, се умножава по получени операцията елемент "степен намаление" и да получите резултата (не забравяйте, че тя трябва да бъде също разделен на модул и отговор - баланс - въпреки че това не е задължително - тъй като това е еквивалент на)
Това е, че е време да покаже пример на питон (който не разбира горното описание - помощ код):
Можете да играете с тази функция - това е много бързо, каза, и тъй като в Python по подразбиране, всички от Big. опитайте се да карам най-голям брой аргументи във функцията, която vzbredut главата си.
В Kriptousikah. също изпълнява тази функция - и аз се опитах всичко възможно да се мотае на сървъра - не работи.
Знаейки колко много студенти в лабораториите по програмиране главата пробиха с тази процедура степенуване в модула, мисля, че този материал ще бъде от полза.