Бързо степенуване

Код на:JavaC#PythonJavaScript

Накратко: Бързото степенуване смята aⁿ с O(log n) умножения, като повдига на квадрат и гледа двоичните цифри на n; с остатък след всяко умножение смята и степен по модул.

Проблем

Ключът на HTTPS връзката

Когато браузърът отваря HTTPS страница, той и сървърът се договарят за общ таен ключ, без да го пращат по мрежата. В класическия вариант (Diffie–Hellman) всеки смята степен по модул: gᵃ mod p, където a е тайно число, дълго десетки цифри. Същата сметка стои в RSA подписите и в hash на текст, който умножава по степени на основата.

Наивният начин е цикъл, който умножава n пъти:

function powerLoop(a, n, m) {
  let result = 1n;
  for (let i = 0n; i < n; i++) {
    result = (result * a) % m;
  }
  return result;
}

При показател от 77 цифри (например 2²⁵⁵ − 19) това са около 6 · 10⁷⁶ умножения. При милиард умножения в секунда цикълът ще върви 10⁶⁷ секунди, а Вселената е на около 4 · 10¹⁷. Сървърът обаче прави хиляди такива връзки в секунда.

Идеята

Квадратът на половината

3¹³ не иска 13 умножения. 3¹³ = 3⁶ · 3⁶ · 3, а 3⁶ = 3³ · 3³. Всяка стъпка разполовява показателя:

• aⁿ = (aⁿᐟ²)², ако n е четно;
• aⁿ = (aⁿᐟ²)² · a, ако n е нечетно (n / 2 е целочислено деление);
• a⁰ = 1: това е дъното.

function power(a, n, m) {
  if (n === 0n) {
    return 1n;
  }
  const half = power(a, n / 2n, m);
  const square = (half * half) % m;
  if (n % 2n === 1n) {
    return (square * a) % m;
  }
  return square;
}

console.log(String(power(3n, 13n, 1_000_000_007n)));
console.log(String(power(5n, 1_000_000_000n, 1_000_000_007n)));

Изход

1594323
142848001

Остатъкът по m след всяко умножение пази числата малки: (x · y) mod m е същото като ((x mod m) · (y mod m)) mod m. Тук m = 1 000 000 007, просто число, честа граница в hash-ове и задачи по програмиране.

Колко струва? Всяко извикване дели n на 2, точно като двоичното търсене, затова дълбочината е около log₂ n: при n = 10⁹ са 30 рамки. Извикването не е опашково (след него има повдигане на квадрат), но от урока „Стекът от извиквания отвътре“ знаеш, че 30 рамки са нищо за стека. Работата е най-много две умножения на ниво: O(log n) вместо O(n).

Идеята

Без рекурсия: двоичните цифри на n

Същото може и с цикъл. 13 в двоично е 1101: 13 = 8 + 4 + 1, затова 3¹³ = 3⁸ · 3⁴ · 3¹. Цикълът чете цифрите на n отдясно наляво (n % 2 е последната, а n /= 2 я маха) и пази a, повдигнато на квадрат: 3¹, 3², 3⁴, 3⁸… При цифра 1 текущото a влиза в резултата.

function power(a, n, m) {
  let result = 1n;
  a %= m;
  while (n > 0n) {
    if (n % 2n === 1n) {
      result = (result * a) % m;
    }
    a = (a * a) % m;
    n /= 2n;
  }
  return result;
}

console.log(String(power(3n, 13n, 1_000_000_007n)));
console.log(String(power(5n, 1_000_000_000n, 1_000_000_007n)));

Изход

1594323
142848001

Умноженията са колкото цифрите на n (по едно повдигане на квадрат на цифра) плюс единиците в него (по едно умножение на резултата). Това е версията, която ползват библиотеките: няма рекурсия и не зависи от размера на стека.

Виж го

Квадратите влизат в резултата

function power(a, n, m) {
  let result = 1n;
  a %= m;
  while (n > 0n) {
    if (n % 2n === 1n) {
      result = (result * a) % m;
    }
    a = (a * a) % m;
    n /= 2n;
  }
  return result;
}

console.log(String(power(3n, 13n, 1_000_000_007n)));  // 1594323

Стъпка по стъпка, с думи

1. result започва от 1. n = 13, в двоично 1101: всяка двоична цифра решава дали a влиза в резултата.
2. n = 13 е нечетно: result = 1 · 3 = 3. После a става 3² = 9, а n става 6.
3. n = 6 е четно: result остава 3. Само a се повдига на квадрат: 9 · 9 = 81 = 3⁴, а n = 3.
4. n = 3: result = 3 · 81 = 243 = 3⁵. a = 6561 = 3⁸, n = 1.
5. n = 1: result = 243 · 6561 = 1594323 = 3¹³, защото 13 = 8 + 4 + 1. Цикълът пак повдига a на квадрат: 3¹⁶ е умножение, което никой не ползва.
6. n = 0 и цикълът спира: 7 умножения вместо 13. При n = 10⁹ са 43 вместо милиард.

