問題タブ [deterministic]

C++/C では、2 つの浮動小数点数または倍精度数を絶対的に等しいかどうか比較できないことを知っています。なんらかの理由で、絶対等価を使用する if 条件を記述した場合、if 条件が同じデータに対してプログラムの異なる実行で同じ結果を返すことが保証されますか? それとも純粋に非決定論的であり、結果は異なる可能性がありますか?

上限は 2^n であり、これらが両方とも有限のマシンであることを考えると、n 状態 NFA と 2^n 以下の状態を持つ DFA の両方の交差が有効になるため、そう考えています。

私はここで間違っていますか？

反復によって解決できる解決策がある問題がありますが、正規表現とsplit()

本質的にコンマで区切られた文字列（Excelがクリップボードに入れている）があります。セル値にコンマが含まれている場合、セル全体が引用符で囲まれていることに注意してください (おそらく、その文字列内のコンマをエスケープするため)。文字列の例は次のとおりです。

さて、この文字列を個々のセルにエレガントに分割したいのですが、値にコンマを含むセルを分割するため、コンマを区切り文字として使用する通常の分割式を使用できないという問題があります。この問題のもう 1 つの見方は、コンマの前に偶数個の引用符がある場合にのみ、コンマで分割できるということです。

これはループで解決するのは簡単ですが、このロジックをキャプチャできる正規表現.split関数があるかどうか疑問に思っています。この問題を解決するために、ロジック用の決定論的有限オートマトン (DFA) を構築しました。

問題は次のようになります: DFA で最終状態 (ここでは状態 4) に到達するたびに新しい配列要素 (/s に対応) が生成されるように、この文字列を分割する方法はありますか?

Web サイトで n 個の分割テストを実行しています。均等に分散された整数のユーザー ID を n 個のバケットの 1 つに割り当て、決定論的に同じユーザーが常に同じテストを受けるようにしたいと考えています。

この時点で、ユーザー ID を n で変更することにより、分割テストのリストからインデックスを選択できます。特定のテストに重みを付けたい場合はどうすればよいですか?

たとえば、バケット #1/21 は 90% の確率で割り当てられ、残りの 20 個のテストは 0.5% の確率で割り当てられます。

どういうわけかリストのサイズを拡大し、これを達成するために mod テクニックを使用できるように感じますが、潜在的に巨大な一時的なリストをメモリに保持するのはエレガントではないようです。

誰かがプログラムの決定論的なバグの例を教えてもらえますか?

ありがとう。

私は QueryPerformanceCounter を使用して、アプリケーションでタイミングを計っています。ただし、数日間実行した後、アプリケーションが正しく機能しなくなったようです。アプリケーションを再起動するだけで、再び機能し始めます。これにより、タイミング コードにオーバーフローの問題があると思われます。

私の質問は、上記のコードが数週間連続して実行されている間、決定論的に機能するかどうかです。

そうでない場合、問題はどこにありますか？オーバーフローはによって処理されたと思いました

しかし、それでは十分ではないでしょうか？

編集: 元のコードは私が書いたのではなく、Ryan M. Geiss が書いたものであることに注意してください。コードの元のソースへのリンクはコード内にあります。

演算子DETERMINISTICの右側で関数を使用すると、Oracle の実行計画が大混乱を引き起こします。LIKEこれは私の状況です：

状況

次のようなクエリを実行するのが賢明だと思いました（簡略化）：

?そして、私はのようなものにバインドします'Eder%'。現在customers、addresses非常に大きなテーブルです。そのため、インデックスを使用することが重要です。もちろん、通常のインデックスがありaddresses.cust_idます。しかし、関数ベースのインデックスも作成しましたspecial_char_filter(customers.surname)。これは非常にうまく機能します。

トラブル

問題は、like句を含む上記のクエリが FULL TABLE SCANS on で実行プランを作成することaddressesです。このクエリの何かが、Oracle が でインデックスを使用できないようにしているようですaddresses.cust_id。

回避策

私の問題の解決策は次のとおりであることがわかりました。

DETERMINISTIClike 演算子の右側から( !) 関数を削除し、バインド変数を Java で事前に計算しました。現在、このクエリは超高速で、FULL TABLE SCANS はありません。これも非常に高速です (同等ではありませんが)。

混乱

私はこれを理解していません。like演算子の右側に決定論的関数があることの何が問題になっていますか? 私はこれをOracle 11.2.0.1.0で観察しました

これはこのサイトでの私の最初の質問であり、RSAの基本的な数学的理解しかありませんので、ご容赦ください。:)

