バーチャル量子コンピュータで素因数分解

素因数分解は位数に弱い？

今回は、仮想の量子コンピュータを使って「$\operatorname{mod}N$ に関する 整数 $A$ の位数」というものを計算し、それを基に長い桁数の素因数分解をする遊びをしてみようと思います。

この記事は2022-09-30に行われた VRCエンジニア作業飲み集会 の 第0回LightningTalk会 にて話した「1024bit数の素数因数分解」の内容を加筆修正したものです。

https://twitter.com/VRCENGAssoc/status/1581127883283902464

アーカイブ動画(私の発表は36:25～、日本語字幕あり):
https://www.youtube.com/watch?t=2185&cc_load_policy=1&v=Bgh-vmVpnGQ

「実際の量子コンピュータでどのようにして位数を求めるのか」という話の詳細はここでは取り扱いません。
量子コンピュータで使われる手法の参考リンク:

https://qiskit.org/textbook/ja/ch-algorithms/shor.html
https://ja.wikipedia.org/wiki/量子コンピュータ
https://en.wikipedia.org/wiki/Shor's_algorithm

RSA暗号

桁数が大きい合成数の素因数分解が現実的な計算量では困難であることを安全性の前提とした公開鍵暗号の一つ。1977年に発明された。ja.wikipedia.org - RSA暗号
SSL公開鍵(Webのセキュア(HTTPS)通信など)、SSH公開鍵などで現在も使われている所が多いが、RSA暗号からは楕円曲線暗号(ECDSA, ED25519, ...)などのより強力な暗号方式への移行が徐々に進んでいる。例えばRSA 1024bit鍵は2011年以降使用禁止扱いであり、RSA 2048bit鍵は2031年以降使用禁止扱いとなる見込み。 nict.go.jp - 暗号の安全性評価

en.wikipedia.org - RSA_Factoring_Challenge: RSA素因数分解チャレンジ（抜粋）

RSA_Number	10進 桁数	2進 桁数	素因数分解 された日
RSA-100	100	330	1991-04-01
RSA-640	193	640	2005-11-02
RSA-768	232	768	2009-12-12
RSA-240	240	795	2019-12-02
RSA-250	250	829	2020-02-28
RSA-260	260	862	未踏
RSA-896	270	896	未踏
RSA-1024	309	1024	未踏
RSA-1536	463	1536	未踏
RSA-2048	617	2048	未踏

2020-02-28 に解かれた RSA-250 (10進250桁・2進829桁) の素因数分解:

RSA-250 = 214032465024074496126442307283933356300861471514475501779775492088141802344714013664
          334551909580467961099285187247091458768739626192155736304745477052080511905649310668
          7691590019759405693457452230589325976697471681738069364894699871578494975937497937
RSA-250 = 641352894770715802787901901705773890848250147429434472081168596320245323446302386235
          98752668347708737661925585694639798853367
        × 333720275949781565562260106053551142279407603447675546667845209870238417292100370802
          57448673296881877565718986258036932062711

おそらくまだ素因数分解されていない RSA-2048 (10進617桁・2進2048桁) の合成数:

RSA-2048 = 25195908475657893494027183240048398571429282126204032027777137836043662020707595556264018
           52588078440691829064124951508218929855914917618450280848912007284499268739280728777673597
           14183472702618963750149718246911650776133798590957000973304597488084284017974291006424586
           91817195118746121515172654632282216869987549182422433637259085141865462043576798423387184
           77444792073993423658482382428119816381501067481045166037730605620161967625613384414360383
           39044149526344321901146575444541784240209246165157233507787077498171257724679629263863563
           73289912154831438167899885040445364023527381951378636564391212010397122822120720357

数学記号のおさらい

高校数学A 整数の性質 （合同式、ユークリッドの互除法、一次不定方程式、二進法など）
小5算数 約数・公約数・最大公約数・倍数・公倍数・最小公倍数
小3算数 あまりの出る割り算

を覚えていると有り難いです。

• $\operatorname{mod}$ : モジュロ(modulo)・剰余演算、割り算における余りの値を取得する演算記号。
  • $A^R\equiv 1\ (\operatorname{mod}N)$ のような 整数の合同式 の表記が一杯出てきます。
  • $\operatorname{mod}N$ の事を 「法 $N$」 という言い方をする事があります。
• $\gcd(a,b)$ : 最大公約数(greatest common divisor)。 greatest common measure と言う事も。
  • $\gcd(a,b)=1$ である事を 「$a$ と $b$ は互いに素」 と表記したりする。
• $\operatorname{lcm}(a,b)$ : 最小公倍数 (least common multiple)。
  • $\lambda(PQ)=\operatorname{lcm}(P-1,Q-1)$ のような式がちょっと出てきます。

仮想量子コンピュータを使って素因数分解してみよう

今回取り組む問題はこちら：

https://yukicoder.me/problems/no/3056

No.3056 量子コンピュータで素因数分解 Easy
実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / リアクティブ問題

問題文

二つの異なる奇素数 $P$ と $Q$ の積である整数 $N$ が与えられるので、$P$ と $Q$ を出力してください。ただし、あなたは量子コンピュータにアクセスして $N$ と互いに素な $N$ 未満の正の整数 $A$ について法 $N$ に関する $A$ の位数をクエリすることができます。

ここで整数 $N\ge 2$ と $N$ と互いに素な正の整数 $A$ について、法 $N$ に関する $A$ の位数とは $A^R\equiv 1\mod N$ を満たす最小の正の整数 $R$ のことをいいます。

入出力

入力の一行目には

N

が与えられます。 $N$ は $2^{1024}$ 未満の正の整数であり、ちょうど二つの異なる奇数の素因数を持つことが保証されています。 $N$ と互いに素な $N$ 未満の正の整数 $A$ をクエリすると、法 $N$ に関する $A$ の位数が入力されます。 質問クエリのフォーマットは

? A

です。条件を満たさない $A$ をクエリすると不正解となります。 解答クエリのフォーマットは

! P Q

です。$P,Q\gt 1$ と $PQ=N$ を満たすとき正解となります。 クエリ回数に制限はありませんが、クエリの応答時間も含めて制限時間以内に $N$ の二つの異なる素因数を出力してください。

リアクティブ形式の問題なので、(自力で素因数分解を完遂しようとしない限りは)ジャッジサーバの応答プログラムと対話的にやり取りする必要があります。

https://yukicoder.me/wiki/reactive

キーワード: 位数（"A mod N" の乗法次数・剰余位数）

ここで整数 $N\ge 2$ と $N$ と互いに素な正の整数 $A$ について、法 $N$ に関する $\boldsymbol{A}$ の位数 とは $A^R\equiv 1\mod N$ を満たす最小の正の整数 $R$ のことをいいます。

