素数判定にb^p-1 ≡ 1 mod p を導入する

素数判定にb^p-1 ≡ 1 mod p を導入しようとしているところだが,その前にIsPrimeの代わりにTotientFuncを呼んでいるところをIsPrimeに切り替えておこう.⇒いや,すでに整理されている.FactoringSubなどで使われていたが,すでに廃止されている.

素因数分解などで i の範囲をmaxにしているところがあるのではないか?素因数を取るためには√maxまで検査すれば十分である.⇒いや,その辺りは抜かりなく対処している.FactoringSubでは max = BSqrt(n) としている.TotientFuncではそのような手当は行っていないが,(x / d < d)でレンジチェックしているので問題なさそうだ.多少とも効率を改善することになったかどうかはあまり,はっきりしない.

とりあえず,これでN=9223372036854775807の範囲(Int64)では万遍なく動作することになったと言えると思う.ただし,1/Nでは配列サイズの上限があるので,MAXARRAYSIZE = 268435455より大きいNでは循環節などの表示はできない.同様の理由でcycle, stripeが表示不能になる場合もある.ともかく,時間は掛かるが停止しないで動作できるようになったのではないか?

Nが10桁のときのSeedTestを実行しているところだが,さすがに遅い.ネックになっているのは素因数分解のところと思われるが,取り敢えず今のところ打つ手はない.というか,ψ数を使って因数分解する話があったはずなのだが… しばらくはこれを使って An Efficient Factoring Algorithm by Repunit Number Methodを読み直しながら遊んでみることにしよう.銀林浩「初等整数論入門」の読み直しもやらなくては…

N=1234567890,B=1でPrimeTestを実行して,下記のエラーが出た.

image

B=1のときは,固定部がN桁になるため,配列サイズオーバーが起きていた.上限を設定して回避するようにした.また,このエラーメッセージを出力ペーンにも出力するようにした.nを調整して,MAXARRAYSIZE=268435455以下に設定すれば,正常に描画できる.

N=268435455で上限オーバーは発生しなくなったが,1/nやU,nUなどが空欄のままになっている.特に,1/nは更新されずに古いままの値が残っているのはまずい.⇒今度は問題なく描画されている.⇒PrimeTestではなく,InvertTestだったかもしれない.いや,更新された.ただし,かなり重い.⇒描画は出ている.⇒base2.ValueChangedイベントが掛かって,ValueChangedをダブって実行していた.

ValueChangedの中でパラメータを変更するのは問題がある.⇒ValueChangedの中で変更しているのではない.Inverse_ClickではBをある範囲で変化させながらテストしているのでこのような動作になることは不可避だ.

B=10,K=1でMatrixTestを実行して,ゼロ除算例外が発生した.障害はResidueFuncProで起きている.DispResidueCycle → MakeStripePatternだ.べきを小さくするためにK-1の剰余を取っていた.剰余を取る際にはゼロ割りに注意する必要がある.

cycleの出力がおかしい.#が0になっているためだろう.N=268435468,B=10, K=7で,n^7.この値はPowerResidueFuncの戻り値だ.⇒除数上限オーバーが起きていた.PowerResidueFuncの戻り値が負のとき,TextBox5~19までは****を表示しているが,cyclelen,dropnum,TextBox14は手当てされていない.

PowerResidueFuncは一つのセッションで二度呼ばれる.①剰余と②逆数は同じ関数で計算している.引数が異なるので,結果は同じにならない.剰余計算の場合はKが除数となるので,Nが巨大数でも問題なく計算できる.実際,正しい答えが出ている.⇒誤動作していると思ったのは,Kを見落としていたためだ.

一つかなり奇妙なことに気付いた.N=268435472,K=6のとき,#2でcycle=2,4,2になる.しかし,マトリックスを見ると,これは2の行だ.剰余R=4で行番号と一致しない.

image

マトリックスの最左列はNを示していると考えられるので,N mod K がRと一致しなくてはならないと考えられるのだが… 実際,別の数字で確認すると,

  • N=268435472 R=4 → 2,4,2,4
  • N=268435473 R=3 → 3,3,3,3
  • N=268435474 R=4 → 4,4,4,4
  • N=268435475 R=1 → 5,1,5,1
  • N=268435476 R=0 → 0,0,0,0
  • N=268435477 R=1 → 1,1,1,1
  • N=268435478 R=4 → 2,4,2,4
  • N=268435479 R=3 → 3,3,3,3
  • N=268435480 R=4 → 4,4,4,4
  • N=268435481 R=1 → 5,1,5,1
  • N=268435482 R=0 → 0,0,0,0

のようにすべての行が出揃っているのだが,微妙に一致しないところがある.剰余数列は6パターンあるが,剰余は0, 1, 4, 3, 4, 1, 0で1と4が2回重複出現している.これはおそらくべきが掛かっているためと思われるが,それがどのように作用しているのかはこれだけではまだ分からない.いまのテストの設定ではべき=2となっている.

べきが変化するとstripeが影響を受けるが,おそらくcycleの方にもなんらかの影響があるものと思われる.いずれにしても,この小さなマトリックスの中で起きていることなので,解析は可能だろう.これはもちろん,Kが素数であるか否かなどの要因もからんでいるものと推定されるが,整理できると思う.動作も安定してきたので,そろそろリリースの準備に入ってもよいのではないだろうか?

いつの間にか保存ファイル名がtotient.txtからnamechanged.txtに変わっている.VBのデザイナー画面では「べき剰余数列.txt」と入っているが,app.configにはtotient.txtと記録されているので,totient.txtというのがデフォルトファイル名だ.namechangedというのは,どこかの時点で設定したファイル名で,この値はTextBox16に入力→リターンキーで変更すると,My.Settings.filename = filenameに格納される.アプリ起動時にはMy.Settings.filename から取り出され,TextBox16に格納している.「namechange.txt」という文字列は現行のファイル上には存在していない… 確かに,前にそのような名前を設定したことはあるが,それがどこから出てくるのかはナゾだ.

リリース版とデバッグ版は別アプリということになっているようだ.それぞれが異なるファイル名を保持できる.

コメントを残す

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

CAPTCHA