問題タブ [number-theory]

コンピューター アーキテクチャに関するビデオを見ていたら、ある疑問が頭に浮かびました。足し算と基本演算はコンピュータ上でどのように機能しますか? つまり、2+2 = 4 であることはわかっていますが、その理由はわかりません。2つのリンゴを別の2つに追加すると4つになることを知っていますが、これの可能なデモンストレーションはありますか?

私の質問は、コンピューターが最も基本的なレベルで 2 + 2 = 4 であることをどのように認識しているのかということです。数値を加算する関数があることは知っていますが、基本的なレベルでは、その加算はどのように実行されますか?

コンピューターが実行する最も基本的で使用される操作は合計であるため、コンピューターがどのように機能するかをよりよく理解するためにこれを知りたいだけです（私は信じています）

N 個の自然数の集合 1,2,3,4...N があるとします。各数値の前に + または - 記号を挿入し、結果の数値をすべて足すことができます。得られた最小の負でない値は、D(N) として示されます。

D(1)+D(2)+...+D(19216812112) の値を求める

問題は、S の要素の二乗和が与えられた数 n に等しくなるように、正の整数の最大の集合 S を見つけることです。

例えば：

4 = 2²
20 = 4² + 2²
38 = 5² + 3² + 2²
300 = 11² + 8² + 7² + 6² + 4² + 3² + 2² + 1²。

時間内に実行されるアルゴリズムがありますが、O(2^(sqrt n) * n)遅すぎます (正方形のすべてのサブセット)。

素数を法とする大きな階乗を含む問題を解決しようとしていたところ、別のソリューションで次のアルゴリズムが見つかりました。

数論の基礎は知っていますが、これがどのように機能するのか理解できないようです。

nChooseK 関数は、[n!/(nk)!k!] の組み合わせの定義を、フェルマーの小定理を使用して計算された剰余逆数と組み合わせて除算を置き換えているようです。ただし、回答の 1 つによると、factMod 関数は実際には階乗を計算しません。この場合、nChooseK 関数はどのように機能しますか?

フィボナッチ数列の n 番目の数を教えてくれる関数があります。問題は、フィボナッチ数列でより大きな数を見つけようとすると非常に遅くなることです。これを修正する方法を知っている人はいますか?

結果、

5分経っても値を取得できませんrtfib(100)

PS: オクターブ 3.8.1 を使用しています

素因数への整数の因数分解について読み、Pollard の rho アルゴリズムの概念実装の証明を行いました。

https://en.wikipedia.org/wiki/Pollard%27s_rho_algorithm

このアルゴリズムは実装が簡単で、これまでのところ機能しています。ただし、特定の数値では失敗する場合があります (実際に失敗します)。ウィキペディアのページでは、別の開始条件を使用してアルゴリズムを再起動するか、ランダム ジェネレーター関数を選択することを提案しています。

それは私にはあまり決定論的に聞こえません。アルゴリズムが最終的に終了することを保証するアプローチはありますか?

楕円曲線の整数因数分解が最新技術であることは知っています。あとで笑わせるためにそれを実装する予定です。そのためには、最初に小さな数の素因数分解アルゴリズムが必要です。そのため、最初にポラーズ ロー アルゴリズムのようなものを処理する必要があります。

、、およびの3Nビットの数値があります。私は簡単に計算することはできませんが、とは簡単に計算できます。モジュロ演算が符号なしで、ビットをラップしないことが事前にわかっている場合は、代わりに を計算できます。ただし、モジュロ演算が署名されている場合、または加算がラップアラウンドにつながる可能性がある場合は、何かを行うことは可能ですか。ABC(A + B) % CA % CB % CA + BN((A % C) + (B % C)) % CAB

((A % C) + (B % C)) % C常に機能することに依存できない理由について、混乱があるようです。署名されていない例を次に示します。

署名された例を次に示します。

私は練習のために前年の試験問題を解いていましたが、私が認識していない数論関係がなければ解けない/疑う/解けない問題に出くわしました。

問題は：

N 個の整数の配列を指定して、前のすべての整数の約数である最小の整数を見つけます。

問題は、モジュロ演算の結果をキャッシュできない場合、複雑さが O(n^2) になり、時間制限と潜在的な問題があるため、問題の自動テストに合格するのに十分な速度で実行されないことです。 300 万要素のサイズ。

d | a1、d | a2、d | a3, ..., d | ？そうでない場合、問題へのアプローチについて他に何か提案はありますか?

どんな助けでも大歓迎です！

Javaで岡本内山暗号を実装しています。アルゴリズムはこちら

公開鍵の場合、パラメータhの値は次のように計算されます。

どこ、

gは素数pの原始根(340 ビット)

g、h、およびnにBigInteger 型を使用しました。コードを実行すると、終了しません。これがコードです。hの計算方法を教えてください。

私はしばらくこの問題を試していますが、何度も間違った答えを得ています。数が非常に大きくなる可能性があります <=2^2014. 22086. プライムパワーテスト

私のアルゴリズムについての説明:

1. 与えられた数値について、その数値を素数べき乗の形式で表現できるかどうかを確認しています。
2. したがって、素数べき乗をチェックする最大制限は log n base 2 です。
3. i最後に、問題は数値の n乗根log (n base 2)を見つけることになり、それが素数の場合は答えが得られますexit。
4. 私はあらゆる種類の最適化を使用し、膨大なテストケースをテストしましたが、すべてのアルゴリズムで正しい答えが得られました
5. しかし、ジャッジは間違った答えを言います。
6. Spoj には、小さな制約 n<=10^18 に関する別の同様の問題があり、Python と C++ (C++ で最高のソルバー) で既に受け入れられています。

これが私のpythonコードです。何か間違ったことをしている場合は、私に提案してください。私はPythonにあまり精通していないので、私のアルゴリズムは少し長いです。前もって感謝します。

私のアルゴリズム: