利用者:Tsukitakemochi/sandbox

ここはTsukitakemochiさんの利用者サンドボックスです。編集を試したり下書きを置いておいたりするための場所であり、百科事典の記事ではありません。ただし、公開の場ですので、許諾されていない文章の転載はご遠慮ください。

登録利用者は自分用の利用者サンドボックスを作成できます（サンドボックスを作成する、解説）。

その他のサンドボックス: 共用サンドボックス | モジュールサンドボックス

記事がある程度できあがったら、編集方針を確認して、新規ページを作成しましょう。

「決定的アルゴリズム」について

入力: n > 1; 判定対象の奇数

出力: n が合成数なら composite、さもなくば prime を返す。

n-1

を 2 のべき乗で割って、

2^{s}\cdot d

の形式にする。

以下を

[2,\min(n-1,\lfloor 2(\ln n)^{2}\rfloor )]

の範囲の全ての a について繰り返す:

a^d mod n ≠ 1 かつ [0, s − 1] の範囲の全ての r について

a^{d\cdot 2^{r}}

mod n ≠ −1 なら、composite を返す。

prime を返す。

2024/12/18 時点で書かれている以上のアルゴリズムは、そもそも最初のｎ＝3 から、ˈcompositeˈ という間違った結果を出してしまうと共に、英語版のアルゴリズムとも相違している。より英語版に近い以下のアルゴリズムによれば、少なくともｎ＝100万までの数値ではエラトステネスの篩に一致する結果を得ることを検証できている。問題がなければ、次のものに置き換えさせて頂こうと思います。

入力: n > 1; 判定対象の奇数

出力: n が合成数なら composite、さもなくば prime を返す。

n-1

を 2 のべき乗で割って、

2^{s}\cdot d

の形式にする。

以下を所定の集合の全ての a について繰り返す:

x の初期値を a^d mod n とし、y の初期値を 0 とする。

以下をs回繰り返す:

y の値を

x^{2}

mod n とし、

(y=1 and x≠1 and x≠n-1) ならcompositeを返す。

x に y を代入する。

y≠1 ならcompositeを返す。

prime を返す。

a として設定する集合としては、 $[2,\min(n-1,\lfloor 2(\ln n)^{2}\rfloor )]$ の範囲の全ての整数である。ただし、判定対象の数 n が十分小さければ＜以下同じ＞

なお、具体的な C# のプログラムは以下の通り。

   List<int> alist1=new List<int>{2,3,7}, 
               alist2=new List<int>{2,3,5,7,11,13,17}; 
   bool knowcompositef(long n) {
       List<int> alist = new List<int>(); 
       if (n<4759123141) { 
           alist = alist1; 
       } else if (n<341550071728321) {
           alist = alist2; 
       } else {
           MessageBox.Show("n over the limit !!!"); }
       // long lnn = (long)(Math.Log(n)), amax=2*lnn*lnn; 
       // if (amax>n-1) {amax=n-1; } 
       bool jg=iscomposite(alist,n);  
           return jg;  
   } // ============================================== 
   bool iscomposite(List<int> alist, long n) {
       long d=n-1, s=0; 
       for (;;) { if (d%2==1) { break; }
           d/=2; s++; }
       foreach (int a in alist) { 
           long x=adn(a,d,n), y=0; 
           for (long r=0, dd=d; r<s; r++, dd*=2, x=y) {  
               y=(x*x)%n; // y=(a^(d*(2^r)))mod n
               // x == (long)Math.Pow(a,(d*Math.Pow(2,r)))%n;
               // y == (long)Math.Pow(a,(d*Math.Pow(2,r+1)))%n; 
               if (y == 1 && x != 1 && x != n-1) { 
                   return true; } } // composite  
           if (y != 1) { return true; } } // composite  
       return false; // === prime !!! 
   } // ============================================== 
   long adn(long aa,long d,long n) { // get a**d mod n 
       long tr=1;
       for ( ; d>0; ) {
           if (d%2==1) { tr *= aa;  tr%=n;  d-=1; } 
           aa*=aa;  aa%=n;  d /= 2; } 
       return tr; 
   } // ==============================================

一般的な定理

性質

フェルマーの小定理は、乱数を発生する用途に使われることがある。しかし、このような場合、あらゆる（p と互いに素な）a について、

b=a^{n}{\pmod {p}}

が、 $n=1..p-1$ に沿って

1\leq b<p

の全要素を順繰りに巡ることを保証しているわけではない点には注意すべきである。実際、次の各表では、 $n=p-1$ である右端の列が全てゼロになることは確かだが、それ以外にもゼロは出現している。

$p=3$ の場合：

		$n$
		$1$	$2$
$a$	$1$	$1$	$1$
$a$	$2$	$2$	$1$

