Как считать большие степени

Как вычислить большую степень?

Онлайн калькулятор разложения Шенкса (задача дискретного логарифмирования) выдал подобные результаты.

2^(1⋅24) ≡ 265(mod541)
2^(2⋅24) ≡ 436(mod541)
.

Заранее могу сказать, что посчитал он правильно, однако сам способ вычисления я совершенно не понял.

Какие подходы задействованы для вычисления:
а) большой степени
б) откуда взялось деление с остатком?
в) не понял суть знака «тождественно равно» (вики прочитал, но разницы от обычного знака равенства не уяснил)

• Вопрос задан более трёх лет назад
• 5101 просмотр

• Facebook
• Вконтакте
• Twitter

Большую степень не вычисляют в лоб, тем более, что при выполнении действий в модульной арифметике её не нужно хранить целиком, достаточно хранить остаток от деления на известное постоянное число. Знак «тождественное равенство» используется как знак равенства в модульной арифметике, если модуль указан отдельно, поскольку сами числа, естественно, не равны.

Дискретное логарифмирование — формально, задача на пространстве решений, на котором можно применять модульную арифметику над многочленами или числами, с некоторым простым числом в качестве размера множества, частного для деления по модулю и вообще.

Саму степень по модулю можно вычислить довольно простым образом: Вначале раскладываем показатель на двоичные составляющие: 2*24 = 48 = 32+16 = 2^5+2^4. Потом пользуемся двумя тождествами: Первое x^(a+b)=x^a*x^b — произведение степеней одного числа равно степени числа в сумме показателей (забыл точное название). Второе (x*y) mod n = (x mod n)*(y mod n) — неважно, когда брать остаток, в начале или в конце. В итоге возведение числа 2 в большую степень по модулю N выполняется так: в результат заносится 1, в аргумент 2, потом в цикле по разрядам показателя если текущий двоичный разряд показателя 1, результат множится на аргумент и берется остаток по модулю N, который кладется в результат, а аргумент потом умножается на себя и остаток аргумента по модулю N кладется в аргумент.

Итого: аргумент принимает последовательно значения 2, 4, 16, 256, 65536 mod 541 = 75, 75*75 mod 541 = 215, а результат — 1, 1, 1, 1, 75, 75*215 mod 541 = 436.

Как посчитать число в большой степени

Мы разобрались, что вообще из себя представляет степень числа. Теперь нам надо понять, как правильно выполнять ее вычисление, т.е. возводить числа в степень. В этом материале мы разберем основные правила вычисления степени в случае целого, натурального, дробного, рационального и иррационального показателя. Все определения будут проиллюстрированы примерами.

Понятие возведения в степень

Начнем с формулирования базовых определений.

Возведение в степень – это вычисление значения степени некоторого числа.

То есть слова "вычисление значение степени" и "возведение в степень" означают одно и то же. Так, если в задаче стоит "Возведите число 0 , 5 в пятую степень", это следует понимать как "вычислите значение степени ( 0 , 5 ) 5 .

Теперь приведем основные правила, которым нужно придерживаться при таких вычислениях.

Как возвести число в натуральную степень

Вспомним, что такое степень числа с натуральным показателем. Для степени с основанием a и показателем n это будет произведение n -ного числа множителей, каждый из которых равен a . Это можно записать так:

Чтобы вычислить значение степени, нужно выполнить действие умножения, то есть перемножить основания степени указанное число раз. На умении быстро умножать и основано само понятие степени с натуральным показателем. Приведем примеры.

Условие: возведите – 2 в степень 4 .

Решение

Используя определение выше, запишем: ( − 2 ) 4 = ( − 2 ) · ( − 2 ) · ( − 2 ) · ( − 2 ) . Далее нам нужно просто выполнить указанные действия и получить 16 .

Возьмем пример посложнее.

Вычислите значение 3 2 7 2

Решение

Данную запись можно переписать в виде 3 2 7 · 3 2 7 . Ранее мы рассматривали, как правильно умножать смешанные числа, упомянутые в условии.

Выполним эти действия и получим ответ: 3 2 7 · 3 2 7 = 23 7 · 23 7 = 529 49 = 10 39 49

Если в задаче указана необходимость возводить иррациональные числа в натуральную степень, нам потребуется предварительно округлить их основания до разряда, который позволит нам получить ответ нужной точности. Разберем пример.

Выполните возведение в квадрат числа π .

Решение

Для начала округлим его до сотых. Тогда π 2 ≈ ( 3 , 14 ) 2 = 9 , 8596 . Если же π ≈ 3 . 14159 , то мы получим более точный результат: π 2 ≈ ( 3 , 14159 ) 2 = 9 , 8695877281 .

