PreTeXt Sample Book: Abstract Algebra (SAMPLE ONLY)

<section>
    <title>Large Powers of Integers</title>
    <p>
      Computing large powers can be very time-consuming.
      Just as anyone can compute <m>2^2</m> or <m>2^8</m>,
      everyone knows how to compute
      <me>
        2^{2^{1000000} }
      </me>.
      However, such numbers are so large that we do not want to attempt the calculations;
      moreover, past a certain point the computations would not be feasible even if we had every computer in the world at our disposal.
      Even writing down the decimal representation of a very large number may not be reasonable.
      It could be thousands or even millions of digits long.
      However, if we could compute something like <m>2^{37398332 } \pmod{ 46389}</m>,
      we could very easily write the result down since it would be a number between 0 and 46,388.
      If we want to compute powers modulo <m>n</m> quickly and efficiently,
      we will have to be clever.<fn>
      The results in this section are needed only in <xref ref="integers" />
      (not really).
      </fn>
    </p>
    <p>
      The first thing to notice is that any number <m>a</m> can be written as the sum of distinct powers of 2;
      that is, we can write
      <me>
        a = 2^{k_1} + 2^{k_2} + \cdots + 2^{k_n}
      </me>,
      where <m>k_1 \lt k_2 \lt \cdots \lt k_n</m>.
      This is just the binary representation of <m>a</m>.
      For example, the binary representation of 57 is 111001,
      since we can write <m>57 = 2^0 + 2^3 + 2^4 + 2^5</m>.
    </p>
    <p>
      The laws of exponents still work in <m>{\mathbb Z}_n</m>;
      that is, if <m>b \equiv a^x \pmod{ n}</m> and <m>c \equiv a^y \pmod{ n}</m>,
      then <m>bc \equiv a^{x+y} \pmod{ n}</m>.
      We can compute <m>a^{2^k} \pmod{ n}</m> in <m>k</m> multiplications by computing
      <md>
        <mrow>a^{2^0} \pmod{ n}</mrow>
        <mrow>a^{2^1} \pmod{ n }</mrow>
        <mrow>\vdots</mrow>
        <mrow>a^{2^k} \pmod{ n}</mrow>
      </md>.
      Each step involves squaring the answer obtained in the previous step,
      dividing by <m>n</m>, and taking the remainder.
    </p>
    <example xml:id="example-cyclic-repeated-squares">
      <title>Repeated Squares</title>
      <p>
        We will compute <m>271^{321} \pmod{ 481}</m>.
        Notice that
        <me>
          321 = 2^0 +2^6 + 2^8
        </me>;
        hence, computing <m>271^{321} \pmod{ 481}</m> is the same as computing
        <me>
          271^{2^0 +2^6 + 2^8 } \equiv 271^{2^0} \cdot 271^{2^6} \cdot 271^{2^8} \pmod{481}
        </me>.
        So it will suffice to compute
        <m>271^{2^i} \pmod{481}</m> where <m>i = 0, 6, 8</m>.
        It is very easy to see that
        <me>
          271^{2^1}  = \mbox{73,441} \equiv 329 \pmod{481}
        </me>.
        We can square this result to obtain a value for <m>271^{2^2} \pmod{481}</m>:
        <md>
          <mrow>271^{ 2^2}  &amp; \equiv (271^{ 2^1})^2 \pmod{ 481}</mrow>
          <mrow>&amp; \equiv (329)^2 \pmod{ 481}</mrow>
          <mrow>&amp; \equiv \mbox{108,241} \pmod{ 481}</mrow>
          <mrow>&amp; \equiv 16 \pmod{ 481}</mrow>
        </md>.
        We are using the fact that <m>(a^{2^n})^2  \equiv a^{2 \cdot 2^n} \equiv a^{ 2^{n+1} } \pmod{ n}</m>.
        Continuing, we can calculate
        <me>
          271^{ 2^6 } \equiv 419 \pmod{ 481}
        </me>
        and
        <me>
          271^{ 2^8 }  \equiv 16 \pmod{ 481}
        </me>.
        Therefore,
        <md>
          <mrow>271^{ 321} &amp; \equiv 271^{ 2^0 +2^6 + 2^8 } \pmod{ 481}</mrow>
          <mrow>&amp; \equiv 271^{ 2^0 } \cdot 271^{ 2^6 } \cdot 271^{ 2^8 } \pmod{ 481}</mrow>
          <mrow>&amp; \equiv 271 \cdot 419 \cdot 16 \pmod{ 481}</mrow>
          <mrow>&amp; \equiv \mbox{1,816,784} \pmod{ 481}</mrow>
          <mrow>&amp; \equiv 47 \pmod{ 481}</mrow>
        </md>.
      </p>
    </example>

    <p>
      The method of repeated squares will prove to be a very useful tool when we explore <acro>RSA</acro> cryptography.
      To encode and decode messages in a reasonable manner under this scheme,
      it is necessary to be able to quickly compute large powers of integers mod <m>n</m>.
    </p>
    <remark xml:base="sage/cyclic-info.xml">
  <title>Sage</title>
  <p>
    Sage support for cyclic groups is a little spotty <mdash /> but we can still make effective use of Sage and perhaps this situation could change soon.
  </p>
</remark>
  </section>