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
    (Why is this true?) Fermat's little theorem says $m^{p-1}\equiv 1 \pmod p$. Do you mean why is Fermat's little theorem true? I don't understand what the author meant by $n$ not dividing $m-1$ either. But $g$ exists because, for instance, Euclid's algorithm gives it constructively.2012-10-16
  • 0
    I know Fermat's little theorem. I am just not seeing the implications to get $m \equiv 1\mod p$2012-10-16
  • 0
    Don't $m$ and $p$ have to be relatively prime for Fermat's Little Theorem?2012-10-16
  • 0
    Right-so $m=2^{10000!}-kp(n/p)$ and if $m, p$ weren't relatively prime, $p$ would divide $m$, and so would also have to divide $2^{10000!}$. So, come to think, $p=2$ has to be specifically excluded. But for any **odd** $p$, $m$ is relatively prime to $p$ as desired.2012-10-16
  • 0
    What is $(n/p)$?2012-10-16
  • 0
    $n$ divided by $p$. I just factored $p$ out of $n$ to make things explicit.2012-10-17

0 Answers 0