Research Cryptanalysis: The Tonelli–Shanks Algorithm and Its Role in the Bitcoin Ecosystem with Practical Examples for Google Colab

📌 Abstract: This paper examines the mathematical apparatus for extracting the square root modulo a prime number—the Tonelli–Shanks algorithm. It shows how the choice of a prime number $p \equiv 3 (against 4)$ For the curve secp256k1 (used in Bitcoin), this allows the entire procedure to be reduced to a single exponentiation, dramatically speeding up the recovery of compressed public keys. Google Colab scripts are provided, clearly demonstrating all stages: checking the quadratic residue, calculating the root, decompressing the key, and comparing performance.

1. Introduction: The essence of the root extraction problem

In elliptic curve cryptography (ECC), the problem of finding such a number often arises. $r$ , What: $r^{2} \equiv n (against p)$

Where $p$ — odd prime, and $n$ — a quadratic residue. This operation is the basis for public key decompression in Bitcoin: given a known coordinate $x$ points on the curve need to restore the coordinates $and$ The general Tonelli–Shanks algorithm works for any odd prime $p$ , but its complexity $THE (\log^{4} p)$ can be significantly reduced with special selection $p$ .

2. Mathematical basis and cryptographic formulas

2.1. secp256k1 Curve

Bitcoin uses an elliptic curve: ${and}^{2} \equiv x^{3} + 7 (against p)$

Where $p = 2^{256} - 2^{32} - 977$ Key feature: $p \equiv 3 (against 4)$ This is not a coincidence, but a deliberate choice that allows the iterative Tonelli–Shanks algorithm to be replaced by direct computation: $r = n^{\frac{p + 1}{4}} (against p)$

This simplification is one of the factors that influenced the choice secp256k1 to use the NIST curves.

2.2 Legendre symbol and residue verification

Before extracting the root, you need to make sure that $n$ — quadratic residue. Euler criterion: $n^{\frac{p - 1}{2}} \equiv 1 (against p)$

Otherwise, the root doesn’t exist. We always check this condition in our scripts.

3. The Role of the Algorithm in Bitcoin: Key Compression

The compressed public key contains only $x$ (32 bytes) and prefix 0x02 (even $and$ ) or 0x03 (odd). To restore the full point:

Calculate $n = x^{3} + 7 against p$ .
Find $and = \sqrt{n} against p$ (using the formula for $p \equiv 3 against 4$ ).
Select the root with the desired parity corresponding to the prefix.

This procedure saves 32 bytes per public key in the UTXO set, which is critical for scalability.

4. Hands-on demonstration in Google Colab

Below are ready-to-run scripts for running in the Colab environment. They cover all key aspects: subtraction checking, root calculation, key recovery, and performance testing.

🧪 How to use: Copy the code into a Colab cell (Python 3) and run it. All examples use the core library pow with three arguments (modular exponentiation), which is completely safe and efficient.

4.1 Basic root function for secp256k1

# Базовый модуль для работы с secp256k1
p = 2**256 - 2**32 - 977

