How to factorise large number without calculator?

Question

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

Answer 1

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 ------

Answer 2

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.

Answer 3

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:

1. Compute $k = ed-1$

2. 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.

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

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

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

6. 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).