0

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?

Siong Thye Goh
  • 149,520
  • 20
  • 88
  • 149
  • $2^{1000}$ is actually a pretty small number as far as multiprecision arithmetic goes. –  Jun 13 '17 at 03:00

1 Answers1

2

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}$$

Siong Thye Goh
  • 149,520
  • 20
  • 88
  • 149
  • 1
    I think a more helpful (for him) answer would be to tell him that $a\cdot b \mod c = (a\mod c \cdot b \mod c )\mod c$ and for that reason he can applies modulo at every iteration (extending the relation to any amount of elements) – Anonymous Jun 13 '17 at 02:03
  • 1
    and for this reason he doesn't need to evalue $2^{1000}$ first, which I intuitively think is the point in which he struggles. – Anonymous Jun 13 '17 at 02:04
  • Wonderful suggestion. =) – Siong Thye Goh Jun 13 '17 at 02:04
  • I say this because he said "$2^{1000}$ is too big" – Anonymous Jun 13 '17 at 02:05
  • To compute the requested Power One will use the pow(x,y,z) function in python: pow (2,1000-k, 8*k+1), wich does fast modular exponentiation. But I dont know if there is a similar function in octave. – miracle173 Jun 13 '17 at 03:24