def mod_sqrt_secp256k1(n):
    """Возвращает квадратный корень n mod p для p ≡ 3 mod 4.
       Если n не является вычетом, генерирует ValueError."""
    if pow(n, (p - 1)//2, p) != 1:
        raise ValueError(f"{n} не является квадратичным вычетом")
    return pow(n, (p + 1)//4, p)

# Пример: корень для точки G (x-координата генератора)
x_G = 0x79be667ef9dcbbac55a06295ce870b07029bfcdb2dce28d959f2815b16f81798
n = (pow(x_G, 3, p) + 7) % p
y = mod_sqrt_secp256k1(n)
print(f"Восстановленный y: {hex(y)}")
print(f"Проверка: y^2 mod p == n? {pow(y, 2, p) == n}")

4.2. Complete decompression of a compressed key

def decompress_pubkey(x_hex, prefix):
    """Восстанавливает полный открытый ключ (x, y) по сжатому представлению.
       prefix: '02' или '03' (строка)."""
    x = int(x_hex, 16)
    n = (pow(x, 3, p) + 7) % p
    y = mod_sqrt_secp256k1(n)
    # Выбираем чётность
    if (prefix == '02' and y % 2 == 0) or (prefix == '03' and y % 2 == 1):
        return x, y
    else:
        return x, p - y

# Пример с генератором (префикс 04 — несжатый, но мы возьмём 02)
x_comp = '79be667ef9dcbbac55a06295ce870b07029bfcdb2dce28d959f2815b16f81798'
x_full, y_full = decompress_pubkey(x_comp, '02')
print(f"x = {hex(x_full)}")
print(f"y = {hex(y_full)} (чётный)")

4.3 Performance Comparison: General Tonelli–Shanks vs. Direct Formula

import time

# Реализация классического Тонелли-Шенкса (для p ≠ 3 mod 4)
def tonelli_shanks(n, p):
    if pow(n, (p-1)//2, p) != 1:
        return None
    if p % 4 == 3:
        return pow(n, (p+1)//4, p)
    # Общий случай (для демонстрации)
    Q = p - 1
    S = 0
    while Q % 2 == 0:
        Q //= 2
        S += 1
    z = 2
    while pow(z, (p-1)//2, p) != p-1:
        z += 1
    M = S
    c = pow(z, Q, p)
    t = pow(n, Q, p)
    R = pow(n, (Q+1)//2, p)
    while t != 1:
        i = 1
        while pow(t, 2**i, p) != 1:
            i += 1
        b = pow(c, 2**(M-i-1), p)
        M = i
        c = pow(b, 2, p)
        t = (t * b * b) % p
        R = (R * b) % p
    return R

# Тестируем на случайном n (квадратичный вычет)
import random
# Генерируем вычет: возьмём квадрат случайного числа
rnd = random.randint(2, p-2)
n_test = pow(rnd, 2, p)

start = time.time()
y1 = tonelli_shanks(n_test, p)
time_ts = time.time() - start

start = time.time()
y2 = pow(n_test, (p+1)//4, p)
time_formula = time.time() - start

print(f"Тонелли-Шенкс: {y1}  (время {time_ts:.6f} с)")
print(f"Прямая формула: {y2} (время {time_formula:.6f} с)")
print(f"Результаты совпадают? {y1 == y2}")

4.4. Mass testing on a set of keys

# Список известных x-координат (первые несколько точек из стандарта)
test_x = [
    '79be667ef9dcbbac55a06295ce870b07029bfcdb2dce28d959f2815b16f81798',
    'c6047f9441ed7d6d3045406e95c07cd85c778e4b8cef3ca7abac09b95c709ee5',
    'f9308a019258c31049344f85f89d5229b531c845836f99b08601f113bce036f9'
]
for x_hex in test_x:
    x = int(x_hex, 16)
    n = (pow(x, 3, p) + 7) % p
    try:
        y = mod_sqrt_secp256k1(n)
        print(f"x = {x_hex[:10]}... → y = {hex(y)[:12]}... (чётность {y % 2})")
    except ValueError as e:
        print(f"x = {x_hex[:10]}... → {e}")

5. Historical context and cryptanalytic conclusion

Early versions of Bitcoin Core used only uncompressed keys (65 bytes). The transition to compressed keys (33 bytes) was made possible by efficient root extraction. Satoshi Nakamoto chose secp256k1, likely recognizing that the condition $p \equiv 3 (against 4)$ radically simplifies implementation and improves wallet performance.

From a cryptanalytic point of view, the Tonelli–Shanks algorithm in general has a complexity of $THE (\log^{4} p)$ , but for secp256k1 it comes down to $THE (\log^{3} p)$ (modular exponentiation). This provides orders of magnitude improvements in bulk transaction processing.

6. Conclusion

Despite its theoretical universality, the Tonelli-Shanks algorithm is used in the Bitcoin ecosystem in a “truncated” version due to a thoughtful choice of parameters. The presented Colab scripts allow one to visually verify the correctness of the formulas and conduct their own experiments with performance and key recovery. Understanding this mechanism is important for cryptocurrency protocol developers and researchers in applied cryptography.

📎 Application. Complete code for Google Colab (single block)

# ====================================================================
# tonelli_shanks_demo.ipynb  —  Полная демонстрация для Google Colab
# ====================================================================

p = 2**256 - 2**32 - 977

# 1. Проверка вычета и корень для p % 4 == 3
def mod_sqrt_secp256k1(n):
    if pow(n, (p - 1)//2, p) != 1:
        raise ValueError("Не квадратичный вычет")
    return pow(n, (p + 1)//4, p)

# 2. Декомпрессия
def decompress(x_hex, prefix):
    x = int(x_hex, 16)
    n = (pow(x, 3, p) + 7) % p
    y = mod_sqrt_secp256k1(n)
    if (prefix == '02' and y % 2 == 0) or (prefix == '03' and y % 2 == 1):
        return x, y
    return x, p - y

# 3. Классический Тонелли-Шенкс (для сравнения)
def tonelli_shanks(n, p):
    if pow(n, (p-1)//2, p) != 1:
        return None
    if p % 4 == 3:
        return pow(n, (p+1)//4, p)
    Q = p - 1
    S = 0
    while Q % 2 == 0:
        Q //= 2
        S += 1
    z = 2
    while pow(z, (p-1)//2, p) != p - 1:
        z += 1
    M = S
    c = pow(z, Q, p)
    t = pow(n, Q, p)
    R = pow(n, (Q+1)//2, p)
    while t != 1:
        i = 1
        while pow(t, 2**i, p) != 1:
            i += 1
        b = pow(c, 2**(M - i - 1), p)
        M = i
        c = pow(b, 2, p)
        t = (t * b * b) % p
        R = (R * b) % p
    return R

# ==================== ТЕСТЫ ====================
print("=== Базовый тест (точка G) ===")
x_G = 0x79be667ef9dcbbac55a06295ce870b07029bfcdb2dce28d959f2815b16f81798
n_G = (pow(x_G, 3, p) + 7) % p
y_G = mod_sqrt_secp256k1(n_G)
print(f"y = {hex(y_G)}")

print("\n=== Декомпрессия (префикс 02) ===")
x, y = decompress('79be667ef9dcbbac55a06295ce870b07029bfcdb2dce28d959f2815b16f81798', '02')
print(f"x = {hex(x)}\ny = {hex(y)}")

print("\n=== Сравнение времени (1000 итераций) ===")
import time, random
n_test = pow(random.randint(2, p-2), 2, p)
t0 = time.perf_counter()
for _ in range(1000):
    _ = tonelli_shanks(n_test, p)
t1 = time.perf_counter()
for _ in range(1000):
    _ = pow(n_test, (p+1)//4, p)
t2 = time.perf_counter()
print(f"Тонелли-Шенкс: {t1 - t0:.4f} сек")
print(f"Прямая формула: {t2 - t1:.4f} сек")
print(f"Ускорение: {(t1 - t0) / (t2 - t1):.1f}x")

Deep Cryptanalysis: The Tonelli-Shanks Algorithm in the Bitcoin Ecosystem

A fundamental mathematical method for extracting the square root modulo a prime number.

The Tonelli-Shanks algorithm is a fundamental mathematical method for extracting the square root of a prime number. In elliptic curve cryptography (ECC), which underpins Bitcoin, this algorithm plays a critical role in public-key transactions.

Mathematical base and cryptographic formulas

The main task of the algorithm is to find a solution to a comparison of the form: $r^{2} \equiv n (against p)$

Where $p$ — an odd prime number, $n$ — quadratic residue modulo $p$ , A $r$ — the desired root.

secp256k1 curve

Bitcoin uses an elliptic curve secp256k1, which is given by the Weierstrass equation: ${and}^{2} \equiv x^{3} + 7 (against p)$

where is the parameter $p$ equal $2^{256} - 2^{32} - 977$ It is noteworthy that for this curve $p \equiv 3 (against 4)$ .

Optimization for Bitcoin (p ≡ 3 mod 4)

In general, the Tonelli-Shanks algorithm requires computing the Legendre symbols and cyclic squaring. However, due to the specific choice of prime number $p$ for the curve secp256k1, the condition is satisfied $p \equiv 3 (against 4)$ This is a cryptanalytic fact of colossal importance: it allows us to reduce the Tonelli-Shanks algorithm to a single exponentiation operation!

Formula for direct root calculation: $r = n^{\frac{p + 1}{4}} (against p)$

Interacting with Bitcoin Cryptography: Key Compression

The root extraction algorithm is used in Bitcoin to decompress (recover) the public key. The compressed public key contains only the coordinate $x$ (32 bytes) and 1 prefix byte (0x02 or 0x03) indicating the parity of the coordinate $and$ This saves 32 bytes of data in each transaction.

The recovery process $and$ :

We calculate $n = x^{3} + 7 (against p)$
Finding the square root $and = \sqrt{n} (against p)$ (using the Tonelli-Shanks algorithm or a simplified formula).
We choose from two roots ( $and$ And $p - and$ ) one whose parity matches the compressed key prefix (0x02 = even, 0x03 = odd).

Implementation in various languages (Examples)

Python

def mod_sqrt_bitcoin(n, p):
    # Для secp256k1 p % 4 == 3
    if pow(n, (p - 1) // 2, p) != 1:
        raise ValueError("Не является квадратичным вычетом")
    return pow(n, (p + 1) // 4, p)

p = 2**256 - 2**32 - 977
x = 0x79be667ef9dcbbac55a06295ce870b07029bfcdb2dce28d959f2815b16f81798 # x координата точки G
n = (pow(x, 3, p) + 7) % p
y = mod_sqrt_bitcoin(n, p)
print(hex(y))

SageMath

p = 2^256 - 2^32 - 977
F = GF(p)
E = EllipticCurve(F, [0, 7])
x = F(0x79be667ef9dcbbac55a06295ce870b07029bfcdb2dce28d959f2815b16f81798)
n = x^3 + 7
# SageMath автоматически использует оптимальный алгоритм под капотом (Тонелли-Шенкс или прямое вычисление)
y = n.sqrt()
print(hex(y))

Magma

p := 2^256 - 2^32 - 977;
F := FiniteField(p);
x := F!16#79be667ef9dcbbac55a06295ce870b07029bfcdb2dce28d959f2815b16f81798;
n := x^3 + 7;
is_sq, y := IsSquare(n);
if is_sq then
    print y;
end if;

BETTING/GP

p = 2^256 - 2^32 - 977;
x = 0x79be667ef9dcbbac55a06295ce870b07029bfcdb2dce28d959f2815b16f81798;
n = Mod(x^3 + 7, p);
y = sqrt(n);
print(y);

Historical examples and applications

Bitcoin address evolution: In early versions of Bitcoin Core, Satoshi Nakamoto used uncompressed keys (prefix 0x04, 65 bytes long). The introduction of compressed keys (prefixes 0x02/0x03, 33 bytes long) was made possible by efficient square root algorithms. This reduced the set’s UTXO size and network fees.

Cryptanalytic Insight: The Tonelli-Shanks algorithm in its classical form takes $THE (\log^{4} p)$ , however, due to the choice of a prime number $p \equiv 3 (against 4)$ the difficulty drops to $THE (\log^{3} p)$ (the complexity of modular exponentiation). This fact is one of the reasons why the secp256k1 curve was chosen over the random curves from the NIST standards.

Final conclusion

The Tonelli-Shanks algorithm is an integral part of the public key infrastructure in elliptic curve cryptography. The genius of Bitcoin’s choice of parameters is that the curve secp256k1is based on a simple field where the condition $p \equiv 3 (m the d 4)$ p≡3(mod4). This mathematical property eliminates the need for a full Tonelli-Shanks iterative loop, reducing square root extraction to a single exponentiation operation. As a result, the library libsecp256k1achieves superior performance in key decompression and ECDSA signature verification, which is critical for the scalability of the entire Bitcoin blockchain ecosystem.

Bibliography

Antonopoulos, A. M. (2014). Mastering Bitcoin: Unlocking Digital Cryptocurrencies . O’Reilly Media. Chapter 4: Keys, Addresses, and Wallets describes elliptic curve parameters secp256k1and key compression mechanisms. [ dokumen ]
Cohen, H., Frey, G., et al. (2005). Handbook of Elliptic and Hyperelliptic Curve Cryptography . Chapman and Hall/CRC. Section 11.23 contains a formal mathematical description of the Tonelli-Shanks algorithm. [ ru.wikipedia ]
Shanks, D. (1973). “Five number-theoretic algorithms”. Proceedings of the Second Manitoba Conference on Numerical Mathematics . Original work improving on the classical Tonelli method. [ gyarmatikati.web.elte ]
Tonelli, A. (1891). “Bemerkung über die Auflösung quadratischer Congruenzen”. Nachrichten der Akademie der Wissenschaften in Göttingen . Primary publication of the concept of calculating square roots. [ arxiv ]
Vasilenko, O. N. (2006). Number-Theoretical Algorithms in Cryptography . American Mathematical Society. Contains proofs of correctness and complexity analysis of number-theoretic algorithms, including the Tonelli-Shanks method. [ scribd ]