で符号化する際数が素数であるかどうかをチェックするバイナリ/単項

Question

数が素数であるかどうかをアルゴリズムのチェックを次の今

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. 

、Iは、関数のようなアルゴリズムによって実行される除算の数を分析しなければなりません

1）数値は単項式で符号化されます（つまり、4は1111です）。分割数が多項式であることをどのように示しますか？

2）数値は2進数で符号化されます（つまり、4は100です）。部門の数が指数関数的であることをどのように示しますか？

Answer 1

n が一緒につながっているとします（1^nと記されています）。 nは明らかに私たちの入力の長さです。 11、111、...、1^(n-1)の整数をすべて1^nに分割します。何個の数値を1^nに分けて、nの関数で表しますか？これは多項式ですか？

xを表すには、log_2(x)（ログベース2はx）ビットが約2進数であることに注意してください。また、x-2部門（2、3、4、5、...、x-1はxに分割されます）を実行する予定です。したがって、log_2(x)ビットの場合は、x-2ディビジョンを使用します。代わりに、nを入力のサイズとします。だから我々はn = log_2(x)を持っている。 nの機能の観点から、いくつの部門を取るのでしょうか？

Answer 2

ヒント：

（バイナリ|単項）の桁数であるとして、問題の大きさnの定義数の表現。

ここで、nの数字でいくつの異なる数字をエンコードできるかを考えてみましょう。