| 查看: 808 | 回复: 0 | |||
[交流]
多项式g,f，在模p意义下的最大公因数，
程序计算
|
const { trace } = require("console" ;function gcdModP(g, f, p) { let d = g.slice(); // 复制 g(x) 的系数到 d(x) 数组中 let r = f.slice(); // 复制 f(x) 的系数到 r(x) 数组中 while (!isZeroPoly(r)) { let t = trim(d); if (t.length < r.length) { [t, r] = [r, t] } // 复制 d(x) 的系数到 t(x) 数组中 for (let i = 0; i < r.length; i++) { let j1 = t.length - r.length + i; t[j1] = t[j1] || 0n let quotient = (t[j1] * modInverse(r, p)) % p; // 计算商 for (let j = 0; j < r.length; j++) { let index = t.length - r.length + i + j; // console.log(index) t[index] = t[index] || 0n t[index] -= quotient * r[j]; // 更新 t(x) 的系数 t[index] = (t[index] % p + p) % p; // 取模 } // console.log(t); } d = r.slice(); // 复制 r(x) 的系数到 d(x) 数组中 r = t.slice(d.length - r.length + 1); // 复制 t(x) 的系数到 r(x) 数组中 // console.log(d, r); r = trim(r); } // 将 d(x) 的系数除以它的首项系数，确保它是首项系数为 1 的幂次多项式 let dLeadingCoefficient = d[d.length - 1]; for (let i = 0; i < d.length; i++) { d = (d * modInverse(dLeadingCoefficient, p)) % p; } return d; } function modInverse(a, p) { // 使用扩展欧几里得算法计算 a 在模 p 意义下的逆元 let [x, y] = extendedEuclideanAlgorithm(a, p); return (x % p + p) % p; } function extendedEuclideanAlgorithm(a, b) { // 扩展欧几里得算法返回 a 和 b 的最大公因数 d，以及满足 ax + by = d 的整数 x 和 y if (b === 0n) { return [1n, 0n, a]; } let [x, y, d] = extendedEuclideanAlgorithm(b, a % b); return [y, x - (a / b) * y, d]; } /** * @param {Array<Number>} array */ function trim(array) { let i = 0; for (; i < array.length; i++) { // const element = array[index]; if (array != 0n) { break } } let j = array.length - 1; for (; j > 0; j--) { // const element = array[index]; if (array[j] != 0n) { break } } return array.slice(i, j + 1) } // console.log(trim([0n, 0n, 0n, 0n, 0n, 0n])); /** * 判断一个多项式是否为 0。 * * @param {Array} poly - 待判断的多项式 * @returns {boolean} 是否为 0 */ function isZeroPoly(poly) { for (let i = 0; i < poly.length; i++) { if (poly !== 0n) { return false; } } return true; } test() function test() { // console.log(modInverse(5n, 47n)); // console.log(trimStart([0n, 0n, 1n, 2n])) // 测试用例 1 let g1 = [6n, 2n]; let f1 = [17n, 15n]; let p1 = 7n; console.log("结果", gcdModP(g1, f1, p1)); // // 测试用例 3 let f3 = [3n, 1n, 3n, 1n]; let g3 = [3n, 1n]; // 3 + x let p3 = 101n; console.log("结果3", gcdModP(g3, f3, p3)); let f4 = [3n, 4n, 4n, 1n]; let g4 = [3n, 1n]; // 3 + x let p4 = 101n; console.log("结果4", gcdModP(g4, f4, p4)); } module.exports = { gcdModP } 多项式g,f，在模p意义下的最大公因数， 结果4为什么是1呀，有人帮忙解答下吗 发自小木虫Android客户端 |
回复此楼» 猜你喜欢
焦虑
已经有10人回复
-
298-一志愿中国农业大学-求调剂
已经有3人回复
-
265求调剂
已经有3人回复
-
297求调剂
已经有3人回复
-
302求调剂
已经有8人回复
-
环境工程调剂
已经有7人回复
-
268求调剂
已经有6人回复
-
311求调剂
已经有11人回复
-
工科材料085601 279求调剂
已经有4人回复
-
301求调剂
已经有9人回复
