{"id":66840,"date":"2026-10-15T09:20:26","date_gmt":"2026-10-15T06:20:26","guid":{"rendered":"https:\/\/wpcalc.com\/en\/?p=66840"},"modified":"2026-10-15T09:20:26","modified_gmt":"2026-10-15T06:20:26","slug":"modular-exponentiation-calculator","status":"publish","type":"post","link":"https:\/\/wpcalc.com\/en\/mathematics\/modular-exponentiation-calculator\/","title":{"rendered":"Modular Exponentiation Calculator"},"content":{"rendered":"<section class=\"not-prose calculator-box\" aria-labelledby=\"calculator-title\"><div class=\"flex items-baseline sm:items-center justify-between gap-2 sm:gap-3\"><div class=\"flex flex-col sm:flex-row sm:items-center gap-2\"><span class=\"icon icon-calculator text-primary-700! text-base! dark:text-primary-300!\" aria-hidden=\"true\"><\/span><h2 id=\"calculator-title\" class=\"text-lg font-display font-bold\">Compute a Power Modulo m<\/h2><\/div><div class=\"calcdash-favorite group\">\n  <button type=\"button\" class=\"favorite\" id=\"favorite\" data-favorite-id=\"66840\" data-favorite-title=\"Modular Exponentiation\" data-favorite-url=\"https:\/\/wpcalc.com\/en\/mathematics\/modular-exponentiation-calculator\/\" data-favorite-excerpt=\"Computes b^e mod m instantly, even when the power has hundreds of digits, using fast square-and-multiply exponentiation. Enter a base, a non-negative exponent and a positive modulus, and optionally see every repeated-squaring step.\" aria-label=\"Add to Favorites\" data-favorite-icon=\"icon icon-arithmetic\">\n    <span class=\"icon icon-shape-star-empty\" aria-hidden=\"true\"><\/span>\n  <\/button>\n  <div class=\"calcdash-favorite__tip\" aria-hidden=\"true\">\n   <span class=\"favorite-tooltip\" id=\"favorite-tooltip\"><\/span>\n  <\/div>\n  <span class=\"sr-only\" role=\"status\" id=\"favorite-status\"><\/span>\n<\/div><\/div><form action=\"https:\/\/wpcalc.com\/en\/mathematics\/modular-exponentiation-calculator\/\" method=\"POST\" class=\"calculator\" id=\"calculator-66840\" data-post=\"66840\"><fieldset class=\"fieldset-input is-1\"><legend class=\"sr-only\">Input Fields<\/legend><div class=\"field has-term\" id=\"input-1\"><label for=\"field-1\">Base (b)<\/label><div class=\"term\">b<\/div>  <div class=\"absolute bottom-0 left-16 top-8 w-2 h-0.5 bg-blue-500\"><\/div><input type=\"number\" name=\"base_b\" id=\"field-1\" aria-describedby=\"calc-info-1\" placeholder=\"e.g. 3 or -12\" step=\"1\" value=\"3\"\/><small id=\"calc-info-1\">Any whole number, positive or negative<\/small><\/div><div class=\"field has-term\" id=\"input-2\"><label for=\"field-2\">Exponent (e)<\/label><div class=\"term\">e<\/div>  <div class=\"absolute bottom-0 left-16 top-8 w-2 h-0.5 bg-blue-500\"><\/div><input type=\"text\" name=\"exponent_e\" id=\"field-2\" aria-describedby=\"calc-info-2\" data-number inputmode=\"decimal\" autocomplete=\"off\" spellcheck=\"false\" placeholder=\"e.g. 644\" min=\"0\" value=\"644\"\/><small id=\"calc-info-2\">Non-negative whole number; can be far too large for b\u1d49 to be computed directly<\/small><\/div><div class=\"field has-term\" id=\"input-3\"><label for=\"field-3\">Modulus (m)<\/label><div class=\"term\">m<\/div>  <div class=\"absolute bottom-0 left-16 top-8 w-2 h-0.5 bg-blue-500\"><\/div><input type=\"text\" name=\"modulus_m\" id=\"field-3\" aria-describedby=\"calc-info-3\" data-number inputmode=\"decimal\" autocomplete=\"off\" spellcheck=\"false\" placeholder=\"e.g. 645\" min=\"1\" value=\"645\"\/><small id=\"calc-info-3\">Positive whole number<\/small><\/div><div class=\"field is-checkbox\" id=\"input-4\"><input type=\"checkbox\" id=\"field-4\" value=\"1\" checked=\"checked\"\/><label for=\"field-4\">Show repeated-squaring steps<\/label><\/div><\/fieldset><div class=\"buttons\"><button type=\"submit\" data-text=\"Re-Calculate\" id=\"calculate-button\" data-post=\"66840\">Calculate<\/button><button type=\"reset\">Reset<\/button><\/div><div class=\"field is-checkbox hidden!\" id=\"field-auto-calc\"><input type=\"checkbox\" id=\"auto-calc\"><label for=\"auto-calc\">Calculate automatically<\/label><small>If enabled, the result will update automatically when you change any value.<\/small><\/div><div class=\"fieldset-result is-hidden\" aria-labelledby=\"result-title\" aria-live=\"polite\" role=\"region\"> <h3 class=\"result-title bg-gradient-to-r from-primary-50 to-gray-50 dark:from-primary-900 dark:to-gray-800\" id=\"result-title\"><span class=\"icon icon-s-pulse\" aria-hidden=\"true\"><\/span> Your Results<\/h3><div class=\"result-box\"><div class=\"field-result\" id=\"output-1\"><span class=\"field-title\"><span>Result (b\u1d49 mod m)<\/span><span class=\"result-term\">b\u1d49 mod m<\/span><\/span><span class=\"field-value\" id=\"result-1\"><\/span><button type=\"button\" class=\"copy-result\" data-tooltip=\"Copy Result\" aria-label=\"Copy Result\"><span class=\"copy-icon icon icon-document-copy\" aria-hidden=\"true\"><\/span><\/button><\/div><div class=\"field-result\" id=\"output-2\"><span class=\"field-title\"><span>Reduced base (b mod m)<\/span><span class=\"result-term\">b mod m<\/span><\/span><span class=\"field-value\" id=\"result-2\"><\/span><button type=\"button\" class=\"copy-result\" data-tooltip=\"Copy Result\" aria-label=\"Copy Result\"><span class=\"copy-icon icon icon-document-copy\" aria-hidden=\"true\"><\/span><\/button><\/div><div class=\"field-result is-column\" id=\"output-3\"><span class=\"field-title\"><span>Repeated-squaring steps<\/span><\/span><span class=\"field-value\" id=\"result-3\"><\/span><button type=\"button\" class=\"copy-result\" data-tooltip=\"Copy Result\" aria-label=\"Copy Result\"><span class=\"copy-icon icon icon-document-copy\" aria-hidden=\"true\"><\/span><\/button><\/div><\/div><div class=\"result-actions\"><button type=\"button\" class=\"copy-link\"><svg viewBox=\"0 0 20 20\" fill=\"currentColor\" aria-hidden=\"true\"><path d=\"M12.232 4.232a2.5 2.5 0 0 1 3.536 3.536l-1.225 1.224a.75.75 0 0 0 1.061 1.06l1.224-1.224a4 4 0 0 0-5.656-5.656l-3 3a4 4 0 0 0 .225 5.865.75.75 0 0 0 .977-1.138 2.5 2.5 0 0 1-.142-3.667l3-3Z\"\/><path d=\"M11.603 7.963a.75.75 0 0 0-.977 1.138 2.5 2.5 0 0 1 .142 3.667l-3 3a2.5 2.5 0 0 1-3.536-3.536l1.225-1.224a.75.75 0 0 0-1.061-1.06l-1.224 1.224a4 4 0 1 0 5.656 5.656l3-3a4 4 0 0 0-.225-5.865Z\"\/><\/svg><span class=\"copy-link__text\">Copy link to this calculation<\/span><\/button><span class=\"sr-only\" role=\"status\" id=\"copy-link-status\"><\/span><\/div><\/div><a href=\"#respond\" class=\"hidden transition-opacity duration-300 opacity-0 w-50 text-sm justify-center items-center gap-2 px-4 py-2 rounded bg-gray-200 text-gray-700 hover:bg-gray-300\" id=\"leave-comment\"><span class=\"icon icon-comments\" aria-hidden=\"true\"><\/span>Leave a Comment<\/a><\/form><\/section><section id=\"calc-reactions\" class=\"not-prose hidden my-12 bg-gradient-to-r from-primary-50 to-gray-50 border border-indigo-100 rounded-xl px-6 py-4 shadow-sm\" data-post=\"66840\" aria-live=\"polite\" aria-labelledby=\"calc-reactions-title\"><p id=\"calc-reactions-title\" class=\"text-sm text-gray-500 text-center mb-2\">How did this result make you feel?<\/p><div role=\"group\" aria-labelledby=\"calc-reactions-title\" class=\"grid grid-cols-3 sm:flex sm:flex-row sm:justify-around gap-4 sm:items-center sm:flex-wrap\"><button type=\"button\" aria-pressed=\"false\" class=\"reaction-btn flex flex-col items-center gap-1 text-sm text-gray-700 hover:text-primary-600 cursor-pointer transition-transform hover:scale-105\" data-reaction=\"like\"><span class=\"reaction-count\" data-reaction-count=\"like\">0<\/span><span class=\"reaction text-3xl\" aria-hidden=\"true\">\ud83d\ude00 <\/span><span class=\"reaction-description font-medium\">Like <\/span><\/button><button type=\"button\" aria-pressed=\"false\" class=\"reaction-btn flex flex-col items-center gap-1 text-sm text-gray-700 hover:text-primary-600 cursor-pointer transition-transform hover:scale-105\" data-reaction=\"helpful\"><span class=\"reaction-count\" data-reaction-count=\"helpful\">0<\/span><span class=\"reaction text-3xl\" aria-hidden=\"true\">\ud83d\udca1 <\/span><span class=\"reaction-description font-medium\">Helpful <\/span><\/button><button type=\"button\" aria-pressed=\"false\" class=\"reaction-btn flex flex-col items-center gap-1 text-sm text-gray-700 hover:text-primary-600 cursor-pointer transition-transform hover:scale-105\" data-reaction=\"confused\"><span class=\"reaction-count\" data-reaction-count=\"confused\">0<\/span><span class=\"reaction text-3xl\" aria-hidden=\"true\">\ud83d\ude15 <\/span><span class=\"reaction-description font-medium\">Confused <\/span><\/button><button type=\"button\" aria-pressed=\"false\" class=\"reaction-btn flex flex-col items-center gap-1 text-sm text-gray-700 hover:text-primary-600 cursor-pointer transition-transform hover:scale-105\" data-reaction=\"disappointed\"><span class=\"reaction-count\" data-reaction-count=\"disappointed\">0<\/span><span class=\"reaction text-3xl\" aria-hidden=\"true\">\ud83d\ude1e <\/span><span class=\"reaction-description font-medium\">Disappointed <\/span><\/button><button type=\"button\" aria-pressed=\"false\" class=\"reaction-btn flex flex-col items-center gap-1 text-sm text-gray-700 hover:text-primary-600 cursor-pointer transition-transform hover:scale-105\" data-reaction=\"inaccurate\"><span class=\"reaction-count\" data-reaction-count=\"inaccurate\">0<\/span><span class=\"reaction text-3xl\" aria-hidden=\"true\">\u274c <\/span><span class=\"reaction-description font-medium\">Inaccurate <\/span><\/button><\/div><div id=\"reaction-message\" class=\"hidden mt-8 rounded-md border border-primary-100 bg-white\/50 backdrop-blur-sm px-4 py-2 text-sm text-center shadow-sm\"><\/div><\/section><div class=\"calcdash-ad not-prose calcdash-ad--calc_result calcdash-ad--in-article\"><ins class=\"adsbygoogle\" style=\"display:block\" data-ad-client=\"ca-pub-1721569815777345\" data-ad-slot=\"6317458308\" data-ad-layout=\"in-article\" data-ad-format=\"fluid\"><\/ins><script>(adsbygoogle = window.adsbygoogle || []).push({});<\/script><\/div>\n<style id=\"wpcoderpro-inline-1\">.formula-box {\r\n\tborder-bottom: none !important;\r\n}<\/style><section class=\"formula-box\" aria-labelledby=\"formula-title\">\r\n\t<div id=\"formula-title\" class=\"not-prose font-display mb-4\"><span class=\"icon icon-formula\" aria-hidden=\"true\"><\/span><h2>Modular Exponentiation Formula<\/h2><\/div>\r\n\t<figure class=\"not-prose formula\">\r\n\t\t<figcaption class=\"formula-title\">Formula<\/figcaption>\r\n\t\t<div class=\"text-base text-gray-800\" id=\"formula\">\n\\[ c \\;=\\; b^e \\bmod m \\]\n\\[ e = \\sum_{k=0}^{n} e_k\\,2^k \\;\\;\\Longrightarrow\\;\\; b^e \\;\\equiv\\; \\prod_{k:\\; e_k = 1} \\bigl(b^{2^k} \\bmod m\\bigr) \\pmod{m}, \\qquad b^{2^k} \\equiv \\bigl(b^{2^{k-1}}\\bigr)^2 \\pmod{m} \\]\n<\/div>\r\n\t<\/figure>\r\n\t<\/p>\n<p><strong>Where:<\/strong><\/p>\n<ul>\n<li>\\(b\\) \u2014 the base (any whole number)<\/li>\n<li>\\(e\\) \u2014 the exponent (a non-negative whole number)<\/li>\n<li>\\(m\\) \u2014 the modulus (a positive whole number)<\/li>\n<li>\\(e_k\\) \u2014 the bits of \\(e\\) in its binary expansion<\/li>\n<li>\\(c\\) \u2014 the result: the remainder of \\(b^e\\) upon division by \\(m\\)<\/li>\n<\/ul>\n<p>The first line defines modular exponentiation. The second line is the square-and-multiply (binary exponentiation) identity the calculator uses: the exponent is decomposed into powers of two, the powers \\(b^{2^k}\\) are found by repeated squaring, and only the ones matching set bits are multiplied together \u2014 all modulo \\(m\\), so the intermediate numbers never explode.<\/p>\n<p>\r\n<\/section>\n<style id=\"wpcoderpro-inline-459\">.calculation-box {\r\n\tborder-bottom: none !important;\r\n}<\/style><section id=\"calculation\" class=\"calculation-box\" aria-labelledby=\"calculation-title\">\r\n\t<div id=\"calculation-title\" class=\"not-prose font-display\"><span class=\"icon icon-unordered-list\" aria-hidden=\"true\"><\/span><h2>Modular Exponentiation \u2013 Calculation Example<\/h2><\/div>\r\n\r\n<\/p>\n<p><strong>Example:<\/strong> compute \\(3^{644} \\bmod 645\\), the calculator's default values. The integer \\(3^{644}\\) has 308 digits, so evaluating the power first and reducing afterwards is hopeless.<\/p>\n<p><strong>Step 1 \u2014 reduce the base:<\/strong> \\(3 \\bmod 645 = 3\\).<\/p>\n<p><strong>Step 2 \u2014 write the exponent in binary:<\/strong><\/p>\n<p>\\[ 644 = 512 + 128 + 4 = 1010000100_2 \\]<\/p>\n<p>Repeated squaring modulo 645 gives \\(3^4 \\equiv 81\\), \\(3^{128} \\equiv 396\\) and \\(3^{512} \\equiv 111 \\pmod{645}\\) for the set bits.<\/p>\n<p><strong>Step 3 \u2014 multiply those values, reducing mod 645 each time:<\/strong><\/p>\n<p>\\[ 3^{644} \\equiv 81 \\times 396 \\times 111 \\equiv 471 \\times 111 \\equiv 52281 \\equiv 36 \\pmod{645} \\]<\/p>\n<p><strong>Result:<\/strong> \\(3^{644} \\bmod 645 = 36\\). The algorithm needed only 9 squarings and 3 multiplications \u2014 12 modular operations instead of the 643 a naive approach would require.<\/p>\n<p>\n\r\n<\/section>\n<h2>How to Use the Calculator<\/h2>\n<ol>\n<li>Enter the <strong>Base (b)<\/strong> \u2014 any whole number, positive or negative.<\/li>\n<li>Enter the <strong>Exponent (e)<\/strong> \u2014 a non-negative whole number. It may be far too large for \\(b^e\\) to be computed directly; that is exactly what this tool is for.<\/li>\n<li>Enter the <strong>Modulus (m)<\/strong> \u2014 any positive whole number.<\/li>\n<li>Leave <strong>Show repeated-squaring steps<\/strong> ticked if you want the binary expansion of the exponent and a table of every squaring step; untick it for a plain answer.<\/li>\n<li>Read <strong>Result (b\u1d49 mod m)<\/strong>, the <strong>Reduced base (b mod m)<\/strong>, and the step-by-step breakdown.<\/li>\n<\/ol>\n<h2>What Is Modular Exponentiation?<\/h2>\n<p>Modular exponentiation answers the question: <em>what is the remainder when \\(b^e\\) is divided by \\(m\\)?<\/em> The result always lies between \\(0\\) and \\(m-1\\). Equivalently, it is the number \\(c\\) with \\(0 \\le c &lt; m\\) such that \\(b^e \\equiv c \\pmod{m}\\). For example, \\(3^{644} \\bmod 645 = 36\\) means \\(3^{644}\\) leaves a remainder of 36 when divided by 645.<\/p>\n<p>The naive way \u2014 computing \\(b^e\\) and then taking the remainder \u2014 fails quickly. \\(3^{644}\\) already has 308 digits, and cryptographic applications routinely use exponents with hundreds of digits, where \\(b^e\\) would have more digits than there are atoms in the universe. The fix is the square-and-multiply method: write the exponent in binary, obtain \\(b^{2^k} \\bmod m\\) by repeatedly squaring and reducing, then multiply together only the values corresponding to set bits. This needs just \\(O(\\log e)\\) modular multiplications instead of \\(e-1\\), and because every intermediate result is reduced modulo \\(m\\), no number ever grows beyond roughly \\(m^2\\).<\/p>\n<p>Modular exponentiation is the workhorse of public-key cryptography. RSA encryption and decryption are a single modular exponentiation with a huge modulus; Diffie\u2013Hellman key exchange and the ElGamal scheme rely on it too. It also powers primality tests such as the Fermat and Miller\u2013Rabin tests, which check whether \\(a^{n-1} \\equiv 1 \\pmod n\\) \u2014 you can explore the underlying number theory with our <a href=\"https:\/\/wpcalc.com\/en\/mathematics\/fermats-little-theorem\/\">Fermat's Little Theorem<\/a> and <a href=\"https:\/\/wpcalc.com\/en\/mathematics\/eulers-theorem\/\">Euler's Theorem<\/a> calculators.<\/p>\n<p>The step display makes the algorithm transparent: the table lists every bit position \\(k\\) of the exponent next to \\(b^{2^k} \\bmod m\\), the bold rows are the ones actually used, and their product (reduced mod \\(m\\)) is your answer. This is precisely what computer algebra systems do internally, and seeing it once is the best way to understand why huge exponents are cheap.<\/p>\n<h2>Assumptions, Limits and Tips<\/h2>\n<ul>\n<li><strong>Exponent must be non-negative.<\/strong> A negative exponent would require the modular inverse of \\(b\\), which exists only when \\(\\gcd(b, m) = 1\\). To handle that case, first find the inverse with our <a href=\"https:\/\/wpcalc.com\/en\/mathematics\/multiplicative-inverse-modulo\/\">Multiplicative Inverse Modulo<\/a> calculator and then use its output as the base with a positive exponent.<\/li>\n<li><strong>Modulus must be positive.<\/strong> If \\(m = 1\\), every integer is congruent to 0, so the result is 0 \u2014 that is mathematically correct, not an error.<\/li>\n<li><strong>Negative bases are fine.<\/strong> The base is first reduced to its least non-negative residue \\(b \\bmod m\\), so \\(-12\\) and \\(m - 12\\) give the same answer.<\/li>\n<li><strong>Exponent 0 gives \\(1 \\bmod m\\)<\/strong> (which is 0 only when \\(m = 1\\)), consistent with \\(b^0 = 1\\).<\/li>\n<li><strong>Size limits:<\/strong> the base and modulus may each have up to 1000 digits, and the exponent may be as large as \\(10^{18}\\). Since the algorithm is logarithmic in the exponent, even that runs instantly.<\/li>\n<li><strong>Check answers with a different route:<\/strong> for a composite modulus you can split the computation into prime-power pieces and recombine them \u2014 try our <a href=\"https:\/\/wpcalc.com\/en\/mathematics\/chinese-remainder-theorem\/\">Chinese Remainder Theorem<\/a> calculator to verify results independently.<\/li>\n<\/ul>\n","protected":false},"excerpt":{"rendered":"<p>Computes b^e mod m instantly, even when the power has hundreds of digits, using fast square-and-multiply exponentiation. Enter a base, a non-negative exponent and a positive modulus, and optionally see every repeated-squaring step.<\/p>\n","protected":false},"author":3168,"featured_media":0,"comment_status":"open","ping_status":"","sticky":false,"template":"","format":"standard","meta":{"_acf_changed":false,"footnotes":""},"categories":[7],"tags":[72],"class_list":["post-66840","post","type-post","status-publish","format-standard","hentry","category-mathematics","tag-arithmetic-calculators"],"acf":[],"_links":{"self":[{"href":"https:\/\/wpcalc.com\/en\/wp-json\/wp\/v2\/posts\/66840","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/wpcalc.com\/en\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/wpcalc.com\/en\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/wpcalc.com\/en\/wp-json\/wp\/v2\/users\/3168"}],"replies":[{"embeddable":true,"href":"https:\/\/wpcalc.com\/en\/wp-json\/wp\/v2\/comments?post=66840"}],"version-history":[{"count":1,"href":"https:\/\/wpcalc.com\/en\/wp-json\/wp\/v2\/posts\/66840\/revisions"}],"predecessor-version":[{"id":67123,"href":"https:\/\/wpcalc.com\/en\/wp-json\/wp\/v2\/posts\/66840\/revisions\/67123"}],"wp:attachment":[{"href":"https:\/\/wpcalc.com\/en\/wp-json\/wp\/v2\/media?parent=66840"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/wpcalc.com\/en\/wp-json\/wp\/v2\/categories?post=66840"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/wpcalc.com\/en\/wp-json\/wp\/v2\/tags?post=66840"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}