FreeBSDのswapファイルがうまく作成できなかったので調べてみた

FreeBSDにてswapファイルを作成する場合

/etc/rc.confに以下のような行を記述するという手法がググると多数ヒットしますがこの手法はobsoluteです。最新(現時点で14.0)のFreeBSDでは使えません。

swapfile="/swapfile"

いつから使えないかよくわかりませんが2013/6/27のコミットで単純にwarningを出すようになったと書いてますので相当前から使えなかったのではないかと思います。
そこで man fstabを参考に以下のような記述をfstabに追加しました。

md90 none swap sw,file=/swapfile 0 0

この状態で swapon -a をすると確かにswapが作成されます。しかし再起動をしてみるとswapinfoで見ても作成されていません。再起動した状態でswaponをしようとすると

swapon: md90 on /swap90: Device already in use 

のようなエラーが発生して止まってしまいます。この原因を調べたところエラーになる原因が判明しました。

上記のようにfstabを記述し起動をすると早い段階で /etc/rc.d/swapが実行されます。このときにmdが作成されるのですがこの時点では/swapfileはリードオンリーです。このためデバイスが作成されどもswapができなくなりエラーなっているようでした。これを解決するには

md90 none swap sw,file=/swapfile,late 0 0

とmount optionにlateをつけることで解決できます。lateをつけることにより後から遅れてこの部分の処理が /etc/rc.d/swaplateでされるからです。このときにはボリュームはRWでマウントされているでしょうから正常にswapをすることができるというわけです。
Posted by issei

カテゴリ: BSD

mod p^kにおける平方根

一つ前のエントリでは

\[
x^2 = a \pmod{p}
\]

の解がわかると

\[
x^2 = a \pmod{p^2}
\]

を解くことが出来たのでした。同じ考え方で任意の$p^k$について次のようにして求めることが出来ます。

\[
(x-\sqrt{a})^k
\]
を計算して
$\sqrt{a}$の係数が$\pmod{p^k}$で1になるように逆数を乗じればokです。

$\sqrt{a}$の係数が$p$で割り切れてしまうとまずいのでそのことだけ証明しないといけませんが、結論だけから言うとその係数は
$(2u)^{k-1}$に$\mod{p}$で等しくなります。つまり$u^2=a\pmod{p}$としたとき

\[
(u_{k}-v_{k}\sqrt{a})
=(u-\sqrt{a})^k
\]
とすると

\[
v_k=(2u)^{k-1}\pmod{p}
\]
となります。よって$v_k$は$p$と互いに素で、逆数が存在することになり解を求めることが出来ます。
Posted by issei

カテゴリ: 数学

mod p^2における平方根

\[
x^2 = a \pmod{p}
\]

の解がわかると

\[
x^2 = a \pmod{p^2}
\]

を解くことができます。その手順について解説します。

$x^2 = a \pmod{p}$の解があるということは

\[
x^2 - a = up
\]

なる$u$があるということです。左辺は次のように変形することができます。

\[
(x-\sqrt{a})(x+\sqrt{a})=up
\]

両辺を二乗すれば

\[
(x-\sqrt{a})^2(x+\sqrt{a})^2=u^2p^2
\]
これより

\[
 \begin{aligned}
((x^2+a)-2x\sqrt{a})((x^2+a)+2x\sqrt{a})=u^2p^2\\
\end{aligned}
\]

を得るので$2x$で各係数を割れば

 \[
\begin{aligned}
\left(\frac{x^2+a}{2x}-\sqrt{a}\right)
\left(\frac{x^2+a}{2x}+\sqrt{a}\right)=\frac{u^2p^2}{4x^2}\\
\end{aligned}
\]

となり$\frac{x^2+a}{2x}$が解になります。最後の$2x$で割るというところが微妙ですが、これはここから$p^2$での剰余を考えて演算をするということで解決できます。


\[
8^2-7=3\cdot 19\\
\]
が既知とします。

\[
\begin{aligned}
(8-\sqrt{7})(8+\sqrt{7})&=3\cdot 19\\
(71-16\sqrt{7})(71+16\sqrt{7})&=3^2\cdot 19^2\\

\end{aligned}
\]

ここで
\[
16 x = 1\ \pmod{19^2}
\]
なる数を探します。すると$158$であることがわかるので左辺の各項に乗じて$19^2$での剰余を求めると

\[
(27-\sqrt{7})(27+\sqrt{7})=0  \pmod{19^2}
\]
を得ることができます。

