数値の因数分解（オプション2）

合成数の因数分解アルゴリズムのバリアントの1つをご紹介したいと思います。

単純化するために、図1に示す[1]のように、合成数A = 35の残差の行列を考えます。

すでに述べたように[1]、合成数Aのパワー残差の表（図1）には特定の特徴があります。

34	1	34	1	34	1	34	1	34	1	34	1	34	1	34	1	34	1	34	1	34	1	34	1	34	1	34	1	34	1	34	1	34	1
33	4	27	16	3	29日	12	11	13	9	17	1	33	4	27	16	3	29日	12	11	13	9	17	1	33	4	27	16	3	29日	12	11	13	9
32	9	8	11	2	29日	18	16	22	4	23	1	32	9	8	11	2	29日	18	16	22	4	23	1	32	9	8	11	2	29日	18	16	22	4
31	16	6	11	26	1	31	16	6	11	26	1	31	16	6	11	26	1	31	16	6	11	26	1	31	16	6	11	26	1	31	16	6	11
30	25	15	30	25	15	30	25	15	30	25	15	30	25	15	30	25	15	30	25	15	30	25	15	30	25	15	30	25	15	30	25	15	30
29日	1	29日	1	29日	1	29日	1	29日	1	29日	1	29日	1	29日	1	29日	1	29日	1	29日	1	29日	1	29日	1	29日	1	29日	1	29日	1	29日	1
28	14	7	21	28	14	7	21	28	14	7	21	28	14	7	21	28	14	7	21	28	14	7	21	28	14	7	21	28	14	7	21	28	14
27	29日	13	1	27	29日	13	1	27	29日	13	1	27	29日	13	1	27	29日	13	1	27	29日	13	1	27	29日	13	1	27	29日	13	1	27	29日
26	11	6	16	31	1	26	11	6	16	31	1	26	11	6	16	31	1	26	11	6	16	31	1	26	11	6	16	31	1	26	11	6	16
25	30	15	25	30	15	25	30	15	25	30	15	25	30	15	25	30	15	25	30	15	25	30	15	25	30	15	25	30	15	25	30	15	25
24	16	34	11	19	1	24	16	34	11	19	1	24	16	34	11	19	1	24	16	34	11	19	1	24	16	34	11	19	1	24	16	34	11
23	4	22	16	18	29日	2	11	8	9	32	1	23	4	22	16	18	29日	2	11	8	9	32	1	23	4	22	16	18	29日	2	11	8	9
22	29日	8	1	22	29日	8	1	22	29日	8	1	22	29日	8	1	22	29日	8	1	22	29日	8	1	22	29日	8	1	22	29日	8	1	22	29日
21	21	21	21	21	21	21	21	21	21	21	21	21	21	21	21	21	21	21	21	21	21	21	21	21	21	21	21	21	21	21	21	21	21
20	15	20	15	20	15	20	15	20	15	20	15	20	15	20	15	20	15	20	15	20	15	20	15	20	15	20	15	20	15	20	15	20	15
19	11	34	16	24	1	19	11	34	16	24	1	19	11	34	16	24	1	19	11	34	16	24	1	19	11	34	16	24	1	19	11	34	16
18	9	22	11	23	29日	32	16	8	4	2	1	18	9	22	11	23	29日	32	16	8	4	2	1	18	9	22	11	23	29日	32	16	8	4
17	9	13	11	12	29日	3	16	27	4	33	1	17	9	13	11	12	29日	3	16	27	4	33	1	17	9	13	11	12	29日	3	16	27	4
16	11	1	16	11	1	16	11	1	16	11	1	16	11	1	16	11	1	16	11	1	16	11	1	16	11	1	16	11	1	16	11	1	16
15	15	15	15	15	15	15	15	15	15	15	15	15	15	15	15	15	15	15	15	15	15	15	15	15	15	15	15	15	15	15	15	15	15
14	21	14	21	14	21	14	21	14	21	14	21	14	21	14	21	14	21	14	21	14	21	14	21	14	21	14	21	14	21	14	21	14	21
13	29日	27	1	13	29日	27	1	13	29日	27	1	13	29日	27	1	13	29日	27	1	13	29日	27	1	13	29日	27	1	13	29日	27	1	13	29日
12	4	13	16	17	29日	33	11	27	9	3	1	12	4	13	16	17	29日	33	11	27	9	3	1	12	4	13	16	17	29日	33	11	27	9
11	16	1	11	16	1	11	16	1	11	16	1	11	16	1	11	16	1	11	16	1	11	16	1	11	16	1	11	16	1	11	16	1	11
10	30	20	25	5	15	10	30	20	25	5	15	10	30	20	25	5	15	10	30	20	25	5	15	10	30	20	25	5	15	10	30	20	25
9	11	29日	16	4	1	9	11	29日	16	4	1	9	11	29日	16	4	1	9	11	29日	16	4	1	9	11	29日	16	4	1	9	11	29日	16
8	29日	22	1	8	29日	22	1	8	29日	22	1	8	29日	22	1	8	29日	22	1	8	29日	22	1	8	29日	22	1	8	29日	22	1	8	29日
7	14	28	21	7	14	28	21	7	14	28	21	7	14	28	21	7	14	28	21	7	14	28	21	7	14	28	21	7	14	28	21	7	14
6	1	6	1	6	1	6	1	6	1	6	1	6	1	6	1	6	1	6	1	6	1	6	1	6	1	6	1	6	1	6	1	6	1
5	25	20	30	10	15	5	25	20	30	10	15	5	25	20	30	10	15	5	25	20	30	10	15	5	25	20	30	10	15	5	25	20	30
4	16	29日	11	9	1	4	16	29日	11	9	1	4	16	29日	11	9	1	4	16	29日	11	9	1	4	16	29日	11	9	1	4	16	29日	11
3	9	27	11	33	29日	17	16	13	4	12	1	3	9	27	11	33	29日	17	16	13	4	12	1	3	9	27	11	33	29日	17	16	13	4
2	4	8	16	32	29日	23	11	22	9	18	1	2	4	8	16	32	29日	23	11	22	9	18	1	2	4	8	16	32	29日	23	11	22	9
1	1	1	1	1	1	1	1	1	1	1	1	1	1	1	1	1	1	1	1	1	1	1	1	1	1	1	1	1	1	1	1	1	1