私は大学での最終年度のプロジェクトのためにJavaWebアプリケーションを書いています。これは、聞いたことがある人のための安全な投票システムである「Pret-a-voter」のWebベースの実装です。

基本的に私の問題は、監査人の役割を果たす誰かを与えたいということです。

• ソースバイト配列（暗号化されるプレーンテキスト）
• RSA公開鍵ファイル
• 「宛先」バイト配列。これは、平文と公開鍵を指定して暗号データ​​を自分で計算した結果です。

次に、監査人が最初の2つの項目を使用して暗号化を実行できるようにし、3番目の項目が結果であることに満足してもらいたいと思います。したがって、暗号化を決定論的にする必要があります。つまり、同じ平文と公開鍵を使用した暗号化が繰り返されるたびに同じ暗号化データを生成する必要があります。

（注-このプロジェクトでは非常に小さなデータブロックを使用しています-対称暗号化はまったく含まれていません...これがRSAの「興味深い」使用法であることを認識しています！）

とにかく私はJavaでそれを見つけました

デフォルトのランダムパディングスキームを使用しますが、コストは11バイトです（したがって、2048ビットのキーペアを使用すると、2048 / 8-11 = 245バイトを暗号化できます）。同じ平文の暗号化を繰り返すと、異なる暗号文が生成されますが、これは明らかに私が望むECBモードではありません。

私の質問は-私は以下を使うべきですか？

多くの場所で、RSAはパディングなしでは安全ではないことを読みました。それは、攻撃者が平文/暗号文の辞書を作成できるからですか？これは、監査人が私の暗号化を検証できるようにするために必要な確定的暗号化の副作用であり、私のスキームでは監査人は信頼されているので、それで問題ありません。

私の質問のパート2は、よりJava関連です。上記のようにRSA/ECB / NoPaddingを使用する場合、（たとえば）長さ128のソースバイト配列（1024ビットRSAキーペアの場合）を提供し、それを暗号化して長さの別のバイト配列を取得できると思います128.次に、別の1024の長さの公開鍵を使用してそれを再度暗号化しようとすると、次のようになります。

javax.crypto.BadPaddingException：メッセージがモジュラスより大きい

誰かが理由を知っていますか？

編集-NoPaddingを使用した暗号化は、常にこの例外を生成するとは限りません-それは一時的なものです。ただし、暗号化によってこの例外が生成されない場合でも、復号化によって次の例外が生成されます。

javax.crypto.BadPaddingException：データはゼロで始まる必要があります

これを読んでくれてありがとう！どんな助けでも大歓迎です。

編集-申し訳ありませんが、私の元の質問は、私が何をしたいのかについてあまり明確ではなかったので、ここに[試み]の説明があります：

• 平文は選挙における有権者の投票です。
• Pret-a-voterは、投票者の機密保持などを犠牲にすることなく、エンドツーエンドで検証できるようにすることを目的としています。投票後、投票者には、投票が正しく記録されたことを確認するために使用できる領収書が提供されます。この領収書には、後で投票が改ざんされていないことが示されます。投票者は、領収書の情報をWebに投稿された同一のコピーと比較します。
• ただし、投票者がどのように投票したかを証明することはできません（強制につながる可能性があるため）。そのため、情報は平文ではなく、投票の暗号化されたコピーになります。
• 実際、平文は4回暗号化され、4つの異なる非対称キーが2つの異なるテラーによって保持され、それぞれが2つのキーを保持します。したがって、投票（平文）が公開鍵＃1を使用して暗号化する1人のテラーに提供され、次にその暗号文を2番目の公開鍵で暗号化し、その暗号文を2番目のテラーに提供します。仕方。結果の暗号文（4つの連続した暗号化の結果）は、Webに投稿されたものです（公開されます）。テラーは信頼されています。
• 暗号化された各投票は、中心が投票であり、暗号化のいくつかの層がある「タマネギ」として視覚化できます。投票するには、各レイヤーを順番に削除する必要があります。つまり、対応する秘密鍵（テラーが保持している）を逆の順序で適用する必要があります。これはセキュリティの鍵です。投票を復号化するには、すべての出納係が協力して作業する必要があります。
• Web掲示板は、5つの列を持つテーブルとして視覚化できます。最初の（左側）は完全に暗号化された投票（各投票者の領収書にも表示されます）を保持し、投票の段階で表示される唯一の列です。2番目の列には同じ投票のセットが含まれていますが、外層が削除されています。出納係2は、集計段階で秘密鍵を使用して投票を復号化することにより、この列と列3にデータを入力します。集計段階の最後に、列5には、集計できる完全に復号化された投票が含まれます。
• 各投票者は、列1の暗号化された投票にリンクする領収書を受け取ります。これは投票方法を示していませんが、選挙プロセス全体を通じて暗号化された投票を確認できるため、投票が改ざんされていないことを確認できます。 1列目にはそのまま残っています。もちろん、これは「エンドツーエンド検証」の半分にすぎません。投票者は、復号化が正しく行われたことを検証できないためです。つまり、投票から暗号化の外層を差し引いた列2にエントリがあります。 。各有権者は、列1のポイントまでの検証にのみ責任があります。
• その後、1列目のエントリが2列目に復号化されることを確認するのは監査人の責任です。これを行う方法は、確定的暗号化と、暗号化に使用される公開鍵が公開されていることに依存することです。
• 公開鍵は公開されているため、5列目から1列目まで単純に線を引いて、暗号化が繰り返されるときに誰かの投票に参加することは望ましくありません。つまり、暗号化された投票にあなたを結び付ける領収書は、実際にはあなたを暗号化されていない、読みやすい投票->強制！したがって、列1、3、および5のみが公開され（これが各テラーが2つの暗号化を実行する理由です）、列3の各エントリについて、{2,4}の対応するエントリの1つのみが監査人に公開されます。これにより、誰もが（監査人でさえ）暗号化された投票を暗号化されていない投票にリンクすることができなくなります。
• したがって、監査人は列3のエントリを取得し、列2の対応するエントリと公開鍵を与えられ、同じ暗号化を実行して、列2のエントリを実際に取得することを確認する必要があります。
• まとめると、これはエンドツーエンドの検証可能性を提供します。

