Реализаия метода согласования и Полига-Хеллмана на JavaScript
Автор: Alexei Shulzhickij • Октябрь 23, 2022 • Лабораторная работа • 654 Слов (3 Страниц) • 117 Просмотры
Реализаия метода согласования и Полига-Хеллмана на JavaScript
Введем три константы для дальнейших расчетов:
a = 110
b = 12
p = 11807
Метод согласования (метод больших и малых шагов).
В основе метода лежит следующий факт: пусть и ; тогда для любого целого числа x, , найдутся такие целые числа l,t, что , . В этих условиях для нахождения числа x из сравнения [pic 1][pic 2][pic 3][pic 4][pic 5]
[pic 6]
Воспользуемся полученным разложением:
.[pic 7]
Это означает, что искомое значение l, t, могут быть найдены перебором величин и в указанных границах, а после этого будет определена и величина x.[pic 8][pic 9]
Вычилслим h, составим таблицы и и найдем индексы общих элементов:[pic 10][pic 11]
BGsteps = (p, a, b) => { p = BigInt(p), a = BigInt(a), b = BigInt(b) let h = BigInt(Math.ceil(Math.sqrt(Number(p)))) let bat = [...Array(Number(h)).keys()].map((s, t) => b * a ** BigInt(t) % p) let ahl = [...Array(Number(h)).keys()].map((s, l) => (a ** h) ** BigInt(l + 1) % p) let ret = bat.filter(s => ahl.includes(s)).map(s => { let [t, l] = [bat.indexOf(s), ahl.indexOf(s) + 1] return Number(h) * l - t }) return ret.length ? ret : 'Нет решений' |
Метод Полига-Хеллмана.
Пусть задано сравнение , и известно разложение p−1 на простые множители:[pic 12]
[pic 13]
Необходимо найти натуральное число x, удовлетворяющее сравнению. Заметим, что на практике всегда рассматривается случай, когда a – первообразный корень по модулю p. В этом случае сравнение имеет решение при любом b, взаимно простом с p.
Составим таблицу значений в переменную rij, составим систему уравнений по этой таблице и перебором значений (сложность перебора равна O(n)) найдем решение[pic 14]
SilverPH = (p, a, b) => { p = BigInt(p), a = BigInt(a), b = BigInt(b) let dups = [] let factors = factorizen(p - 1n) factors.forEach(s => dups[s] = 1 + (dups[s] || 0)) factors = [...dups.keys()].map(s => ({ q: BigInt(s), a: BigInt(dups[s] || 0) })).filter(s => s.a) let rij = Array(factors.length).fill().map((s, i) => Array(Number(factors[i].q)).fill()).map((s, i) => s.map((s, j) => a ** (BigInt(j) * (p - 1n) / factors[i].q) % p)) let findMod = (q, x) => BigInt(rij[q].indexOf(rij[q].find(s => s == x) || rij[q].find(s => s == x < 0 ? x + p : x - p))) let xs = factors.map((e, i) => { let x0 = findMod(i, b ** ((p - 1n) / e.q) % p) let x1 = findMod(i, BigInt((b * BigInt(Math.ceil(Number(a) ** Number(-x0))))) ** (p - 1n) / (e.q ** 2n) % p) let m = e.q ** e.a return { val: (x0 + x1 * e.q) % m == 0 ? 1 : (x0 + x1 * e.q) % m, mod: m } }) let x = 2n while ((x < p ** 2n) && !xs.every(s => x % s.mod == s.val)) x++; return x == p ** 2n - 1n ? 'Нет решений' : Number(x) |
...