1
$\begingroup$

Hi I am studying for an exam and having some problems solving one of the questions. It reads as follows: Factor $$N=44370047$$ using Quadratic Sieve by using the information that you get from squaring the following numbers modulo N.

$$33965, 2145407, 19416874, 15213395$$

I know how the algorithm works, i.e $$19416874^2\mod 44370047 = 9 = 3^2$$

And then calculating $$gcd(19416874-3,44370047)$$

I can do this using the computer easily but I have no idea how to calculate the modulo of numbers of this size by hand. Any help would be greatly appreciated as I am currently banging my head against the wall.

Improve this question
$\endgroup$
1
  • 2
    $\begingroup$ The basic long division algorithm yields quotient and remainder, does this not fit your needs? $\endgroup$
    – yyyyyyy
    Apr 11, 2017 at 21:09

1 Answer 1

Reset to default
1
$\begingroup$

You probably know the algorithms to multiply and divide numbers by hand; that's what you do. Yes, it will be painful. No, there's no other way, but I don't think you will be expected to do it in an exam (confirm that with your instructor, however).

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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