2
$\begingroup$

Pretty much every thing is in the title, really! I'm trying to come up with an efficient algorithm to factorize large integer as an homework for a parallel programming course.

I've seen a few pages explaining the algorithms, but just can't wrap my head around the notation enough to actually implement the thing.

For exemple, in the very beginning, to demonstrate inefficiency of Fermat's Factirization for primes whose factors are nearer 1 than from the square root we have for n=1649:

         41^2 - n = 32         42^2 - n = 115         43^2 - n = 200 ... and then         41^2 ≡ 32 (mod n),           43^2 ≡ 200 (mod n),   we have          41^2 * 43^2 ≡ 80^2 (mod n),    that is,          (41 * 43)^2 ≡ 80^2 (mod n). 

What does the (mod n) stands for?

I understand the modulo operator, as used in many programming language, but I'm not sure whether this is what is meant here as I can't figure what are his operands, in that context...

Thank you very much, Pascal

  • 3
    see [Modular arithmetic](http://en.wikipedia.org/wiki/Modular_arithmetic)2012-04-11
  • 0
    Assuming all the numbers in question are positive, he's saying that e.g. $(41^2\text{ mod }n) = (32 \text{ mod }n)$. If $k$ is negative, then for math purposes, (assuming $n$ positive) you should add a bunch of copies of $n$ to make it positive, and then look at $k\text{ mod }n$.2012-04-11
  • 1
    In computer science mod is a binary operator, in mathematics $x \equiv y \ (\mod z)$ is a relation, the computer-science equivalent of which would be x mod z = y mod z.2012-04-12

2 Answers 2