コンピュータプログラムのアルゴリズムに関する注意事項

コンピュータープログラミングとは何ですか?

簡単に言えば、コンピュータに何をすべきかを指示します。コンピューターは多くのことを実行できますが、自分で考えることはあまり得意ではありません。プログラマーは、子供に食事を与えるなどの具体的な詳細をコンピューターに伝え、コンピューターに言語アルゴリズムを理解させる必要があります。

アルゴリズムとは、問題解決の解決策の正確かつ完全な記述を指します。アルゴリズムは、問題を解決するための戦略的なメカニズムを記述するための体系的な方法を表します。つまり、ある仕様の入力に対して、限られた時間内で必要な出力を得ることが可能です。アルゴリズムに欠陥があるか、問題に対して不適切な場合、そのアルゴリズムを実行しても問題は解決されません。アルゴリズムが異なると、同じタスクを完了するために使用する時間、空間、効率が異なる場合があります。アルゴリズムの品質は、空間の複雑さと時間の複雑さによって測定できます。
アルゴリズムの命令は、実行時に初期状態と（おそらく空の）初期入力から開始し、限定的で明確に定義された一連の状態を経て、最後に出力を生成して最終段階で停止する計算を記述します。州。 。ある状態から別の状態への遷移は、必ずしも決定的であるとは限りません。ランダム化アルゴリズムを含む一部のアルゴリズムには、ランダムな入力が含まれます。
形式的アルゴリズムの概念は、部分的にはヒルベルトの決定問題を解決しようとする試みから生まれ、その後の効率的な計算可能性や効率的な方法を定義する試みの中で具体化されました。これらの試みには、それぞれ 1930 年、1934 年、1935 年にクルト・ゲーデル、ジャック・ヘルブランド、スティーブン・コール・クレーンによって提案された再帰関数、1936 年にアロンゾ・チャーチによって提案されたラムダ計算、1936 年にエミール・レオン・ポストのフォーミュレーション 1、そして 1936 年にアラン・チューリングのチューリング・マシンが含まれていました。 1937年。現在でも、直感的なアイデアを正式なアルゴリズムとして定義するのが難しい場合がよくあります。

特徴

アルゴリズムには次の5つの重要な特性が必要です:
1.有限性
アルゴリズムの有限性とは、アルゴリズムが限られた数のステップを実行した後に終了できなければならないことを意味します
2.正確性(明確性)
。アルゴリズムの各ステップには正確な定義が必要です;
3. 入力 (Input)
アルゴリズムには、操作オブジェクトの初期状況を記述するために 0 個以上の入力があります。いわゆる 0 入力は、アルゴリズム自体の定義を指します。 . 初期条件は外れています;
4. 出力
アルゴリズムには、入力データの処理結果を反映する 1 つ以上の出力があります。出力のないアルゴリズムは意味がありません。 5. 実現可能性 (有効性) アルゴリズムで実行されるすべての計算ステップは、基本的な実行可能な操作ステップに分解できます。つまり、各計算ステップは限られた時間内で実行できます。 内部完了 (有効性とも呼ばれます)。

要素

1. データオブジェクトの操作と操作: コンピュータが実行できる基本的な操作が命令の形式で説明されています。コンピュータ システムが実行できるすべての命令のセットが、コンピュータ システムの命令システムになります。コンピュータの基本的な計算と操作は次のとおりです。 1. 算術演算: 加算、減算、乗算、除算など。 2. 論理演算: OR、AND、NOT などの演算。 3. 関係演算: 大なり、より小さい、等しい、および等しくない 4. データ送信: 入力、出力、代入およびその他の操作 [1] 2. アルゴリズム制御構造: アルゴリズムの機能構造は、選択された操作に依存するだけでなく、操作間の実行順序に関係します。

分類