Отметим, что необходимость высчитывать степени иррациональных чисел на практике возникает сравнительно редко. Мы можем тогда записать ответ в виде самой степени ( ln 6 ) 3 или преобразовать, если это возможно: 5 7 = 125 5 .

Отдельно следует указать, что такое первая степень числа. Тут можно просто запомнить, что любое число, возведенное в первую степень, останется самим собой:

Это понятно из записи .

От основания степени это не зависит.

Так, ( − 9 ) 1 = − 9 , а 7 3 , возведенное в первую степень, останется равно 7 3 .

Как возвести число в целую степень

Для удобства разберем отдельно три случая: если показатель степени – целое положительное число, если это ноль и если это целое отрицательное число.

В первое случае это то же самое, что и возведение в натуральную степень: ведь целые положительные числа принадлежат ко множеству натуральных. О том, как работать с такими степенями, мы уже рассказали выше.

Теперь посмотрим, как правильно возводить в нулевую степень. При основании, которое отличается от нуля, это вычисление всегда дает на выходе 1 . Ранее мы уже поясняли, что 0 -я степень a может быть определена для любого действительного числа, не равного 0 , и a 0 = 1 .

5 0 = 1 , ( – 2 , 56 ) 0 = 1 2 3 0 = 1

0 0 – не определен.

У нас остался только случай степени с целым отрицательным показателем. Мы уже разбирали, что такие степени можно записать в виде дроби 1 a z , где а – любое число, а z – целый отрицательный показатель. Мы видим, что знаменатель этой дроби есть не что иное, как обыкновенная степень с целым положительным показателем, а ее вычислять мы уже научились. Приведем примеры задач.

Возведите 2 в степень – 3 .

Решение

Используя определение выше, запишем: 2 – 3 = 1 2 3

Подсчитаем знаменатель этой дроби и получим 8 : 2 3 = 2 · 2 · 2 = 8 .

Тогда ответ таков: 2 – 3 = 1 2 3 = 1 8

Возведите 1 , 43 в степень – 2 .

Решение

Переформулируем: 1 , 43 – 2 = 1 ( 1 , 43 ) 2

Вычисляем квадрат в знаменателе: 1,43·1,43. Десятичные дроби можно умножить таким способом:

В итоге у нас вышло ( 1 , 43 ) – 2 = 1 ( 1 , 43 ) 2 = 1 2 , 0449 . Этот результат нам осталось записать в виде обыкновенной дроби, для чего необходимо умножить ее на 10 тысяч (см. материал о преобразовании дробей).

Ответ: ( 1 , 43 ) – 2 = 10000 20449

Отдельный случай – возведение числа в минус первую степень. Значение такой степени равно числу, обратному исходному значению основания: a – 1 = 1 a 1 = 1 a .

Пример: 3 − 1 = 1 / 3

9 13 – 1 = 13 9 6 4 – 1 = 1 6 4 .

Как возвести число в дробную степень

Для выполнения такой операции нам потребуется вспомнить базовое определение степени с дробным показателем: a m n = a m n при любом положительном a , целом m и натуральном n .

Таким образом, вычисление дробной степени нужно выполнять в два действия: возведение в целую степень и нахождение корня n -ной степени.

У нас есть равенство a m n = a m n , которое, учитывая свойства корней, обычно применяется для решения задач в виде a m n = a n m . Это значит, что если мы возводим число a в дробную степень m / n , то сначала мы извлекаем корень n -ной степени из а , потом возводим результат в степень с целым показателем m .

Проиллюстрируем на примере.

Вычислите 8 – 2 3 .

Решение

Способ 1. Согласно основному определению, мы можем представить это в виде: 8 – 2 3 = 8 – 2 3

Теперь подсчитаем степень под корнем и извлечем корень третьей степени из результата: 8 – 2 3 = 1 64 3 = 1 3 3 64 3 = 1 3 3 4 3 3 = 1 4

Способ 2. Преобразуем основное равенство: 8 – 2 3 = 8 – 2 3 = 8 3 – 2

После этого извлечем корень 8 3 – 2 = 2 3 3 – 2 = 2 – 2 и результат возведем в квадрат: 2 – 2 = 1 2 2 = 1 4

Видим, что решения идентичны. Можно пользоваться любым понравившимся способом.

Бывают случаи, когда степень имеет показатель, выраженный смешанным числом или десятичной дробью. Для простоты вычислений его лучше заменить обычной дробью и считать, как указано выше.

Возведите 44 , 89 в степень 2 , 5 .

Решение

Преобразуем значение показателя в обыкновенную дробь – 44 , 89 2 , 5 = 49 , 89 5 2 .

А теперь выполняем по порядку все действия, указанные выше: 44 , 89 5 2 = 44 , 89 5 = 44 , 89 5 = 4489 100 5 = 4489 100 5 = 67 2 10 2 5 = 67 10 5 = = 1350125107 100000 = 13 501 , 25107

