問題タブ [modular-arithmetic]

-x が 2 進数の場合、x mod 3 を見つける方法は? 10 進数への変換を使用してから % 演算子を使用することはできません。

-例- x が 1101 の場合、出力は 1 になるはずですが、1101 を 13 に変換して % 3 で検索しないでください

素数を法とする方程式で作業するために、フロートでガウス消去法を実行する一連の線形方程式を解くJavaでコードを書き直そうとしています。問題は、それが機能しないことであり、何が問題なのかわかりません。方程式の小さなセットでは機能するようですが、大きなセットでは機能しないため、デバッグが困難になります。

私のアルゴリズムは最初の行を取り、最初の要素の逆数を見つけることでこれを正規化し、行のすべての要素にこの逆数を掛けます。次に、この行を他の行から十分な回数減算して、最初の要素をゼロにします。次の反復では、次の行に移動し、行 i のピボット要素が列 i になるまで同じ手順を実行します。最後に、前の行からすべての行を減算して、すべての列 (最後のものを除く) のゼロ以外の要素を 1 つだけ作成します。(今のところ、私は double を使用していますが、これは必要ありませんが、これは問題にはなりません)。これが私のコードです：

これは小さな例 (mod 29) で動作します:

どちらが正しいか (最初の変数 = 0、2 番目の変数 = 1.0、3 番目の変数 = 0)、WolframAlpha で 0*k^0 + 1*k^1 + 0*k^2 for k = 1..3 を確認できます。

この例では、10 個の変数と方程式 a*k^0 + b*k^1 + c*k^2... (mod 29) for k = 1..11 を使用すると、次の行列が得られます。

私のアルゴリズムを使用すると、答えが得られます。

しかし、これは間違っています！（WolframAlphaで確認できます）。正解は (abc ...) = (8 13 9 13 4 27 18 10 12 24 15) です。

誰かが私の間違いを見つけることができますか? または、Gauss mod p の実行方法を誤解していますか?

Enigma Coding Machine をプログラムしようとしています。ローターとリフレクターを正常に動作させることができましたが、ローターの前進を解決しようとしています.

これに精通していない人のために。Enigma Machine は、置換暗号である 3 つのローターと、13 組の文字を含むリフレクターで構成されます。文字をエンコードするには、最初のローターによって最初にエンコードされます。次に、エンコードされた文字が 2 番目のローターに渡され、さらにもう 1 つのローターを介してリフレクターに渡されます。リフレクターは、この新しい文字をペアになっている文字と交換します。このペアになった文字は、最終的にエンコードされた文字になるまで、ローターを介して逆方向にエンコードされます。

個々の文字がエンコードされる前に、ローターがシフトされます。非常に長いメッセージがある場合、何かがエンコードされる前に、最初のローターが 1 つシフトされ、この文字がシステムを通過してエンコードされます。次に、2 番目の文字がエンコードされる前に、最初のローターが再びシフトされます。ローターは、再びスタートに達するまで継続的にシフトされます。25 番目の文字がエンコードされた後、最初のローターは開始位置に到達しますが、2 番目のローターは 1 桁移動します。次に、最初のローターがさらに 26 回回転してから、2 番目のローターが再び回転します。2 番目のローターが 26 回回転すると、3 番目のローターが 1 回転します。これは、25 25 25 に達するまで発生し続け、その時点で 0 0 0 にリセットされ、サイクルが再び開始されます。これは時を刻む時計を思い起こさせます。

これはおそらく剰余演算でプログラムできることは知っていますが、方法がわかりませんか? そのため、どんな助けでも大歓迎です。

2 つの BigInteger の積を BigIntegers モジュラ素数に累乗したものを計算する必要があります。

私は計算しています - y^r * r^s (mod p)。

私が使用しているコードは機能しますが、不要な計算を実行していると感じずにはいられません。これは、大規模な BigInteger が関係している場合はかなりコストがかかります。

理想的には、v1 を一度に計算する方法が必要です。これは可能ですか？

バイナリデータを数値に格納できるかどうか、および可能な限り多くのバイナリデータを単一の数値に格納するにはどうすればよいか疑問に思っています。

たとえば、次のテキストを数値に格納するとします。

Lorem ipsum dolor sit amet, consectetur adipiscing elit. Donec egestas nunc eget rhoncus blandit.

