Modulus Function

Question

I am watching a tutorial an i saw how to use the modulus they said if 20/7 = 2.8571422857 you must subtract the whole number then multiply it by the divisor

now am trying to understand a Public key encryption example this person said 595^611 mod 899 = 119

i cant see how he got the 119 which is w

is video is http://www.youtube.com/watch?v=FxwmpsRCuqQ

what i did was take 611 divide it by 899 then i got 611 when i raise 585 to 611 as in 595^611 i got math error on my calculator please any one can you assist me how he got to that number are is he wrong? oh if u illustrating cann u use umber that can be process by calculator

Answer 1

Well, $899=30^2-1=29\cdot 31$ is its prime decomposition. We can solve separately $595^{611}$ both modulo $29$ and modulo $31$.

$595=600-5=20\cdot 30 -5 = 20\cdot 29+20\ -5 \equiv 15 \pmod{29}$, similarly
$595=20\cdot 31 -20\ -5\equiv -25\equiv 6 \pmod{31}$

The powers modulo a prime $p$ are always periodic, with period a divisor of $p-1$. (Euler-Fermat: $a^{p-1}\equiv 1 \pmod p$ if $a\not\equiv 0\pmod p$.)

So, for the exponents, we have $611\equiv 23 \pmod{28}$ and $611\equiv 11 \pmod{30}$.

From these, we get $595^{611}\equiv {15}^{611}\equiv {15}^{23} \pmod{29}$ and $595^{611}\equiv 6^{11}\pmod{31}$.

Now you can start to calculate the powers of $15$ modulo $29$, e.g. $15^2=225\equiv 22\equiv -7 \pmod{29}$, then $15^3\equiv -7\cdot 15 =-105 \equiv -18\equiv 11 \pmod{29}$, $\ 15^4\equiv 11\cdot 15=165\equiv 20$, and so on...

Finally, when you get $595^{611}\equiv x\pmod{29}$ and $595^{611}\equiv y\pmod{31}$, you can find/verify the required remainder modulo $899$.

Answer 2

Computing $595^{611} \mod 899$ is something most calculators can not do. First, they can not even compute $595^{611}$. Second, even if they could, the result would have to be exact, which, again, most can not do. Some high-end calculators by HP and TI can do this, and these may even have built in routines to compute $a^b mod\ c$.

If you want do this computation, you have to program a loop which gets appropriate powers of $595$ and gets their remainder mod $899$. A simple version would be

$\begin{align} &a = 595\\ &b = 611\\ &c = 899\\ &ans = 1\\ &for\ i = 1\ to\ b\\ &\quad ans = ans \times b\\ &\quad if\ ans>c\ then \ ans = ans\ mod\ c\\ \end{align} $

For large numbers, you would do repeated squaring of $ans$ and multiplying by $a$ using the binary representation of $b$.

All this is very well known. The subject to look up is "arbitrary precision arithmetic".