アルゴリズムは、基本アルゴリズム、データ構造アルゴリズム、数論および代数アルゴリズム、計算幾何アルゴリズム、グラフ理論アルゴリズム、動的計画法および数値解析、暗号化アルゴリズム、並べ替えアルゴリズム、検索アルゴリズム、およびランダム化アルゴリズムに大別できます。 、並列アルゴリズム、エルミート変形モデル、ランダム フォレスト アルゴリズム。
アルゴリズムは大きく 3 つのカテゴリに分類できます。
1. 限定的で決定的なアルゴリズム このタイプのアルゴリズムは、限られた時間内に終了します。指定されたタスクの実行には長い時間がかかる場合がありますが、それでも一定の時間内に終了します。このようなアルゴリズムの結果は、多くの場合、入力値に依存します。
2.有限非決定的アルゴリズム このタイプのアルゴリズムは限られた時間で終了します。ただし、特定の値 (または複数の値) について、アルゴリズムの結果は一意ではなく、確実ではありません。

３つの無限アルゴリズムとは、終了定義条件が定義されていない、または入力データが定義された条件を満たせないために終了しないアルゴリズムのことです。多くの場合、終了条件の定義に失敗すると、無限アルゴリズムが発生します。

基本的な整数論の予備

二次剰余

まず、式 x2≡n(modp) を見てみましょう。n を与えて、x の値を求めます。それが見つかる場合、n は mod p の二次剰余であり、実際には mod p の意味での n の究極の 2 乗です。 Cipolla は、上記の方程式で x を見つけるために使用されるアルゴリズムです。

ルジャンドル記号

ルジャンドル記号は、数値が p の二次剰余であるかどうかを判断するための強力なツールです。p は奇数の素数でなければなりません。 (n,p) は、n が p に関するルジャンドル記号であることを意味します。実際には、n が p の二次剰余であるかどうかを判断することです。

(np)=⎧⎩⎨1——p は n の倍数ではありません、n は p の 2 次剰余です −1——p は n の倍数ではありません、n は p の 2 次非剰余です (二次剰余または非剰余) 0——p は n の倍数です

それは多くのナンセンスのように思えますが、ルジャンドルは巨人の肩の上に立つことでそれを要約しただけです。
実際、ルジャンドル関数もいくつかの性質をまとめていますが、一般的にはオイラー基準のみが使用されており、ルジャンドル記号が積関数である場合に役立つ可能性があります。
しかし、n が p の二次剰余であるかどうかを判断する方法はまだわかりません。以下のオイラーの基準を見てみましょう

ll Legendre(ll a, ll p)
{

} 12341234

オイラーの基準

まず、オイラーの定理をおさらいしましょう xφ(p)≡1(modp)
ここでの p は奇数の素数なので、xp−1≡1(modp)
xp−1 に対して平方根演算を実行します。虚数体、xp−12≡±1(modp) が 1 であれば平方根は必ず解けますが、-1 であれば絶対に解けません。したがって、x が n の二次剰余であるかどうかには、このオイラー基準が使用されます。

if(qsm(n,(p-1)/2)==p-1){ printf("No rootn");
継続
}12341234

-1 は mod の意味で p- です。 1ページ目。

アルゴリズムの流れ

nとpが与えられたとき
pに対するnのルジャンドル記号が1だとしても、nの平方根はどうやって求めるのでしょうか？
今こそ心を開く時です。

数値 a を見つけます

数値 a をランダムに選択し、そのルジャンドル記号が -1 になるまで a2−n に対して平方根演算を実行します (つまり、そのルジャンドル記号の値を計算します)。解決しました）これまでのところ）。
(a2−n)p−12=−1を満たすaを見つけることです
理由は気にしないでください、それについては後で話します、私たちは今、静かにシポラを崇拝します。

while(1){
a=rand()%p;
w=(a*a-n+p)%p; if(qsm(w,(p-1)/2)==p-1 )break;
}1234512345

ランダムで探しているので、探すのに時間がかかりますか？
答え: いいえ!
∙定理 1: x2≡n(modp) には p−12 n があるので、方程式には解が存在します
⇒定理 1: x2≡n(modp) を証明します。異なる数 u、v がある場合、それらを次の式に持ち込んでください。 x 最後に、方程式を解くことができ、u2−v2|p が満たされることは明らかです。つまり、(u+v)(u−v)|p が満たされます。なぜなら、
u2−v2|p であるため、p は a であることはできません。 (u-v) の倍数、つまり (u+v)|p である場合、p に存在するそのような数値ペアの数は p−12 です
定理 1 によると、a がランダムに見つかる期待値は 2 です。

