0
$\begingroup$

I have this RSA-crypto question on my exam, to make a long story short, we do not need to go in to all details about the question, but rather the specifics with which I get stuck.

I have no idea how to solve this specific task:

http://s22.postimg.org/rh0vgoaz5/Sk_rmavbild_2015_10_22_kl_22_39_02.png

Sorry that the picture is not uploaded here directly but I don't have enough reputation here to do so, so please click the link.

They are using mod 779 btw.

Now What I don't get is how they can simplify 574^2 to -41. Because from what I see neither Fermat's little theorem or Eulers theorem can be applied here, are they using some other formula? Cause if not, this seems next to impossible to calculate without a calculator, and calculators are not allowed on the best.

Thanks in advance.

$\endgroup$
1
$\begingroup$

http://mathworld.wolfram.com/LongMultiplication.html
http://mathworld.wolfram.com/LongDivision.html

   574
 x 574
------
2870
 4018
+ 2296
------
329476

         422
     -------
779 | 329476
      3116|
      ----v
       1787
       1558
       ----
        2296
        1558
        ----
         738  <- remainder

$738 \equiv 738\hspace{-0.04 in}-\hspace{-0.05 in}779 \equiv -\hspace{.02 in}(779\hspace{-0.04 in}-\hspace{-0.05 in}738) \equiv -\hspace{.02 in}42 \;\;\; \pmod{779}$

$\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.