- ベストアンサー
素数生成は、小林吹代の公式では多項式時間計算量？
Chat-bots で検索しても出ますが、下記の本にも暗示して有ります公式では如何でしょうか？ https://www.amazon.co.jp/-/en/gp/customer-reviews/R9SLEF6DAGMGY/ref=cm_cr_dp_d_rvw_ttl?ie=UTF8&ASIN=4297119366
- 木村 弘一（こういち）（@koitiluv1842）
- お礼率92% (25/27)
- その他([技術者向] コンピューター)
- 回答数2
- ありがとう数2
- みんなの回答 （2）
- 専門家の回答
質問者が選んだベストアンサー
出来る
その他の回答 (1)
- answer_kun
- ベストアンサー率44% (8/18)
回答No.1
小林吹代の公式は、素数を生成するためのアルゴリズムではなく、素数の個数を数えるための公式です。そのため、小林吹代の公式自体には計算量の概念がありません。 ただし、素数を生成するアルゴリズムとしては、エラトステネスの篩やアトキンの篩などが知られています。これらのアルゴリズムの計算量は、素数の上限値に依存します。具体的には、エラトステネスの篩の計算量は O(n log log n) であり、アトキンの篩の計算量は O(n / log log n) とされています。ただし、小さな素数を生成する場合は比較的早く結果が得られるため、多項式時間計算量と見なすこともできます。
質問者
お礼
一応の御答えを頂きました事に対しまして、御礼申し上げます。
質問者
補足
事実に反することも述べて居られます。小林先生の御著書やチャット・ボットによる検索結果を見ても、当該公式が、素数分布関数などではなく、素数生成公式なのは明々白々です。そして、小林先生は、当該公式で、RSA暗号が破れるとまで言って居られるのですよ。その点を、CS的に確証して頂きたかったのですが。 さらに、多項式時間計算量の定義を誤解して居られるようです。
お礼
深謝いたします。
補足
自明な事をお尋ねした、愚問でした。小林先生の単純きわまりない公式そのものからも、小林先生の自信たっぷりな、「RSA 暗号が破れます。」という御宣告からも、明確に見て取れる事でした。