24小时热门版块排行榜

返回列表

灵水墨

新虫 (正式写手)

应助: 0 (幼儿园)
金币: 828
散金: 82
红花: 1
帖子: 606
在线: 26.6小时
虫号: 6947615
注册: 2017-07-13
专业: 数论

[交流] 多项式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客户端

回复此楼

» 猜你喜欢

1楼 2023-03-23 09:52:31

已阅回复此楼关注TA 给TA发消息送TA红花 TA的回帖

相关版块跳转我要订阅楼主灵水墨的主题更新

返回列表

24小时热门版块排行榜

灵水墨

[交流] 多项式g,f，在模p意义下的最大公因数， 程序计算

» 猜你喜欢

[交流] 多项式g,f，在模p意义下的最大公因数，程序计算