On Mon, May 29, 2006 at 05:04:46PM -0700, Geoffrey Irving wrote:
For an extremely common example of switching between different moduli, look at this:
http://mathworld.wolfram.com/ChineseRemainderTheorem.html
For example, RSA uses m_1 = p, m_2 = q prime, where M = pq is the public key.
I'm not convinced, to me it seems that all variables in those cases are just integers. The above page says: Let r and s be positive integers which are relatively prime [So, r and s are definitely just normal integers, element of N+] and let a and b be any two integers. [Also a and b are not an element of a finite group thus, they are plain integers, element of Z]. Then there is an integer N such that [Also N is an integer...] N = a (mod r) Well, as I said in a previous post: the modulo works on whole expressions. The above says: N is equivalent to a, if you work modulo r. It doesn't force N or 'a' to be element of Z_r. The question arises however: how would you implement this in code? I don't think the above equation is something you can do anything sensible with by itself -- at most you could already have a value of N and 'a', and then want to check if they are equal. You could do that as follows: if (abelian_group<r>(a) == N) ... or if (a == abelian_group<r>(N)) ... because it makes sense to have operator== implicitely convert a normal integer to the finite group of it's other argument. I'd agree that it might be annoying in this case that 'r' has to be a constant. But, that isn't an argument to not have templated finite group types. After all, neither a, nor N ARE finite. Perhaps we need notation/API like this: if (Modulo(r).equals(a, N)) or even using boost::foobar::equals; if (equals(a, N).modulo(r)) because casting one of the two arguments to Z_r before you start to compare isn't really defendable from a mathematical point of view (though valid, of course). The ideal situation would be to have an algorithm (for comparing two integers) that is optimised for a (runtime definable) modulo. Now, to get back that page. If you want to solve the set of equations: N == a (mod r) N == b (mod s) Then you need a function/algorithm especiall for that, for example: N = ChineseRemainder(a, b, r, s); I don't think it would even make sense to cast a or b to Z_r or Z_s respectively. What I meant when I said that I can't think of a case where you need to switch modulo, is that when you have an element of Z_p, then it doesn't really make sense to turn it into Z_q. The only exception being when q devides p. Thus: unsigned_integer x; unsigned_integer::set_modulo(r); x = N; unsigned_integer::set_modulo(s); // use x make no sense. Which is why I wonder why you wouldn't do: Z<r> x = N; Z<s> y = N; except for the case that r and s have to be dynamically determined. -- Carlo Wood <carlo@alinoe.com>