An Efficient Factoring Algorithm by Repunit Number Method を読む

どうも,なかなか話が合わない.EFMでは[8’]として,

Let p be a prime number which is neither 2 nor 5, and the recursion unit of p be U, then pU/9 is a repunit number Rn, i.e., pU=10n-1.

という命題を提示し,その証明を与えているが,その中でpが素数でpとeが互いに素のとき,b^e-1≡0 mod p となるような最小の整数eが存在し,これはpがb^n-1を割り切ることを意味するとしている.これは,フェルマーの小定理を言い換えただけのものであるから,正しい.従って,pU=b^e-1となるような最小の整数Uが存在するとし,これはUがpの循環単位であることを意味するとしている.

n=11, e=2, K=7, B=5のとき,@=5, U=284, nU=4444,rep=1111で,Uは11の循環単位である.このとき,5^5%11=284…1となるので,B^@%n=U…1が成立している.ここで,@は循環節の桁数である.eという指数はべき剰余数列のψに相当する数と考えられるが,Q=264に相当する数がψないし#に出てくるような計算式を立てられるだろうか?#ないしψはKより小さいと考えられるので,相当大きなKが必要になる.nもかなり大きな数でなくてはならないだろう.K = 1111に設定するとかなり近い数字に近づく.Kが素数でないと大きな数が出てこない.ちょっと的が外れている感じ.

N^eの計算値を再利用するために出力用のテキストボックスを追加しようと思ったのだが,すでに十二分に画面が混み合っているので出力ペーンに書き出すことにする.EFAと実装が合わない点として,09 Mar 2005のメールには For example 21 is a composite but has a repunit number 111 with recursion unit 03 とあるが,これは道具箱の動作とあっていない.1/21=0.04761904761904761904761904…で,U=047619,nU=999999, rep=111111だ.これは明らかに誤認と思われる.このメールに記載されたリストでは,U=047619となっているので,何か勘違いしていたのではないだろうか?

EFAではn→r{m}(m桁のレピュニット数)のとき,nをr{m}のオリジネータと呼んでいる.このとき,nの素因数分解とr{m}には明らかに何らかの相関がある.nは必ずしもレピュニット数のオリジネータになる訳ではないので,nから生成されるレピュニット類似の数をrep(n)と表記することにしよう.rep(n)がレピュニット数r(m)になる条件を調べることは意味があるように思われる.

Bの素因数分解も出す必要がある.レピュニットに関わりがある.

09 Mar 2005のメールには誤りがあるが,その下の方のリストは正しいので,注意深い読者なら多分気付いたことだろう.このメールの終わりの方に,pが素数であるための5条件というのを列挙している.この項目はチェックする必要がある.もし,これらが正しいとすると素数判定をかなり/ある程度高速化できる可能性がある.

(1) p has a repunit R_k=pU(p)/9
(2) k divides p-1
(3) for p > 3, (p,9)=1
(4) p divides R_k
(5) p and k are mutually prime

コメントを残す

メールアドレスが公開されることはありません。 が付いている欄は必須項目です

CAPTCHA