4.3: Метод повторюваних квадратів

Обчислення великих потужностей може зайняти дуже багато часу. Так само, як кожен може обчислити\(2^2\) або\(2^8\text{,}\) кожен знає, як обчислити

\[ 2^{2^{1{,}000{,}000} }\text{.} \nonumber \]

Однак такі цифри настільки великі, що ми не хочемо намагатися проводити розрахунки; більш того, повз певного моменту обчислення були б нездійсненними, навіть якби ми мали кожен комп'ютер у світі в нашому розпорядженні. Навіть записати десяткове подання дуже великого числа може бути нерозумним. Це може бути тисячі або навіть мільйони цифр. Однак, якби ми могли обчислити щось на зразок

\[ 2^{37{,}398{,}332 } \pmod{ 46{,}389}\text{,} \nonumber \]

ми могли б дуже легко записати результат вниз, оскільки це буде число між\(0\) і\(46{,}388\text{.}\) Якщо ми хочемо обчислити потужності по модулю\(n\) швидко і ефективно, нам доведеться бути розумними. ¹

Результати в цьому розділі потрібні тільки в Главі 7.

Перше, що слід помітити, це те, що будь-яке число\(a\) може бути записано як сума різних повноважень,\(2\text{;}\) що ми можемо написати

\[ a = 2^{k_1} + 2^{k_2} + \cdots + 2^{k_n}\text{,} \nonumber \]

де\(k_1 \lt k_2 \lt \cdots \lt k_n\text{.}\) Це просто двійкове представлення\(a\text{.}\) Наприклад, двійкове представлення 57 є 111001, так як ми можемо написати\(57 = 2^0 + 2^3 + 2^4 + 2^5\text{.}\)

Закони експонентів все ще працюють в\({\mathbb Z}_n\text{;}\) тому, що, якщо\(b \equiv a^x \pmod{ n}\) і\(c \equiv a^y \pmod{ n}\text{,}\) тоді\(bc \equiv a^{x+y} \pmod{ n}\text{.}\) Ми можемо обчислити\(a^{2^k} \pmod{ n}\) в\(k\) множеннях шляхом обчислення

\ почати {збирати*} a^ {2^0}\ pmod {n}\ a^ {2^1}\ pmod {n}\\ vdots\\ a^ {2^k}\ pmod {n}\ текст {.} \ end {збирати*}

Кожен крок передбачає квадрат відповіді, отриманої на попередньому кроці, поділ на\(n\text{,}\) і взяття залишку.

Приклад 4.28

Ми обчислимо\(271^{321} \pmod{ 481}\text{.}\) Зверніть увагу, що

\[ 321 = 2^0 +2^6 + 2^8; \nonumber \]

отже, обчислення\(271^{ 321} \pmod{ 481}\) - це те ж саме, що обчислювальна

\[ 271^{ 2^0 +2^6 + 2^8 } \equiv 271^{ 2^0 } \cdot 271^{2^6 } \cdot 271^{ 2^8 } \pmod{ 481}\text{.} \nonumber \]

Так що досить буде обчислити\(271^{ 2^i } \pmod{ 481}\) де\(i = 0, 6, 8\text{.}\) Це дуже легко побачити, що

\[ 271^{ 2^1} = 73{,}441 \equiv 329 \pmod{ 481}\text{.} \nonumber \]

Ми можемо квадратувати цей результат, щоб отримати значення для\(271^{ 2^2} \pmod{481}\text{:}\)

\ почати {вирівнювати*} 271^ {2^2} &\ equiv (271^ {2^1}) ^2\ pmod {481}\\ &\ equiv (329) ^2\ pmod {481}\\ pmod {481}\\ equiv 16\ pmod {481}\ текст {}. \ end {вирівнювати*}

Використовуємо те, що\((a^{2^n})^2 \equiv a^{2 \cdot 2^n} \equiv a^{ 2^{n+1} } \pmod{ n}\text{.}\) Продовжуючи, ми можемо обчислити

\[ 271^{ 2^6 } \equiv 419 \pmod{481} \nonumber \]

і

\[ 271^{ 2^8 } \equiv 16 \pmod{481}\text{.} \nonumber \]

Тому,

\ почати {вирівнювати*} 271^ {321} &\ еквив 271^ {2^0 +2^6 + 2^8}\ pmod {481}\\ equiv 271^ {2^0}\ cdot 271^ {2^8}\ pmod {481}\\ &\ еквівалент 271\ cdot 419\ cdot 16\ pmod {481}\\ &\ еквівалент 1 {,} 816 {,} 784\ pmod {481}\\ &\ еквівалент 47\ pmod {481}\ текст {.} \ end {вирівнювати*}

Метод повторюваних квадратів виявиться дуже корисним інструментом, коли ми досліджуємо главу 7. Для розумного кодування і декодування повідомлень за цією схемою необхідно вміти швидко обчислювати великі потужності цілих чисел мод\(n\text{.}\)