注)
$2x$が$p$と互いに素であることが重要です。$x$はあきらかに$p$と素ですが2を乗じているので$p$は奇素数でなければなりません。
Posted by issei

カテゴリ: 数学

mod Pにおける平方根 その3

8N+1の素数について、もう一つ別の考え方を解説します。多分Tonelli–Shanksのアルゴリズムと同じ考えに基づくものと思われます。

$p-1=2^s t$(ただし$t$は奇数)とおきます。すると任意の$x$に対して
\[
(x^t)^{2^s} = 1
\]
ですから$x^t$は1の$2^t$乗根です。

例えば97を考えると
\[
96 = 2^5\cdot 3
\]
ですから $x^3$は1の32乗根です。一般的に1の32乗根は32個あり、そのうち16個が32乗してはじめて1になる数です。ある数$\omega$が32乗して初めて1になる数とすれば
$\omega^3, \omega^5, \cdots, \omega^31$もまた32乗根してはじめて1になる数です。よって1つそのような数を見つければ他の数は自然と見つかることになります。

(余談ながらその逆数$\omega^{-1}, \omega^{-3},\cdots, \omega^{-31}$も然りです) 

$\omega$を32乗して初めて1になる数(例えば42)としてその数を2乗、4乗としてこれを木の形にしてみます。(下図参照)

51024png

空白になっているところにも$2$の冪乗根があるはずですがそれは何かわからないので空欄にしておきます。また平方根についてはaが平方根の1つなら-aもまた平方根ですので剰余を0から95ではなく-48から47までの間になるように書いています。木の葉のほうから辿れば

42 → 18 → 33 → 22 → -1

です。この中に$a^3$があれば答えは簡単です。例えば$a$が$47$とすれば、$a^3=33$ですから、1つ下の$18$を使って
\[
a^3 = 33 = 18^2
\]
これより両辺に$a$をかけて
\[
a^4 = 18^2a
\]
を得て
\[
(a^2 18^{-1})^2 = a
\]

が答えになります。$18$の逆数 ($18 x =1$なる数)が出てきますがこれは普通に求めてもいいし、そもそも$18^{16-1}=27$が逆数なのでそれを利用しても簡単に求まります。
答えとしては$-12$が得られます。実際$-12^2=47$です。

そうではない場合(例えば$11$)を探す場合は次のようにします。$11^3=-27$です。$-27$を冪冪で累乗していくと

\[
\begin{eqnarray}
(-27)^2 = -47\\
(-47)^2 = -22
\end{eqnarray}
\]
となり、ここで$-22$が出ます。$-22$はツリーのルートのすぐ右側にあるので、この数はツリーの右側にあることがわかります。ところで$\omega$ですが次のような性質を持っています。

  • $\omega^2$を乗ずると2段目のノードに対して左右に移動する
  • $\omega^4$を乗ずると3段目のノードに対して左右に移動する
  • $\cdots$
この性質を利用して$\omega^2(=18)$を42に乗じて(-20になる)そのノードを右側のツリーの同じ場所におきます。そしてそこからまた冪冪でルートに戻っていきます。
このルートの中に求めるノードがあればそれが答えです。残念ながら今回もみつからないので$\omega^4$を乗じます。そうすると-27が無事見つかりました。これから答えが求まります。


71024png


最後に32乗してはじめて1になる数の見つけかたですが、これは平方非剰余な数を3乗すれば求めるものになります。平方非剰余な数は全体の半数ですからランダムに選んで$(p-1)/2$乗して判定することができます。

この方法は運が悪いと沢山計算をする必要がありますが木の高さは $s$ですから最悪でも$s^2$くらいのオーダーの計算量になります。
一方葉は$2^s$のオーダでこれを全部計算するのはsが大きくなるととんでもない数になります。$s$が小さいときは非効率ですが大きくなるにつれて優位性が増すと思われます。
Posted by issei

カテゴリ: 数学

mod Pにおける平方根 その2

一つ前のエントリで8N+1型以外の素数についての平方根の計算方法を解説しました。8N+1については同じような考えで求めようとしてもなかなかうまくいきません。
\[
a^n = \pm a (ただしnは偶数)
\]
の形になかなか持ち込めないのがその要因です。今まで考えきた演算は$p$での剰余をもって演算するもので代数学的には$F_p$で演算と呼ばれるものです。$F_p$は$p$個の元からなる有限の集合で、その元同士に加減乗除が定義されているものです。この空間で演算をしている限りこの問題をクリアすのはどうも不可能なようです。そこで発想をちょっと変えて$F_p$ではなく$F_q$で考えることにします。$F_q$とは$F_p$の世界で既約な方程式の根を追加した体(加減乗除がうまく定義された集合)です。$F_p$は$p$個の元からなる体ですが、$F_q$は$q$個の元からなるので$F_q$と表現します。今回はちなみに$q=p^2$なので、$F_{p^2}$と記述するのが正確なのかもしれませんが、とりあえず$F_q$と表現しておきます。なんか難しいこと言ってますが発想としては簡単で$F_p$での平方根が存在しない数の平方根があると仮定してそれを追加したもの・・とゆるく考えておけばよいかと思います。

