Past exam of the year 1 of the computer science course of the University of Oxford / 2013 / Discrete mathematics, probability and continuous mathematics / 2 / g

Table of contents
- Solution g

Solution

Repeated squaring computes

a, a^{2}, a^{4}, a^{8}, \dots

by successively squaring. The binary representation of the exponent specifies which of these values to multiply. For modular exponentiation, reduce after every multiplication; only a number of steps proportional to the logarithm of the exponent is needed.

Here

13 \equiv 2 (mod 11)

and

17 = 16 + 1

. Successive squares give

2^{2} \equiv 4, 2^{4} \equiv 16 \equiv 5, 2^{8} \equiv 25 \equiv 3, 2^{16} \equiv 9 (mod 11) .

Therefore

1 3^{17} \equiv 2^{16} 2 \equiv 9 \cdot 2 \equiv 7 (mod 11); remainder 7.

 Ancestors (11)

 View article source

 Discussion (0) New discussion

There are no discussions about this article yet.

 Articles by others on the same topic (0)

There are currently no matching articles.

  See all articles in the same topic Create my own version