Ответ: 13 501 , 25107 .

Если в числителе и знаменателе дробного показателя степени стоят большие числа, то вычисление таких степеней с рациональными показателями – довольно сложная работа. Для нее обычно требуется вычислительная техника.

Отдельно остановимся на степени с нулевым основанием и дробным показателем. Выражению вида 0 m n можно придать такой смысл: если m n > 0 , то 0 m n = 0 m n = 0 ; если m n 0 нуль остается не определен. Таким образом, возведение нуля в дробную положительную степень приводит к нулю: 0 7 12 = 0 , 0 3 2 5 = 0 , 0 0 , 024 = 0 , а в целую отрицательную – значения не имеет: 0 – 4 3 .

Как возвести число в иррациональную степень

Необходимость вычислить значение степени, в показателе которой стоит иррациональное число, возникает не так часто. На практике обычно задача ограничивается вычислением приблизительного значения (до некоторого количества знаков после запятой). Обычно это считают на компьютере из-за сложности таких подсчетов, поэтому подробно останавливаться на этом не будем, укажем лишь основные положения.

Если нам нужно вычислить значение степени a с иррациональным показателем a , то мы берем десятичное приближение показателя и считаем по нему. Результат и будет приближенным ответом. Чем точнее взятое десятичное приближение, тем точнее ответ. Покажем на примере:

Вычислите приближенное значение 21 , 174367 .

Решение

Ограничимся десятичным приближением a n = 1 , 17 . Проведем вычисления с использованием этого числа: 2 1 , 17 ≈ 2 , 250116 . Если же взять, к примеру, приближение a n = 1 , 1743 , то ответ будет чуть точнее: 2 1 , 174367 . . . ≈ 2 1 , 1743 ≈ 2 , 256833 .

Онлайн калькулятор разложения Шенкса (задача дискретного логарифмирования) выдал подобные результаты.

2^(1⋅24) ≡ 265(mod541)
2^(2⋅24) ≡ 436(mod541)
.

Заранее могу сказать, что посчитал он правильно, однако сам способ вычисления я совершенно не понял.

Какие подходы задействованы для вычисления:
а) большой степени
б) откуда взялось деление с остатком?
в) не понял суть знака "тождественно равно" (вики прочитал, но разницы от обычного знака равенства не уяснил)

• Вопрос задан более года назад
• 602 просмотра

Большую степень не вычисляют в лоб, тем более, что при выполнении действий в модульной арифметике её не нужно хранить целиком, достаточно хранить остаток от деления на известное постоянное число. Знак "тождественное равенство" используется как знак равенства в модульной арифметике, если модуль указан отдельно, поскольку сами числа, естественно, не равны.

Дискретное логарифмирование – формально, задача на пространстве решений, на котором можно применять модульную арифметику над многочленами или числами, с некоторым простым числом в качестве размера множества, частного для деления по модулю и вообще.

Саму степень по модулю можно вычислить довольно простым образом: Вначале раскладываем показатель на двоичные составляющие: 2*24 = 48 = 32+16 = 2^5+2^4. Потом пользуемся двумя тождествами: Первое x^(a+b)=x^a*x^b – произведение степеней одного числа равно степени числа в сумме показателей (забыл точное название). Второе (x*y) mod n = (x mod n)*(y mod n) – неважно, когда брать остаток, в начале или в конце. В итоге возведение числа 2 в большую степень по модулю N выполняется так: в результат заносится 1, в аргумент 2, потом в цикле по разрядам показателя если текущий двоичный разряд показателя 1, результат множится на аргумент и берется остаток по модулю N, который кладется в результат, а аргумент потом умножается на себя и остаток аргумента по модулю N кладется в аргумент.

Итого: аргумент принимает последовательно значения 2, 4, 16, 256, 65536 mod 541 = 75, 75*75 mod 541 = 215, а результат – 1, 1, 1, 1, 75, 75*215 mod 541 = 436.

Предлагаем попробовать наш калькулятор степеней, который поможет возвести в степень онлайн любое число.

Использовать калькулятор очень просто — введите число, которое вы хотите возвести в степень, а затем число — степень и нажмите на кнопку «Посчитать».

Примечательно то, что наш онлайн калькулятор степеней может возвести в степень как положительную, так и отрицательную. А для извлечения корней на сайте есть другой калькулятор.

Как возвести число в степень.

Давайте рассмотрим процесс возведения в степень на примере. Пусть нам необходимо возвести число 5 в 3-ю степень. На языке математики 5 — это основание, а 3 — показатель (или просто степень). И записать это можно кратко в таком виде:

Возведение в степень

А чтобы найти значение, нам будет необходимо число 5 умножить на себя 3 раза, т. е.

5 3 = 5 x 5 x 5 = 125

