({{, (RefLink[PowerMod, paclet:ref/PowerMod])[a,b,m]
gives (a^b) mod m. }, {, (RefLink[PowerMod, paclet:ref/PowerMod])[a,-1,m]
finds the modular inverse of a modulo m.}, {, (RefLink[PowerMod, paclet:ref/PowerMod])[a,1/r,m]
finds a modular r(^th) root of a.}})

OpenersNotesSection(Spacer1)Details

Integer mathematical function, suitable for both symbolic and numerical manipulation.

For positive b, (RefLink[PowerMod, paclet:ref/PowerMod])[a,b,m] gives the same result as (RefLink[Mod, paclet:ref/Mod])[a^b, m] but is much more efficient.

(RefLink[PowerMod, paclet:ref/PowerMod])[a,b,m] allows negative and rational values of b. It returns unevaluated if the corresponding modular inverse or root does not exist.

(RefLink[PowerMod, paclet:ref/PowerMod]) automatically threads over lists.

OpenersPrimaryExamplesSection(Spacer1)Examples  (7)

OpenersExampleSection0(Spacer1)Basic Examples  (1)

PowerMod[2,10,3]

Mod[2^10,3]

OpenersExampleSection1(Spacer1)Scope  (3)

Compute the multiplicative inverse of 3 modulo 7:

PowerMod[3,-1,7]

Check the result:

Mod[3 5,7]

(RefLink[PowerMod, paclet:ref/PowerMod]) works with numbers of any size, and does not need to compute the explicit power:

PowerMod[2,10^9,18]

(RefLink[PowerMod, paclet:ref/PowerMod]) automatically threads itself over lists:

PowerMod[2,{10,11,12,13,14},5]

OpenersExampleSection2(Spacer1)Generalizations & Extensions  (1)

Compute the modular square root of 6 modulo 10:

PowerMod[6,1/2,10]

OpenersExampleSection3(Spacer1)Properties & Relations  (1)

Build an RSA-like toy encryption scheme. Start with the modulus:

{p,q}=Prime[RandomInteger[{10^4,10^5},{2}]];
n=p q

Find the universal exponent of the multiplication group modulo n:

λ=CarmichaelLambda[n]

Private key:

d=NestWhile[#1+1& ,Round[n/3],GCD[λ,#1]=!=1&]

Public key:

e =PowerMod[d,-1,λ]

Encrypt a message:

PowerMod[ToCharacterCode["RSA in Mathematica"],e,n]

Decrypt it:

FromCharacterCode[PowerMod[%,d,n]]

OpenersExampleSection4(Spacer1)Possible Issues  (1)

Modular square roots may not exist:

PowerMod[2,1/2,5]

({{DocumentationFooterIconsRelatedFunction.png, ({{See Also}, {(RefLink[PowerModList, paclet:ref/PowerModList])  ▪  (RefLink[ModularInverse, paclet:ref/ModularInverse])  ▪  (RefLink[Mod, paclet:ref/Mod])  ▪  (RefLink[Power, paclet:ref/Power])  ▪  (RefLink[ExtendedGCD, paclet:ref/ExtendedGCD])  ▪  (RefLink[MultiplicativeOrder, paclet:ref/MultiplicativeOrder])  ▪  (RefLink[EulerPhi, paclet:ref/EulerPhi])  ▪  (RefLink[PrimitiveRoot, paclet:ref/PrimitiveRoot])}})}})

({{DocumentationFooterIconsRelatedTutorial.png, ({{Tutorials}, {▪(RefLinkPlain[Integer and Number Theoretic Functions, paclet:tutorial/IntegerAndNumberTheoreticalFunctions])}})}})

({{DocumentationFooterIconsRelatedGuide.png, ({{Related Guides}, {▪(RefLinkPlain[Number Theory, paclet:guide/NumberTheory])}, {▪(RefLinkPlain[Cryptographic Number Theory, paclet:guide/CryptographicNumberTheory])}, {▪(RefLinkPlain[Integer Functions, paclet:guide/IntegerFunctions])}, {▪(RefLinkPlain[Number Theoretic Functions, paclet:guide/NumberTheoreticFunctions])}, {▪(RefLinkPlain[Cryptography, paclet:guide/Cryptography])}, {▪(RefLinkPlain[Diophantine Equations, paclet:guide/DiophantineEquations])}, {▪(RefLinkPlain[Multiplicative Number Theory, paclet:guide/MultiplicativeNumberTheory])}})}})

({{(Spacer1), ({{(Spacer1)Related Links}, {(WebLink[DocumentationFooterIconsRelatedLinks-NKS.png(Spacer1)NKS|Online, http://www.wolframscience.com/nksonline/index/search.cgi?SearchIndex=PowerMod]) ((WebLink[A New Kind of Science, http://www.wolframscience.com/nksonline/]))}})}})