図 1合成数A = 35のべき乗の表。

値が数値Aの約数の倍数である行を除外する場合、残りの値が1である2つの列が必ずあります。 図 1は、番号12、24の列です。

これらの2つの列のうち、最大の列番号は（x-1）と（y-1）の積です。ここで、 xとyは Aの約数です。 この場合、列番号24はオイラー関数[2]の値に等しく、その値は
（x-1）*（y-1）=ѱ（n） 。

数Aとオイラー関数ѱ（n）の差は（x + y-1）です。

これらのパターンにより、方程式系を構成できます。

Ѱ（n）=（x-1）*（y-1）
A-ѱ（n）=（x + y-1）
式（1）

順列を使用して、方程式系（1）を2次方程式（2）に還元できます。

y ^2- （A-ѱ（n）+ 1）y + A = 0
式（2）

この方程式をうまく解くには、 ѱ（n）だけが欠落しています。

さらに、テーブルの数Aのパワー残差の特性を考慮します（図1）。 逆値の概念を紹介します[3]。 数値の範囲（1、A-1）からcの値を選択し、 cにxとyの複数の除数がないようにすると、同じ範囲（1、A-1）からの値dが常に存在します。

c * d≡1（mod A）
式（3）

つまり c * d = nA +1 。ここで、 nは1〜 （A-2）の値を取ることができます。

表記d = inv（c） 、つまり dはcの逆数です。 単純係数xとyの積に等しい合成数Aの場合、逆値のペアの数は

（A-（x-1）-（y-1）-1）/ 2
フォーミュラ（4）

表の行（図1）の逆の値は、番号ѱ（n）の列に対して対称に配置されます。

表の列の逆値（図1）は、最初の列の逆値のペアに対して対称に配置されます。

ѱ（n）を見つけるための一連のアクションを検討します。

1.検索範囲を縮小します。 （A-1）から、最も近い整数に計算されたAの平方根の値を取得します。 ѱ1によって得られた結果を示します。

2.数値Aの約数x 、 yの倍数ではなく、数値cを選択します。 cのパワー残差の重複値の最小数が望ましいです。

3.数d = inv（s）を見つけます。 拡張ユークリッドアルゴリズムを使用して見つけることができます[4]。

4.指数1から始まり、 Aの平方根以下の数値mで終わるdのべき乗残差を求めます。

5.配列で見つかったべき乗則の残差を見つけ、それをMで示します。 配列Mは昇順でソートされ、指数でインデックス付けされます。

6. cのremainder ₁乗をAで割った余りを計算し、 Mの値と比較します。

7.一致するものがない場合、 ѱ1からmを引き 、結果の値をѱ1に割り当てます。 次に、一致するまで段落6と7を繰り返します。

8.一致する場合、配列Mの値に一致する次数インデックスの大きさをѱ1から減算し、結果の値をѱ1に割り当てます。

この場合、 ѱ1 =ѱ（n）です。

仕組みは次のとおりです。 （A-1）= 34 （図1）から35の平方根、つまり 5、29を取得します。 cについては、 18を選択します。 inv（18）= 2です。 m = 5の場合、配列M = {2、4、8、16、32} 。 35で割った29の累乗の18の残りは23です。 inv（23）= 32 。 この値は配列内にあり、インデックスは5です。 29から5を引く必要があります。 結果の値24はѱ（n）です。 次に、式（2）のAとѱ（n）を代入し、 yを見つけます。 y ₁ = 7 、 y ₂ = 5

別の例。

2から11次、マイナス1は2047です。
2047 = 23 * 89
2047/3 = 682および剰余1
c = 682、inv（s）= 3
2047の平方根= 45、剰余22。
2047-45 = 2002
m = 20
M = {3、9、27、81、243、729、140、420、1260、1733、1105、1268、1757、1177、1484、358、1074、1175、1478、340}
2002年の682を2047で除算し、残りは1013です。inv（1013）= 1657、配列に一致するものはありません。
2002-20 = 1982
682の1982乗は2047で除算され、残りは524です。inv（524）= 1504、配列に一致するものはありません。
1982-20 = 1962
682の1962乗は2047で除算され、残りは71です。inv（71）= 173、配列には一致がありません。
1962-20 = 1942
682の1942乗は2047で除算され、残りは1623です。inv（1623）= 729、配列に一致があり、インデックスは6です
1942-6 = 1936 =ѱ（n）
y ^2- （2047-1936 + 1）y + 2047 = 0
y 2-112y + 2047 = 0
y ₁ = 89
y ₂ = 23

文学
1.「数字の対称性」、 habrahabr.ru / post / 218053
2.「オイラー関数」、 en.wikipedia.org / wiki / Euler_Function 。
3.「リターン番号」、 en.wikipedia.org / wiki / Return_Number
4.「公開キー暗号化」、 ikit.edu.sfu-kras.ru / files / 15 / l5.pdf