例えば有理数においても$2$の平方根は存在しませんが、仮にそれを$\sqrt{2}$と書くとすれば
\[
x+y\sqrt{2}
\]
という数の集合を考えることができてその集合に対して加減乗除が定義できます。例えば上記の数は二乗することが可能で二乗した結果は

\[
(x^2+2y^2 )+ (2xy)\sqrt{2}
\]

であってその結果もまた $x + y\sqrt{2}$の形に書けることがわかります。つまり$x+y\sqrt{2}$の形の集合を考えれば全ての加減乗除はその内部で閉じておりまた完結していることになります。

$F_q$もそれと同じ原理を用います。$F_p$から平方非剰余の数を$T$1つ選びその平方根があると仮定してそれを$\sqrt{T}$と表すことにし、この数を$F_p$に追加します。この集合に対して加減乗除が成立するためには
\[
x+y\sqrt{T}
\]と表すことができる数全て集めれば証明は割愛しますが十分で実際演算が閉じてうまく定義できることがわかります。xの選び方はp通りyの選び方はp通りですからこの体は$p^2$個の元からなることになります。この$q=p^2$とするとこの集合に対してもフェルマーの小定理が存在し

\[
x^q=x
\]

が成立することが知られています。つまり$F_q$では$q$乗すると元に戻ります。ところで$F_p$では

\[
x^p=x
\]

が成立しました。したがって$F_q$で任意の元を$p$乗すると、$F_p$に含まれる数はその位置を変えません(固定される)。しかし$F_p$に含まれない数はそうではなく、別な数に移動しますがその数は共役元になることが知られています。つまり
\[
(x+y\sqrt{T})^p = (x-y\sqrt{T})
\]
です。となれば$F_q$では任意の元を$p+1$乗すると

\[
(x+y\sqrt{T})^{p+1} = (x+y\sqrt{T})(x-y\sqrt{T}) = x^2 -y^2 T
\]

となりその数がなんであり$F_p$に属することになります。今

\[
x^2 -y^2 T=a
\]
となるようにうまく$x,y$を選ぶことができれば$p+1$は奇数ですから

\[
(x+y\sqrt{T})^\frac{p+1}{2}
\]

がその平方根になります。仮に$y$を1とすれば

\[
T= x^2 -a
\]

よってこの$T$が平方非剰余であるものを選んでその$\frac{p+1}{2}$乗を計算すればそれが答えになります。なお計算上は$x$と$y$だけが重要で$\sqrt{T}$が何ものであるかとは気にする必要がなく、$x, y$のペアでのみ演算をし$T$は二乗したら$T$となる数とゆるく考えておけば問題ありません。つまり単純に無理数の$\sqrt{T}$と考えても問題ないということになります。

例)
$p=41$とし$8$の平方根を考えます。$5^2-8=17$は非平方剰余です。よって$F_{1681}$で考えることにより
\[
(5+\sqrt{17})^{21}
\]
が答えになります。

実際計算をしてみると
\[
\begin{eqnarray}
(5+\sqrt{17})^2=(1+10\sqrt{17})\\
(5+\sqrt{17})^4=(20+20\sqrt{17})\\
(5+\sqrt{17})^8=(25+21\sqrt{17})\\
(5+\sqrt{17})^{16}=(4+25\sqrt{17})
\end{eqnarray}
\]
ですので
\[
(5+\sqrt{17})^{16}(5+\sqrt{17})^{4}(5+\sqrt{17})^{1} =34
\]

となります。

数が膨れあがらないのはその都度41で係数の剰余を取っているからです。また21回掛け合わせる必要はなく21は16+4+1ですから16乗、4乗、1乗したものを掛け合わせれば十分です。

余談)
$F_p$のような体を有限体(要素の数が有限なので)と言いますがその要素の数(位数とよぶ)は必ず$p$の冪であり、また$p$の冪の有限体は必ず存在することがわかっています。
Posted by issei

カテゴリ: 数学