ユークリッドの互除法メニュー【合同式・modの演算・modの逆元・高速な累乗の計算・RSA暗号の基本原理】
【合同式】コード
reader.on('close', () => {
const [N, A] = lines[0].split(' ').map(Number);
const surplus = A % N;
for (let i = 1; i <= 100000; i++) { // 1〜100000まで 順番に…
if (i % N === surplus) { // i÷N の剰余と A÷N の剰余が同じなら
console.log(i); // iを表示
}
}
});
剰余が一致するかどうか 順番に演算しています。
【mod の演算】コード 1/2《C++の実装例参照》
reader.on('close', () => {
const N = Number(lines[0]);
const [a, cal, b] = lines[1].split(' ');
const [A, B] = [a, b].map(Number); // a, b を数値に変換して A, B に代入
let ans = 1; // A[cal]B (mod N)
switch (cal) {
case '+':
ans = (A % N + B % N) % N;
break;
case '-':
ans = (A % N - B % N + N) % N;
break;
case '*':
ans = (A % N) * (B % N) % N;
break;
case '^':
for (let i = 0; i < B; i++){
ans *= A;
ans %= N;
}
break;
}
console.log(ans);
});A[cal]B (mod N) の計算でした。C++の実装例を参照しました。
cal が ‘-‘ の場合 A % N – B % N が負の数になると演算結果がマイナスになるので N 加算してから剰余を計算しないとダメみたいね。
【mod の演算】コード 2/2 《数式の通り計算すると50点》
reader.on('close', () => {
const N = Number(lines[0]);
const [a, cal, b] = lines[1].split(' ');
const [A, B] = [a, b].map(Number);
let ans = 0; // A[cal]B (mod N)
switch (cal) {
case '+':
ans = (A + B) % N;
break;
case '-':
ans = (A - B) % N;
break;
case '*':
ans = (A * B) % N;
break;
case '^':
ans = (A ** B) % N;
break;
}
console.log(ans);
});イマイチ 納得できなかったので 数式の流れに沿ってコードを書くと (演算結果が負の数になるケース) と (大きな数値になるケース) は ☓ でした。
【mod の逆元】コード《拡張ユークリッドの互除法》
reader.on('close', () => {
const extgcd = (a, b) => { // 拡張ユークリッドの互除法
if (b) {
const [y, x] = extgcd(b, a % b);
return [x, y - Math.floor(a / b) * x];
}
return [1, 0];
};
const [M, A] = lines[0].split(' ').map(Number);
console.log((extgcd(M, A)[1] + M) % M);
});
A × N = 1(mod M) となる 1 以上 M 未満の整数 N を 「mod M での A の mod 逆元」といい A^{-1} (mod M) と書く…
そうです。
mod M での A の mod 逆元を求めるには、 x , y についての 1 次方程式 Ax + My = 1 の 解 x が分かれば良い…。
前出の 拡張ユークリッドの互除法 のコード3 の function ectgcd(a, b)を用いて求めています。
【高速な累乗の計算】コード1/3《for文で計算》
reader.on('close', () => {
const [A, B, M] = lines[0].split(' ').map(Number);
let ans = 1;
for (let i = 0; i < B; i++){ // A ^ B(mod M)
ans *= A;
ans %= M;
}
console.log(ans);
});for文では 計算量オーバーになるかと思ったけど 通過できました。
【高速な累乗の計算】コード 2/3《繰り返し二乗法》
// A^B(mod M)
reader.on('close', () => {
const pow = (a, b, m) => {
b = b.toString(2).split('').map(Number);
ans = 1;
while (b[0]) {
if (b.pop()) {
ans = (ans * a) % m;
}
a = (a * a) % m;
}
return ans;
};
const [A, B, M] = lines[0].split(' ').map(Number);
console.log(pow(A, B, M));
});シフト演算子 使ったことがなかったので ｂ を 2進数の文字列に変換してから 更に数値化した配列に変換しました。
【高速な累乗の計算】コード 3/3《C++ の実装例参照》
reader.on('close', () => {
const pow = (a, b, m) => {
ans = 1;
while (b > 0) {
if (b & 1) {
ans = (ans * a) % m;
}
a = (a * a) % m;
b >>= 1;
}
return ans;
};
const [A, B, M] = lines[0].split(' ').map(Number);
console.log(pow(A, B, M));
});C++ の実装例を書き換えましたが C++ と同じ演算子で OKでした。
【RSA 暗号の基本原理】コード
reader.on('close', () => {
const extgcd = (a, b) => { // 拡張ユークリッドの互除法
if (b) {
let [y, x] = extgcd(b, a % b);
y -= Math.floor(a / b) * x;
return [x, y];
}
return [1, 0];
};
const pow = (a, b, m) => {
let ans = BigInt(1);
while (b > 0) {
if (b & 1) {
ans = (ans * a) % m;
}
a = (a * a) % m;
b >>= 1;
}
return Number(ans);
};
const [p, q, e, M] = lines[0].split(' ').map(Number);
const [n, m] = [p * q, (p - 1) * (q - 1)];
const d = (extgcd(m, e)[1] + m) % m;
console.log(d);
const E = pow(BigInt(M), e, BigInt(n));
console.log(E);
console.log(pow(BigInt(E), d, BigInt(n)));
});メニューの最初からやり直して やっと何とかできたって感じ。演算でBigInt()使うのって 久しぶり。
【RSA 暗号の基本原理】コード 2 《BigInt()使用せずエラー》
reader.on('close', () => {
const extgcd = (a, b) => { // 拡張ユークリッドの互除法
if (b) {
let [y, x] = extgcd(b, a % b);
y -= Math.floor(a / b) * x;
return [x, y];
}
return [1, 0];
};
const pow = (a, b, m) => {
ans = 1;
while (b > 0) {
if (b & 1) {
ans = (ans * a) % m;
}
a = (a * a) % m;
b >>= 1;
}
return ans;
};
const [p, q, e, M] = lines[0].split(' ').map(Number);
const [n, m] = [p * q, (p - 1) * (q - 1)];
d = (extgcd(m, e)[1] + m) % m;
console.log(d);
E = pow(e, M, n) % n;
console.log(E);
console.log(pow(E, d, n));
});ほぼ正解だと思うのですが 0点 でした。BigInt() を使わないとダメだったのか…。
コメント