Scribd Logo
Upload

Welcome to Scribd!

  • 93 views

    Modular Exponentiation - Article

    Uploaded by

    Aebee Alcaraz
    The document discusses modular exponentiation and describes an efficient method called successive squaring. It explains that to compute ab mod m, one can successively square b until reaching the largest power less than or equal to the exponent a and then multiply the appropriate squares. This allows computation of large powers with far fewer multiplications than naive exponentiation. Python code is provided to implement successive squaring to compute modular powers. Examples are worked out by hand and with the code.

    Copyright:

    © All Rights Reserved
    Download as PDF, TXT or read online from Scribd

    Modular Exponentiation - Article

    Uploaded by

    Aebee Alcaraz
    93 views4 pages
    The document discusses modular exponentiation and describes an efficient method called successive squaring. It explains that to compute ab mod m, one can successively square b until reaching the largest power less than or equal to the exponent a and then multiply the appropriate squares. This allows computation of large powers with far fewer multiplications than naive exponentiation. Python code is provided to implement successive squaring to compute modular powers. Examples are worked out by hand and with the code.

    Original Description:

    modulo arithmetic

    Original Title

    Modular Exponentiation.article

    Copyright

    © © All Rights Reserved

    Available Formats

    PDF, TXT or read online from Scribd

    Did you find this document useful?

    Is this content inappropriate?

    The document discusses modular exponentiation and describes an efficient method called successive squaring. It explains that to compute ab mod m, one can successively square b until reaching the largest power less than or equal to the exponent a and then multiply the appropriate squares. This allows computation of large powers with far fewer multiplications than naive exponentiation. Python code is provided to implement successive squaring to compute modular powers. Examples are worked out by hand and with the code.

    Copyright:

    © All Rights Reserved
    Download as PDF, TXT or read online from Scribd
    Download as pdf or txt
    93 views4 pages

    Modular Exponentiation - Article

    Uploaded by

    Aebee Alcaraz
    The document discusses modular exponentiation and describes an efficient method called successive squaring. It explains that to compute ab mod m, one can successively square b until reaching the largest power less than or equal to the exponent a and then multiply the appropriate squares. This allows computation of large powers with far fewer multiplications than naive exponentiation. Python code is provided to implement successive squaring to compute modular powers. Examples are worked out by hand and with the code.

    Copyright:

    © All Rights Reserved
    Download as PDF, TXT or read online from Scribd
    Download as pdf or txt
    of 4

    Modular Exponentiation

    What is the fastest way to compute a large integer power of a number modulo
    m?
    For instance, suppose I want to compute 460 mod 69. One way to do this
    is to just compute 460 in Z and then reduce the answer:

    460 = 1329227995784915872903807060280344576

    modulo 69. This gives the result 460 ≡ 58 (mod 69). This seems like a lot
    of work just to get to the number 58, so one naturally wonders if there is an
    easier way? The answer is yes.
    Throughout this lecture we work with a fixed modulus m. We will do arith-
    metic with congruence classes, so we are working in the ring Z/mZ. We will
    write a as shorthand for [a]m (the congruence class of a modulo m). Here
    a = [a]m stands for the congruence class of all integers x such that x ≡ a
    (mod m); this is the set of all integers of the form a + mk, for k ∈ Z.
    Let me remind you that a = c iff a ≡ c (mod m).
    Let me also remind you that the set Z/mZ can be written as {a : 0 ≤ a ≤
    m − 1}.
    We are going to use congruence classes to do our computations since it is
    more convenient to write equalities instead of congruences at each step.
    The main point in computing with congruence classes modulo m is that
    we have stipulated that m = 0 but all the other rules of algebra still hold,
    except that we cannot necessarily make sense of division.
    We can always rewrite a congruence class using a different choice of repre-
    sentative, because congruence classes are equivalence classes. When doing
    multiplication, addition, or subtraction we can always reduce the answer to
    a class of the form a where 0 ≤ a ≤ m − 1 or 0 ≤ |a| ≤ m−12 .

    This reduction process means that numbers don’t get too large as we com-
    pute large powers in modular arithmetic.
    Let’s revisit the computation of 460 mod 69. This the same as computing
    (4)60 in Z/69Z. We’d like to compute it by hand with the least amount of
    effort.

    1
    We start by successively squaring 4 until we get to the biggest exponent less
    than or equal to 60 (in this case it is 32, since the next square would have
    exponent 64, which exceeds 60):

    j 1 2 4 8 16 32
    (4)j 4 16 49 55 58 52

    Now express the exponent 60 in binary: 60 = 32 + 16 + 8 + 4 (or (111100)2 ).


    Hence we have

    (4)60 = (4)32+16+8+4 = (4)32 (4)16 (4)8 (4)4 = 52 · 58 · 55 · 49


    = (−17) · (−11) · (−14) · (−20) = 187 · 280 = (−20) · 4
    = −80 = −11 = 58.

    How many (modular) multiplications did we do? We squared 5 times to get


    the table of successive squares, so that’s 5. Then we had to multiply four of
    them together, because the binary expansion of 60 has four 1s. That took
    another 3 multiplications.
    So, instead of doing 59 multiplications to compute the 60th power of 4, we
    did it using only a total of 8 multiplications, using the method of successive
    squaring.
    You might think that this is best possible, but further improvements could
    be made. If we knew about Euler’s theorem, for instance, the number of
    multiplications needed can be further reduced to just 4.
    For another example, let’s compute (2)100 modulo 101. By successive squar-
    ing we get

    (2)2 = 4, (2)4 = 16, (2)8 = 256 = 54,


    (2)16 = 2916 = 88 = −13, (2)32 = 169 = 68 = −33,
    (2)64 = 1089 = 79 = −22.

    Now the binary expansion of 100 = 64 + 32 + 4 is (1100100)2 , so we can get


    the 100th power of 2 by doing 2 more (modular) multiplications:

    (2)100 = (2)64+32+4 = (2)64 · (2)32 · (2)4 = (−22) · (−33) · (16)


    = 726 · 16 = 19 · 16 = 304 = 1.

    So (2)100 = 1. In other words, if x ≡ 2 (mod 101) then x100 ≡ 1 (mod 101).

    2
    The computation of (2)100 = 1 we just did required just 6 + 2 = 8 modular
    multiplications.
    It should be pointed out that by Fermat’s Little Theorem the answer can be
    obtained with no computation at all. Fermat’s Little Theorem is a special
    case of Euler’s Theorem.
    The method of successive squaring is easy to implement on a computer.
    First, let’s look at code that converts a given number n to binary.

    def binary(n):
    """returns the binary expansion of n"""
    answer = "" # empty string
    while n>0:
    if n % 2 == 1:
    answer = "1"+answer # prepend the bit "1"
    else:
    answer = "0"+answer # prepend the bit "0"
    n = n//2
    return answer

    In this code, the % operator computes the integer remainder while the //
    operator computes the integer quotient.
    Putting the code into a text file named binary.py and then starting a
    terminal positioned in the same folder allows us to import and run the code,
    as usual:

    $ python
    >>> from binary import *
    >>> binary(60)
    ’111100’
    >>> binary(100)
    ’1100100’
    >>> quit()
    $

    Now we modify the binary conversion code slightly to compute modular


    powers by the method of successive squaring.

    def modpower(b,e,n):

    3
    """returns the value of b to the e-th power mod n
    computed by the method of successive squaring."""
    result = 1 # to get started
    s,q = b,e # s=current square, q=current quotient
    while q > 0:
    if q%2 == 1:
    result = (s * result) % n
    s = (s * s) % n # compute the next square
    q = q//2 # compute the next quotient
    return result

    If we put the code into a plain text file named modpower.py then we can
    import it and run it in a terminal, as usual.

    $ python
    >>> from modpower import *
    >>> modpower(4,60,69)
    58
    >>> modpower(2,100,101)
    1
    >>> quit()

    This agrees with what we got by hand in the examples considered in this
    lecture.

    You might also like