申し訳ありませんが、それは非常に長かったです-決定論的な暗号化の必要性を説明していることを願っています。私は多くの基本的な詳細を見逃しました（私はこのスキームを大幅に変更しました）が、うまくいけば、コア原則がすべてそこにあります。読んでくれてありがとう-本当に感謝しています。

n体問題を計算するJavaプログラムがあります。反復ごとに、各ボディが他のすべてのボディに及ぼす力をチェックし、力に従ってそれらを動かします。

ボディは常に同じ場所から始まり (ボディ 0 からボディ n まで円形に配置されています)、常に同じ順序 (ボディ 0 から n) で検査および移動されます。ただし、プログラムを 30 回実行すると、実行時間が大幅に異なります。1 つの実行時間は 2,947,188 ミリ秒 (49 分) で、別の実行時間は 920,967 ミリ秒 (15 分) です。私はたくさんの体に総当たり法 (O(n^2)) を使用しているので、これらの時間の大きさに驚かされません。しかし、なぜ決定論的アルゴリズムにこのような差異があるのか​​ 疑問に思っていますか? それが何度も同じアルゴリズムである場合、実行時間は同じ（または少なくとも近い）べきではありませんか？

あなたが尋ねる前に、はい、私は実測時間ではなく、計算を行うスレッドの時間を測定しています。

編集- 私はこのように時間を測定しています:

これは計算ステップ以外の何かを測定しますか?

2 番目の編集- 次のように時間を測定するように変更しました。

ただし、結果はまだ再現できません。また、フラグ -Xint を使用してプログラムを実行しようとしましたが、結果はまだ再現できませんでした。

問題がアルゴリズムとマルチスレッド内にあると想定しても安全ですか? それとも、まだ Java に関連する問題でしょうか?

私は現在、C++ および C# で記述された (レガシー) プログラムに取り組んでいます。いくつかの重い計算を実行しますが、完全に決定論的である必要があります。つまり、同じ入力でも同じ出力が得られます... 問題は、(同じコンピューター上で、同じコンパイル済み実行可能ファイルを使用して) 2 回実行すると、わずかに異なる出力が生成されることです。

アプリケーションは、SQL サーバー データベースに対して読み取りと書き込みを行います (DB への一意のアクセス権があるため、DB の値に干渉するものは他にありません)。

実行間の唯一の明らかな違いは、それぞれに一意の名前 (単なる文字列変数) が割り当てられていることです。

コード内にランダムなオブジェクトはなく、すべてのループは、事前に決められた反復回数、または条件が満たされるまで実行され、一定時間実行されません。少量のマルチスレッドがあります。これはスレッドセーフであると確信していますが、自分で確認します。

この逸脱した動作の原因となる、私が探すべき明らかなものは他にありますか?