23
\$\begingroup\$

The Chinese Remainder Theorem tells us that we can always find a number that produces any required remainders under different prime moduli. Your goal is to write code to output such a number in polynomial time. Shortest code wins.

For example, say we're given these constraints:

  • \$n \equiv 2 \mod 7\$
  • \$n \equiv 4 \mod 5\$
  • \$n \equiv 0 \mod 11\$

One solution is \$n=44\$. The first constraint is satisfied because \$44 = 6\times7 + 2\$, and so \$44\$ has remainder \$2\$ when divided by \$7\$, and thus \$44 \equiv 2 \mod 7\$. The other two constraints are met as well. There exist other solutions, such as \$n=814\$ and \$n=-341\$.

Input

A non-empty list of pairs \$(p_i,a_i)\$, where each modulus \$p_i\$ is a distinct prime and each target \$a_i\$ is a natural number in the range \$0 \le a_i < p_i\$. You can take input in whatever form is convenient; it doesn't have to actually be a list of pairs. You may not assume the input is sorted.

Output

An integer \$n\$ such that \$n \equiv a_i \mod p_i\$ for each index \$i\$. It doesn't have to be the smallest such value, and may be negative.

Polynomial time restriction

To prevent cheap solutions that just try \$n=0, 1, 2, \dots\$, and so on, your code must run in polynomial time in the length of the input. Note that a number \$m\$ in the input has length \$Θ(\log m)\$, so \$m\$ itself is not polynomial in its length. This means that you can't count up to \$m\$ or do an operation \$m\$ times, but you can compute arithmetic operations on the values.

You may not use an inefficient input format like unary to get around this.

Other bans

Built-ins to do the following are not allowed: Implement the Chinese Remainder theorem, solve equations, or factor numbers.

You may use built-ins to find mods and do modular addition, subtraction, multiplication, and exponentiation (with natural-number exponent). You may not use other built-in modular operations, including modular inverse, division, and order-finding.

Test cases

These give the smallest non-negative solution. Your answer may be different. It's probably better if you check directly that your output satisfies each constraint.

[(5, 3)] 
3

[(7, 2), (5, 4), (11, 0)]
44

[(5, 1), (73, 4), (59, 30), (701, 53), (139, 112)]
1770977011

[(982451653, 778102454), (452930477, 133039003)]
68121500720666070
\$\endgroup\$
9
  • \$\begingroup\$ Why no division? \$\endgroup\$
    – jimmy23013
    Mar 22, 2015 at 8:31
  • \$\begingroup\$ @user23013 No modular division, since it's basically modular inverse. \$\endgroup\$
    – xnor
    Mar 22, 2015 at 8:34
  • \$\begingroup\$ Does matrix inversion count as solving equations? \$\endgroup\$
    – flawr
    Mar 22, 2015 at 15:44
  • \$\begingroup\$ @flawr: I would think so. \$\endgroup\$
    – Alex A.
    Mar 22, 2015 at 19:32
  • \$\begingroup\$ @xnor: What do you think? And how about optimization functions? \$\endgroup\$
    – flawr
    Mar 22, 2015 at 20:49

6 Answers 6

9
\$\begingroup\$

Mathematica, 55 51 45

Modular inverse is banned, but modular exponentiation is allowed. By Fermat's little theorem, n^(-1) % p == n^(p-2) % p.

