繰り返し二乗法

// 繰り返し二乗法（基本版）
function fastPower(base, exponent) {
    if (exponent === 0) return 1;
    
    let result = 1;
    let currentBase = base;
    let currentExp = exponent;
    
    while (currentExp > 0) {
        // 指数が奇数なら結果に基数を乗算
        if (currentExp % 2 === 1) {
            result *= currentBase;
        }
        
        // 基数を二乗し、指数を半分に
        currentBase *= currentBase;
        currentExp = Math.floor(currentExp / 2);
    }
    
    return result;
}

// モジュラー繰り返し二乗法
function fastPowerMod(base, exponent, modulus) {
    if (exponent === 0) return 1;
    
    let result = 1;
    let currentBase = base % modulus;
    let currentExp = exponent;
    
    while (currentExp > 0) {
        if (currentExp % 2 === 1) {
            result = (result * currentBase) % modulus;
        }
        
        currentBase = (currentBase * currentBase) % modulus;
        currentExp = Math.floor(currentExp / 2);
    }
    
    return result;
}

// 再帰版実装（教育的）
function fastPowerRecursive(base, exponent) {
    if (exponent === 0) return 1;
    if (exponent === 1) return base;
    
    if (exponent % 2 === 0) {
        // 偶数の場合: a^n = (a^(n/2))^2
        const half = fastPowerRecursive(base, exponent / 2);
        return half * half;
    } else {
        // 奇数の場合: a^n = a * a^(n-1)
        return base * fastPowerRecursive(base, exponent - 1);
    }
}

// 使用例
console.log(fastPower(3, 10)); // 59049
console.log(fastPowerMod(3, 13, 7)); // 6
console.log(fastPowerRecursive(2, 16)); // 65536

// 効率性の比較
function compareEfficiency(base, exponent) {
    console.time('ナイーブ法');
    let naiveResult = 1;
    for (let i = 0; i < exponent; i++) {
        naiveResult *= base;
    }
    console.timeEnd('ナイーブ法');
    
    console.time('繰り返し二乗法');
    const fastResult = fastPower(base, exponent);
    console.timeEnd('繰り返し二乗法');
    
    console.log(`結果一致: ${naiveResult === fastResult}`);
    
    // 理論的な計算回数
    const naiveMultiplications = exponent;
    const fastMultiplications = Math.ceil(Math.log2(exponent + 1));
    const speedup = naiveMultiplications / fastMultiplications;
    
    console.log(`ナイーブ法: ${naiveMultiplications}回の乗算`);
    console.log(`繰り返し二乗法: ${fastMultiplications}回の反復`);
    console.log(`理論的高速化: 約${speedup.toFixed(1)}倍`);
}

compareEfficiency(3, 100);

// 二進表現を使った理解
function explainBinaryExponentiation(base, exponent) {
    console.log(`${base}^${exponent} の計算過程:`);
    console.log(`指数の二進表現: ${exponent} = ${exponent.toString(2)}₂`);
    
    let result = 1;
    let currentPower = base;
    let exp = exponent;
    let step = 0;
    
    while (exp > 0) {
        const bit = exp % 2;
        console.log(`ステップ${++step}: 二進ビット = ${bit}`);
        
        if (bit === 1) {
            result *= currentPower;
            console.log(`  → result *= ${currentPower} → result = ${result}`);
        }
        
        if (exp > 1) {
            currentPower *= currentPower;
            console.log(`  → 基数を二乗: ${Math.sqrt(currentPower)} → ${currentPower}`);
        }
        
        exp = Math.floor(exp / 2);
    }
    
    console.log(`最終結果: ${result}`);
    return result;
}

explainBinaryExponentiation(3, 13);

// 暗号学的応用例（RSA暗号の簡易版）
function simpleRSADemo() {
    // 小さな素数を使用（実際のRSAはもっと大きな数）
    const p = 61, q = 53;
    const n = p * q; // 3233
    const phi = (p - 1) * (q - 1); // 3120
    const e = 17; // 公開指数
    
    // 秘密指数dを計算（簡略化）
    const d = 2753; // modularInverse(e, phi)
    
    const message = 123;
    
    // 暗号化: c = m^e mod n
    const encrypted = fastPowerMod(message, e, n);
    console.log(`暗号化: ${message}^${e} mod ${n} = ${encrypted}`);
    
    // 復号化: m = c^d mod n
    const decrypted = fastPowerMod(encrypted, d, n);
    console.log(`復号化: ${encrypted}^${d} mod ${n} = ${decrypted}`);
    
    console.log(`復号成功: ${message === decrypted}`);
}

simpleRSADemo();

// 大きな数での効率性実証
function largePowerDemo() {
    const base = 2;
    const exponent = 1000;
    const modulus = 1000000007; // 大きな素数
    
    console.log(`大きな数での計算: ${base}^${exponent} mod ${modulus}`);
    
    console.time('モジュラー繰り返し二乗法');
    const result = fastPowerMod(base, exponent, modulus);
    console.timeEnd('モジュラー繰り返し二乗法');
    
    console.log(`結果: ${result}`);
    console.log(`反復回数: ${Math.ceil(Math.log2(exponent + 1))}`);
    console.log(`ナイーブ法なら${exponent}回の乗算が必要`);
}

largePowerDemo();