Exponenta Banner
exponenta event banner

powermod

Модульное возведение в степень

свернуть все на странице

Синтаксис

c = powermod(a,b,m)

Описание

пример

c = powermod(a,b,m) возвращает модульное возведение в степень a mod b m. Вход a,b должны быть целые числа и m должно быть неотрицательное целое число. Для получения дополнительной информации смотрите Модульное Возведение в степень.

Примеры

свернуть все

Вычислите модульное возведение в степень a  mod b m при помощи powermod. powermod функция эффективна, потому что она не вычисляет экспоненциальный a b.

c = powermod(3,5,7)
c =
     5

Небольшая теорема Ферма утверждает, что, если p является главным и a не является делимым p, то a (p –1) ультрасовременный p равняется 1.

Протестируйте небольшую теорему Ферма на p = 5, a = 3. Как ожидалось, powermod возвращает 1.

p = 5;
a = 3;
c = powermod(a,p-1,p)
c =
1

Протестируйте тот же случай на все значения a меньше, чем p. Функция powermod действует поэлементный, чтобы возвратить вектор из единиц.

p = 5;
a = 1:p-1;
c = powermod(a,p-1,p)
c =
     1     1     1     1

Небольшая теорема Ферма утверждает, что, если p является простым числом и a, не является делимым p, то a (p –1) ультрасовременный p равняется 1. Наоборот, если a (p –1) ультрасовременный p равняется 1, и a не является делимым p, то p является не всегда простым числом (p может быть псевдоначалом).

Протестируйте числа от 300 к 400 для простоты чисел при помощи небольшой теоремы Ферма с основным 2.

p = 300:400;
remainder = powermod(2,p-1,p);
primesFermat = p(remainder == 1)
primesFermat =
   307   311   313   317   331   337   341   347   349   353...
   359   367   373   379   383   389   397

Найдите псевдоначала Ферма путем сравнения результатов с isprime. 341 псевдоглавный Ферма.

primeNumbers = p(isprime(p));
setdiff(primesFermat,primeNumbers)
ans =
   341

Входные параметры

свернуть все

Основа в виде номера, вектора, матрицы, массива, или символьного числа или массива. a должно быть целое число.

Экспонента или степень в виде номера, вектора, матрицы, массива, или символьного числа или массива. b должно быть целое число.

Делитель в виде номера, вектора, матрицы, массива, или символьного числа или массива. m должно быть неотрицательное целое число.

Больше о

свернуть все

Модульное возведение в степень

Для положительной экспоненты b модульное возведение в степень c задан как

c = a  mod b m.

Для отрицательной экспоненты b определение может быть расширено путем нахождения модульной мультипликативной инверсии d a m по модулю, который является

c = d ‒b ультрасовременный m.

где d удовлетворяет отношению

a mod d m = 1.

Смотрите также

| | |

Введенный в R2018a

Документация Symbolic Math Toolbox

Поддержка