Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question
3  
see Modular arithmetic –  Raymond Manzoni Apr 11 '12 at 20:56
    
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$. –  Charles Staats Apr 11 '12 at 21:59
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. –  Robert Israel Apr 12 '12 at 0:41

2 Answers 2

A useful way to think about $a \equiv b$ (mod $n$) is "$a$ and $b$ have the same remainder when divided by $n$".

share|improve this answer

The statement $x \equiv k \pmod n$ means that $\frac{x-k}{n}$ is an integer, (note this requires $n \neq 0$). Equivalently, $x = mn + k$ for some integer $m$.

In this case we have $n=1649$, and the statment $41^2 \equiv 32 \pmod n$ means that $41^2$ is 32 more than a multiple of $1649$.

The notation translates from programming (ignoring possible overflow) as follows:

x % n == k // True

implies

$x \equiv k \pmod n$.

If $x\geq 0$ and $k$ is the smallest positive integer for which $x \equiv k \pmod n$, then x % n == k. (This is true in C and Javascript at least, I just tested).

For example 10 % 3 == 1 implies $10 \equiv 1 \pmod 3$, and $10 \equiv 1 \pmod 3$ implies 10 % 3 == 1. But, $10 \equiv 4 \pmod 3$, does not imply 10 % 3 == 4.

If $x \leq 0$ and $k$ is the largest negative integer (smallest absolute value) for which $x \equiv k \pmod n$, then x % n == k.

That is, the modulo operator in most programming languages keeps the sign of the number.

share|improve this answer
1  
Nope. % and mod are different for negative numbers. (Alternatively: % is busted.) –  JeffE Apr 11 '12 at 22:41
    
To be honest, I considered making the distinction when I was writing my post, but I decided against it. He said he is aware of the modulo operator already and just wanted to know how the mathematical notation is read. I will update my comment shortly. –  nullUser Apr 12 '12 at 1:21

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.