複数フィールドを作成します

作成すると言われていますが、実際にはプログラムする必要は全くありません。理解の便宜上、複数フィールドとしています。
一般的に学習する複素数体には、i2=−1を満たすiが存在します。
同様の領域も作成します。a2−n の平方根を取る必要があり、a2−n には p ではない二次剰余があるため、ω=a2−n−−−−−√ と定義します。次に、ω も i と同様に ω2=a2−n を満たすので、新しい領域を定義します。

struct CN{
ll x,y;
CN フレンド演算子 *(CN x,CN y){
CN z;
z.x=(x.x*y.x%p+x.y*y.y%p*w%p)%p ;
z.y=(x.x*y.y%p+x.y*y.x%p)%p; z を返します。 z を見つけることができます。この領域の表現は、通常の複素数に似ています: a+bω

答えを求めてください

必要なものは、x2≡n(modp)、つまりxの値です

aとωがわかったので、次のことを得ることができます答えは、です。

答え = (a+ω)p+12

本当ですか?本物！しかし、この答えは実数と虚数で構成されているのではありませんか?

ラグランジュの定理によれば、虚数の係数は 0 でなければならないと結論付けることができます。

(CN CQSM (CN X, LL Y) {\ 紫色の高速パワー CN Z; z.x = 1, z.y = 0; \ while (y) {if (y & 1) z*x;

x の初期化に注意してください= x* x;
y/=2;
} return z;
}123456789123456789
w=(a*a-n+p)%p;
u.x=a,u.y=1;//なぜ u.y は 1— —複素数の場合 統計では統計係数を使用するだけです
u=Cqsm(u,(p+1)/2);
ll yi=u.x,er=p-u.x; if(yi>er)swap(yi,er) ; if(yi==er){ printf("%lldn",yi);
} else{ printf("%lld %lldn",yi,er);
}12345678910111234567891011

なぜ答えが 2 つあるのでしょうか?たとえば、4√=±2、x2≡(p−x)2(modp) は明らかです。x2≡x2−2px+p2(modp) が分解され、すべての p が削除されるため、x2≡(p−x ) となります。 2(modp)。

原理を証明

し、簡単に説明するためにいくつかの定理を考え出します。

定理

∙定理2: (a+b)p≡ap+bp(modp)

⇒定理2を証明する: 二項定理によると:
(a+b)p≡∑pi=0Cipap−ibi(modp) )
≡∑pi=0p!(p−i)!i!ap−ibi(modp)
i=0 または i=p の場合にのみ、式に p の因数がないことがわかります。は途中の p の因数なので省略できるので (a+b)p≡ap+bp(modp)
∙定理 3: ωp≡−ω(modp)
⇒定理 3: ωp
=ωp−1 を証明∗ω
=(ω2) p−12∗ω
=(a2−n)p−12∗ω—— ω2=a2−n なので
=−ω—— (a2−n)p−12= を満たすから−1
∙定理 4: ap ≡a(modp)
⇒ 定理 3: ap を証明する フェルマーの小定理によると
≡ap−1≡1(modp)
したがって ap≡a*ap−1≡a(modp)

導出

問題: x2≡ n(modp) は x を解きます

Cipolla: x≡(a+ω)p+12(modp) の実数
式を直接変換します:
(a+ω)p+12 (modp)
≡((a+ω )p+1)12(modp)
≡((a+ω)p(a+ω))12(modp)
≡((ap+ωp)(a+ω ))12(modp) 定理 2 による
≡((a−ω)(a+ω))12(modp) 定理 3 および定理 4 による
≡(a2−ω2)12(modp) 定理 3 による定理 4
≡(a2−(a2−n) )12(modp) は ω2=a2−n
≡n12(modp) を満たします
したがって (a+ω)p+12≡n12≡n√(modp)
これ想像力が豊かすぎる！ ！ ！ ！ ！ ！ ！ ！ ！ ！ ！ ！ ！ ！

以上がコンピュータプログラムのアルゴリズムに関する注意事項の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。