問題タブ [number-theory]

私は計算したい：

a ^{b c d . . .} mod m

この数値は大きすぎますが、 a 、 b 、 c 、 ... および m は単純な 32 ビット int に収まるため、効率的な方法をご存知ですか。

何か案は？

警告:この質問は、 ^b mod mを見つけることとは異なります。

^{また、 a b cは (a b} ) ^cと同じではないことに注意してください。^{後者は a bc}と同じです。べき乗は右結合です。

Python で [[1,2],[3,4]] mod 7 のような行列のモジュラー逆を取りたいと思います。私はnumpy（行列の反転を行いますが、剰余行列の反転は行いません）を見て、いくつかの数論パッケージをオンラインで見ましたが、この比較的一般的な手順を実行しているようには見えません（少なくとも、私には比較的一般的です）。

ちなみに、上の行列の逆行列は [[5,1],[5,3]] (mod 7) です。私はPythonにそれをやってもらいたいと思っています。

このコードが数値の因数の合計を返すのはなぜですか?

いくつかの Project Euler の問題では、問題の一部として因数の合計を計算するよう求められます。そこのフォーラムの 1 つで、誰かが次の Java コードをその合計を見つける最善の方法として投稿しました。以下の私の要約にスキップできます）：

今、何度も試してみましたが、うまくいくことがわかりました。問題は、なぜですか？

因数100: とし1,2,4,5,10,20,25,50,100ます。合計は217です。素因数分解は2*2*5*5です。この関数はあなたに[5*(5+1)+1]*[2*(2+1)+1] = [25+5+1]*[4+2+1] = 217

ファクタリング8: 1,2,4,8. 合計は15です。素因数分解は2*2*2です。この関数はあなたに[2*(2*(2+1)+1)+1]=15

アルゴリズムは次のように要約されます (Fi因子 F または F sub i の i 番目のインデックスを意味するために使用):

ここで、mは一意の素因数の数、Niは素因数分解で各一意の要素が発生する回数です。

この式が因数の合計に等しいのはなぜですか? 私の推測では、分配特性を介して素因数のすべての一意の組み合わせ (つまり、すべての一意の要素) の合計に等しいと思いますが、その方法はわかりません。

これが問題です（4つの素数の合計）は次のように述べています：

入力には、すべての行に 1 つの整数 N (N<=10000000) が含まれます。これは、4 つの素数の合計として表現する必要がある数です。

サンプル入力:
24
36
46

サンプル出力:
3 11 3 7
3 7 13 13
11 11 17 7

この考えは一目で思い浮かびます

• N 以下のすべての素数を見つける
• 整数分割問題 (ナップサック) でリストの長さ (.length = 4) を見つける

しかし、複雑さはこのアルゴリズムにとって非常に悪いと思います。この問題は、よりゴールドバッハの予想にも似て います。どうすればこの問題を解決できますか?

それを取得する 1 つの方法は、自然数 (1,.., n ) をそれぞれ因数分解し、素因数が繰り返されているかどうかを確認することですが、n が大きい場合は時間がかかります。1,.., nから二乗のない数値を取得するより良い方法はありますか?

素数より小さい 2 つの整数のすべての組み合わせをチェックするために 2 つのループを使用できますpが、非常に非効率的です。この問題にアプローチするためのより良いアルゴリズムはありますか? 何か案が？

どこでp mod 4 = 1。

ありがとう、

非常に大きなランダムな数をどのように生成しますか？私は2^10 ^ 9（10億ビット）のオーダーを考えています。任意のプログラミング言語-ソリューションは他の言語に翻訳されると思います。

[1、N]に一様分布したいのですが。

私の最初の考え：

-各桁をランダムに生成して連結することができます。問題：非常に優れた疑似乱数ジェネレーターでさえ、数百万桁のパターンを開発する可能性がありますよね？

• ランダムな数値をランダムな指数に上げることで、大きなランダムな数値を作成するのに役立つ可能性があります。問題：結果の数値がまだランダムになるように数学を機能させる必要があり、妥当な時間（たとえば、1時間）で計算できるはずです。

• それが役立つ場合は、（たとえば実数を使用して）おそらくより狭い範囲でおそらく不均一な分布を生成して変換することを試みることができます。問題：これも同様に難しいかもしれません。

何か案は？

多くの試行錯誤を経て、次のPythonコード行を見つけました。

次の出力を生成します。

つまり、2 の累乗は2**(N-1)、1 まで、2 の累乗は逆になります。これはまさに私の問題（fftおよびウェーブレット関連）に必要なものです。しかし、なぜそれが機能するのかよくわかりませんか？私が理解している最後の剰余演算は、シリーズの真ん中にある 1 を提供します。最初の剰余演算の係数 3 が頭を悩ませています。誰でも説明できますか？具体的には、基数 2 と係数 3 の関係は?

私はオイラー問題78を解こうとしています。これは基本的に、分配関数p（n）が1000000で割り切れる最初の数を要求します。

私は五角数に基づくオイラーの再帰式を使用します（ここでpentsは適切な符号とともに計算されます）。これが私のコードです：

正しい結果が得られるようにps見えますが、遅すぎます。計算を高速化する方法はありますか、それとも完全に異なるアプローチが必要ですか？

私は群論のどん底に投げ込まれ、私が持っている暗号学のクラスに少し迷っています。基本的に私がJavaで実装しなければならない実用的なものは、

order(素数, p-1 の因数のリスト, 任意の a)

これは、グループ Z*p 内の a の順序を返す必要があります。ここで、f は p-1 の素因数のリストです。f に重複が含まれる場合にメソッドが機能することを確認します。たとえば、p=17 の場合を考えてみましょう

これが私がこれまでに持っているものです（メモ内の手順から取得）

素因数 f のリストは別のメソッドによって生成され、次に渡されます

私が持っているメモは理解するのが非常に難しく、実際に何を返すべきか教えてくれる人がいるかどうか疑問に思っていました. また、この群論のスニペットを理解できるように教えてください。それは私のさらなる実践に役立ちます。