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.