バイナリ形式では、これは次のとおりです。

これを数値に変換すると、次のようになります。2.15146353486 * 10^16

これをバイナリに戻すのが問題です00000010。

明らかに、私はここで何をしているのかわからないので、これが「なぜこれがうまくいかないのか」ではないことを理解してください。質問、私が求めているのは、私がやりたいことは可能ですか？

バイナリは ASCII または BASE-64 に、またはその逆に変換できるため、数値への変換とその逆も同様に機能するはずです。結局のところ、Base64 は基本的に 64 ベースの数システムですが、10 進数は 10 ベースのシステムであり、2 進数は 2 ベースのシステムです。

アドバイスをいただければ幸いです。

Intel Westmere と AMD Bulldozer で導入された PCLMULQDQ 命令を使用して CRC32 を効率的に実装する方法に関する次の論文を読んでいます。

V.ゴパルら。「PCLMULQDQ 命令を使用した汎用多項式の高速 CRC 計算」。http://www.intel.com/content/dam/www/public/us/en/documents/white-papers/fast-crc-computation-generic-polynomials-pclmulqdq-paper.pdf _

アルゴリズムは理解できましたが、定数 $k_i$ の計算方法がわかりません。たとえば、IEEE 802.3 多項式の定数値を提供します。

• k1 = x^(4*128+64) mod P(x) = 0x8833794C
• k4 = x^128 mod P(x) = 0xE8A45605
• mu = x^64 div P(x) = 0x104D101DF

等々。1 つの多項式のみをサポートする必要があるため、これらの定数を使用できますが、興味があります。これらの数値はどのように計算されたのでしょうか? 算術演算は GF(2) で行わなければならないため、典型的な bignum の実装 (Python が提供する実装など) だけを使用することはできません。

私は、OpenCL で高速なバイナリ累乗の実装を設計しようとしています。私の現在の実装は、この本の pi に関するものと非常によく似ています。

改善の余地はありますか？現在、私のプログラムは大部分の時間をこの関数に費やしています。

こんにちは、コード sprint5 の問題で nCr MODm を実装する際に問題があります。問題へのリンクは…… https://www.hackerrank.com/contests/codesprint5/challenges/matrix-tracingです。私がまだ学んだことは、階乗計算と逆階乗計算、および pow(a,b) MODm の計算にモジュラー算術の規則を適用できることです。しかし、間違った答えにつながる何が欠けているのかわかりません。これが私の現在のコードです。

これは数学関連の質問でもありますが、C++ で実装したいと思います...そのため、フォーム2^nに数値があり、その桁の合計を計算する必要があります (基数 10;P )。私の考えは、次の式で計算することです。

すべての桁について: floor(n/floor(log2(10))).

第1項はべき乗剰余で簡単に計算できるのですが、それ以外は困っています。は大きいのでn、大きな整数ライブラリを使用したくないため、pow(2,n)モジュロなしでは計算できません。第 1 項のコード スニペット:

しかし、2番目にはわかりません。floor「0」（2/10）になるため、個別に指定することもできません。これを達成することは可能ですか？（http://www.mathblog.dk/project-euler-16/より簡単な解決策。）もちろん、この方法で実行できない場合は、他の方法を探します。（たとえば、リンクのコメントのように、数字をバイト配列に格納します）。

編集：既存の回答に感謝しますが、数学的に解決する方法を探しています。bignum や digit-vector なしで実装できる 1 つのアイデアを思いついたので、それが機能するかどうかをテストします。

したがって、合計については上記の式があります。しかし、どちらが2^n/10^kのように書くことができます。次に、小数部分とその整数部分を取り、整数部分で剰余累乗を行います。最後の反復の後、10 を法とする分数も掛けます。うまくいかない場合、または上記のアイデアのどこかが間違っている場合は、ベクトル ソリューションに固執し、答えを受け入れます。2^n/2^(log2 10^k)2^(n-k*log2 10)2^(n-k*log2 10) = 2^(floor(n-k*log2 10)) * 2^(fract(n-k*log2 10))

編集：わかりました、非整数​​モジュロで剰余べき乗を行うことはできないようです（？）（または私はそれについて何も見つけていません）。だから、私は数字/ベクトルベースのソリューションをやっています。

コードが完全に機能しません!

適切な値が得られません: (1366 ではなく 1390):