1
$\begingroup$

I have recently learned a trick in modular exponentiation that is new to me. By example (as in the linked question/answer above):

$$2^{1386}=2^{2^{10}}\cdot 2^{2^8}\cdot 2^{2^6}\cdot 2^{2^5}\cdot 2^{2^3}\cdot 2^{2^1}\equiv 2^{2^6}\cdot 2^{2^5}\cdot 2^{2^4}\cdot 2^{2^3}\cdot 2^{2^2}\cdot 2^{2^1}\pmod {1387}$$

since it was found that $2^{2^7}\equiv 2^{2^1}\pmod {1387}.$

After a little thought, I stumbled upon the notion that changing the exponentiation base from $2$ to $3$ might yield a similar result, and in fact I found that

$$1386_{10}=10101101010_2=1220100_3$$

Nothing spectacular about this, except when computing $2^{1386}\pmod{1387}$ using a cubing operation instead of squaring:

$$2^3=8\\ 8^3=512\\ 512^3\equiv 512\pmod{1387}$$

So we have that $2^{3^3}\equiv 2^{3^2}\pmod{1387}$, which means that

$$2^{3^6+2\cdot 3^5+2\cdot 3^4+3^2}\equiv 2^{6\cdot 3^2}\equiv 2^{2\cdot 3^3}\equiv 2^{2\cdot 3^2}\equiv 512^2\equiv 1\pmod{1387}$$

This seems to be a very useful result. Using repeated squaring, it took $7$ steps to identify a repeat point like this.

Are there any good references on this particular feature of modular exponentiation? In this question I was attempting to apply the above logic to Mersenne Primes (without success).

One obvious difficulty with this process is that there is no guarantee that a given base will produce effective results; this was especially true in my trials with Mersenne Primes, where finding an exponent that would produce a "small" repeat proved very difficult. So I would like to get information on the theory surrounding this topic to perhaps improve my calculations.

$\endgroup$
2
+50
$\begingroup$

Here is a bit information regarding basic theory and certain applications of modular exponentiation.

Basics: Elementary Number Theory

As far as I know modular exponentiation is, embedded within modular arithmetic, a relatively small part of elementary number theory. So, you will presumably not find complete books dealing with this theme. The basic information can be found by looking through some of the books about elementary number theory. See e.g. chapter $4$ of Elementary Number Theory with Applications from Thomas Koshy with a small section about Modular Exponentiation (and a comment, which may surprise you).

Here's a nice online summary about Modular Arithmetic with a special section about Modular Exponentiation.

Applications: Finite Fields and Cryptography

Much less elementary are applications using modular exponentiation. They can be found in finite fields and cryptography, whereby finding fast algorithms is the main stimulus. Here are two papers just to give you a first impression. These papers are not necessarily representative for the current development, since I'm not an expert (only sometimes a practitioner using certain cryptographic techniques).

Finite Fields: In Algorithms for Exponentiation in Finite Fields you will see how fast exponentiation in finite fields $\mathbb{F}_q^n$ is presented with $q$ a small prime power (not only base $2$) and polynomial basis exponentiation in $\mathbb{F}_2^n$.

Cryptography: The other paper which could be of interest for you shows how modular exponentiation is employed for creating a fast RSA algorithm. In the paper Modular Exponentiation using Parallel Multipliers modular exponentiation of long integers is the main theme for developing fast algorithms. Maybe you also want to look at the paper about Spectral Modular Exponentiation with section $4.1$ talking about Fermat/Mersenne Ring Arithmetic.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.