powermod
Modular exponentiation
Syntax
Description
c = powermod(
returns the modular exponentiation ab mod m. The input a
,b
,m
)a,b
must be integers, and
m
must be a nonnegative integer. For more information, see
Modular Exponentiation.
Examples
Compute Modular Exponentiation
Compute the modular exponentiation ab mod m by using powermod
. The
powermod
function is efficient because it does not
calculate the exponential ab.
c = powermod(3,5,7)
c = 5
Prove Fermat's Little Theorem
Fermat's little theorem states that if p is prime and a is not divisible by p, then a(p–1) mod p is 1.
Test Fermat's little theorem for p = 5
, a =
3
. As expected, powermod
returns
1
.
p = 5; a = 3; c = powermod(a,p-1,p)
c = 1
Test the same case for all values of a less than
p. The function powermod
acts
element-wise to return a vector of ones.
p = 5; a = 1:p-1; c = powermod(a,p-1,p)
c = 1 1 1 1
Compute Fermat Primes Using Fermat Primality Test
Fermat's little theorem states that if p is a prime number and a is not divisible by p, then a(p–1) mod p is 1. On the contrary, if a(p–1) mod p is 1 and a is not divisible by p, then p is not always a prime number (p can be a pseudoprime).
Test numbers from 300
to 400
for
primality by using Fermat's little theorem with base
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
Find Fermat pseudoprimes by comparing the results with
isprime
. 341
is a Fermat
pseudoprime.
primeNumbers = p(isprime(p)); setdiff(primesFermat,primeNumbers)
ans = 341
Input Arguments
a
— Base
number | vector | matrix | array | symbolic number | symbolic array
Base, specified as a number, vector, matrix, array, or a symbolic number
or array. a
must be an integer.
b
— Exponent or power
number | vector | matrix | array | symbolic number | symbolic array
Exponent or power, specified as a number, vector, matrix, array, or a
symbolic number or array. b
must be an integer.
m
— Divisor
number | vector | matrix | array | symbolic number | symbolic array
Divisor, specified as a number, vector, matrix, array, or a symbolic
number or array. m
must be a nonnegative
integer.
More About
Modular Exponentiation
For a positive exponent b, the modular exponentiation c is defined as
c = ab mod m.
For a negative exponent b, the definition can be extended by finding the modular multiplicative inverse d of a modulo m, that is
c = d ‒b mod m.
where d satisfies the relation
ad mod m = 1.
Version History
Introduced in R2018a
Comando de MATLAB
Ha hecho clic en un enlace que corresponde a este comando de MATLAB:
Ejecute el comando introduciéndolo en la ventana de comandos de MATLAB. Los navegadores web no admiten comandos de MATLAB.
Select a Web Site
Choose a web site to get translated content where available and see local events and offers. Based on your location, we recommend that you select: .
You can also select a web site from the following list:
How to Get Best Site Performance
Select the China site (in Chinese or English) for best site performance. Other MathWorks country sites are not optimized for visits from your location.
Americas
- América Latina (Español)
- Canada (English)
- United States (English)
Europe
- Belgium (English)
- Denmark (English)
- Deutschland (Deutsch)
- España (Español)
- Finland (English)
- France (Français)
- Ireland (English)
- Italia (Italiano)
- Luxembourg (English)
- Netherlands (English)
- Norway (English)
- Österreich (Deutsch)
- Portugal (English)
- Sweden (English)
- Switzerland
- United Kingdom (English)