Posted by: jonkatz | December 19, 2009

## “x mod y” is now controversial?

A sensible discussion regarding whether “simple” algorithms should appear at SODA has been derailed in the comments by people arguing whether computer scientists have destroyed mathematics by using the notation “$x \bmod y$” to refer to the integer in $\{0, \ldots, y-1\}$ that is congruent to $x$ modulo $y$.

Although I find the opinions expressed in the comments extreme, and see nothing wrong with using $x \bmod y$ in the sense above as long as it is clear to the reader, I have to say that I myself sometimes find the notation confusing. When Yehuda and I wrote our textbook, we noticed this and decided to write $[x \bmod y]$ to refer to reduction of $x$ modulo $y$, as opposed to $x'=x \bmod y$ for the “standard” mathematical notion of equality modulo $y$. (As a personal preference, I don’t like using \pmod to write $x'=x \pmod y$ though I can understand others who choose to use it.) For that matter, we also distinguished between an assignment operator “$:=$” and the equality predicate “$=$”. That way, the expressions “$a:=[x \bmod y]$” and “$a=x \bmod y$” and “$a=[x \bmod y]$” can all be distinguished from each other.

While it’s ok to be pedantic and obsessive in one’s own writing (as I am), it seems wrong to require it of others especially if there is no danger of misinterpretation.

Advertisements

## Responses

1. In the simple case of the integers, using “x mod y” simply to denote the integer remainder is a useful cheat that usually doesn’t do any harm. And it can help make crypto more accessible to beginners, and papers easier to read. Plus, as computer scientists we are necessarily more sensitive than the average mathematician to how objects are represented.

All this said, I’m a little bit sympathetic to the basic complaint (though not the nasty attitude!). As soon as one moves to slightly more general groups (e.g., lattices!), the “simple” view of mod is not only far less useful, it actually can inhibit understanding. Frequently one doesn’t care which set of distinguished representatives is used, and focusing on the representation just obscures what’s really going on in the scheme and proof.

It’s often expedient to teach mod as if it only meant “remainder,” but I think this should be avoided; it inhibits a true understanding.

(This entire argument reminds me of the debates over whether BASIC should be taught to introductory programmers…)

2. Chris, on the one hand you’re right that one ultimately had to understand the general notion of quotient groups; on the other hand, I don’t see how it hurts to use the “x mod y” notation to express mapping to a distinguished representative in each class (as long as one is clear how one is choosing the distinguished representative, which could be {0, …, y-1} or {-y/2, …, y/2}, or something more general in general groups).

In particular, I don’t see how reduction modulo a fundamental parallelepiped P of a lattice is any more confusing if one write it as v mod P. (Or, as I would have it, [v mod P].)

3. Jon, all things being equal [v mod P] is certainly no better than v mod P (it’s probably worse). But my post was less about notation, than what we mean by “mod.”

When I write “v mod P,” I typically don’t intend for it to mean “reduction of a point modulo a fundamental parallelepiped of a lattice.” (That’s the “remainder” meaning of mod.) This is because it largely doesn’t matter what basis/fundamental region is used, or how we represent the result. All that matters is the quotient group interpretation, i.e., which coset of the lattice the point lies in. Focusing on the set of distinguished representatives would mostly just be a distraction, and the proofs are almost always clearer when representation is left out.

4. I’m still not sure I follow. Sometimes that is what you mean, and then being able to distinguish between (for example) v’ = v mod P and v’ = [v mod P] can be helpful.

Or, to throw the question back to you, what notation would you use if you wanted to talk about reduction of a point modulo a fundamental parallelepiped of a lattice? (E.g., in writing pseudocode?)

5. Even in pseudocode, I’d probably still just refer to the quotient group R^n / Lambda, and not fix a representation.

In real code, one has to use a concrete representation. But in real code there is no longer any need for notation. 🙂

I’m oversimplifying here, of course. Even the “abstract” algorithms are (slightly) representation-dependent. My original point is just that, even if we use mod notation as shorthand for “remainder” (which I do not object to!), we should remain vigilant to remember what it truly means in abstract algebra terms. Otherwise our notational “crutch” has actually handicapped us.

6. One must truly be vigilant! Some cryptographic papers fail to recognise fatal attacks by assuming that every integer in sight satisfies 0 \le x < p. This often happens when x is used as an exponent modulo p as well as an integer modulo p.

For myself, I distinguish the notation a = b (mod p), which is clearly an assignment operation, from a \equiv b (mod p) which is a predicate. I prefer the brackets around the mod, I suppose it makes it more clear exactly what the modulus is, e.g., in the case where it is a polynomial.

Anyway, can you say more about the debate at SODA? What is a "simple" algorithm? Euclid is a simple algorithm, but damned hard to analyse completely.

7. I like the notation “x mod y” for “the reminder of dividing x by y” and the notation “x \equiv y (mod m)” for “x and y are congruent modulo m.

Here is why:

1. The division operation, denoted by a binary operator / as in x/y, has no such thing as a ‘reminder’. (And x/y is defined as the multiplication of x with y’s multiplicative inverse.)

