Re: [boost] Infinite precision integer draft

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:
> 
>     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_at_[hidden]>