Modulo operations in octave

Question

I have to calculate mod$(2^{1000-k},8k+1)$ (k≤50)with octave. How can I do that? $2^{1000}$ is too big...

I think I can split the modulo operation but the code becomes heavy. Is there a way to set octave to manage these huge number?

Answer 1

Edit: (thanks to Anonymous' suggestion):

To compute $$2^{1000-k} \mod 8k+1.$$

We do not need to compute the value of $2^{1000-k}$ explicitly.

In fact, we can use the properties that $$(ab \mod c) = (a \mod c)( b \mod c)$$

Looping through $1000-k$ is manageable for a computer.

You just have to repeatedly multiply by $2$ and take modulo $8k+1$ for $1000-k$ times.

I have attached a code in Python.

A faster approach would be exponentiation by squaring which makes use of the idea that

$$x^n = \begin{cases} x(x^2)^{\frac{n-1}{2}} & n \text{ is odd} \\ (x^2)^{\frac{n}{2}} & n \text{ is even}\end{cases}$$