|
const Cube = require('cubejs'); |
|
const fs = require('fs'); |
|
const {cube2number, randint, buffer2cubes, cubes2buffer} = require('./utils.js'); |
|
const {exit} = require('process'); |
|
|
|
Cube.initSolver(); |
|
|
|
const pow = (a, n) => { |
|
const r = new Cube(); |
|
const x = a.clone(); |
|
while (n !== 0n) { |
|
if (n % 2n === 1n) { |
|
r.multiply(x); |
|
} |
|
x.multiply(x); |
|
n /= 2n; |
|
} |
|
return r; |
|
}; |
|
const inv = (a) => { |
|
return (new Cube()).move(a.solve()); |
|
}; |
|
|
|
const str = '['+(fs.readFileSync('./output.txt')+'').split('g').join('"g"').split('h').join('"h"').split('c1').join('"c1"').split('c2').join('"c2"').split('}').join('},')+']'; |
|
const json = JSON.parse(str.split('},\n]').join('}]')); |
|
const ORDER = 43_252_003_274_489_856_000n; |
|
const ords = [134217728, 4782969, 125, 49, 11]; |
|
|
|
const extgcd = (a,b)=>{ |
|
let [x0,y0,x1,y1] = [1n,0n,0n,1n]; |
|
while(b != 0){ |
|
[q,a,b] = [a/b, b, a%b]; |
|
[x0,x1] = [x1, x0-q*x1]; |
|
[y0,y1] = [y1, y0-q*y1]; |
|
} |
|
return [a, x0, y0]; |
|
}; |
|
const modinv = (a, n) => { |
|
let [g,x,y] = extgcd(a,n); |
|
return (x + n) % n; |
|
}; |
|
|
|
const dlogBG = (g, gx, ord)=>{ |
|
const m = Math.ceil(Math.sqrt(ord)); |
|
const hash = {}; |
|
for(let j=0; j<m; j++){ |
|
const gj = pow(g, BigInt(j)); |
|
const gstr = cube2number(gj); |
|
if(gstr in hash)continue; |
|
hash[gstr] = j; |
|
} |
|
const ginv = inv(g); |
|
const ginvm = pow(ginv, BigInt(m)); |
|
let gamma = gx; |
|
for(let i=0; i<m; i++){ |
|
const gstr = cube2number(gamma); |
|
if(gstr in hash){ |
|
// console.log(gstr); |
|
// console.log(hash[gstr]); |
|
const ans = i*m + hash[gstr]; |
|
// console.log(pow(g,BigInt(ans)).solve()); |
|
// console.log(gx.solve()); |
|
return ans; |
|
} |
|
gamma = gamma.multiply(ginvm); |
|
} |
|
console.log('error'); |
|
}; |
|
|
|
const dlogPH = (g, gx)=>{ |
|
const anses = [0,0,0,0,0]; |
|
for(let i=0; i<5; i++){ |
|
const ord = ords[i]; |
|
const gg = pow(g, ORDER / BigInt(ord)); |
|
const gxx = pow(gx, ORDER / BigInt(ord)); |
|
anses[i] = BigInt(dlogBG(gg, gxx, ord)); |
|
} |
|
// garner |
|
res = 0n |
|
for(let i=0; i<5; i++){ |
|
[d,x,y] = extgcd(BigInt(ords[i]), ORDER/BigInt(ords[i])); |
|
res += y * (ORDER / BigInt(ords[i])) * anses[i]; |
|
} |
|
res = (res % ORDER + ORDER) % ORDER; |
|
console.log(anses); |
|
console.log(res); |
|
return res; |
|
}; |
|
|
|
const cubes = []; |
|
for(const dat of json){ |
|
let {g,h,c1,c2} = dat; |
|
g = (new Cube()).move(g); |
|
h = (new Cube()).move(h); |
|
c1 = (new Cube()).move(c1); |
|
c2 = (new Cube()).move(c2); |
|
// h = g^x |
|
// c1 = g^y |
|
// c2 = m * h^y |
|
// h^y = (g^x)^y |
|
// given g^x, g, find x |
|
const y = dlogPH(g, c1); |
|
const gy = pow(g, BigInt(y)); |
|
console.log(cube2number(c1) === cube2number(gy)); |
|
const hy = pow(h, BigInt(y)); |
|
const m = c2.multiply(inv(hy)); |
|
cubes.push(m); |
|
} |
|
const buf = cubes2buffer(cubes); |
|
console.log(buf); |
|
console.log((new TextDecoder).decode(buf)); |