次のアルゴリズムは、数値が素数であるかどうかをチェックします。
Given a number n,loop over all numbers smaller than n and check whether they divide n.
If one of them divides n, answer no. Otherwise, answer yes.
ここで、次の2つの場合に、入力の長さの関数としてアルゴリズムによって実行される除算演算の数を分析する必要があります。
1）数値は単項でエンコードされます（つまり、4は1111です）。分割数が多項式であることをどのように示しますか？
2）数値は2進数でエンコードされます（つまり、4は100です）。分割数が指数関数的であることをどのように示すことができますか？
をn 1つなぎ合わせたとします（表記1^n）。 n明らかに、入力の長さです。11、、111...、からのすべての整数を。に分割1^(n-1)し1^nます。1^nの関数として、いくつの数に分割しnますか？これは多項式ですか？
をほぼ2進数で表すには、log_2(x)（の2を底とする対数x）ビットが必要であることに注意してください。また、分割xを実行することに注意してください（ 、、、、、 ...、はに分割されます）。したがって、ビットには除算を使用します。代わりに、入力のサイズとするとします。だから私たちは持っています。では、関数の観点から、いくつの分割を行うのでしょうか。x-22345x-1xlog_2(x)x-2nn = log_2(x)n
ヒント：
n問題のサイズを、数値の（2進数| 1進数）表現の桁数として定義します。
次に、数字でエンコードできるさまざまな数値の数を検討しnます。