From: Carlo Wood (carlo_at_[hidden])
Date: 2006-05-30 11:24:04
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:
> 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) ...
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))
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
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
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.
x = N;
// 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_at_[hidden]>
Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk