# Factoring RSA number knowing some B-smooth numbers

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.

• The basic long division algorithm yields quotient and remainder, does this not fit your needs? – yyyyyyy Apr 11 '17 at 21:09