Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

I'm having trouble finding info in the docs about how to solve a system of congruences. The closest I can find is 'matsolvemod' in here: http://pari.math.u-bordeaux.fr/dochtml/html.stable/Vectors,_matrices,_linear_algebra_and_sets.html

but I'm not sure if that's exactly what it's used for because I don't really understand where the M parameter comes in with a system of congruences. Is there a function for solving a system of linear equations of the form:

x = a1 (mod b1) x = a2 (mod b2) ... x = an (mod bn)

(or even for just 2 or 3 congruences is fine)

EDIT: Okay, I've tried just using the algorithm and basic arithmetic instead of finding a function to do it for me automatically but am receiving an error:

enter image description here

share|improve this question
2  
Did you read the algorithm outlined on the Wikipedia page I linked in your previous question? There's a walkthrough with 2 congruences (pairwise coprime, though) and then for the general case. Then you can implement it using only standard arithmetic and a modular inverse algorithm (which PARI should have). If this is about using a built-in function of PARI/GP to solve general systems of congruences, it's off-topic here. –  Thomas Mar 17 '13 at 23:03
    
I've edited the comment to show how I've attempted to solve the example system of congruence you gave in my last question –  user1136342 Mar 18 '13 at 1:20
1  
I don't know much about PARI/GP but I think Mod does more than just take the value of a modulo b (it changes its datatype, too). Can you try just using a%b instead? Though I'm not sure how to get the modular inverse in that case, you'll need to look that up. I'm sorry, I'm not of much help - I don't use PARI/GP. –  Thomas Mar 18 '13 at 1:30
    
That works- thanks! Both of your answers have been really helpful to me even though you don't use PARI/GP –  user1136342 Mar 18 '13 at 1:37
add comment

1 Answer

up vote 2 down vote accepted

Pari's "chinese" function (as in Chinese Remainder Theorem) does the solution for you, for two congruences. You can fold in more congruences via induction.

? chinese(Mod(42,91), Mod(11, 37))
%1 = Mod(3045, 3367)

The previous example solves for $x \equiv 42 \pmod{91}$ and $x \equiv 11 \pmod{37}$, which is unique modulo $91 \cdot 37 = 3367$. You can use "raise" to promote a Mod object to the integers.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.