Int デモ — 多倍長整数の威力
Int は符号付き任意精度の整数型である。
メモリが許す限り何桁でも正確に計算でき、
素数判定・冪剰余・拡張GCD などの数論アルゴリズムも組み込まれている。
このページでは 5 つのデモを通じて、多倍長整数ならではの威力を紹介する。 以下の出力はすべて calx で実際に計算したものである。 ソースコードはページ末尾に掲載しており、 calx をビルドすれば手元で同じ結果を確認できる。
Demo 1: フィボナッチ数 — 巨大整数の世界
フィボナッチ数 $F(n)$ は $F(0)=0,\; F(1)=1,\; F(n)=F(n-1)+F(n-2)$ で定義される数列で、 $n$ が大きくなると桁数が爆発的に増大する。 $F(10000)$ は 2092 桁の整数だが、calx なら わずか数ミリ秒で計算できる。
さらに $\gcd(F(m), F(n)) = F(\gcd(m, n))$ という美しい性質も検証する。
F(10) = 55
F(100) = 354224848179261915075
F(1000) = 43466557686937456435688527675040625802564660517371...76137795166849228875
(209 桁)
F(10000) = 33644764876431783266621612005107543310302148460680...07331005994736687500
(2092 桁, 1240 us)
性質: gcd(F(m), F(n)) = F(gcd(m, n))
F(12) = 144, F(18) = 2584
gcd(F(12), F(18)) = 8
F(gcd(12,18)) = F(6) = 8
一致: YES
F(10000) は 2092 桁の巨大整数だが、わずか数ミリ秒で計算できる。
Demo 2: RSA 暗号のミニデモ
RSA 暗号は「大きな合成数の素因数分解が困難」という性質に基づく公開鍵暗号方式である。 ここではメルセンヌ素数 $M_{89}$ と $M_{107}$ を使い、 暗号化と復号が完全に一致することを示す。
isProbablePrime, powMod, inverseMod の
3 つの関数だけで暗号システムを実現できる。
p = M_89 = 618970019642690137449562111 (27 桁)
q = M_107 = 162259276829213363391578010288127 (33 桁)
p is prime: YES
q is prime: YES
n = p * q
= 100433627766186892221372630609062766858404681029709092356097
(60 桁)
公開鍵: (n, e=65537)
秘密鍵: d = 1549942339788538120339598676074529255065...
(59 桁)
平文: m = 123456789
暗号文: c = 29218147349019509605720103336682850319524446576038257010336
復号: m'= 123456789
一致: YES
平文: m = 314159265358979323846264338327950288
暗号文: c = 25667820348330719542646315697318086285143970060900766556547
復号: m'= 314159265358979323846264338327950288
一致: YES
Demo 3 で検証したメルセンヌ素数を鍵に使い、暗号化→復号が完全に一致。
Demo 3: メルセンヌ素数の検証
メルセンヌ素数 $M_p = 2^p - 1$ は、$p$ 自体が素数のときにのみ素数になりうる （必要条件であって十分条件ではない）。 $p = 11, 23, 29, \ldots$ のように $p$ が素数でも $M_p$ が合成数になる場合がある。
メルセンヌ素数 M_p = 2^p - 1:
p 素数? M_p の桁数 M_p
----------------------------------------------------------------------
2 YES 1 3
3 YES 1 7
5 YES 2 31
7 YES 3 127
13 YES 4 8191
17 YES 6 131071
19 YES 6 524287
31 YES 10 2147483647
61 YES 19 2305843009213693951
89 YES 27 618970019642690137449562111
107 YES 33 162259276829213363391578010288127
127 YES 39 170141183460469231731687303715884105727
2^p - 1 が素数にならない p の例:
M_11 = 2047 素数: NO
M_23 = 8388607 素数: NO
M_29 = 536870911 素数: NO
M_37 = 137438953471 素数: NO
M_41 = 2199023255551 素数: NO
M_43 = 8796093022207 素数: NO
M_127 は 39 桁の素数 — 1876 年にリュカが手計算で検証。
コンピュータ登場以前に人間が検証した最大の素数である。
Demo 4: 巨大階乗と二項係数
階乗 $n!$ は $n$ とともに爆発的に増大する。 $1000!$ は 2570 桁の整数であり、末尾のゼロの数は $\lfloor 1000/5 \rfloor + \lfloor 1000/25 \rfloor + \lfloor 1000/125 \rfloor + \lfloor 1000/625 \rfloor = 249$ 個である。
--- 階乗 n! ---
10! = 3628800
20! = 2432902008176640000
50! = 304140932017133780436126081660...0000000000 (65 桁, 0 us)
100! = 933262154439441526816992388562...0000000000 (158 桁, 0 us)
1000! = 402387260077093773543702433923...0000000000 (2570 桁, 66 us)
1000! の末尾のゼロの数: 249 個
(理論値: floor(1000/5)+floor(1000/25)+floor(1000/125)+floor(1000/625) = 249)
--- 二項係数 C(n, k) ---
C( 10, 5) = 252
C( 20, 10) = 184756
C( 50, 25) = 126410606437752
C(100, 50) = 100891344545564193334812497256
パスカルの三角形 (n=0..10):
1
1 1
1 2 1
1 3 3 1
1 4 6 4 1
1 5 10 10 5 1
1 6 15 20 15 6 1
1 7 21 35 35 21 7 1
1 8 28 56 70 56 28 8 1
1 9 36 84 126 126 84 36 9 1
1 10 45 120 210 252 210 120 45 10 1
Demo 5: 拡張ユークリッド互除法と冪剰余
拡張ユークリッド互除法は不定方程式 $ax + by = \gcd(a,b)$ の整数解を求める。 冪剰余 $a^n \bmod m$ は暗号や数論の基本演算である。 フェルマーの小定理 $a^{p-1} \equiv 1 \pmod{p}$ の検証と、 整数平方根も実演する。
拡張ユークリッド互除法: $ax + by = \gcd(a, b)$
--- 拡張ユークリッド互除法: ax + by = gcd(a, b) ---
35 * (1) + 15 * (-2) = 5
検算: 5 = gcd(35, 15) OK
240 * (-9) + 46 * (47) = 2
検算: 2 = gcd(240, 46) OK
1071 * (-3) + 462 * (7) = 21
検算: 21 = gcd(1071, 462) OK
冪剰余: $a^n \bmod m$
--- 冪剰余: a^n mod m ---
2^1000 mod (10^9+7) = 688423210
フェルマーの小定理: a^(p-1) mod p = 1
314159265^(10^9+6) mod (10^9+7) = 1
(= 1: YES)
整数平方根
--- 整数平方根 ---
isqrt(10^100) = 100000000000000000000000000000000000000000000000000
(= 10^50: YES)
isqrt(2^256) = 340282366920938463463374607431768211456
(= 2^128: YES)
12345678^2 = 152415765279684
isSquare: YES, sqrt = 12345678
ソースコードと実行方法
このページの全出力は以下の C++ プログラムから生成された。 calx をビルドすれば、手元で同じ結果を確認できる。
example_int_demo.cpp (クリックで展開)
// Copyright (C) 2026 Kiyotsugu Arai
// SPDX-License-Identifier: LGPL-3.0-or-later
// example_int_demo.cpp
// 多倍長整数デモ: Int の威力を5つのシナリオで実演
#include <math/core/mp/Int.hpp>
#include <math/core/mp/Int/IntGCD.hpp>
#include <math/core/mp/Int/IntSqrt.hpp>
#include <math/core/mp/Int/IntModular.hpp>
#include <math/core/mp/Int/IntPrime.hpp>
#include <math/core/mp/Int/IntCombinatorics.hpp>
#include <iostream>
#include <iomanip>
#include <string>
#include <chrono>
#include <vector>
using namespace calx;
// ============================================================================
// Demo 1: フィボナッチ数 — 巨大整数の世界
// — F(1000) は 209 桁、F(10000) は 2092 桁の整数
// ============================================================================
static void demo_fibonacci() {
std::cout << "============================================================\n";
std::cout << " Demo 1: Fibonacci Numbers — The World of Giant Integers\n";
std::cout << "============================================================\n\n";
// 小さな値
std::cout << " F(10) = ";
{
Int a(0), b(1);
for (int i = 2; i <= 10; ++i) {
Int t = a + b;
a = std::move(b);
b = std::move(t);
}
std::cout << b << std::endl;
}
// F(100)
std::cout << " F(100) = ";
{
Int a(0), b(1);
for (int i = 2; i <= 100; ++i) {
Int t = a + b;
a = std::move(b);
b = std::move(t);
}
std::cout << b << std::endl;
}
// F(1000)
std::cout << "\n F(1000) = ";
{
Int a(0), b(1);
for (int i = 2; i <= 1000; ++i) {
Int t = a + b;
a = std::move(b);
b = std::move(t);
}
std::string s = b.toString();
// 先頭50桁 + ... + 末尾20桁
if (s.size() > 80) {
std::cout << s.substr(0, 50) << "..." << s.substr(s.size() - 20)
<< "\n (" << s.size() << " 桁)\n";
} else {
std::cout << s << "\n";
}
}
// F(10000) — 計時
{
auto start = std::chrono::high_resolution_clock::now();
Int a(0), b(1);
for (int i = 2; i <= 10000; ++i) {
Int t = a + b;
a = std::move(b);
b = std::move(t);
}
auto end = std::chrono::high_resolution_clock::now();
auto us = std::chrono::duration_cast<std::chrono::microseconds>(end - start).count();
std::string s = b.toString();
std::cout << "\n F(10000) = " << s.substr(0, 50) << "..."
<< s.substr(s.size() - 20)
<< "\n (" << s.size() << " 桁, " << us << " us)\n";
}
// フィボナッチ数の性質: gcd(F(m), F(n)) = F(gcd(m, n))
std::cout << "\n 性質: gcd(F(m), F(n)) = F(gcd(m, n))\n";
{
// F(12) と F(18) を計算
auto fib = [](int n) -> Int {
Int a(0), b(1);
for (int i = 2; i <= n; ++i) {
Int t = a + b;
a = std::move(b);
b = std::move(t);
}
return n == 0 ? a : b;
};
Int f12 = fib(12);
Int f18 = fib(18);
Int g = gcd(f12, f18);
Int f6 = fib(6);
std::cout << " F(12) = " << f12 << ", F(18) = " << f18 << "\n";
std::cout << " gcd(F(12), F(18)) = " << g << "\n";
std::cout << " F(gcd(12,18)) = F(6) = " << f6 << "\n";
std::cout << " 一致: " << ((g <=> f6) == 0 ? "YES" : "NO") << "\n";
}
std::cout << std::endl;
}
// ============================================================================
// Demo 2: RSA 暗号のミニデモ
// — 大きな素数・冪剰余・モジュラ逆元で暗号化と復号
// ============================================================================
static void demo_rsa() {
std::cout << "============================================================\n";
std::cout << " Demo 2: RSA Encryption — Mini Demo\n";
std::cout << "============================================================\n\n";
// メルセンヌ素数を使用 (Demo 3 で検証済み)
// M_89 = 2^89 - 1 (27桁の素数)
// M_107 = 2^107 - 1 (33桁の素数)
Int p = pow(Int(2), 89u) - Int(1);
Int q = pow(Int(2), 107u) - Int(1);
std::cout << " p = M_89 = " << p << " (" << p.toString().size() << " 桁)\n";
std::cout << " q = M_107 = " << q << " (" << q.toString().size() << " 桁)\n";
// 素数性の確認
std::cout << " p is prime: " << (isProbablePrime(p) ? "YES" : "NO") << "\n";
std::cout << " q is prime: " << (isProbablePrime(q) ? "YES" : "NO") << "\n\n";
// n = p * q
Int n = p * q;
std::cout << " n = p * q\n";
std::cout << " = " << n << "\n";
std::cout << " (" << n.toString().size() << " 桁)\n\n";
// phi(n) = (p-1)(q-1)
Int phi = (p - Int(1)) * (q - Int(1));
// 公開指数 e = 65537
Int e(65537);
std::cout << " 公開鍵: (n, e=" << e << ")\n";
// 秘密指数 d = e^-1 mod phi(n)
Int d = IntModular::inverseMod(e, phi);
std::cout << " 秘密鍵: d = " << d.toString().substr(0, 40) << "...\n";
std::cout << " (" << d.toString().size() << " 桁)\n\n";
// 暗号化: メッセージ m を暗号化
Int m(123456789);
std::cout << " 平文: m = " << m << "\n";
// c = m^e mod n
Int c = powMod(m, e, n);
std::cout << " 暗号文: c = " << c << "\n";
// 復号: m' = c^d mod n
Int m_dec = powMod(c, d, n);
std::cout << " 復号: m'= " << m_dec << "\n";
std::cout << " 一致: " << ((m <=> m_dec) == 0 ? "YES" : "NO") << "\n";
// もう少し大きなメッセージ
Int m2("314159265358979323846264338327950288");
std::cout << "\n 平文: m = " << m2 << "\n";
Int c2 = powMod(m2, e, n);
std::cout << " 暗号文: c = " << c2 << "\n";
Int m2_dec = powMod(c2, d, n);
std::cout << " 復号: m'= " << m2_dec << "\n";
std::cout << " 一致: " << ((m2 <=> m2_dec) == 0 ? "YES" : "NO") << "\n";
std::cout << std::endl;
}
// ============================================================================
// Demo 3: メルセンヌ素数の検証
// — 2^p - 1 が素数になる特別な p を検証
// ============================================================================
static void demo_mersenne() {
std::cout << "============================================================\n";
std::cout << " Demo 3: Mersenne Primes — 2^p - 1\n";
std::cout << "============================================================\n\n";
// 既知のメルセンヌ素数指数
int exponents[] = {2, 3, 5, 7, 13, 17, 19, 31, 61, 89, 107, 127};
// 素数でないもの (比較用)
int non_mersenne[] = {11, 23, 29, 37, 41, 43};
std::cout << " メルセンヌ素数 M_p = 2^p - 1:\n\n";
std::cout << std::setw(6) << "p" << " "
<< std::setw(8) << "素数?" << " "
<< "M_p の桁数" << " "
<< "M_p" << std::endl;
std::cout << std::string(70, '-') << std::endl;
for (int p : exponents) {
Int mp = pow(Int(2), static_cast<unsigned>(p)) - Int(1);
bool is_prime = isProbablePrime(mp);
std::string s = mp.toString();
std::string display = (s.size() <= 40) ? s
: s.substr(0, 30) + "..." + s.substr(s.size() - 5);
std::cout << std::setw(6) << p << " "
<< std::setw(8) << (is_prime ? "YES" : "no") << " "
<< std::setw(10) << s.size() << " "
<< display << std::endl;
}
std::cout << "\n 2^p - 1 が素数にならない p の例:\n";
for (int p : non_mersenne) {
Int mp = pow(Int(2), static_cast<unsigned>(p)) - Int(1);
bool is_prime = isProbablePrime(mp);
std::cout << " M_" << p << " = " << mp << " 素数: "
<< (is_prime ? "YES" : "NO") << std::endl;
}
std::cout << "\n M_127 は 39 桁の素数 — 1876 年にリュカが手計算で検証。\n";
std::cout << " コンピュータ登場以前に人間が検証した最大の素数である。\n";
std::cout << std::endl;
}
// ============================================================================
// Demo 4: 巨大階乗と二項係数
// — 1000! の桁数、C(100,50) の厳密値
// ============================================================================
static void demo_factorial_binomial() {
std::cout << "============================================================\n";
std::cout << " Demo 4: Factorial & Binomial Coefficients\n";
std::cout << "============================================================\n\n";
// 階乗
std::cout << " --- 階乗 n! ---\n";
for (int n : {10, 20, 50, 100, 1000}) {
auto start = std::chrono::high_resolution_clock::now();
Int fact = IntCombinatorics::factorial(Int(n));
auto end = std::chrono::high_resolution_clock::now();
auto us = std::chrono::duration_cast<std::chrono::microseconds>(end - start).count();
std::string s = fact.toString();
if (s.size() <= 50) {
std::cout << " " << std::setw(4) << n << "! = " << s << "\n";
} else {
std::cout << " " << std::setw(4) << n << "! = " << s.substr(0, 30)
<< "..." << s.substr(s.size() - 10) << " ("
<< s.size() << " 桁, " << us << " us)\n";
}
}
// 1000! の末尾ゼロの数
std::cout << "\n 1000! の末尾のゼロの数: ";
{
Int fact1000 = IntCombinatorics::factorial(Int(1000));
auto [q, count] = removeFactor(fact1000, Int(10));
std::cout << count << " 個\n";
std::cout << " (理論値: floor(1000/5)+floor(1000/25)"
"+floor(1000/125)+floor(1000/625) = "
<< (200 + 40 + 8 + 1) << ")\n";
}
// 二項係数
std::cout << "\n --- 二項係数 C(n, k) ---\n";
{
struct { int n, k; } cases[] = {{10, 5}, {20, 10}, {50, 25}, {100, 50}};
for (auto& [n, k] : cases) {
Int c = IntCombinatorics::binomial(Int(n), Int(k));
std::string s = c.toString();
std::cout << " C(" << std::setw(3) << n << ", " << std::setw(2)
<< k << ") = ";
if (s.size() <= 40) {
std::cout << s;
} else {
std::cout << s.substr(0, 30) << "... (" << s.size() << " 桁)";
}
std::cout << "\n";
}
}
// パスカルの三角形の性質
std::cout << "\n パスカルの三角形 (n=0..10):\n";
for (int n = 0; n <= 10; ++n) {
std::cout << std::string(static_cast<size_t>(30 - n * 3), ' ');
for (int k = 0; k <= n; ++k) {
Int c = IntCombinatorics::binomial(Int(n), Int(k));
std::cout << std::setw(5) << c << " ";
}
std::cout << "\n";
}
std::cout << std::endl;
}
// ============================================================================
// Demo 5: 拡張ユークリッド互除法と冪剰余
// — 不定方程式の解と巨大な冪の剰余
// ============================================================================
static void demo_number_theory() {
std::cout << "============================================================\n";
std::cout << " Demo 5: Extended GCD & Modular Exponentiation\n";
std::cout << "============================================================\n\n";
// 拡張ユークリッド互除法: ax + by = gcd(a, b) の解
std::cout << " --- 拡張ユークリッド互除法: ax + by = gcd(a, b) ---\n\n";
{
struct { int a, b; } cases[] = {{35, 15}, {240, 46}, {1071, 462}};
for (auto& [a, b] : cases) {
Int x, y;
Int g = IntGCD::extendedGcd(Int(a), Int(b), x, y);
std::cout << " " << a << " * (" << x << ") + "
<< b << " * (" << y << ") = " << g << "\n";
// 検算
Int check = Int(a) * x + Int(b) * y;
std::cout << " 検算: " << check << " = gcd(" << a << ", "
<< b << ") "
<< ((check <=> g) == 0 ? "OK" : "NG") << "\n\n";
}
}
// 巨大な冪剰余
std::cout << " --- 冪剰余: a^n mod m ---\n\n";
{
// 2^1000 mod (10^9 + 7)
Int mod(1000000007);
Int result = powMod(Int(2), Int(1000), mod);
std::cout << " 2^1000 mod (10^9+7) = " << result << "\n";
// フェルマーの小定理: a^(p-1) ≡ 1 (mod p)
Int p(1000000007);
Int a(314159265);
Int fermat = powMod(a, p - Int(1), p);
std::cout << "\n フェルマーの小定理: a^(p-1) mod p = 1\n";
std::cout << " " << a << "^(10^9+6) mod (10^9+7) = " << fermat << "\n";
std::cout << " (= 1: " << ((fermat <=> Int(1)) == 0 ? "YES" : "NO")
<< ")\n";
}
// 巨大整数の平方根
std::cout << "\n --- 整数平方根 ---\n\n";
{
// 10^100 の平方根 = 10^50
Int n = pow(Int(10), 100u);
Int s = IntSqrt::sqrt(n);
std::cout << " isqrt(10^100) = " << s << "\n";
std::cout << " (= 10^50: "
<< ((s <=> pow(Int(10), 50u)) == 0 ? "YES" : "NO") << ")\n";
// 2^256 の平方根
Int n2 = pow(Int(2), 256u);
Int s2 = IntSqrt::sqrt(n2);
std::cout << "\n isqrt(2^256) = " << s2 << "\n";
std::cout << " (= 2^128: "
<< ((s2 <=> pow(Int(2), 128u)) == 0 ? "YES" : "NO") << ")\n";
// 完全平方数判定
Int perfect = Int(12345678) * Int(12345678);
Int root;
bool is_sq = IntSqrt::isSquare(perfect, &root);
std::cout << "\n 12345678^2 = " << perfect << "\n";
std::cout << " isSquare: " << (is_sq ? "YES" : "NO")
<< ", sqrt = " << root << "\n";
}
std::cout << std::endl;
}
// ============================================================================
// main
// ============================================================================
int main() {
std::cout << "###########################################################\n";
std::cout << "# calx Int Demo — 多倍長整数の威力 #\n";
std::cout << "###########################################################\n\n";
demo_fibonacci();
demo_rsa();
demo_mersenne();
demo_factorial_binomial();
demo_number_theory();
std::cout << "###########################################################\n";
std::cout << "# 全デモ完了 #\n";
std::cout << "###########################################################\n";
return 0;
}API の詳細は Int API リファレンス を参照のこと。
ビルドと実行
cd calx
mkdir build && cd build
cmake .. -G "Visual Studio 17 2022" -A x64
cmake --build . --config Release --target example-int-demo
examples\Release\example-int-demo.exe計測環境
このページの計算時間は以下の環境で計測した参考値である。
- CPU: AMD Ryzen Threadripper PRO 5995WX (Zen 3)
- OS: Windows 11 Pro
- コンパイラ: MSVC 17.x (Visual Studio 2022), Release x64