The Ben-Or / Tiwari interpolation algorithm.M1, M2, M3 := x^3*y^4, x*y^3*z, x^6*z^2;a1, a2, a3 := 101,103,997;f := a1*M1+a2*M2+a3*M3;d := degree(f);T := 3;for i from 0 to 2*T-1 do v||i := eval( f, {x=2^i,y=3^i,z=5^i} ) od ;V := Matrix([[v0,v1,v2],[v1,v2,v3],[v2,v3,v4]]);S := Vector([-v3,-v4,-v5]);L := LinearAlgebra:-LinearSolve(V,S);Lambda := L[1]+L[2]*z+L[3]*z^2+z^3;factor(Lambda);m1,m2,m3 := 1600,270,648;ifactor(m1), ifactor(m2), ifactor(m3);M1,M2,M3 := x*y^3*z, x^3*y^4, x^6*z^2;M := Matrix([[1,1,1],[m1,m2,m3],[m1^2,m2^2,m3^2]]);V := <v0,v1,v2>;LinearAlgebra:-LinearSolve(M,V);a1,a2,a3 := 103,101,997;a1*M1+a2*M2+a3*M3;f;If we don't know the number of terms of LUklbXJvd0c2Iy9JK21vZHVsZW5hbWVHNiJJLFR5cGVzZXR0aW5nR0koX3N5c2xpYkdGJzYlLUkjbWlHRiQ2JVEiZkYnLyUnaXRhbGljR1EldHJ1ZUYnLyUsbWF0aHZhcmlhbnRHUSdpdGFsaWNGJy1JKG1mZW5jZWRHRiQ2JC1GIzYoLUYsNiVRInhGJ0YvRjItSSNtb0dGJDYtUSIsRicvRjNRJ25vcm1hbEYnLyUmZmVuY2VHUSZmYWxzZUYnLyUqc2VwYXJhdG9yR0YxLyUpc3RyZXRjaHlHRkUvJSpzeW1tZXRyaWNHRkUvJShsYXJnZW9wR0ZFLyUubW92YWJsZWxpbWl0c0dGRS8lJ2FjY2VudEdGRS8lJ2xzcGFjZUdRJjAuMGVtRicvJSdyc3BhY2VHUSwwLjMzMzMzMzNlbUYnLUYsNiVRInlGJ0YvRjJGPS1GLDYlUSJ6RidGL0YyRkFGQUZB then we can try T = 3 then T = 5 etc. say.
So we would doT := 5; for i from 0 to 2*T-1 do v||i := eval( f, {x=2^i,y=3^i,z=5^i} ) od ;This leads to very large integers. Instead we will also work mod p to eliminate arithmetic with large rationals. We need LUklbXJvd0c2Iy9JK21vZHVsZW5hbWVHNiJJLFR5cGVzZXR0aW5nR0koX3N5c2xpYkdGJzYmLUkjbWlHRiQ2JVEicEYnLyUnaXRhbGljR1EldHJ1ZUYnLyUsbWF0aHZhcmlhbnRHUSdpdGFsaWNGJy1JI21vR0YkNi1RIj5GJy9GM1Enbm9ybWFsRicvJSZmZW5jZUdRJmZhbHNlRicvJSpzZXBhcmF0b3JHRj0vJSlzdHJldGNoeUdGPS8lKnN5bW1ldHJpY0dGPS8lKGxhcmdlb3BHRj0vJS5tb3ZhYmxlbGltaXRzR0Y9LyUnYWNjZW50R0Y9LyUnbHNwYWNlR1EsMC4yNzc3Nzc4ZW1GJy8lJ3JzcGFjZUdGTC1JJW1zdWJHRiQ2JS1GLDYlUSJtRidGL0YyLUYjNiUtRiw2JVEiaUYnRi9GMkYvRjIvJS9zdWJzY3JpcHRzaGlmdEdRIjBGJ0Y5 to recover the monomial evaluations uniquely and we can bound LUklbXJvd0c2Iy9JK21vZHVsZW5hbWVHNiJJLFR5cGVzZXR0aW5nR0koX3N5c2xpYkdGJzYoLUklbXN1YkdGJDYlLUkjbWlHRiQ2JVEibUYnLyUnaXRhbGljR1EldHJ1ZUYnLyUsbWF0aHZhcmlhbnRHUSdpdGFsaWNGJy1GIzYlLUYvNiVRImlGJ0YyRjVGMkY1LyUvc3Vic2NyaXB0c2hpZnRHUSIwRictSSNtb0dGJDYtUSI8RicvRjZRJ25vcm1hbEYnLyUmZmVuY2VHUSZmYWxzZUYnLyUqc2VwYXJhdG9yR0ZILyUpc3RyZXRjaHlHRkgvJSpzeW1tZXRyaWNHRkgvJShsYXJnZW9wR0ZILyUubW92YWJsZWxpbWl0c0dGSC8lJ2FjY2VudEdGSC8lJ2xzcGFjZUdRLDAuMjc3Nzc3OGVtRicvJSdyc3BhY2VHRlctSShtc3Vic3VwR0YkNigtRi82JVEicEYnRjJGNS1GIzYlLUYvNiVRIm5GJ0YyRjVGMkY1LUYjNiUtRi82JVEiZEYnRjJGNUYyRjUvJTFzdXBlcnNjcmlwdHNoaWZ0R0Y/Rj0vSSttc2VtYW50aWNzR0YkUSxbbm9uZSxub25lXUYnLUZBNi1RIj1GJ0ZERkZGSUZLRk1GT0ZRRlNGVUZYLUklbXN1cEdGJDYlLUkjbW5HRiQ2JFEiNUYnRkQtRiM2JS1GYHA2JFEiOEYnRkRGMkY1RmRvRkQ=.p := nextprime(5^8);T := 5; for i from 0 to 2*T-1 do v||i := Eval( f, {x=2^i,y=3^i,z=5^i} ) mod p od ;V := Matrix([seq([seq(v||(i+j),j=0..T-1)],i=0..T-1)]);k := Gausselim(V) mod p;T := 3;V := Matrix([seq([seq(v||(i+j),j=0..T-1)],i=0..T-1)]);S := Vector([-v3,-v4,-v5]);L := Linsolve(V,S) mod p;Lambda := L[1]+L[2]*z+L[3]*z^2+1*z^3;Roots(Lambda) mod p;TTdSMApJQVJUQUJMRV9TQVZFLzE4NDQ2ODg0MjI0MjE2MTgwMjQ2WCwlKWFueXRoaW5nRzYiRiVbZ2whIiUhISEjKiIkIiQiJSw3IihlJSlvIiIrLyFSQWcjRidGKCIuIypmQUBLNiVGKEYpIjE7M19TW0hfbEYlTTdSMApJQVJUQUJMRV9TQVZFLzE4NDQ2ODg0MjI0MjE2MTgwMzY2WColKWFueXRoaW5nRzYiRiVbZ2whIyUhISEiJCIkIS4jKmZBQEs2JSExOzNfU1tIX2whNW8oWyY9UUUhKmZZNUYlTTdSMApJQVJUQUJMRV9TQVZFLzE4NDQ2ODg0MjI0MjE2MTgwNzI2WColKWFueXRoaW5nRzYiRiVbZ2whIyUhISEiJCIkISorZyQqeiMiKGdQayIhJT1ERiU=TTdSMApJQVJUQUJMRV9TQVZFLzE4NDQ2ODg0MjI0MjE2MTgwODQ2WCwlKWFueXRoaW5nRzYiRiVbZ2whIiUhISEjKiIkIiQiIiIiJSs7IigrK2MjRiYiJHEjIiYrSChGJiIkWyciJy8qPiVGJQ==TTdSMApJQVJUQUJMRV9TQVZFLzE4NDQ2ODg0MjI0MjE2MTgwOTY2WColKWFueXRoaW5nRzYiRiVbZ2whIyUhISEiJCIkIiUsNyIoZSUpbyIiKy8hUkFnI0YlTTdSMApJQVJUQUJMRV9TQVZFLzE4NDQ2ODg0MjI0MjE2MTgxMzI2WColKWFueXRoaW5nRzYiRiVbZ2whIyUhISEiJCIkIiQoKioiJC4iIiQsIkYlTTdSMApJQVJUQUJMRV9TQVZFLzE4NDQ2ODg0MjI0MjE2MTc2NzUwWCwlKWFueXRoaW5nRzYiRiVbZ2whIiUhISEjOiImIiYiJSw3IidxZTciJ1AkUiIiJywkSCIiJ08tN0YnRihGKUYqIidDPE5GKEYpRipGKyImLHomRilGKkYrRiwiJ1YjKUdGKkYrRixGLSInMT86RiU=TTdSMApJQVJUQUJMRV9TQVZFLzE4NDQ2ODg0MjI0MjE2MTc2ODcwWCwlKWFueXRoaW5nRzYiRiVbZ2whIiUhISEjOiImIiYiIiIiIiFGJ0YnRiciJ3coKlFGJkYnRidGJyInXDk7IidAUFBGJkYnRiciJjM6KiInSS5GIiU9REYnRiciJ0ZdQyImU3gkIiUrKSlGJ0YnRiU=TTdSMApJQVJUQUJMRV9TQVZFLzE4NDQ2ODg0MjI0MjE2MTc3MTEwWCwlKWFueXRoaW5nRzYiRiVbZ2whIiUhISEjKiIkIiQiJSw3IidxZTciJ1AkUiJGJ0YoIicsJEgiRihGKSInTy03RiU=TTdSMApJQVJUQUJMRV9TQVZFLzE4NDQ2ODg0MjI0MjE2MTc3MjMwWColKWFueXRoaW5nRzYiRiVbZ2whIyUhISEiJCIkIScsJEgiISdPLTchJ0M8TkYlTTdSMApJQVJUQUJMRV9TQVZFLzE4NDQ2ODg0MjI0MjE2MTc4MDcwWColKWFueXRoaW5nRzYiRiVbZ2whIyUhISEiJCIkIicqKnk6IiZzNikiJ0giKVFGJQ==