.. _Extended8ModExp:
.. raw:: html
.. |--| unicode:: U+2013 .. en dash
.. |---| unicode:: U+2014 .. em dash, trimming surrounding whitespace
:trim:
.. This file is part of the OpenCSF eTextbook project. It was
.. auto-generated by scripts from the OpenDSA eTextbook project.
.. See https://OpenCSF.org for more details. OpenCSF is distributed
.. under a Creative Commons Attribution-NonCommercial 4.0 International
.. License (see http://creativecommons.org/licenses/by-nc/4.0/),
.. Copyright (c) 2019-2021 by Michael S. Kirkpatrick. OpenDSA is
.. distributed under an MIT open source license, Copyright (c) 2012-2021
.. by the OpenDSA Project Contributors.
.. avmetadata::
:author: Michael S. Kirkpatrick
:requires:
:satisfies:
:topic:
Extended Example: Parallel Modular Exponentiation
=================================================
Modular exponentiation is a mathematical calculation that is used in a variety
of applications, including public key cryptography. This operation simply
consists of performing an integer exponentiation and applying a modulus. For
instance, 2\ :superscript:`3` mod 7 = 8 mod 7 ≡ 1 mod 7. This parallel form makes
use of the fact that multiplication is associative; if we want to compute
(2\ :superscript:`3` * 5\ :superscript:`4` ) mod 7, we can calculate
2\ :superscript:`3` mod 7 and 5\ :superscript:`4` mod 7 in parallel, then multiply
their results together. This form uses an intentionally slow implementation of
modular exponentiation to illustrate the performance improvement from
parallelism.
.. codeinclude:: SynchProblems/ExtEx-8.c
:linenos: true