Соответственно, если мы хотим найти значение числа 7 в 5 степени, мы должны число 7 умножить на себя 5 раз, т. е. 7 x 7 x 7 x 7 x 7. Другое дело когда требуется возвести число в отрицательную степень.

Как возводить в отрицательную степень.

При возведении в отрицательную степень необходимо использовать простое правило:

как возводить в отрицательную степень

Все очень просто — при возведении в отрицательную степень мы должны поделить единицу на основание в степени без знака минус — т. е. в положительной степени. Таким образом, чтобы найти значение
2 -3

Возвести в степень (по модулю) + большие числа

Алгоритм быстрого возведения в степень онлайн с решением по модулю и без модуля. Функциональность поддерживает работу с большими числами.

Использование:

alt=»✔» />Заполняем необходимые данные целыми числами, отвечая на вопросы формы.
alt=»✔» />Жмем кнопку вычислить и получаем результат.

alt=»ℹ» />Галочка «по модулю» позволяет указать модуль, по которому необходимо возводить в степень.
alt=»ℹ» />Галочка «с решением» позволяет получить этапы вычисления: каким образом число возводилось в степень.

Ограничения калькулятора:

Максимальное число, которое можно возвести в степень — 1 000 000.
Максимальная степень, в которую можно возвести — 5000.
Модуль может быть довольно-таки большим, до 100 символов в числе. [1; 10e100)

Алгоритм быстрого возведения в степень (по модулю).

Одним из основных действий арифметики вычетов, возникающих, например, в криптографии, является вычисление а х (mod m), то есть нахождение такого у, что

где a, x, m — натуральные числа. Далее считаем, что a < m. Запись у = b (mod m) означает, что у ≡ b (mod m) и 0 ≤ у < m, т.е, y — наименьший неотрицательный вычет по модулю m, лежащий в том классе, что и b.

Если вычислять «в лоб», т.е. последовательно находить (приводим формулы по модулю):

то нужно выполнить (x — 1) умножение в кольце Z_m, Если n — количество разрядов в двоичной записи х, то число умножений не меньше, чем 2 n-1.

Лемма 1: Пусть x, m, a ∈ N. Пусть x = (x₀x₁ … x_n-1)₂ т.е.

Определим целые а_j по реккурентным формулам

Алгоритм (быстрого возведения в степень). Даны натуральные a, m и x = (x_n-1x_n-2 … x₀)₂. Нужно вычислить y = a x (mod m),

1. Вычисляем a_j (0 ≤ j ≤ n — 1) по формулам (2),

Лемма 2. Пусть n — число разрядов в двоичной записи x. Тогда, приведенный выше алгоритм требует выполнения не более, чем, 2(n -1) умножений в кольце Z_m

Пример 1. Возведем число 2 50 без модуля.

50₁₀ = 110010₂ , считаем длину в двоичной записи n = 6. Следовательно, нам надо посчитать a₁ … a₆ по формулам 2 из теории.

a₁ = 2; a₂ = 2 2 = 4, a₃ = 4 2 = 16, a₄ = 16 2 = 256, a₅ = 256 2 = 65536, a₆ = 65536 2 = 4294967296

x₁ = 0, x₂ = 1, x₃ = 0, x₄ = 0, x₅ = 1, x₆ = 1 — двоичная запись в обратном порядке (от младших разрядов к старшим).

Перемножаем a_i-ые по второй формуле пункта 2. Другими словами, перемножаем между собой те a_i-ые, у которых на соответствующей позиции в двоичной записи степени стоят единицы — это a₂, a₅ и a₆;

2 50 = 4 * 65536 * 4294967296 = 1125899906842624

Пример 2. Возведем число 2 50 по модулю 100. Все аналогично, только считаем a_i-ые и произведения a_i-ых по модулю 100.

50₁₀ = 110010₂ , считаем длину в двоичной записи n = 6. Следовательно, нам надо посчитать a₁ … a₆ по формулам 2 из теории.

a₁ = 2; a₂ = 2 2 = 4, a₃ = 4 2 = 16, a₄ = 16 2 = 56, a₅ = 56 2 = 36, a₆ = 36 2 = 96 по модулю 100

x₁ = 0, x₂ = 1, x₃ = 0, x₄ = 0, x₅ = 1, x₆ = 1 — двоичная запись в обратном порядке (от младших разрядов к старшим).

Перемножаем a_i-ые по второй формуле пункта 2. Другими словами, перемножаем между собой те a_i-ые, у которых на соответствующей позиции в двоичной записи степени стоят единицы — это a₂, a₅ и a₆;

2 50 = 4 * 36 * 96 = 24 по модулю 100.

Заметили неточность в работе калькулятора? Убедительная просьба сообщить об этом в комментариях или через форму обратной связи. Заранее Вас благодарим.