$p=5$ の場合：

		$n$
		$1$	$2$	$3$	$4$
$a$	$1$	$1$	$1$	$1$	$1$
	$2$	$2$	$4$	$3$	$1$
	$3$	$3$	$4$	$2$	$1$
	$4$	$4$	$1$	$4$	$1$

$p=7$ の場合：

		$n$
		$1$	$2$	$3$	$4$	$5$	$6$
$a$	$1$	$1$	$1$	$1$	$1$	$1$	$1$
	$2$	$2$	$4$	$1$	$2$	$4$	$1$
	$3$	$3$	$2$	$6$	$4$	$5$	$1$
	$4$	$4$	$2$	$1$	$4$	$2$	$1$
	$5$	$5$	$4$	$6$	$2$	$3$	$1$
	$6$	$6$	$1$	$6$	$1$	$6$	$1$

三角形外心位置ベクトルの証明

「ページ」に置かれている式

U={\frac {a^{2}(b^{2}+c^{2}-a^{2})A+b^{2}(c^{2}+a^{2}-b^{2})B+c^{2}(a^{2}+b^{2}-c^{2})C}{a^{2}(b^{2}+c^{2}-a^{2})+b^{2}(c^{2}+a^{2}-b^{2})+c^{2}(a^{2}+b^{2}-c^{2})}}.

は、次のように証明できる。

ステップ１

ΔABC の外心を U とし、これと、各頂点とを線で結ぶと、小三角形が３つ現れる。ここに結んだ各線分の長さは U の性質上等しいはずであり、これを r とする。個々の小三角形は、二等辺三角形だが、これは二等角三角形でもあることを意味する。ΔUBC、ΔUCAのそれぞれにつき、内角の和は180°だから、

∠CUB=180°- (∠UBC + ∠BCU) = 180°- 2∠BCU

∠AUC = 180°- (∠UCA + ∠CAU) = 180°- 2∠UCA

一方、U の全周を分担する角に目をつけると、

∠BUA = 360°- (∠AUC + ∠CUB)

= 2 (∠BCU +∠UCA)

= 2 ∠BCA

ステップ２

r および a, b, c (頂点 A,B,C の各対辺) を用いると、各二等辺三角形の高さ（元の三角形の辺とUとの距離）はそれぞれ r cos∠CAB、 r cos∠ABC、 r cos∠BCA。面積 S_A, S_B, S_C は, それぞれ (a r cos∠CAB)/2、 (b r cos∠ABC)/2、 (c r cos∠BCA)/2。これらから、もともとの三角形の面積Sは、

S = r(a cos∠CAB + b cos∠ABC + c cos∠BCA)/2.

ステップ３

ΔABCと、ΔABUを、共通辺cを底辺と見て比較すると、三角形の面積の性質上、それはお互いの高さに比例するはずである。 Uを通り、辺ABに並行な線を引くと、これによってΔABCの斜辺 CA （長さは b）は両三角形の高さに比例する割合で分割され、図３に従えば、

m/b = S_C/S = c cos∠BCA/(a cos∠CAB + b cos∠ABC + c cos∠BCA). 　

次に、Uを通り、辺CAに平行な線を引き、ΔABCと、ΔABUを、共通辺 b を底辺と見て比較、ΔABCの斜辺 AB （長さは c）の分割を見ると、図に従えば、

n/c = S_B/S = b cos∠ABC/(a cos∠CAB + b cos∠ABC + c cos∠BCA).

左下に現れた平行四辺形を使うと、 U の位置ベクトルは、

U = A + (C-A)m/b + (B-A)n/c

= A + ((C-A)c cos∠BCA + (B-A)b cos∠ABC) /(a cos∠CAB + b cos∠ABC + c cos∠BCA)

= (A a cos∠CAB + B b cos∠ABC + C c cos∠BCA)/(a cos∠CAB + b cos∠ABC + c cos∠BCA).

ここで、

\cos \alpha ={\frac {b^{2}+c^{2}-a^{2}}{2bc}}

等の余弦定理をあてはめると、

U={\frac {a(b^{2}+c^{2}-a^{2})A/2bc+b(c^{2}+a^{2}-b^{2})B/2ca+c(a^{2}+b^{2}-c^{2})C/2ab}{a(b^{2}+c^{2}-a^{2})/2bc+b(c^{2}+a^{2}-b^{2})/2ca+c(a^{2}+b^{2}-c^{2})/2ab)}}

={\frac {a^{2}(b^{2}+c^{2}-a^{2})A+b^{2}(c^{2}+a^{2}-b^{2})B+c^{2}(a^{2}+b^{2}-c^{2})C}{a^{2}(b^{2}+c^{2}-a^{2})+b^{2}(c^{2}+a^{2}-b^{2})+c^{2}(a^{2}+b^{2}-c^{2}).}}