2. The integer division is a clearly related operation. Should it use the same notation or not? If it uses the same notation, then you can only know what x/y is from some contextual information. For example, in the C language the operation denoted by x/y depends on the types of x and y (and there are three possible operations, if I counted correctly). Still, there is no reason to depart from the infix notation. So “x div y” seems like a sensible choice. (Usually, this is defined as the biggest integer that doesn’t exceed x/y, but see http://portal.acm.org/citation.cfm?id=128862, which was also pointed out by Warren in the original discussion.)

3. The reminder operation is also a binary operation, clearly related to integer division, so it makes sense to stick to the infix notation and three letter operators, as in “x rem y” or “x mod y”. (“x mod y” is defined to be “x – (x div y) y”).

4. A good notation should be mnemonic and should facilitate manipulations. With a binary mod we have laws like “(x+y) mod m = x mod m + y mod m” that are completely analogous to other distributivity laws in shape, hence easy to assimilate. (For example, “(x+y)/m=x/m+y/m”.)

5. So, is it ‘rem’ or ‘mod’? The operation is related to integer division (and this suggests using ‘rem’), but also to congruence modulo m because “x mod m \equiv x (mod m)”. In general, you can `factor mod to the right’ as in “x mod m = y mod m” becomes “x \equiv y (mod m)”. Again, such laws tend to have a nice shape that is easy to remember.

That said, I think it’s perfectly fine for someone to use a notation I’d never use (like rem(x,y)) as long as it’s clear what it means.

8. But in real code there is no longer any need for notation.

The whole field of programming languages is about finding good notations (usually withing the confines of ASCII or UNICODE).

9. With a binary mod we have laws like “(x+y) mod m = x mod m + y mod
m”

If mod means “integer remainder,” then this is not true! The LHS is
always less than m, but the RHS may be an integer as large as 2(m-1).
In general, the set of integers {0, …, m-1} is not robust to many
operations at all; this is good reason to avoid the “remainder”
semantics unless the integer representation is explicitly needed (as
it was in the original hashing application).

10. Obviously, the notation is not mnemonic enough. 🙂 I guess my point (4) is ruined.

I meant “x+y \equiv x mod m + y mod m (mod m)”. The reason I keep this in mind is that the reminder operation implemented on most processors (and hence in most programming languages) does not have this property, which programmers tend to assume. This is assumed, for example, when you keep taking the reminder at intermediate steps of a computation to avoid overflow, given that the final result is a congruence class.

Also, note that my definition (which matches TAoCP, Python, and Haskell among others) is different from “(x mod y) is the integer in 0..y-1 that is congruent modulo y to x”, aka the E-definition. I don’t like much the (IEEE) definition that breaks the law I got wrong, but among the so-called F-definition (what I said) and the E-definition I don’t have a preference.

I agree that you should not be representation dependent, unless needed. I’m talking only about integers when I say that “x mod y” seems a good notation to me.

11. Hey guys,

My comment here is out of context, but I can’t resist to ask you guys.

It is about the competition in the Crypto conferences.

It is a (almost) common sense that Crypto, Eurocrypt, TCC are the most important crypto conferences nowadays. A lot of researchers do not include Asiacrypt in the set of most important conferences. However, I’ve been observing that the competition in Asiacrypt is as tough as in Crypto. Record of submissions, a lot of good papers being rejected, etc, etc.

So, I would like to ask you: Do you consider that Asiacrypt is in the same patamar as the three big (Crypto, Eurocrypt, TCC)?

I’ve seen some people that considers CT-RSA and PKC more important than Asiacrypt.

I am placing this question because I have to define a calendar for next year. In the near future, I intend to participate in the admission process for a PhD program in US. If I get a paper accepted in one of the major conferences, I’ll be a stronger applicant,. . . , I guess.

So, guys, what is your opinion?

Kind regards.

Regular and foreign guy that likes crypto

PS: I didn’t include applied crypto conferences like FSE and CHES in the discussion.

By the way, I am sorry about the out of context comment, but any comment about that will be very valuable.

12. Regular guy, see here and here =)

As far as PhD admissions go, I think having a publication at any reasonable conference will already help your application tremendously. Want to apply to Maryland? 😉

13. Two things:

1. Christ, I would never write “(x+y) mod m = x mod m + y mod m”. Mixing “mod” and “=” is confusing. Either it would be clear that the objects lie in Z/nZ and I would write x + y = x + y. Or, I would write

x+ y (mod m) \equiv x (mod m) + y (mod m).

To put this in mathematical context: you are either working in the quotient structure or not. If you are in the quotient structure then “=” makes sense but there is no need to put the (mod). If you are not working in the quotient structure then you are dealing with a relation which is not equality, so use \equiv.

2. I think Asiacrypt is just as strong as CRYPTO and Eurocrypt. Maybe 10 years ago this was not true, but it is now.

14. Please replace the word “Christ” above by “Chris”.

I think Christmas is getting to me.

15. Yes, of course. Maryland has one of the best graduate computer science programs in US.
🙂

In 2010, I intend to submit papers to CT-RSA and TCC. The competition is ferocious, but it is worth trying. Maybe Asiacrypt, if I feel too confident.

So, I have until October/November to get some results.

Thanks

Regular guy

16. Even having a paper in submission is pretty good, whether it gets in or not.