上は $3^x\operatorname{mod}35$ の周期性を示す図（図はショアのアルゴリズム - qiskit.orgより）。 $3^{12}\equiv 1\ (\operatorname{mod})$ であり、位数 $R=12$ の周期を持っている。

この場合、位数が $12$ と偶数なので $3^{12}-1=(3^6-1)(3^6+1)$ と因数分解する事により $3^6-1=728\equiv 28,\ 3^6+1=730\equiv 30\ (\operatorname{mod}35)$
$\gcd(28,35)=7,\ \gcd(30,35)=5$
のようにして素因数を発見できる。

この $A^x\operatorname{mod}N$ の性質を持つ状態の生成と、その位数の検出を量子コンピュータが担う事になる。

十分な量子ビットを持つ量子コンピュータ で Shor のアルゴリズム などを用いることで、この 位数 の値を見つけられるとされています。
https://qiskit.org/textbook/ja/ch-algorithms/shor.html
https://ja.wikipedia.org/wiki/量子コンピュータ

基本に近い解答コード例

• $A$ の値を $\{2,3,...,N-2\}$ の中から適当に選び、 $\gcd(A,N)=1$ であることを確かめる。もし $\gcd(A,N)\ne 1$ であればそれは素因数を見つけたということなので出力して終了する。
  • $A=1$ の時の位数は明らかに $R=1$、 $A=N-1$ の時の位数は明らかに $R=2$ だが、これは素因数を発見するためのヒントにならないので、$A=1$ と $A=N-1$ の質問クエリはなるべく送らないようにした方が良い。
• 量子コンピュータを使って、 $\operatorname{mod}N$ における $A$ の位数 $R$ の値を求める。
• 位数 $R$ が偶数なら、 $A^R-1=(A^{R/2}-1)(A^{R/2}+1)\equiv 0\ (\operatorname{mod}N)$ より、 $(A^{R/2}-1)$ か $(A^{R/2}+1)$ が $N$ の素因数を持つ可能性が高いので、 $\gcd((A^{R/2}-1)\operatorname{mod}N,N)\operatorname{mod}N$ や $\gcd((A^{R/2}+1)\operatorname{mod}N,N)\operatorname{mod}N$ の値を計算して調べる。
• 位数 $R$ が奇数だったり、偶数であっても不幸にも $N$ の素因数を発見できなかったりした場合、 $A$ の値を変えて位数を求め直す。

という処理を繰り返して素因数を探します。経験的には、乱択した $A$ を使うと 2/3 くらいの確率で、その位数を用いて素因数を発見できるようです。

探索順固定

https://yukicoder.me/submissions/803572