(PowerMod[x=1##&@@#/#,#-2,#]x).#2&@@Thread@#&

Example:

In[1]:= f = (PowerMod[x=1##&@@#/#,#-2,#]x).#2&@@Thread@#&;

In[2]:= f[{{5, 3}}]

Out[2]= 3

In[3]:= f[{{7, 2}, {5, 4}, {11, 0}}]

Out[3]= 1584

In[4]:= f[{{5, 1}, {73, 4}, {59, 30}, {701, 53}, {139, 112}}]

Out[4]= 142360350966

Just for fun:

ChineseRemainder@@Reverse@Thread@#&
\$\endgroup\$
2
  • 1
    \$\begingroup\$ You can save one byte by swapping the order of the arguments of the innermost function, such that you can use PowerMod[#2,#-2,#] and I also don't think there's a requirement for the function to be named, bringing it down to 48. \$\endgroup\$ Mar 22, 2015 at 15:46
  • \$\begingroup\$ Yes, unnamed functions are OK. \$\endgroup\$
    – xnor
    Mar 22, 2015 at 23:29
6
\$\begingroup\$

Python 2, 165 101 99 98 85 bytes

Using Fermat's little theorem like the other answers. Doesn't bother with keeping final sum within modular range, since we're not interested in the smallest solution. Thanks Volatility for saving 13 bytes.

l=input();x=reduce(lambda a,b:a*b[0],l,1)
print sum(x/a*b*pow(x/a,a-2,a)for a,b in l)

[(5, 3)]
3
[(7, 2), (5, 4), (11, 0)]
1584
[(5, 1), (73, 4), (59, 30), (701, 53), (139, 112)]
142360350966
\$\endgroup\$
3
  • 1
    \$\begingroup\$ You can remove the space before for. \$\endgroup\$
    – isaacg
    Mar 22, 2015 at 6:24
  • 1
    \$\begingroup\$ x/a*b*pow(x/a,a-2,a)for a,b in l should work. \$\endgroup\$
    – Volatility
    Mar 23, 2015 at 6:05
  • \$\begingroup\$ Excellent point! I was trying to get rid of the obvious redundancy there but forgot that I could just unpack. \$\endgroup\$
    – Uri Granta
    Mar 23, 2015 at 8:18
4
\$\begingroup\$

Pyth, 40 37 36 29

M*G.^G-H2Hsm*edg/u*GhHQ1hdhdQ

Uses Fermat's little theorem, thanks to alephalpha. Computes using this formula.

\$\endgroup\$
3
\$\begingroup\$

Ruby, 129

Well, comrades, it seems Ruby solutions must be longer because modular exponentiation is not available without loading openssl library and doing conversions to OpenSSL::BN. Still, had fun writing it:

require("openssl")
z=eval(gets)
x=1
z.map{|a,b|x*=a}
s=0
z.map{|a,b|e=a.to_bn;s+=(x/a).to_bn.mod_exp(e-2,e).to_i*b*x/a}
puts(s)
\$\endgroup\$
1
  • \$\begingroup\$ You don't need the parens when calling require, eval, or puts. \$\endgroup\$ Jul 27, 2017 at 15:30
3
\$\begingroup\$

Python 2, 61

n=P=1
for p,a in input():n+=P*(a-n)*pow(P,p-2,p);P*=p
print n

This employs a variation of the product construction that other answers use.

The idea is to loop over the constraints and update the solution n to meet the current constraint without messing up the prior ones. To do so, we track the product P of the primes seen up to now, and observe that adding a multiple of P has no effect modulo any already-seen prime.

So, we just need to change n to satisfy n%p == a by adding the right multiple of P. We solve for the coefficient c:

(n + P*c) % p == a

This requires that c = (a-n) * P^(-1), where the inverse is taken modulo p. As others note, the inverse can be computed by Fermat's Little Theorem as P^(-1) = pow(P,p-2,p). So, c = (a-n) * pow(P,p-2,p), and we update n by n+= P * (a-n) * pow(P,p-2,p).

\$\endgroup\$
1
\$\begingroup\$

Haskell, 68 100 bytes

f l=sum[p#(m-2)*n*p|(m,n)<-l,let a#0=1;a#n=(a#div n 2)^2*a^mod n 2`mod`m;p=product(map fst l)`div`m]

Usage: f [(5,1), (73,4), (59,30), (701,53), (139,112)] -> 142360350966.

Edit: now with a fast "power/mod" function. Old version (68 bytes) with inbuilt power function:

f l=sum[l#m^(m-2)`mod`m*n*l#m|(m,n)<-l]
l#m=product(map fst l)`div`m
\$\endgroup\$
2
  • \$\begingroup\$ I suspect your implementation of power-mod is not polynomial-time since the exponent produces a huge number before the mod. Have you tried the last test case? \$\endgroup\$
    – xnor
    Mar 22, 2015 at 22:49
  • \$\begingroup\$ @xnor: the last test case runs out of memory after a few seconds on my 2GB machine. I've added a fast power/mod function. \$\endgroup\$
    – nimi
    Mar 23, 2015 at 20:23

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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