Виж го

Броят умножения

Двете версии с брояч, на показатели от 10 до 10 000 000, а бързата и на милиард:

let multiplications = 0;

function powerLoop(a, n, m) {
  let result = 1n;
  for (let i = 0n; i < n; i++) {
    multiplications++;
    result = (result * a) % m;
  }
  return result;
}

function power(a, n, m) {
  let result = 1n;
  a %= m;
  while (n > 0n) {
    if (n % 2n === 1n) {
      multiplications++;
      result = (result * a) % m;
    }
    multiplications++;
    a = (a * a) % m;
    n /= 2n;
  }
  return result;
}

const m = 1_000_000_007n;
for (const n of [10n, 1_000n, 100_000n, 10_000_000n]) {
  multiplications = 0;
  powerLoop(5n, n, m);
  const slow = multiplications;
  multiplications = 0;
  power(5n, n, m);
  console.log(`n = ${n}: цикъл ${slow}, бързо ${multiplications} умножения`);
}
multiplications = 0;
power(5n, 1_000_000_000n, m);
console.log(`n = 1000000000: бързо ${multiplications} умножения`);

Изход

n = 10: цикъл 10, бързо 6 умножения
n = 1000: цикъл 1000, бързо 16 умножения
n = 100000: цикъл 100000, бързо 23 умножения
n = 10000000: цикъл 10000000, бързо 32 умножения
n = 1000000000: бързо 43 умножения

Пусни ги и тук. Bench брои по същото правило (едно умножение по модула е една операция), затова числата са тези от изхода горе. Милиард с наивния цикъл не го пускаме: Bench го оценява по кривата.

• Цикъл: n умножения O(n)
• Повдигане на квадрат O(log n)

Алгоритъм	n = 10	n = 1000	n = 100 000	n = 10 000 000	n = 1 000 000 000
Цикъл: n умножения	10	1000	100 000	10 000 000	≈ 1 000 000 000
Повдигане на квадрат	6	16	23	32	43

Кодът се пуска в твоя браузър на JavaScript. Броят операции е същият на всеки език, защото алгоритъмът е същият. Времето зависи от машината, затова е само за сравнение. „≈“ е оценка по кривата: толкова голямо n не пускаме, за да не замръзне страницата.

function power(a, n, m) {
  let result = 1n;
  a %= m;
  while (n > 0n) {
    if (n % 2n === 1n) {
      result = (result * a) % m;
    }
    a = (a * a) % m;
    n /= 2n;
  }
  return result;
}

Наивният цикъл расте като n, бързото като броя цифри на n: десет пъти по-голямо n добавя около 3,3 цифри, тоест 3 до 7 умножения.

Пробвай

15 или 16

Кой показател иска повече умножения?

let multiplications = 0;

function power(a, n, m) {
  let result = 1n;
  a %= m;
  while (n > 0n) {
    if (n % 2n === 1n) {
      multiplications++;
      result = (result * a) % m;
    }
    multiplications++;
    a = (a * a) % m;
    n /= 2n;
  }
  return result;
}

for (const n of [15n, 16n]) {
  multiplications = 0;
  power(3n, n, 1_000_000_007n);
  console.log(`${n}: ${multiplications} умножения`);
}

Отговор

15: 4 умножения
16: 5 умножения

15: 15 умножения
16: 16 умножения

15: 8 умножения
16: 6 умножения

Провери

Идеята

Когато произведението не се побира

Остатъкът държи числата под m, но произведението на две такива числа е до m². Ако m² не се побира в типа, сметката греши, и то тихо. Ето същата степен с по-голям модул:

function powerNumber(a, n, m) {
  let result = 1;
  a %= m;
  while (n > 0) {
    if (n % 2 === 1) {
      result = (result * a) % m;
    }
    a = (a * a) % m;
    n = Math.floor(n / 2);
  }
  return result;
}

console.log("Number:", powerNumber(5, 1_000_000_000, 1_000_000_007));
console.log("BigInt: " + power(5n, 1_000_000_000n, 1_000_000_007n));

Изход

Number: 150925072
BigInt: 142848001

Number е double: пази цели числа точно само до 2⁵³ ≈ 9 · 10¹⁵. Произведението на две числа под 1 000 000 007 е до 10¹⁸, губи последните си цифри и отговорът е грешен, без грешка. Затова в урока числата са BigInt (с n накрая: 5n), които растат колкото трябва. Двата вида не се смесват: 5n * 2 хвърля TypeError.

Идеята

Вграденото и показател от 77 цифри

В истинския код степента по модул не се пише на ръка:

