Exponenta Banner
exponenta event banner

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, то (p-1 ) mod p равно 1.

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

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

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

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

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

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

c = d ‒  b mod m.

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

ad mod m = 1.

См. также

| | |

Представлен в R2018a

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

Поддержка