1
$\begingroup$

I need some help understanding this algorithm. I want to factor $n$. Suppose $n$ has a factor $p$ s.t. the primes that divide $p-1$ are less than $10,000$. And $p-1$ divides $10000!$.

Let $m = 2^{10000!} \mod n$

By Fermat's Little Theorem, since $p-1$ divides $10000!$ we have:

$m \equiv 1 \mod p$ (Why is this true)?

The book then states: There is an excellent chance that $n$ does not divide $m-1$, so that $g = \gcd(m-1, n)$ will be a non-trivial divisor of $n$

How could $n$ ever divide $m-1$ since $m-1$ is smaller than $n$? And how is there a guaranteed $ g = \gcd(m-1, n)$?

  • 0
    $n$ divided by $p$. I just factored $p$ out of $n$ to make things explicit.2012-10-17

0 Answers 0