2623561561を素因数分解する

www.youtube.com

2623561561 を素因数分解する動画がありました．手計算で頑張っていました．もちろん人間が素因数分解するには大変な計算量だということは分かりましたが，パソコンならばどれぐらいで実行できるのか気になったので試してみました．

最小の素因数を返す関数を作る

既に素晴らしいライブラリが存在するので，それら利用するのが簡単です．しかし中身が分からないと感覚的に理解できないので，自分でプログラムを作成することにしました．以下のような，エラトステネスの篩を利用した簡単な Python スクリプトを作成しました．愚直に計算するよりは速いはずですが，最適化はほとんどしていないので既存の関数よりは遅いと思います．

prime.py

import math

def is_prime(a: int) -> int | None:
    p = [i > 1 for i in range(a + 1)]
    b = math.floor(math.sqrt(a)) + 1
    for i in range(2, b):
        if not p[i]:
            continue
        j = i * 2
        while j <= a:
            p[j] = False
            j += i
        if not p[a]:
            return i
    return None

test.py

import unittest
from prime import is_prime, is_prime_bitarray

prime_numbers = [2, 3, 5, 7, 11, 13, 17, 19, 524287, 6700417, 7222181]
composite_numbers = [
    (4, 2),
    (6, 2),
    (8, 2),
    (15, 3),
    (91, 7),
    (121, 11),
    (1025, 5),
    (101 * 103, 101),
    (991 * 997, 991),
]


class PrimeTest(unittest.TestCase):
    def test_prime_numbers(self):
        for u in prime_numbers:
            with self.subTest(u=u):
                self.assertIsNone(is_prime(u))

    def test_composite_numbers(self):
        for u, v in composite_numbers:
            with self.subTest(u=u):
                self.assertEqual(is_prime(u), v)

ユニットテストを実行したところ，以下のように正しく動作することが確認できました．

$ python -m unittest
..
----------------------------------------------------------------------
Ran 2 tests in 3.462s

OK

bitarray を使って高速化する

Python のリストに True, False を入れているので，これを bitarray に置き換えるだけで高速化できそうだと思いましたので試してみました．

import math
from bitarray import bitarray

def is_prime_bitarray(a: int) -> int | None:
    p = bitarray(a + 1)
    p.setall(1)
    p[0] = 0
    p[1] = 0
    b = math.floor(math.sqrt(a)) + 1
    for i in range(2, b):
        if not p[i]:
            continue
        j = i * 2
        while j <= a:
            p[j] = 0
            j += i
        if not p[a]:
            return i
    return None

benchmark.py

from benchmarker import Benchmarker
from prime import is_prime, is_prime_bitarray

def run():
    with Benchmarker(1) as bench:

        @bench("is_prime")
        def _(bm):
            is_prime(7222181)

        @bench("is_prime_bitarray")
        def _(bm):
            is_prime_bitarray(7222181)


if __name__ == "__main__":
    run()

実行すると，1.4 倍ほど速くなりました．全く頭を使わずに高速化できるのは嬉しいですね．

$ python .\benchmark.py  
## benchmarker:         release 4.0.1 (for python)
## python version:      3.11.0
## python compiler:     MSC v.1933 64 bit (AMD64)
## python platform:     Windows-10-10.0.19045-SP0
## python executable:   C:\Users\....\venv\Scripts\python.exe
## cpu model:           Intel64 Family 6 Model 94 Stepping 3, GenuineIntel
## parameters:          loop=1, cycle=1, extra=0

##                                       real    (total    = user    + sys)
is_prime                               1.6855    1.6875    1.6406    0.0469
is_prime_bitarray                      1.1629    1.1562    1.1562    0.0000

## Ranking                               real
is_prime_bitarray                      1.1629  (100.0) ********************
is_prime                               1.6855  ( 69.0) **************

なお，CPUは Intel Core i7-6700 @ 3.40GHz を使用しました．

2623561561を素因数分解

print(is_prime_bitarray(2623561561))

実行すると最小の素因数が得られました．

34613

先程ベンチマークした環境で実行し， 11 分かかりました．2623561561 / 34613 = 75797 であり，is_prime_bitarray(75797) は None となりました．

まとめ

34613 × 75797 = 2623561561

この素因数分解は手元にあったパソコンで10分程度で処理できました．エラトステネスの篩の計算量は $O(N\log \log (N))$であり，現在の RSA 暗号の鍵の長さは 2048 bit (617桁) *1なので，RSA-2048 ならばかなり安全と言えそうな気がしました．

元の動画では5桁の素数2個の積を題材にしており，難易度調整が適切であることが分かりました．

*1:暗号化の安全性 (RSA暗号)より