素因数分解アルゴリズム(因数分解が既知の隣数から導く)
書き終わったらプログラムを書いて検証しようと思います。より小さい自然数で素因数分解が既知の場合に適用できる可能性のあるアルゴリズム。
基本の形はこれです。
$${pq-ab=1}$$
$${(p+1)(q+1)-1=ab}$$
上式は素数界隈では有名な拡張ユークリッド法、ベズーの方程式、モジュラ逆数などの基礎となる式ですが、今回はこれに少し扱いやすいように変形を加えた式を軸に、素因数分解を目指そうと思います。
$${(p+1)(q+1)-1=ab}$$が成立するp,q,a,bにおいて、式を展開すると、
$${pq+p+q=ab}$$
が成り立ちます。このことから、
$${pq+p+q=ab≡p (mod q)}$$
$${pq+p+q=ab≡q (mod p)}$$
が成り立ちます。もし仮にpとqが互いに素ではなかった場合、$${pq+p+q}$$はpとqの共通する因数と同じ数字を因数に持つことを示すことができます。互いに素ではないpとqで$${(p+1)(q+1)-1=ab}$$の形を作ることができれば、それらのpとqの共通する因数は、abの因数のうちのひとつであると確実に判断することができます。この形を効率的に作ることができれば、abの素因数分解に繋げることができると思います。
まだアルゴリズムは考案中ですが、今のところの作成予定のアルゴリズムを記録のために書き残しておきます。(2024年1月9日追記、雛形を作りました。下に置いておきます。)
以下アルゴリズム
①与えられた因数のわからない自然数nから、拡張ユークリッド互除法を使い、$${rs-n=1}$$となるr,sの組を作る。
②r,sの因数を先に全て求める(以後r,sの素因数は全てわかっているものとする)
③ 拡張ユークリッド互除法を用いて求めた組には$${n-rs=1}$$の形になるものと$${n-rs=-1}$$の形になるものと2種類あるので、条件に合わせて分岐させて以下の処理を行う。
$${n-rs=1}$$の形だった場合、$${n-1=rs}$$ として、$${n=(p+1)(q+1)}$$と置き、rsの方を変形して、$$${rs=r(rxy+x+y)}$$となるr,x,yの組を探す。
$${rs=r(rxy+x+y)}$$が成り立つ場合は、式を変形して、
$${rs=r(rxy+x+y)}$$
$${=r^2xy+rx+ry+1-1}$$
$${=(rx+1)(ry+1)-1}$$
とすることができるのでnの方の式と比較して、p+1とq＋1をrx＋1、ry＋1に対応させてnの因数とする。
$${n-rs=-1}$$の形だった場合、$${n=rs-1}$$として、rsを(cR+1)(cS+1)と置き、$${rs-1=(cR+1)(cS+1)-1}$$を満たす1ではない整数c,R,Sの組を求める。
これを変形すれば、
$${rs-1=(cR+1)(cS+1)-1}$$
$${=c^2RS+cR+cS+1-1}$$
$${=c(cRS+R+S)}$$
となり、nの式と比較して、cとcRS+R+Sをそれぞれ、nの因数とする。
④求めた因数でnを割り、実際のnの因数であるかどうか確かめる。
⑤1から④を全ての因数が素数になるまで続ける。
小さい数で因数分解が既知の整数の組があれば、それらを使ってもう少し大きな数のnを因数分解するためのアルゴリズムとして、これを使うことができる可能性があります。
依然既知の因数分解の組から条件を満たす整数の組み合わせを探すのに時間がかかるかと思いますが、しばらく検証してみようと思います。
ありがとうございました。
コード
def insstep(a,b,bls):
if a<0:
a=abs(a)
if b<0:
b=abs(b)
c=a-b
ansls=[]
hg=1
if c<0:
hg=-1
if c==0:
hg=0
if abs(c)!=1:
print(c,'not one')
bb=b
pbls=[]
for i in range(len(bls)):
if issosu(bls[i])!=1 and bls[i]!=2:
continue
k=1
while bb>1 and bb%bls[i]==0:
print(bb)
pbls+=[bls[i]**k]
bb//=bls[i]
k+=1
if bb>1 and issosu(bb)==1:
pbls+=[bb]
elif bb>1:
print('b list is not all prime factor')
if hg==1:
for i in range(len(pbls)):
p=pbls[i]
bp=b//p
r,s=divmod(bp,p)
for ss in [1,2,3,5,7]:
t=ss**2+s*ss+r
if issosu(t)==1:
continue
j=2
tls=[]
while j <200:
k=1
while t%j==0 and t>1:
tls+=[j**k]
k+=1
t//=j
j+=1
t=ss**2+s*ss+r
#print(ss,r,s,t)
for j in range(len(tls)):
q=tls[j]
qq=t//q
q,qq=q-ss,qq-ss
c=pbls[i]
cd=c*q+1
ce=c*qq+1
#print(c,cd,ce,q,qq)
if a%cd==0 :#and cd!=a and cd!=1:
ansls+=[cd]
if a%ce==0 :#and ce!=a and ce!=1:
ansls+=[ce]
elif hg==-1:
for i in range(len(pbls)):
p=abs(pbls[i])
bp=b//p
r,s=divmod(bp,p)
for ss in [1,2,3,5,7]:
t=ss**2+s*ss+r
if issosu(t)==1:
continue
j=2
tls=[]
while j <200:
k=1
while t%j==0 and t>1:
tls+=[j**k]
k+=1
t//=j
j+=1
t=ss**2+s*ss+r
#print(ss,r,s,t)
for j in range(len(tls)):
q=tls[j]
qq=t//q
q,qq=q-ss,qq-ss
c=pbls[i]
cd=c
ce=c*q*qq+q+qq
if a%cd==0 :#and cd!=a and cd!=1:
ansls+=[cd]
if a%ce==0 :#and ce!=a and ce!=1:
ansls+=[ce]
return ansls
print(insstep(34,35,[5,7]))
issosu()の関数だけ自作の素数判定の関数を使っています。ミラーラビンで動かしています。初動動きましたが、これからしっかりと動くかはわからないので、徐々に試してみます。
ただ、それでも10進で15桁行くのにはハードルが高いかな。。