On 6 Apr., 17:41, Brian Tyler <brian.ty...@[EMAIL PROTECTED]
> wrote:
> I'm currently writing an algorithm which depends at one small point on
> being able to solve a system of the form:
>
> [a_1 b_1][x_1] = [c_1] (mod m_1)
> [a_2 b_2][x_2] = [c_2] (mod m_2)
> [a_3 b_3][x_3] = [c_3] (mod m_3)
>
> where a_i,b_i,c_i \in Z and 1 < m_i \in Z
And what are x_i supposed to be?
If [a_1 b_1] denotes a 1 x 2 matrix and [c_1] a 1 x 1 matrix,
then [x_1] better be a 2x1 matrix -- of integers?
Then, writing x and y for its components, you are really trying to
solve
a_1 x + b_1 y = c_1 - k m_1
or more symmetrically
a_1 x + b_1 y + m_1 k = c_1
in integers x,y,k.
If gcd(a_1,b_1,m_1) divides c_1, such solutions can be found using
Euklid's
generalized algorithm. If not, no such integer solution exists.
>
> At the moment I am using the pari C library to do this, but it adds
loads
> of overhead because I need to convert to the pari type and convert back
> (and if I am using GMP integers this is really slow) So I was hoping to
> write a purpose built algorithm for doing this, but I haven't had any
> luck in finding one.
>
> An ideas?
>
> Many thanks,
> Brian.
|
