powermod

Модульная экспоненция

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

Синтаксис

c = powermod(a,b,m)

Описание

пример

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

Примеры

свернуть все

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

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

Маленькая теорема Ферма утверждает, что если p простая и a не делится на p, то a(p–1) mod 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) mod p равен 1. Наоборот, если a(p–1) mod p равно 1 и a не делится на p, тогда p не всегда является простым числом (p может быть псевдопричиной).

Тестовые номера из 300 на 400 для primality при помощи маленькой теоремы Ферма с базисными 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 = ab mod m.

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

c = d ‒b mod m.

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

a d mod  m = 1.

См. также

| | |

Введенный в R2018a

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

Поддержка

Для просмотра документации необходимо авторизоваться на сайте