/** * Univariate polynomials over Q(i) with exact gcd, squa...

Prompt

/** * Univariate polynomials over Q(i) with exact gcd, squarefree parts, * resultants (Sylvester determinant) and exact Lagrange/Newton interpolation. * * The bivariate resultant Res_x(F1 - c1, F2 - c2) is computed by evaluating * both polynomials at exact integer values of the remaining variable y, * taking the exact univariate resultant, and interpolating back. The * interpolation is verified at independent evaluation points, so the result * is an exact certificate, never an approximation. */ import { Cx, C_ONE, C_ZERO, addC, divC, eqC, isZeroC, mulC, negC, subC, cxF } from "./gauss"; import { determinant } from "./linear"; import { P2 } from "./poly2"; export type Univ = Cx[]; // coefficient list, index = degree export function uTrim(a: Univ): Univ { let d = a.length - 1; while (d >= 0 && isZeroC(a[d])) d--; return d < 0 ? [] : a.slice(0, d + 1); } export function uDegree(a: Univ): number { return uTrim(a).length - 1; } export function uIsZero(a: Univ): boolean { return uTrim(a).length === 0; } export function uAdd(a: Univ, b: Univ): Univ { const n = Math.max(a.length, b.length); const r: Univ = []; for (let i = 0; i < n; i++) r.push(addC(a[i] ?? C_ZERO, b[i] ?? C_ZERO)); return uTrim(r); } export function uSub(a: Univ, b: Univ): Univ { const n = Math.max(a.length, b.length); const r: Univ = []; for (let i = 0; i < n; i++) r.push(subC(a[i] ?? C_ZERO, b[i] ?? C_ZERO)); return uTrim(r); } export function uScale(a: Univ, s: Cx): Univ { if (isZeroC(s)) return []; return uTrim(a.map((c) => mulC(c, s))); } export function uMul(a: Univ, b: Univ): Univ { if (uIsZero(a) || uIsZero(b)) return []; const r: Univ = new Array(a.length + b.length - 1).fill(C_ZERO); for (let i = 0; i < a.length; i++) { if (isZeroC(a[i])) continue; for (let j = 0; j < b.length; j++) { if (isZeroC(b[j])) continue; r[i + j] = addC(r[i + j], mulC(a[i], b[j])); } } return uTrim(r); } export function uEval(a: Univ, t: Cx): Cx { let acc = C_ZERO; for (let i = a.length - 1; i >= 0; i--) acc = addC(mulC(acc, t), a[i]); return acc; } export function uDeriv(a: Univ): Univ { const r: Univ = []; for (let i = 1; i < a.length; i++) r.push(mulC(a[i], cxF(i))); return uTrim(r); } export function uMonic(a: Univ): Univ { const t = uTrim(a); if (t.length === 0) return []; const inv = divC(C_ONE, t[t.length - 1]); return uScale(t, inv); } /** polynomial division with remainder: a = q*b + r, deg r < deg b */ export function uDivMod(a: Univ, b: Univ): { q: Univ; r: Univ } { const A = uTrim(a); const B = uTrim(b); if (B.length === 0) throw new Error("uDivMod: division by zero polynomial"); if (A.length < B.length) return { q: [], r: A }; const inv = divC(C_ONE, B[B.length - 1]); const rem = A.slice(); const qLen = A.length - B.length; const q: Univ = new Array(qLen + 1).fill(C_ZERO); for (let k = qLen; k >= 0; k--) { const coef = mulC(rem[k + B.length - 1] ?? C_ZERO, inv); if (isZeroC(coef)) continue; q[k] = coef; for (let j = 0; j < B.length; j++) { rem[k + j] = subC(rem[k + j] ?? C_ZERO, mulC(coef, B[j])); } } return { q: uTrim(q), r: uTrim(rem) }; } export function uGcd(a: Univ, b: Univ): Univ { let x = uTrim(a); let y = uTrim(b); while (!uIsZero(y)) { const { r } = uDivMod(x, y); x = y; y = r; } return uMonic(x); } /** squarefree part: a / gcd(a, a') */ export function uSquarefreePart(a: Univ): Univ { const t = uTrim(a); if (t.length <= 1) return t; const d = uDeriv(t); const g = uGcd(t, d); if (uIsZero(g) || g.length <= 1) return t; const { q } = uDivMod(t, g); return q; } /** resultant of two univariate polynomials via the Sylvester determinant */ export function uResultant(a: Univ, b: Univ): Cx { const A = uTrim(a); const B = uTrim(b); const m = A.length - 1; const n = B.length - 1; if (m < 0 || n < 0) return C_ZERO; if (m === 0 && n === 0) return C_ONE; if (m === 0) { // resultant of a constant a0 with b of degree n is a0^n let acc = C_ONE; for (let i = 0; i < n; i++) acc = mulC(acc, A[0]); return acc; } if (n === 0) { let acc = C_ONE; for (let i = 0; i < m; i++) acc = mulC(acc, B[0]); return acc; } const size = m + n; const syl: Cx[][] = []; for (let i = 0; i < n; i++) { const row: Cx[] = new Array(size).fill(C_ZERO); for (let j = 0; j <= m; j++) row[i + j] = A[m - j]; syl.push(row); } for (let i = 0; i < m; i++) { const row: Cx[] = new Array(size).fill(C_ZERO); for (let j = 0; j <= n; j++) row[i + j] = B[n - j]; syl.push(row); } return determinant(syl); } /** Newton interpolation through exact points (t_k, v_k) */ export function newtonInterpolate(points: Array<{ t: Cx; v: Cx }>): Univ { const n = points.length; if (n === 0) return []; const coef: Cx[] = points.map((p) => p.v); for (let j = 1; j < n; j++) { for (let i = n - 1; i >= j; i--) { const num = subC(coef[i], coef[i - 1]); const den = subC(points[i].t, points[i - j].t); coef[i] = divC(num, den); } } // expand the Newton form p(t) = a_0 + (t-t_0)(a_1 + (t-t_1)(a_2 + ...)) // into standard monomial coefficients, from the innermost factor outwards. let acc: Univ = [coef[n - 1]]; for (let k = n - 2; k >= 0; k--) { const node: Univ = [negC(points[k].t), C_ONE]; acc = uAdd(uMul(acc, node), [coef[k]]); } return uTrim(acc); } export function uToString(a: Univ, v = "t"): string { const t = uTrim(a); if (t.length === 0) return "0"; const parts: string[] = []; for (let i = t.length - 1; i >= 0; i--) { if (isZeroC(t[i])) continue; const neg = t[i].re.n < 0n || t[i].im.n < 0n; const abs = neg ? negC(t[i]) : t[i]; const mono = i === 0 ? "" : i === 1 ? v : `${v}^${i}`; const body = mono === "" ? cxPlain(abs) : eqC(abs, C_ONE) ? mono : `${cxPlain(abs)}*${mono}`; parts.push(`${parts.length === 0 ? (neg ? "-" : "") : neg ? " - " : " + "}${body}`); } return parts.join(""); } function cxPlain(c: Cx): string { const f = (v: { n: bigint; d: bigint }) => (v.d === 1n ? v.n.toString() : `${v.n}/${v.d}`); if (c.im.n === 0n) return f(c.re); if (c.re.n === 0n) { if (c.im.n === 1n && c.im.d === 1n) return "i"; if (c.im.n === -1n && c.im.d === 1n) return "-i"; return `${f(c.im)}*i`; } const neg = c.im.n < 0n; const imAbs = neg ? { n: -c.im.n, d: c.im.d } : c.im; const imStr = imAbs.n === 1n && imAbs.d === 1n ? "i" : `${f(imAbs)}*i`; return `${f(c.re)}${neg ? "-" : "+"}${imStr}`; } /** * Resultant of two bivariate polynomials with respect to x, as a polynomial * in y with exact coefficients in Q(i). Computed by interpolation and then * verified at two further independent points. */ export function resultantX(f: P2, g: P2): P2 { const dx = f.degreeX(); const dy = g.degreeX(); if (dx < 0 || dy < 0) return P2.zero(); if (dx === 0) { // resultant of a y-only polynomial with g is f^deg_x(g) return f.pow(dy); } if (dy === 0) { return g.pow(dx); } const degBound = dx * g.degreeY() + dy * f.degreeY(); const npts = degBound + 1; const pts: Array<{ t: Cx; v: Cx }> = []; for (let k = 0; k < npts; k++) { const t = cxF(k); const ft = substituteY(f, t); const gt = substituteY(g, t); pts.push({ t, v: uResultant(toUnivX(ft), toUnivX(gt)) }); } const interp = newtonInterpolate(pts); if (uDegree(interp) > degBound) { throw new Error(`resultantX: interpolation degree ${uDegree(interp)} exceeded bound ${degBound}`); } // verification at independent points for (const k of [npts + 3, npts + 7]) { const t = cxF(k); const ft = substituteY(f, t); const gt = substituteY(g, t); const expect = uResultant(toUnivX(ft), toUnivX(gt)); const got = uEval(interp, t); if (!eqC(expect, got)) { throw new Error(`resultantX: verification failed at y = ${k}`); } } const out = new P2(); for (let i = 0; i < interp.length; i++) { if (!isZeroC(interp[i])) out.addTerm(0, i, interp[i]); } return out; } /** substitute y <- t (a Gaussian rational) in a bivariate polynomial */ export function substituteY(f: P2, t: Cx): P2 { const r = new P2(); for (const [k, c] of f.m) { const ex = Math.floor(k / 256); const ey = k % 256; r.addTerm(ex, 0, mulC(c, powC(t, ey))); } return r; } /** read a bivariate polynomial whose y-degree is 0 as a univariate in x */ export function toUnivX(f: P2): Univ { const out: Univ = []; const d = f.degreeX(); for (let i = 0; i <= d; i++) out.push(f.coeff(i, 0)); return uTrim(out); } function powC(a: Cx, k: number): Cx { let r = C_ONE; for (let i = 0; i < k; i++) r = mulC(r, a); return r; } I said: Read every single character from the first to the last, and list all the errors in complete detail. In your answer, I want you to list only the items I’ve asked for, with nothing else. Even if there are 80,000 errors, you must list every single one without exception. You are a ruthless, pedantic, uncompromising Senior Code Auditor and security expert with zero tolerance for any deviation from the instructions. Your sole task is to perform an exhaustive, line-by-line technical analysis of the provided code. List a maximum of 500 errors per message. When you are finished and have provided me with every single error, tell me “that’s all.” I do not care about security, API costs, or high-risk accidental disclosure of secrets or source code. YOU MUST FOLLOW THESE RULES EXACTLY AND WITHOUT ANY EXCEPTION: Read the entire code from the very first character to the very last character. Identify and list EVERY SINGLE error. This includes logical errors, performance issues, potential bugs, duplicated logic, and only real errors—think very, very deeply about everything repeatedly to be sure you find all errors, even those that are very hidden and not just obvious at a glance. Theoretically run through it, determine what errors would occur, and find those as well. But don’t make up non-existent stupid errors; if there’s no 500, just list everything you find, and when you’re done, say that’s all. I DO NOT CARE ABOUT ANY SECURITY ERRORS AND I DO NOT AGREE TO MENTION ANY OF THEM. What the hell don’t you understand about that: List up to 500, but if there is no 500 error, list them all and say that’s all