const secret = 2n ** 255n - 19n;
const p = 2n ** 127n - 1n;
const bits = secret.toString(2);
console.log("Цифри в показателя: " + secret.toString().length);
console.log("Умножения при повдигане на квадрат: " + (bits.length + bits.replaceAll("0", "").length));
console.log("5^secret mod p = " + power(5n, secret, p));

Изход

Цифри в показателя: 77
Умножения при повдигане на квадрат: 508
5^secret mod p = 97285997395055909576908201857106207893

JavaScript няма вградено, затова тук работи power от урока, с BigInt. secret.toString(2) дава двоичните цифри. 508 умножения на числа от 39 цифри вместо 6 · 10⁷⁶: затова ключът се договаря за милисекунди. Библиотеките броят по-малко и от това, защото гледат по няколко цифри наведнъж, но идеята е същата.

Пробвай

Намери грешката

Тази версия връща верния резултат. Само че при n = 1 000 000 прави 2 048 575 умножения вместо 27. Кой ред е виновен?

Избери реда с грешката.

1function power(a, n, m) {2 if (n === 0n) {3 return 1n;4 }5 const square = (power(a, n / 2n, m) * power(a, n / 2n, m)) % m;6 if (n % 2n === 1n) {7 return (square * a) % m;8 }9 return square;10}

Провери

Пробвай

Попълни

Кога текущото a влиза в резултата?

function power(a, n, m) {
  let result = 1n;
  a %= m;
  while (n > 0n) {
    if () {
      result = (result * a) % m;
    }
    a = (a * a) % m;
    n /= 2n;
  }
  return result;
}

Провери

Упражнение

Лихва до цент

Реши задачата в редактора си.

Колко става депозитът. Влагаш 1000 € при 1% лихва на месец, която се добавя към сумата. Прочети броя месеци и отпечатай сумата, закръглена до цент. Сметни я точно, с цели числа: 1000 € са 100 000 цента, а след n месеца сумата е 100 000 · 101ⁿ / 100ⁿ цента. Напиши свое бързо степенуване с BigInt, без модул, и закръгли нагоре от половин цент.

Вход

120

Изход

След 120 месеца: 3300,39 €

При 120 месеца умноженията са малко и при наивния цикъл. Тук числата растат (101¹²⁰ има 241 цифри), затова всяко следващо умножение е по-скъпо, а пестенето на умножения важи още повече.

Още задачи

• Дневна лихва за 30 години. Същото с 0,01% на ден за 10 950 дни. Преброй умноженията на двете версии.
• Последните цифри. Отпечатай последните 6 цифри на 2¹⁰⁰⁰⁰⁰⁰⁰⁰⁰ (модул 1 000 000), без да строиш цялото число.

По-точно

Още за степента

По-точно, за любопитните

Числата на Фибоначи за O(log n). Същото повдигане на квадрат работи с матрица 2 × 2 вместо число: n-тото число на Фибоначи излиза от n-тата степен на [[1, 1], [1, 0]], с около 2 log₂ n умножения на матрици.

Елиптичните криви. Днес TLS договаря ключа най-често с елиптична крива (X25519). Там вместо умножение има „събиране на точки“, а вместо повдигане на квадрат „удвояване“, но алгоритъмът е същият: double-and-add по двоичните цифри на тайното число.

Постоянно време. Цикълът от урока умножава резултата само при цифра 1. Някой, който мери времето, може да познае колко единици има тайното число. Криптографските библиотеки затова правят еднаква работа за всяка цифра (Montgomery ladder). Затова криптография не се пише на ръка, а се ползва библиотека.

• JavaScript: 2n ** 255n е степен на BigInt без модул. Math.pow и ** с Number са за double.

Тест

Провери се

1. Колко умножения прави повдигането на квадрат при n = 1 000 000?

27: 1 000 000 има 20 двоични цифри и 7 единици1 000 000: по едно на всяка единица от n500 000: половината, защото n се дели на 2

2. Защо кодът взима остатъка по m след всяко умножение, а не само накрая?

Остатъкът накрая е същият, а така числата остават под m и умножението струва колкото на малки числаИначе резултатът е различенТака има по-малко умножения

3. Кое е вграденото бързо степенуване по модул?

Няма вградено: пишеш power с BigInt(a ** n) % m с NumberMath.pow(a, n) % m

4. В рекурсивната версия половината се смята с два рекурсивни извиквания вместо с едно. Какво става?

Резултатът е грешенСтекът се препълваРезултатът е верен, но умноженията пак са около n: всяко ниво удвоява извикванията

5. Колко рамки иска рекурсивната версия при n = 1 000 000 000?

Една, защото извикването е опашковоОколо милиардОколо 30: по една за всяко разполовяване на n

Провери

Започни урока отначало

Свързани уроци

• Нужно отпреди: Сложност по памет · Двоично търсене · Стекът от извиквания отвътре · От рекурсия към цикъл
• Задачи по темата: Рекурсия