How to factorise large number without calculator? I would like to factorise $496241$. I know the answer is $677 \times 733$. But I don't know how to get there. 
Here is the full question: 
"A message has been encoded using RSA with a modulus of $m = p q = 496241$ (with
$p$ and $q$ being primes) and encoding exponent of $218821$.
You are advised that $\{13631, 142703\}$ is a valid encoding–decoding pair for the same modulus, $m$.
(a) Use this information to determine $\phi(m)$ for this modulus.
(Using software to directly factorise $m$ is not a valid option for doing this part.)
(b) Verify your answer by determining the primes $p$ and $q$.
Show how these combine to give both $m$ and $\phi(m)$."
I need it so I can solve (a), and it says I cannot use software to directly factorise m. So I guess pen and paper. But there are not tutorial online. Thanks
 A: This answer describes the algorithm to find $\phi(m)$ from a pair $(e,d)$, like your $(e,d) = (13631, 142703)$
Copying, using $N$ instead of your $m$ as notation for the modulus:


*

*Compute $k = ed-1$

*Determine the exponent of $2$, $t$, in the factorization of $k$,
i.e. factor $k$ into the form $k = 2^t r$ with $t > 0$ and $r$ odd.

*Pick a random $x\,|\,2 \leq x < N$

*Compute the sequence
$s = x^{\frac k 2}, x^{\frac k 4}, \dots, x^{\frac k {2^t}} \pmod{N}$

*Determine the first index $i$ such that $s_i \neq \pm 1$ and
$s_{i-1} = 1$


*

*If no such index exists, choose a new $x$ and try again.

*Otherwise, let $p = \gcd(s_i - 1, N)$ and $q = \frac N p$.


*Done.
This is doable by hand calculator for these sizes (you might have to try a few $x$). But given the context probably not what your professor intended.
An alternative, directly following the hint: 
By definition of RSA: $ed = 1 \pmod{\phi(m)}$. So $ed-1 $ is a multiple of $\phi(m)$. Now for the given pair $(e,d)$:
$ed -1 =1945184592$ , which we can divide by factors of 2,
leaving $121574037$, which is divisible by 3, using the standard test
and leaves us with $13508226$, this turns out to be divisble by $13$ (after trying $7$ and $11$) leaving $3117283$ also divisible by $13$, and we are left with $239791$. Then (e.g. checking all primes $< 100$) we find a factor $61$ which leaves $3931$ (which is prime, checking all primes $\sqrt{3931}$ as divisors). So
$$ed-1 = 2^4 \cdot 3 \cdot 13^2 \cdot 61 \cdot 3931$$ and we now we can find $\phi(m)$ because $ed-1$ happens to have a lot of small factors, and we don't have to find $\phi(m)$ by guessing it or something like that. $\phi(m)= (p-1)(q-1)$ should be divisible by $2^2$ at least (as $p,q$ are odd) and we note that $t= \frac{ed-1}{3931} = 494832$ seems a strong candidate for being $\phi(m)$ as it is $< m$ and has the same length and the same starting digits (which we expect, as $p, q$ are around size $\sqrt{m}$ so $m - \phi(m)$ is about 1400 to 1500. So we expect the first two digits to coincide, which rules out the candidates $39131 \cdot 61$ or $2 \cdot 3931 \cdot 61 = 479582$.  
The algorithm I gave first will always work (with probability close to $1$), regardless of being able to factor $ed-1$ an this could be as hard as factoring $m$ itself. So this exercise is somewhat misleading, as here we are "lucky" with our $ed-1$ having a relatively small factor 61.
For (b) note that $m - \phi(m)  =pq -(p-1)(q-1)$ = $p+q-1$,and the left hand side is known as $m$ and $\phi(m)$ are. So we know $p+q$ and $pq$ from which we solve $p$ and $q$ in a standard way (quadratic equation).
A: Although the comment pointing out that factoring numbers is hard in general is correct, that doesn't mean some numbers aren't slightly more easily factored. 
In this case $496241 = 705^2 - 28^2 = (705+28)(705-28) = 677*733$ as desired.
Note that I'm pretty sure I couldn't have spotted this without having the answer, but it does at least potentially provide a route to the correct factorisation.
------ Edited to correct answer ------
A: I hope that you know that you can stop at the square root.  If you have not found a factor by then, you won't.  
If you want to produce a list of prime numbers then the Sieve of Eratosthenes is good though it is not so good for just testing one number.  
