問題タブ [number-theory]

a = a31 a30 . . . a1 a0が 32 ビットのバイナリ ワードであるとします。次のアルゴリズムで計算された
32 ビットのバイナリ ワードを考えてみましょう。b = b31 b30 . . . b1 b0

1. a を右から左にスキャンしb、最初のビット1が見つかるまでそのビットを にコピーします (これも にコピーされbます) 。
2. その後、 のビットのブール否定をコピーしますa。

たとえば、a = 10100 . . . 00に変換されb = 01100 . . . 00ます。aおよびbが 2 進数として解釈される場合、このアルゴリズムが計算する内容を説明してください。

n現在、数値が素数かどうかをチェックするプログラムを MATLAB で作成しようとしています。手始めに、 Fermat Primality Testを実装しています。

フェルマーは、素数pとについて次のように述べてい1 <= b < pます。

したがって、MATLAB ではp = 17、およびb = 11

また

私が抱えている問題は、このインスタンスに対して MATLAB が を返すこと0です。ただし、p素数の場合は を返す必要があり1ます。何が欠けているのかわからないので、どんな助けも大歓迎です!

すべての乗法次数が F13 の乗法群 F の次数 (サイズ) を分割することを示す方法. .

サイクル リーダー反復アルゴリズムは、相対的な順序を維持しながら、すべての偶数番号のエントリを前に移動し、すべての奇数番号のエントリを後ろに移動することによって、配列をシャッフルするアルゴリズムです。たとえば、次の入力があるとします。

出力は次のようになります

このアルゴリズムは O(n) 時間で実行され、O(1) スペースのみを使用します。

^{このアルゴリズムの特殊な詳細の 1 つは、配列をサイズ 3 k} +1のブロックに分割することによって機能することです。どうやらこれはアルゴリズムが正しく機能するために重要なのですが、その理由はわかりません。

アルゴリズムで 3 ^k + 1 の選択が必要なのはなぜですか?

ありがとう！

、 、、の要因を見つける方法はp、RSA 暗号化アルゴリズムで知られています。検索してみましたが、ソースが見つかりませんでした。ヒント、参照、または解決策で十分です。qedn

(e,n)と(d,n)はそれぞれ公開鍵と秘密鍵であり、n = pq.

アセンブリを使用して PIC16 マイクロコントローラに RSA を実装しようとしています!
足し算、引き算、掛け算、べき乗剰余 (すべて符号なし) を実行できる数学ライブラリを作成しました。

しかし今、私は満たす "d" を見つける最後のステップで立ち往生しています:
d*e = 1 (mod phi(n))
少し複雑で符号付き操作が必要な拡張 Euclid アルゴリズムの実装を避けたいです。

オイラーの定理http://en.wikipedia.org/wiki/Modular_multiplicative_inverse#Using_Euler.27s_theorem
で計算してみ ましたが、 p と q が安全な素数でない限り、複雑なプロセスである phi(phi(n) を見つける必要があります。

私が残した唯一のオプションは、kを変更しながらd =（KN + 1）/ eをループして（KN + 1）mod e = 0にすることです。
したがって、私の質問は次のとおりです。この最後の式は、dを計算するための唯一の他のオプションですか?
（そうでない場合）他のオプションは何ですか？
K の極限は？

ご存知のように、モジュロ演算は、ある数値を別の数値で割った余りを求めます。

モジュロの値を取得する正しい方法を見つけるのに苦労しています。

a mod b = c

a >= 0 の場合は c を見つけるのは簡単ですが、a < 0 の場合は混乱します。

ある日、-75 mod 26 = 3 の場合の講義ノートを読みました。

次に、Java で単純なプログラムを作成して、-75 mod 26 の結果を見つけます。プログラムはコンパイルされ、result: -23 を出力します。

では、a < 0 の場合に c を見つける正しい方法は何でしょうか?

以下は私が試したコードです：