mod計算の基本

// 基本的なmod計算
function basicMod(a, m) {
    return a % m;
}

// 高速べき乗（modular exponentiation）
function fastPower(base, exp, mod) {
    let result = 1;
    base = base % mod;
    while (exp > 0) {
        if (exp % 2 === 1) {
            result = (result * base) % mod;
        }
        exp = Math.floor(exp / 2);
        base = (base * base) % mod;
    }
    return result;
}

// モジュラ逆元（拡張ユークリッドの互除法）
function modularInverse(a, m) {
    function extendedGcd(a, b) {
        if (b === 0) return { gcd: a, x: 1, y: 0 };
        const result = extendedGcd(b, a % b);
        return {
            gcd: result.gcd,
            x: result.y,
            y: result.x - Math.floor(a / b) * result.y
        };
    }
    
    const result = extendedGcd(a, m);
    if (result.gcd !== 1) {
        throw new Error("モジュラ逆元が存在しません");
    }
    return ((result.x % m) + m) % m;
}

// mod演算の性質確認
function demonstrateModProperties(a, b, m) {
    // 加法の性質
    const addMod1 = (a + b) % m;
    const addMod2 = ((a % m) + (b % m)) % m;
    console.log(`加法の性質: ${addMod1 === addMod2}`);
    
    // 乗法の性質
    const mulMod1 = (a * b) % m;
    const mulMod2 = ((a % m) * (b % m)) % m;
    console.log(`乗法の性質: ${mulMod1 === mulMod2}`);
    
    return { addMod1, addMod2, mulMod1, mulMod2 };
}

// 使用例
console.log(basicMod(17, 5)); // 2
console.log(fastPower(3, 5, 7)); // 5 (3^5 = 243, 243 mod 7 = 5)
console.log(modularInverse(3, 7)); // 5 (3 * 5 = 15 ≡ 1 (mod 7))

// 暗号学的応用例（簡易RSA）
function simpleRSAExample() {
    const p = 61, q = 53; // 素数
    const n = p * q; // 3233
    const phi = (p - 1) * (q - 1); // 3120
    const e = 17; // 公開指数
    const d = modularInverse(e, phi); // 秘密指数
    
    const message = 123;
    const encrypted = fastPower(message, e, n);
    const decrypted = fastPower(encrypted, d, n);
    
    console.log(`元メッセージ: ${message}`);
    console.log(`暗号化: ${encrypted}`);
    console.log(`復号化: ${decrypted}`);
    console.log(`正しく復号: ${message === decrypted}`);
}

simpleRSAExample();

// 実用的な応用例
class ModularArithmetic {
    constructor(modulus) {
        this.mod = modulus;
    }
    
    add(a, b) {
        return (a + b) % this.mod;
    }
    
    multiply(a, b) {
        return (a * b) % this.mod;
    }
    
    power(base, exp) {
        return fastPower(base, exp, this.mod);
    }
    
    inverse(a) {
        return modularInverse(a, this.mod);
    }
    
    // ハッシュ関数での使用例
    hash(data) {
        let hash = 0;
        for (let i = 0; i < data.length; i++) {
            hash = (hash * 31 + data.charCodeAt(i)) % this.mod;
        }
        return hash;
    }
}

// 法1009での演算
const mod1009 = new ModularArithmetic(1009);
console.log(mod1009.add(500, 600)); // 91
console.log(mod1009.multiply(123, 456)); // 56088 % 1009 = 423
console.log(mod1009.power(2, 10)); // 1024 % 1009 = 15
console.log(mod1009.hash("Hello World")); // ハッシュ値

// 分散システムでの使用例
function consistentHashing(key, numServers) {
    const hashValue = mod1009.hash(key);
    return hashValue % numServers;
}

console.log(consistentHashing("user123", 10)); // サーバー番号