Polynomial Interpolation Write a program that performs Polynomial Interpolation  using true arbitrary precision rational numbers. The input looks like this:

f(1) = 2/3
f(2) = 4/5
f(3) = 6/7
...

You may assume that there's exactly one whitespace before and after the = sign, all the numbers are either fractions or integers. You may also assume, that all fraction in the input are already irreducible.
No error checking is needed, you may assume, that the input is valid and no x is doubled in the f(x).
The output should be in a LaTeX compatible form, the emitted LaTeX code should yield the same graphical representation as the output given here.

f(x) = 123x^2 + \frac{45}{2}x + \frac{7}{4}

The fraction must be reduced as much as possible, eg. something like \frac{2}{4}  is not allowed. If the number is integer, don't use a fraction.
Special rules:
Your program should...

work for polynomials up to degree 12
complete in less then 1 minute for reasonable input
not use any functions that do the whole calculation for you
output the polynomial of smallest possible degree

Testcases:
The given testcases are just for clarification. Your program should yield correct result for all correct inputs.
Input

f(1) = 2/3
f(2) = 4/5
f(3) = 6/7

Output

f(x) = - \frac{4}{105}x^2
       + \frac{26}{105}x
       + \frac{16}{35}

Input

f(-12) = 13/2
f(5/3) = 3/5
f(13) = -6
f(1/5) = -3/4

Output

f(x) = - \frac{2186133}{239455744}x^3
       + \frac{2741731}{149659840}x^2
       + \frac{26720517}{29201920}x
       - \frac{279464297}{299319680}

Input

f(4/3) = 617/81
f(2) = 20/3
f(-8/3) = 6749/81
f(-5) = 7367/12
f(0) = 23/3

Output

f(x) = \frac{1}{2}x^4
     - 2x^3
     + \frac{7}{4}x^2
     + \frac{23}{3}

Input

f(0) = 5
f(1) = 7
f(2) = 9
f(3) = 11
f(4) = 13

Output

f(x) = 2x
     + 5

Input

f(1/2) = -1/2
f(-25) = -1/2
f(-54/12) = -1/2

Output

f(x) = -\frac{1}{2}
J + sh

J script:

i=:0".(1!:1)3
i=:((-:#i),2)$i
c=:|.(%.(x:((i.#i)^~])"0({."1 i)))(+/ .*)(|:{:"1 i)
(":(-.0=c)#(c,.i.-#c))(1!:2)2


sh script:

echo -n 'f(x) = '
tr -d 'f()=' | tr /\\n- r' '_  | ./polyint.ijs | sed -e 's/^/+/;s/_/-/;s/\([0-9]*\)r\([0-9]*\)/\\frac{\1}{\2}/;s/ \([0-9]*$\)/x^\1/;s/\^1//;s/x^0//;s/+\(.*-.*\)/\1/'


Run the sh script:

./pol-int.sh
f(1/2) = -1/2
f(-25) = -1/2
f(-54/12) = -1/2

f(x) = -\frac{1}{2}


.

./pol-int.sh
f(4/3) = 617/8
f(2) = 20/3
f(-8/3) = 6749/81
f(-5) = 7367/12
f(0) = 23/3

f(x) = -\frac{37745}{14592}x^4
       -\frac{853249}{43776}x^3
     +  \frac{57809}{7296}x^2
     + \frac{225205}{2736}x
     +  \frac{23}{3}