import math
n = int(input()) # 合成数 n を取得
def check(v): # 出力チェック関数
    g = math.gcd(v, n)
    if g > 2 and g < n:
        print("!", g, n//g)
        exit()
for a in range(2, n-1): # a = {2,3,4,...,n-2}
    check(a) # 質問前にaをチェック
    print("?", a) # 位数を質問
    r = int(input()) # 位数 r の回答
    if r&1 == 0: # if r is even:
        check(pow(a, r>>1, n)-1) # pow(a, r//2) % n - 1

Python3 (3.10.1 + numpy 1.22.3 + scipy 1.8.0)
平均クエリ数 3.04

探索順固定&ショートコード

https://yukicoder.me/submissions/804438

import math;G=math.gcd;a=g=2;n=int(input())
while g<3:print("?",a);g=max(G(n,pow(a,int(input())>>1,n)-1),G(a:=a+1,n))
print("!",g,n//g)

Python3 (3.10.1 + numpy 1.22.3 + scipy 1.8.0)
コード長 135 Byte
平均クエリ数 3.04

乱択

https://yukicoder.me/submissions/803573

import math
import random
n = int(input()) # 合成数 n を取得
def check(v): # 出力チェック関数
    g = math.gcd(v, n)
    if g > 2 and g < n:
        print("!", g, n//g)
        exit()
while True: # 無限ループ
    a = random.randrange(2, n-1) # 2 <= a <= n-2
    check(a) # 質問前にaをチェック
    print("?", a) # 位数を質問
    r = int(input()) # 位数 r の回答
    if r&1 == 0: # if r is even:
        check(pow(a, r>>1, n)-1) # pow(a, r//2) % n - 1

Python3 (3.10.1 + numpy 1.22.3 + scipy 1.8.0)
平均クエリ数 2.38

2022-10-05のジャッジにおいては、平均クエリ数 2.38 (平均質問クエリ数 1.38 + 解答クエリ数 1.00) でした。 乱数を使っているので、平均クエリ数は実行毎に多少前後する事があります。

質問クエリ数を1回に制限してみよう

実は多くの場合、質問クエリ数をたった1回に制限しても、素因数を有効時間内に見つけることも可能になっています。

つまり、 平均クエリ数 2.00 以下 = 平均質問クエリ数 1.00 以下 + 解答クエリ数 1.00 とする事も多くの場合に満たすことができます。

位数のパターン

下調べとして、10進数で250桁の合成数 $N=$ 2140324650240744961264423072839333563008614715144755017797754920881418023447140136643345519095804679610992851872470914587687396261921557363047454770520805119056493106687691590019759405693457452230589325976697471681738069364894699871578494975937497937 (RSA-250) についての位数 ($A^R\equiv 1\ (\operatorname{mod}N)$ を満たす最小の正の整数 $R$ の値) を幾つか求めてみましょう。

• $\lambda(N)=$ 1070162325120372480632211536419666781504307357572377508898877460440709011723570068321672759547902339805496425936235457293843649377302242656655309877160014593276590170456301939508942252156419201928257742850496807740198212387139736113503271149603290930
  • $\lambda(N)=\lambda(PQ)=\operatorname{lcm}(P-1,Q-1)=$ 2 × 5 × 13 × 6213239 × 440117350342384303 × 101910617047160921359 × 4597395223158209096147 × 8015381692860102796237 × 11015842872223957032465527015746975907581857223611379316467045416408679146689 × 72769022935390028131583224155323574786067394416649454368282707661426220155269516297
• $A=2$ の時の位数: 535081162560186240316105768209833390752153678786188754449438730220354505861785034160836379773951169902748212968117728646921824688651121328327654938580007296638295085228150969754471126078209600964128871425248403870099106193569868056751635574801645465
• $A=3$ の時の位数: 535081162560186240316105768209833390752153678786188754449438730220354505861785034160836379773951169902748212968117728646921824688651121328327654938580007296638295085228150969754471126078209600964128871425248403870099106193569868056751635574801645465
• $A=4$ の時の位数: 535081162560186240316105768209833390752153678786188754449438730220354505861785034160836379773951169902748212968117728646921824688651121328327654938580007296638295085228150969754471126078209600964128871425248403870099106193569868056751635574801645465
• $A=5$ の時の位数: 82320178855413267740939348955358983192639027505567500684529035418516077824890005255513289195992487677345878918171958253372588413638634050511946913627693430252045397727407841500687865550493784763712134065422831364630631722087672008731020857661791610
• $A=6$ の時の位数: 535081162560186240316105768209833390752153678786188754449438730220354505861785034160836379773951169902748212968117728646921824688651121328327654938580007296638295085228150969754471126078209600964128871425248403870099106193569868056751635574801645465
• $A=7$ の時の位数: 1070162325120372480632211536419666781504307357572377508898877460440709011723570068321672759547902339805496425936235457293843649377302242656655309877160014593276590170456301939508942252156419201928257742850496807740198212387139736113503271149603290930
• $A=8$ の時の位数: 535081162560186240316105768209833390752153678786188754449438730220354505861785034160836379773951169902748212968117728646921824688651121328327654938580007296638295085228150969754471126078209600964128871425248403870099106193569868056751635574801645465
• $A=9$ の時の位数: 535081162560186240316105768209833390752153678786188754449438730220354505861785034160836379773951169902748212968117728646921824688651121328327654938580007296638295085228150969754471126078209600964128871425248403870099106193569868056751635574801645465
• $A=10$ の時の位数: 1070162325120372480632211536419666781504307357572377508898877460440709011723570068321672759547902339805496425936235457293843649377302242656655309877160014593276590170456301939508942252156419201928257742850496807740198212387139736113503271149603290930

結構、似たような値が多く出現している事が分かります。今回はこれを利用します。

フローチャート（参考）

今回、質問回数を最小限に抑えるという処理は基本的に以下のような流れで行います。
（場合場合によって処理の省略やアレンジは随時行うので、必ずしも以下のフローチャート通りでは無いです）

処理例1: RSA-180

$A=2$ の位数 $R$ を求めると $R$ は偶数であるものの、 それらでは素因数を見つけることが出来ない、というパターンでの処理例です。

• ジャッジから受け取る、10進180桁の合成数 $N$ : RSA-180 の値です。

191147927718986609689229466631454649812986246276667354864188503638807260703436799058776201365135161278134258296128109200046702912984568752800330221777752773957404540495707851421041

• ジャッジに送信する質問クエリです。 $A=2$ の時の位数を尋ねています。

? 2

• ジャッジから受け取る、 $A=2$ の時の位数です。今回は位数 $R$ として偶数が与えられました。位数 $R$ が偶数の時、素因数を探す際の指数は $R/2$ として調べていきます。

11946745482436663105576841664465915613311640392291709679011781477425453793964799941173512530463461888110721459250705796179704527890823431825307601556612371928350385798227973068052

• $B=\{0,1,2,\dots\}$ として、 $\gcd((A+B)^{R/2}-1\operatorname{mod}N,N)\operatorname{mod}N$ の値をそれぞれ求め、素因数を探します。
• $\gcd(2^{R/2}-1\operatorname{mod}N,N)\operatorname{mod}N=1,$
• $\gcd(3^{R/2}-1\operatorname{mod}N,N)\operatorname{mod}N=1,$
• $\gcd(4^{R/2}-1\operatorname{mod}N,N)\operatorname{mod}N=0,$
• $\gcd(5^{R/2}-1\operatorname{mod}N,N)\operatorname{mod}N=1,$
• $\gcd(6^{R/2}-1\operatorname{mod}N,N)\operatorname{mod}N=1,$
• $\gcd(7^{R/2}-1\operatorname{mod}N,N)\operatorname{mod}N=1,$
• $\gcd(8^{R/2}-1\operatorname{mod}N,N)\operatorname{mod}N=1,$
• $\gcd(9^{R/2}-1\operatorname{mod}N,N)\operatorname{mod}N=1,$
• $\gcd(10^{R/2}-1\operatorname{mod}N,N)\operatorname{mod}N=1,$
• $\gcd(11^{R/2}-1\operatorname{mod}N,N)\operatorname{mod}N=$ 476939688738611836995535477357070857939902076027788232031989775824606225595773435668861833 (素因数発見)
• 476939688738611836995535477357070857939902076027788232031989775824606225595773435668861833 × 400780082329750877952581339104100572526829317815807176564882178998497572771950624613470377 (素因数分解成功)
• ジャッジに送信する解答クエリです。送信後プログラムを終了します。

! 476939688738611836995535477357070857939902076027788232031989775824606225595773435668861833 400780082329750877952581339104100572526829317815807176564882178998497572771950624613470377

処理例2: RSA-250

$A=2$ の位数 $R$ を求めると $R$ が奇数であるパターンでの処理例です。

• ジャッジから受け取る、10進250桁の合成数 $N$ : RSA-250 の値です。

2140324650240744961264423072839333563008614715144755017797754920881418023447140136643345519095804679610992851872470914587687396261921557363047454770520805119056493106687691590019759405693457452230589325976697471681738069364894699871578494975937497937

• ジャッジに送信する質問クエリです。 $A=2$ の時の位数を尋ねています。

? 2

• ジャッジから受け取る、 $A=2$ の時の位数です。今回は位数 $R$ として奇数が与えられました。位数 $R$ が奇数の時、素因数を探す際の指数は $R$ として調べていきます。

535081162560186240316105768209833390752153678786188754449438730220354505861785034160836379773951169902748212968117728646921824688651121328327654938580007296638295085228150969754471126078209600964128871425248403870099106193569868056751635574801645465

• $B=\{0,1,2,\dots\}$ として、 $\gcd((A+B)^{R}-1\operatorname{mod}N,N)\operatorname{mod}N$ の値をそれぞれ求め、素因数を探します。
• $\gcd(2^{R}-1\operatorname{mod}N,N)\operatorname{mod}N=0,$
• $\gcd(3^{R}-1\operatorname{mod}N,N)\operatorname{mod}N=0,$
• $\gcd(4^{R}-1\operatorname{mod}N,N)\operatorname{mod}N=0,$
• $\gcd(5^{R}-1\operatorname{mod}N,N)\operatorname{mod}N=$ 33372027594978156556226010605355114227940760344767554666784520987023841729210037080257448673296881877565718986258036932062711 (素因数発見)
• 33372027594978156556226010605355114227940760344767554666784520987023841729210037080257448673296881877565718986258036932062711 × 64135289477071580278790190170577389084825014742943447208116859632024532344630238623598752668347708737661925585694639798853367 (素因数分解成功)
• ジャッジに送信する解答クエリです。送信後プログラムを終了します。

! 33372027594978156556226010605355114227940760344767554666784520987023841729210037080257448673296881877565718986258036932062711 64135289477071580278790190170577389084825014742943447208116859632024532344630238623598752668347708737661925585694639798853367

質問クエリ数1回のコード解答例

まずは普通(?)に

https://yukicoder.me/submissions/803576

import math # 数学ライブラリ(最大公約数(greatest common divisor, gcd))のため
n = int(input()) # 合成数 n を取得
def check(v): # 出力チェック関数
    g = math.gcd(v, n)
    if g > 2 and g < n:
        print("!", g, n//g)
        exit()
check(3) # 3の素因数をチェック
for a in range(2, n-1): # a = {2,3,4,...,n-2}
    check(a) # 質問前にaをチェック
    print("?", a) # 位数を質問
    r = int(input()) # 位数 r の回答
    if r&1 == 0: # if r is even:
        r >>= 1 # r //= 2
    for b in range(99): # b = {0,1,2,...,98}
        check(pow(a+b, r, n)-1) # pow(a + b, r) % n - 1

• Python3 (3.10.1 + numpy 1.22.3 + scipy 1.8.0)
• 実行時間 103ms、平均クエリ数 1.96
• $A=\{2,3,4,\dots,N-2\},\ B=\{0,1,2,\dots,98\}$ として、 $A$ に対して求めた位数 $R$ を用いて $\begin{cases}\gcd((A+B)^R-1\operatorname{mod}N,N)\operatorname{mod}N&R\text{ is odd}\\\gcd((A+B)^{R/2}-1\operatorname{mod}N,N)\operatorname{mod}N&R\text{ is even}\end{cases}$ で素因数を発見できるか順次調べています。
• $99$ 要素の $B$ の値全てで素因数の発見に失敗した場合は、 $A$ の値を変えて次の質問クエリを送信します。
  • $N=$ 105312291668557186697918027513529248857806893649219117400977309697 のケースでは $A=2$ において素因数の発見が困難です。 → #追加テストケース#A=2,4,8
  • $N=$ 11677649222449681 のケースでは、 ? 2 ? 3 ? 4 ? 5 ? 6 ? 7 ? 8 ? 9 ? 10 の質問クエリの全てで $B\lt 99$ の範囲では素因数を発見できません。このケースの場合、その後 ? 11 の質問クエリを行えば素因数分解可能です。 → #追加テストケース#A=2,3,4,5,6,7,8,9,10
• 26テストケースのうち、1ケース(challenge02.txt)は ? 2 ? 3 の質問2回で素因数分解成功（クエリ数3回=質問2回+解答1回）、 23ケースは ? 2 の質問1回のみで素因数分解成功（クエリ数2回=質問1回+解答1回）、残り2ケース(challenge01.txt, Sample.txt)は $3$ で試し割りした時点・質問0回で素因数分解成功（クエリ数1回=質問0回+解答1回）

ワンライナー

https://yukicoder.me/submissions/803579

import math;n=int(input());P=lambda p:0 if(g:=math.gcd(p,n)%n)<3 else[print("!",g,n//g),exit()];[[P(a),print("?",a),r:=int(input()),[P(pow(a+b,r>>1-r%2,n)-1)for b in range(99)]]for a in range(3,n)]

• Python3 (3.10.1 + numpy 1.22.3 + scipy 1.8.0)
• 実行時間 89ms、コード長197Byte、平均クエリ数 1.92 (最小クエリ数)
• $A=\{3,4,5,\dots,N-1\},\ B=\{0,1,2,\dots,98\}$ として、 $A$ に対して求めた位数 $R$ を用いて $\begin{cases}\gcd((A+B)^R-1\operatorname{mod}N,N)\operatorname{mod}N&R\text{ is odd}\\\gcd((A+B)^{R/2}-1\operatorname{mod}N,N)\operatorname{mod}N&R\text{ is even}\end{cases}$ で素因数を発見できるか順次調べています。
• $99$ 要素の $B$ の値全てで素因数の発見に失敗した場合は、 $A$ の値を変えて次の質問クエリを送信します。
  • $N=$ 6553328781185369079676752688592560556438576503813171946179026893178609140113047452911600703454926723 のケースでは $A=3$ において素因数の発見が困難です。 → #追加テストケース#3,9
  • $N=$ 11677649222449681 のケースでは、 (? 2) ? 3 ? 4 ? 5 ? 6 ? 7 ? 8 ? 9 ? 10 の質問クエリの全てで $B\lt 99$ の範囲では素因数を発見できません。このケースの場合、その後 ? 11 の質問クエリを行えば素因数分解可能です。 → #追加テストケース#2,3,4,5,6,7,8,9,10
• 26テストケースのうち、 24ケースは ? 3 の質問1回のみで素因数分解成功（クエリ数2回=質問1回+解答1回）、残り2ケース(challenge01.txt, Sample.txt)は $3$ で試し割りした時点・質問0回で素因数分解成功（クエリ数1回=質問0回+解答1回）

現実の量子コンピュータはというと

Shorのアルゴリズムでは 2012年に $N=21$ が素因数分解されており arXiv:1111.4147、これが量子コンピュータと Shor のアルゴリズムで素因数分解された最大の整数とされている。 2019年に IBM Q System One で $N=35$ の素因数分解が試みられたが、これはエラーの蓄積により失敗した arXiv:1903.00768。

https://en.wikipedia.org/wiki/Shor's_algorithm

カーマイケルの定理から導く位数

整数 $A,N$ が互いに素である時、 $A^R\equiv 1\ (\operatorname{mod}N)$ が成り立つ、最小の 正の自然数 $R\ge 1$ （$\operatorname{mod}N$ における 整数 $A$ の位数 $R$） はどんな値か、を論じるための定理は幾つかあります。

https://ja.wikipedia.org/wiki/フェルマーの小定理

• フェルマーの小定理
  • $p$ を素数とし、 $a$ を整数とすると、 $a^p\equiv a\ (\operatorname{mod}p)$ が成立する。
  • $p$ を素数とし、 $a$ を $p$ と互いに素な整数とすると $a^{p-1}\equiv 1\ (\operatorname{mod}p)$ が成立する。
• オイラーの定理
  • $a$ を $n\ge 2$ と互いに素な整数とすると、 $a^{\varphi(n)}\equiv 1\ (\operatorname{mod}n)$ が成立する。
    • $\varphi(n)$ は $n$ 未満の $n$ と互いに素な自然数の個数を表す。(オイラー関数)
    • $m,n$ を互いに素な自然数とすると、 $\varphi(mn)=\varphi(m)\varphi(n)$
    • $n$ が素数の時 $\varphi(n)=n-1$ となり、フェルマーの小定理に一致する。
• カーマイケルの定理
  • $a$ を $n\ge 2$ と互いに素な整数とすると、 $a^{\lambda(n)}\equiv 1\ (\operatorname{mod}n)$ が成立する。
    • $n=2^e$ なら、 $\lambda(2^e)=\begin{cases}1&(e=1)\\2&(e=2)\\2^{e-2}&(e\ge 3)\end{cases}$
    • $n$ が奇素数 $p$ を用いて $n=p^e$ と書けるなら、 $\lambda(p^e)=p^{e-1}(p-1)$
    • $n$ が $p_1^{e_1}\dots p_k^{e_k}$ と素因数分解できるなら、 $\lambda(p_1^{e_1}\dots p_k^{e_k})=\operatorname{lcm}\{\lambda(p_1^{e_1}),\dots,\lambda(p_k^{e_k})\}$
    • $\lambda(n)$ はカーマイケル関数。

カーマイケルの定理は、オイラーの定理より厳密に $A^R\equiv 1\ (\operatorname{mod}N)$ が成り立つ値を論じています。

今回の問題の場合、異なる2つの奇数の素数 $P,Q$ の積 $N=PQ$ について、 $\operatorname{mod}N$ に関する、 $N$ と互いに素な整数 $A$ の 位数 $R$ を求める問題になるので、これはカーマイケル関数の性質を用いることで、位数 $R$ は $\lambda(PQ)=\operatorname{lcm}(P-1,Q-1)=(P-1)(Q-1)/\gcd(P-1,Q-1)$ の約数である、と考えることができます。

そこで今回の問題のオンラインジャッジでは、 $\operatorname{lcm}(P-1,Q-1)$ を素因数分解した値をあらかじめ用意して、そこから貪欲法で素因数を1種類ずつ加減していき $A^R\equiv 1\ (\operatorname{mod}N)$ が成り立つ範囲で最も少ない約数を求める事で、高速に $\operatorname{mod}N$ に関する $A$ の位数 を量子コンピュータの代わりに計算しています。

https://yukicoder.me/problems/no/3056/editorial

没バージョン

没バージョン(1)

https://yukicoder.me/submissions/801794

import math;a=g=2;n=int(input())
while g<3:print("?",a);g=math.gcd(n,pow(a,int(input())//2,n)-1);a+=1
print("!",g,n//g)

• 幻の最短コード (119Byte)
• 必要なコード ($\gcd(A,N)=1$ のチェック) も一部省略している嘘解法
• 例えば $N=33$ の素因数分解を試みさせると撃墜可能です
  ? 2 で質問クエリ → 位数 $R=10$ 、 $\gcd(2^5-1\operatorname{mod}33,33)=1$ より素因数発見失敗 → ? 3 で質問クエリ → $N=33$ と互いに素ではない質問クエリを送ってしまうので問題の条件違反により不正解
• #追加テストケース#N=33

没バージョン(2)

https://yukicoder.me/submissions/803578

import math;n=int(input());print("?",2);r=int(input());print("!",g:=max([math.gcd(n,pow(b,r>>1-r%2,n)-1)%n for b in range(99)]),n//g)

• Python3 (3.10.1 + numpy 1.22.3 + scipy 1.8.0)
• コード長133Byte、平均クエリ数2.00 = 質問1回+解答1回
• $A=\{2\},\ B=\{0,1,2,\dots,98\}$ として、 ? 2 の質問のみで求めた位数 $R$ を用いて $\begin{cases}\gcd(B^R-1\operatorname{mod}N,N)\operatorname{mod}N&R\text{ is odd}\\\gcd(B^{R/2}-1\operatorname{mod}N,N)\operatorname{mod}N&R\text{ is even}\end{cases}$ で素因数を発見できるか順次調べています。そのため、最悪ケースでは $B$ の範囲で素因数を見つけられずに誤った解答をする能性があります。2022-10-05: $N=$ 105312291668557186697918027513529248857806893649219117400977309697 のケースが $A=2$ において素因数の発見が難しい例になる事を発見したため、このコードは撃墜（不正解扱いに変更）されました。
• #追加テストケース#A=2,4,8

没バージョン(3)

https://yukicoder.me/submissions/803577

import math;n=int(input());print("?",2);r=int(input());b=g=2
while g<3:g=math.gcd(pow(b,r>>1-r%2,n)-1,n)%n;b+=1
print("!",g,n//g)

• Python3 (3.10.1 + numpy 1.22.3 + scipy 1.8.0)
• コード長129Byte、平均クエリ数2.00 = 質問1回+解答1回
• $A=\{2\},\ B=\{2,3,4,\dots\}$ として、 ? 2 の質問のみで求めた位数 $R$ を用いて $\begin{cases}\gcd(B^R-1\operatorname{mod}N,N)\operatorname{mod}N&R\text{ is odd}\\\gcd(B^{R/2}-1\operatorname{mod}N,N)\operatorname{mod}N&R\text{ is even}\end{cases}$ で素因数を発見できるか順次調べています。そのため、最悪ケースでは素因数を見つけられずに時間超過する可能性があります。2022-10-05: $N=$ 105312291668557186697918027513529248857806893649219117400977309697 のケースが $A=2$ において素因数の発見が難しい例になる事を発見したため、このコードは撃墜（不正解扱いに変更）されました。
• #追加テストケース#A=2,4,8

追加テストケース

ここでは、前項の没バージョン(1)を撃墜するための $N=33$ のケース、没バージョン(2)(3)を撃墜するための $N=(2^{107}-1)\times(2^{127}-1)$ のケース、 $A=\{3,5,6,7,9,10\}$ の時の位数において素因数の発見が難しいケース、ジャッジ対象に含まれていない RSA-232 と RSA-250 の追加テストケースを例示する。

入力テストケースファイルでは、素因数分解させたい合成数 $N$

$N$

出力テストケースファイルでは、 $N=PQ$ と素因数分解済みの相異なる奇の素因数 $P,Q$ および位数の最小公倍数 $\lambda(N)=\lambda(PQ)=\operatorname{lcm}(P-1,Q-1)=(P-1)(Q-1)/\gcd(P-1,Q-1)=f_0^{e_0}\cdot f_1^{e_1}\cdot f_2^{e_2}\cdot\dots\cdot f_{K-1}^{e_{K-1}}$ を素因数分解した、素因数の種類 $K$ と $\{f_i\},\{e_i\}$ の組

$P$
$Q$
$K$
$f_0$ $e_0$
$f_1$ $e_1$
$f_2$ $e_2$
$\vdots$
$f_{K-1}$ $e_{K-1}$

がそれぞれ格納されており、今回のジャッジサーバの応答プログラムでは出力テストケースファイルのみを使用して動作している。（入力テストケースファイルを使用していないため、現状ではyukicoderのシステム上、この問題では撃墜ケースの入力ができない）

https://yukicoder.me/problems/no/3056/code

リアクティブ問題・スペシャルジャッジ問題の仕様:

https://yukicoder.me/problems/374

また、追加テストケースの幾つかは様々な基数における レピュニット $\displaystyle{R_n^{(b)}=\frac{b^n-1}{b-1}\quad(|b|\ge 2,n\ge 1)}$ から生成している。以下の表にはレピュニットが素数となる$n$の値へのリンクは示しているが、テストケースの生成に使用したレピュニットは必ずしも素数とは限らない。

基数	一般型	レピュニットが素数となる$n$の数列
2	$\displaystyle\frac{2^n-1}{2-1}$ (メルセンヌ数)	https://oeis.org/A000043
3	$\displaystyle\frac{3^n-1}{3-1}$	https://oeis.org/A028491
4	$\displaystyle\frac{4^n-1}{4-1}$	$n=\{2\}\text{ only}$
5	$\displaystyle\frac{5^n-1}{5-1}$	https://oeis.org/A004061
6	$\displaystyle\frac{6^n-1}{6-1}$	https://oeis.org/A004062
7	$\displaystyle\frac{7^n-1}{7-1}$	https://oeis.org/A004063
8	$\displaystyle\frac{8^n-1}{8-1}$	$n=\{3\}\text{ only}$
9	$\displaystyle\frac{9^n-1}{9-1}$	$\text{(none)}$
10	$\displaystyle\frac{10^n-1}{10-1}$	https://oeis.org/A004023
11	$\displaystyle\frac{11^n-1}{11-1}$	https://oeis.org/A005808
12	$\displaystyle\frac{12^n-1}{12-1}$	https://oeis.org/A004064
13	$\displaystyle\frac{13^n-1}{13-1}$	https://oeis.org/A016054
14	$\displaystyle\frac{14^n-1}{14-1}$	https://oeis.org/A006032
15	$\displaystyle\frac{15^n-1}{15-1}$	https://oeis.org/A006033
16	$\displaystyle\frac{16^n-1}{16-1}$	$n=\{2\}\text{ only}$
17	$\displaystyle\frac{17^n-1}{17-1}$	https://oeis.org/A006034
18	$\displaystyle\frac{18^n-1}{18-1}$	https://oeis.org/A133857
19	$\displaystyle\frac{19^n-1}{19-1}$	https://oeis.org/A006035
20	$\displaystyle\frac{20^n-1}{20-1}$	https://oeis.org/A127995

N=33

https://yukicoder.me/problems/no/3056/test

challenge01.txt としてテストケース追加済み

#没バージョン(1) のアンチケース (質問クエリ順が決め打ちだと、質問クエリする整数が $N$ と互いに素であるかのチェックを省略した事がバレる例)

• in/33.txt

33

• out/33.txt

3
11
2
2 1
5 1

A=2,4,8

https://yukicoder.me/problems/no/3056/test

challenge02.txt としてテストケース追加済み

#質問クエリ数1回のコード解答例 のアンチケース (質問クエリが A=2 決め打ちだと解答困難な位数を返されるケースが存在する例)

この種のアンチケースにおいて、 $P,Q$ はメルセンヌ数 $R_n^{(2)}=M_n=2^n-1$ に含まれる素因数が代表的な候補。

• in/difficult_a2_01.txt

105312291668557186697918027513529248857806893649219117400977309697

• out/difficult_a2_01.txt
  • ? 2 ? 4 ? 8 質問時の位数 $R$ : 11303
  • 少なくとも $A\lt 10^6$ では $\gcd(A^{R}-1\operatorname{mod}N,N)$ での素因数発見はできず

170141183460469231731687303715884105727
618970019642690137449562111
21
2 1
3 3
5 1
7 2
17 1
19 1
23 1
43 1
73 1
89 1
127 1
337 1
353 1
397 1
683 1
2113 1
5419 1
92737 1
649657 1
2931542417 1
77158673929 1

A=3,9

#質問クエリ数1回のコード解答例 のアンチケース (質問クエリが A=3 決め打ちだと解答困難な位数を返されるケースが存在する例)

$3$進$n$桁のレピュニット $\displaystyle{R_n^{(3)}=\frac{3^n-1}{2}}$ に含まれる素因数 がこのアンチケースにおける $P,Q$ の代表的な候補。

• in/difficult_a3_01.txt

26123919082944578991525969725862672018603930327232748124913487088083521807790505049

• out/difficult_a3_01.txt
  • ? 3 ? 9 質問時の位数 $R$ : 7313
  • 少なくとも $A\lt 10^6$ では $\gcd(A^{R}-1\operatorname{mod}N,N)$ での素因数発見はできず

3754733257489862401973357979128773
6957596529882152968992225251835887181478451547013
21
2 2
3 1
7 1
11 2
13 1
61 1
71 1
103 1
307 1
547 1
613 1
1021 1
1093 1
1871 1
12853 1
30091 1
34511 1
129159847 1
2664097031 1
99810171997 1
374857981681 1

A=2,3,4,6,8,9

$2,3$進$n$桁のレピュニット の最大公約数 $\displaystyle{\gcd\left(R_n^{(2)},R_n^{(3)}\right)=\gcd\left(2^n-1,\frac{3^n-1}{2}\right)\gt n}$ の時に左辺に含まれる素因数 がこのアンチケースにおける $P,Q$ の代表的な候補。

• $\gcd(R_{11}^{(2)},R_{11}^{(3)})$$\displaystyle{=\gcd\left(2^{11}-1,\frac{3^{11}-1}{2}\right)}$$=23$

• $\gcd(R_{43}^{(2)},R_{43}^{(3)})$$\displaystyle{=\gcd\left(2^{43}-1,\frac{3^{43}-1}{2}\right)}$$=431$

• $\gcd(R_{463}^{(2)},R_{463}^{(3)})$$\displaystyle{=\gcd\left(2^{463}-1,\frac{3^{463}-1}{2}\right)}$$=11113$

• in/difficult_a2+a3_01.txt

3423291526382265980807

• out/difficult_a2+a3_01.txt
  • ? 2 ? 3 ? 4 ? 6 ? 8 ? 9 質問時の位数 $R$ : 260420776617983
  • $\gcd(45443^{R}-1\operatorname{mod}N,N)=49383448463$

49383448463
69320625289
6
2 3
3 1
173 1
1583 1
15598057 1
16695719 1

A=2,3,4,5,6,7,8,9,10

$2,3,5,7$進$n$桁のレピュニット の最大公約数 $\displaystyle{\gcd\left(R_n^{(2)},R_n^{(3)},R_n^{(5)},R_n^{(7)}\right)=\gcd\left(2^n-1,\frac{3^n-1}{2},\frac{5^n-1}{4},\frac{7^n-1}{6}\right)\gt n}$ の時に左辺に含まれる素因数 がこのアンチケースにおける $P,Q$ の代表的な候補。

• $\gcd(R_{239}^{(2)},R_{239}^{(3)},R_{239}^{(5)},R_{239}^{(7)})$$\displaystyle{=\gcd\left(2^{239}-1,\frac{3^{239}-1}{2},\frac{5^{239}-1}{4},\frac{7^{239}-1}{6}\right)}$$=\gcd(R_{239}^{(2)},R_{239}^{(3)},R_{239}^{(4)},R_{239}^{(5)},R_{239}^{(6)},R_{239}^{(7)},R_{239}^{(8)},R_{239}^{(9)},R_{239}^{(10)})$$=\gcd\left(2^{239}-1,\frac{3^{239}-1}{2},\frac{4^{239}-1}{3},\frac{5^{239}-1}{4},\frac{6^{239}-1}{5},\frac{7^{239}-1}{6},\frac{8^{239}-1}{7},\frac{9^{239}-1}{8},\frac{10^{239}-1}{9}\right)$$=479$
• $\gcd(R_{137623}^{(2)},R_{137623}^{(3)},R_{137623}^{(5)},R_{137623}^{(7)})$$\displaystyle{=\gcd\left(2^{137623}-1,\frac{3^{137623}-1}{2},\frac{5^{137623}-1}{4},\frac{7^{137623}-1}{6}\right)}$$=\gcd(R_{137623}^{(2)},R_{137623}^{(3)},R_{137623}^{(4)},R_{137623}^{(5)},R_{137623}^{(6)},R_{137623}^{(7)},R_{137623}^{(8)},R_{137623}^{(9)},R_{137623}^{(10)})$$=\gcd\left(2^{137623}-1,\frac{3^{137623}-1}{2},\frac{4^{137623}-1}{3},\frac{5^{137623}-1}{4},\frac{6^{137623}-1}{5},\frac{7^{137623}-1}{6},\frac{8^{137623}-1}{7},\frac{9^{137623}-1}{8},\frac{10^{137623}-1}{9}\right)$$=1376231$
• $\gcd(R_{1136287}^{(2)},R_{1136287}^{(3)},R_{1136287}^{(5)},R_{1136287}^{(7)})$$\displaystyle{=\gcd\left(2^{1136287}-1,\frac{3^{1136287}-1}{2},\frac{5^{1136287}-1}{4},\frac{7^{1136287}-1}{6}\right)}$$=\gcd(R_{1136287}^{(2)},R_{1136287}^{(3)},R_{1136287}^{(4)},R_{1136287}^{(5)},R_{1136287}^{(6)},R_{1136287}^{(7)},R_{1136287}^{(8)},R_{1136287}^{(9)},R_{1136287}^{(10)})$$=\gcd\left(2^{1136287}-1,\frac{3^{1136287}-1}{2},\frac{4^{1136287}-1}{3},\frac{5^{1136287}-1}{4},\frac{6^{1136287}-1}{5},\frac{7^{1136287}-1}{6},\frac{8^{1136287}-1}{7},\frac{9^{1136287}-1}{8},\frac{10^{1136287}-1}{9}\right)$$=27270889$

#質問クエリ数1回のコード解答例 のアンチケース (質問クエリが決め打ちだと連続で解答困難な位数を返されるケースが存在する例)

• in/difficult_a2+a3+a5+a7_01.txt

11677649222449681

• out/difficult_a2+a3+a5+a7_01.txt
  • ? 2 ? 3 ? 4 ? 5 ? 6 ? 7 ? 8 ? 9 ? 10 質問時の位数 $R$ : 116776490052337
  • ? 11 質問時の位数 $R$ : 583882450261685
  • $\gcd(199^{R}-1\operatorname{mod}N,N)=119472911$

97743071
119472911
4
2 1
5 1
9774307 1
11947291 1

A=2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,...

$2,3,5,7,11,13,17,19$進$n$桁のレピュニット の最大公約数 $\displaystyle{\gcd\left(R_n^{(2)},R_n^{(3)},R_n^{(5)},R_n^{(7)},R_n^{(11)},R_n^{(13)},R_n^{(17)},R_n^{(19)}\right)}$$\displaystyle{=\gcd\left(2^n-1,\frac{3^n-1}{2},\frac{5^n-1}{4},\frac{7^n-1}{6},\frac{11^n-1}{10},\frac{13^n-1}{12},\frac{17^n-1}{16},\frac{19^n-1}{18}\right)}$$\gt n$ の時に左辺に含まれる素因数 がこのアンチケースにおける $P,Q$ の代表的な候補。

• $\gcd(R_{5279}^{(2)},R_{5279}^{(3)},R_{5279}^{(5)},R_{5279}^{(7)},R_{5279}^{(11)},R_{5279}^{(13)},R_{5279}^{(17)},R_{5279}^{(19)})$$\displaystyle{=\gcd\left(2^{5279}-1,\frac{3^{5279}-1}{2},\frac{5^{5279}-1}{4},\frac{7^{5279}-1}{6},\frac{11^{5279}-1}{10},\frac{13^{5279}-1}{12},\frac{17^{5279}-1}{16},\frac{19^{5279}-1}{18}\right)}$$=10559$

#質問クエリ数1回のコード解答例 のアンチケース (質問クエリが決め打ちだと連続で解答困難な位数を返されるケースが存在する例)

• in/difficult_a2++a19_01.txt

4445421869801641

• out/difficult_a2++a19_01.txt
  • ? 2 ? 3 ? 4 ? 5 ? 6 ? 7 ? 8 ? 9 ? 10 ? 11 ? 12 ? 13 ? 14 ? 15 ? 16 ? 17 ? 18 ? 19 ? 20 ? 21 ? 22 ? 24 ? 25 ? 26 ? 27 ? 28 ? 29 ? 30 ? 32 ? 33 ? 34 ? 35 ? 36 ? 38 ? 39 ? 40 ? 42 ? 44 ? 45 ? 48 ? 49 ? 50 ? 51 ? 52 ? 53 ? 54 ? 55 ? 56 ? 57 ? 58 ? 59 ? 60 ? 61 ? 63 ? 64 ? 65 ? 66 ? 68 ? 70 ? 71 ? 72 ? 73 ? 75 ? 76 ? 77 ? 78 ? 79 ? 80 ? 81 ? 84 ? 85 ? 87 ? 88 ? 90 ? 91 ? 95 ? 96 ? 97 ? 98 ? 99 ? 100 ? 102 ? 104 ? 105 ? 106 質問時の位数 $R$ : 1111355434112821
  • ? 23 ? 31 ? 37 ? 41 ? 43 ? 46 ? 47 ? 62 ? 67 ? 69 ? 74 ? 82 ? 83 ? 86 ? 89 ? 92 ? 93 ? 94 ? 101 ? 103 ? 107 質問時の位数 $R$ : 2222710868225642
  • $\gcd(107^{R}-1\operatorname{mod}N,N)=66278159$

66278159
67072199
3
2 1
33139079 1
33536099 1

A=5

$5$進$n$桁のレピュニット $\displaystyle{R_n^{(5)}=\frac{5^n-1}{4}}$ に含まれる素因数 がこのアンチケースにおける $P,Q$ の代表的な候補。

• in/difficult_a5_01.txt

6223015277861141707144064053780115482474850138614473859791221052813878332398246712960371341448939305762655394005378184374421834945678711

• out/difficult_a5_01.txt
  • ? 5 質問時の位数 $R$ : 7003
  • 少なくとも $A\lt 10^6$ では $\gcd(A^{R}-1\operatorname{mod}N,N)$ での素因数発見はできず

177635683940025046467781066894531
35032461608120426773093239582247903282006548546912894293926707097244777067146515037165954709053039550781
17
2 2
3 1
5 1
13 1
47 1
149 1
8971 1
9103 1
9769 1
40849 1
29010221 1
13971969971 1
332207361361 1
8737481256739 1
42272797713043 1
45920153384867 1
510241095096183757930733363918820917976121 1

A=6

$6$進$n$桁のレピュニット $\displaystyle{R_n^{(6)}=\frac{6^n-1}{5}}$ に含まれる素因数 がこのアンチケースにおける $P,Q$ の代表的な候補。

• in/difficult_a6_01.txt

61182672763131338697888257100877104143687583125445987205910530345369345734084691011283

• out/difficult_a6_01.txt
  • ? 6 質問時の位数 $R$ : 4331
  • 少なくとも $A\lt 10^6$ では $\gcd(A^{R}-1\operatorname{mod}N,N)$ での素因数発見はできず

17252803354297421346943980322273
3546245297457217493590449191748546458005595187661976371
23
2 5
3 1
5 1
7 2
11 1
29 1
61 1
71 1
101 1
197 1
269 1
311 1
599 1
631 1
701 1
2311 1
9241 1
55987 1
585131 1
37863211 1
1318006741 1
1469029031 1
13872727972847 1

A=7

$7$進$n$桁のレピュニット $\displaystyle{R_n^{(7)}=\frac{7^n-1}{6}}$ に含まれる素因数 がこのアンチケースにおける $P,Q$ の代表的な候補。

• in/difficult_a7_01.txt

291345522143145538957212762561823421428905812676152594106635825218583660862149194075736443

• out/difficult_a7_01.txt
  • ? 7 質問時の位数 $R$ : 5734
  • 少なくとも $A\lt 10^6$ では $\gcd(A^{R/2}-1\operatorname{mod}N,N)$ での素因数発見はできず

444519128147170444656914672945689439050880209231501
655417289594537954307682339857743931943
22
2 2
3 2
5 3
7 1
11 1
13 1
19 1
31 1
43 1
47 1
61 1
181 1
191 1
281 1
2801 1
3083 1
4021 1
159871 1
6568801 1
555915824341 1
31479823396757 1
3421093417510114543 1

A=10

$10$進$n$桁のレピュニット $\displaystyle{R_n^{(10)}=\frac{10^n-1}{9}}$ に含まれる素因数 がこのアンチケースにおける $P,Q$ の代表的な候補。

• in/difficult_a10_01.txt

10947916297441573929678129254926641512362557713396205334080877400559173

• out/difficult_a10_01.txt
  • ? 10 質問時の位数 $R$ : 3185
  • 少なくとも $A\lt 10^6$ では $\gcd(A^{R}-1\operatorname{mod}N,N)$ での素因数発見はできず

5538396997364024056286510640780600481
1976730144598190963568023014679333
13
2 5
3 1
5 1
7 2
11 1
13 1
79 1
127 1
140773 1
86627231 1
237437669039 1
2646669393877 1
10583862670370427978037 1

RSA-232

https://en.wikipedia.org/wiki/RSA_numbers#RSA-232

• in/RSA232.txt

1009881397871923546909564894309468582818233821955573955141120516205831021338528545374366109757154363664913380084917065169921701524733294389270280234380960909804976440540711201965410747553824948672771374075011577182305398340606162079

• out/RSA232.txt

29669093332083606603617799242426306347429462625218523944018571574194370194723262390744910112571804274494074452751891
34038161751975634380066094984915214205471217607347231727351634132760507061748526506443144325148088881115083863017669
12
2 2
5 1
41 1
443 1
165479 1
9558969107 1
19746412471 1
192884403020146233859 1
38252589736891930996676352841652107162937 1
121852699704246278672182283286643773248913917 1
779519473309251176957543614683532598812571459 1
63498076483167021259794181873325947749878784693473 1

RSA-250

https://en.wikipedia.org/wiki/RSA_numbers#RSA-250

• in/RSA250.txt

2140324650240744961264423072839333563008614715144755017797754920881418023447140136643345519095804679610992851872470914587687396261921557363047454770520805119056493106687691590019759405693457452230589325976697471681738069364894699871578494975937497937

• out/RSA250.txt

64135289477071580278790190170577389084825014742943447208116859632024532344630238623598752668347708737661925585694639798853367
33372027594978156556226010605355114227940760344767554666784520987023841729210037080257448673296881877565718986258036932062711
10
2 1
5 1
13 1
6213239 1
440117350342384303 1
101910617047160921359 1
4597395223158209096147 1
8015381692860102796237 1
11015842872223957032465527015746975907581857223611379316467045416408679146689 1
72769022935390028131583224155323574786067394416649454368282707661426220155269516297 1

まとめ

• $A\operatorname{mod}N$ の位数は1つでも求まると、その値から容易に素因数分解されやすい
• 現状、素因数が未知の大きな合成数 $N$ について位数を求める事は一般には難しい
• でも、何らかの技術的革新があれば位数が容易に求められるようになるかもしれない
• 量子コンピュータによる素因数分解向けのShorのアルゴリズムは、応用で楕円曲線暗号の根拠となる離散対数問題も多項式時間で解けるとされている
• 位数こわいですね