SMT solver 入門 - suer のブログ
SAT solver が周りでほのかに流行っている(いた?)ので，個人的には SAT solver よりも断然便利な SMT solver について書いてみようと思いたった． SMT って? SMT は Satisfiable Modulo Theories の略で，SAT だと命題変数を並べて CNF で記述しなければいけないところを，int とか，プログラムで使うような変数が扱える上，述語が使える． なので一般に記述量が減り，人間に(SAT問題よりは)読みやすくなる傾向にあると思う． SMT Solver SMT Solver については http://combination.cs.uiowa.edu/smtlib/ でいろいろ見つかるけれど，ここでは The Yices SMT Solver を使ってみる． 環境準備 Mac OS X Leopard Yices 4.2.2 例題 S
暗号の危殆化に関する調査：IPA 独立行政法人 情報処理推進機構
電子政府、電子商取引において暗号は基盤技術として利用されている。しかし、計算機の進歩等の研究開発の進展により、いくつかの暗号については近い将来に危殆化するものと予想されている。暗号が危殆化すると、電子署名の証拠性に疑義が発生し、電子政府における公文書、電子商取引における契約等の信頼性が揺らぐと考えられる。 このような暗号の危殆化問題について、システム上の影響や技術的・制度的対策、法律上の問題に関する検討は未だ殆どなされていない。そのため、暗号が危殆化した際には、社会的な混乱が予想される。 そこで、本調査では主として電子政府において使用される暗号が危殆化した際の影響、法律上の問題について分析を行い、技術的・制度的対策に関する検討の結果を示した。 1. 暗号技術を取り巻く状況 2. 暗号危殆化の定義 2.1. 暗号危殆化の定義 2.2. 暗号危殆化の要因 2.3. 暗号危殆化の進行過程 3.
インターネット10分講座：暗号アルゴリズムの危殆化 - JPNIC
実は、一般数体ふるい法の計算量は、以下のような漸近的な評価が与えられているのでおおよその推定は可能ですが、正確な計算量の予測にはあまり適していません。 ただし、 そこで、関係式収集ステップの計算量を部分的な実験結果から推定する方法を用いて、CRYPTREC※1では素因数分解問題に関する評価結果を2006年度に公表しています※2。 図1：1年間で関係式収集ステップを完了するのに要求されるコンピュータの処理性能予測（［3］からの引用） この評価結果から、分解にかけるコストに依存するものの、1024ビットのRSAモジュラスの素因数分解はおおよそ2015年.2020年頃から分解の可能性が高まってくるということが読み取れます。従って、今後、新規にシステムを構築する場合には、1024ビットよりも長いサイズのRSAモジュラスを選択することが望ましいものと考えられます。 移行に際してまずはじめに問題となる
特異値分解入門(1) - NtRand
An Excel Add-In Random Number Generator Powered By Mersenne Twister Algorithm ENGLISH RSS 特異値分解入門(1) May 20, 2010 互いに相関を持った正規乱数のセット（多変量正規乱数）を生成すること、これが金融工学のモンテカルロシミュレーションにおいて最も重要な技術となります。 系列の正規乱数列を生成する場合を考えます。 これらの乱数列の相関構造を記述するのが相関行列と呼ばれる の正方行列 です。 最終的に という形に分解することが目標となります（ここで t は転置行列です）。分解して得られた行列 を使って実際に相関乱数を生成する方法については、これも一般的な数値計算の教科書に載っていますのでそちらをご覧ください。 すぐ後で説明するように、この分解にはコレスキー分解を使えと、多くの教科書で教えて
Corecursion - Wikipedia
This article is written like a personal reflection, personal essay, or argumentative essay that states a Wikipedia editor's personal feelings or presents an original argument about a topic. Please help improve it by rewriting it in an encyclopedic style. (February 2020) (Learn how and when to remove this template message) In computer science, corecursion is a type of operation that is dual to recu
なぜ Haskell ではキューが軽んじられているか？ - あどけない話
Haskell ではキューが欲しくなったら Data.Sequence を使えと言われる。Seq は両端キューだし、シーケンスとして使えば、連結(><)や分割(splitAt)が、ならし計算量で O(log N) という優れものである。しかし、内部がfinger treeなのでコードが複雑なのと、計算量が「ならし」なところが玉に傷である。 もっと単純で、最悪計算量を保証する(両端でない)キューが標準で提供されてもいい気がする。その候補には、リアルタイムキューがある。どうして標準でキューが提供されないのだろう？ 僕なりの答えは「需要がない」だ。 問題を解くときにスタックはよく使うが、キューが必要な問題はそんなに思いつかない。僕はネットワーク屋なので、もちろんルータにはキューが必要なことは知っているが、それ以外で有名どころと言えば幅優先探索ぐらいだ。 幅優先探索 でも、Haskellではキュー
Software Rasterization Algorithms for filling triangles
I. Introduction This article discusses various algorithms how to draw a solid triangle. This task is a basic requirement of a graphic engine and is often also called 'Triangle Rasterization/Rasterisation'. Three different approaches are presented which are implemented in the applet above. Note that also the scanline algorithm can be used, but it is designed for the general case of filling a polygo
Optimizing Software Occlusion Culling – index
In January of 2013, some nice folks at Intel released a Software Occlusion Culling demo with full source code. I spent about two weekends playing around with the code, and after realizing that it made a great example for various things I’d been meaning to write about for a long time, started churning out blog posts about it for the next few weeks. This is the resulting series. Here’s the list of p
高速な算術圧縮を実現する「Range Coder」
はじめに 本記事では、全体のサイズが最小となる算術圧縮を高速に実現するRange Coder（以下RC）を紹介します。 算術圧縮は、各文字の出現確率が分かっている場合にそのデータを最小長で表現可能な符号法です。各文字に固定の符号を割り当てるHuffman法とは違い、符号化を状態更新とみなし、すべての文字を符号し終わった後の状態を保存することで符号化を実現します。これにより1文字単位の符号長を1bitより細かく調整することが可能となります。 算術符号は圧縮率が高い反面、ビット単位の演算処理が大量に発生するため、符号化、復号化ともにHuffman符号に比べ遅いという問題点があります。今回紹介するRCは、算術符号の処理をバイト単位で行うことで高速な処理を可能にします。 また、算術圧縮については概要から説明します。 対象読者 C++の利用者を対象としています。データ圧縮の基礎を知っていることが望ま
静かな注目を集める圧縮アルゴリズム「LZMA」
GNUプロジェクトの配布アーカイブなどを中心に、LZMAを用いた圧縮形式を目にする機会が増えてきた。組み込み用途などへの活用も期待されるこの圧縮形式を紹介しよう。 2001年に開発された可逆圧縮アルゴリズム「LZMA」（Lempel-Ziv-Markov chain-Algorithm）が静かな注目を集めている。LZMAといえば、高い圧縮率を備え、Windowsアーカイバ「7-Zip」に採用されていることでも知られる。 ZIPやLHAなど、ファイルのアーカイブと圧縮が統合されているWindows由来のプログラムとは異なり、UNIXやLinuxでは伝統的にアーカイブと圧縮が個々のコマンドとして用意されており、それらを組み合わせて利用することになる。現在では、アーカイブがtar、圧縮にはGNU zip（.gz）やbzip2（.bz2）が併用されることが多い。 .gzや.bz2をしのぐ圧縮率が特
第4回 #DSIRNLP で Active Learning 入門について話しました - 木曜不足
@overlast さん主宰の データ構造と情報検索と言語処理勉強会(DSIRNLP) の第4回にのこのこ参加して、Active Learning 入門なるものを発表してきました。お疲れ様でした＆ありがとうございました＞各位 こちらが発表資料。 Active Learning 入門 from Shuyo Nakatani 入門とか偉そうに歌ったけど勉強し始めてまだ1月半もないので、実は入門しているのは中谷本人である。 動機は資料にも書いたとおり、ドメイン適応をドメイン知識のある人が低コストで行うのに Active Learning の技術が使えるのでは、というあたり。 ここまで実験した範囲でそれなりの手応えはあるものの、非常に単純なテキスト分類問題で試しただけなので、もう少し難しくて現実的なタスクでもいろいろ試してみたいと思っている。 発表資料に間に合わなくて20数回の試行で Query-
SipHashとAdvanced Hash Flooding
https://twitter.com/a4lg/status/279543990972461056 http://crypto.junod.info/2012/12/13/hash-dos-and-btrfs/ あたり経由でカーネルのBtrfs実装に関するHashDoSの話。を経由して SipHash https://www.131002.net/siphash/ について流し読みした。何故暗号論的ハッシュが必要か指摘していたのでめも。 SipHashは、HashDoS耐性のある高速ハッシュアルゴリズムとして使える暗号論的擬似乱数生成器。 高速性は主に、 ・128bitの生成鍵（salt相当）からコストの大きな拡張関数を使わずそのまま初期状態を作れる。 ・ブロックは64bit単位と小さく、状態空間は64bitx4 ・ルックアップテーブルを使わない あたりで実現されていて、 一方で暗号論的
Hash-flooding DoS と SipHash - あどけない話
以前、僕が実装している web サーバ Mighty が、Haskell で書いているにも関わらず、セグメンテーションフォールトを起こしていた。調べたところ hashable ライブラリがリンクする C の DJBX33X が、SipHash に変わったことが原因だった。このときから SipHash が気になっていたし、以前社内で説明した "Efficient Denial of Service Attacks" との関係も知りたかったので、少し調べてみた。この記事は、その覚え書き。 Hash-flooding DoS の歴史 1998 年に Alexander Peslyak 氏が Phrack Magazine で、Hash-flooding DoS を受けたことを報告している。ハッシュは、N 個の要素を挿入するのに通常 O(N) かかるが、ハッシュ値がすべて衝突する最悪の場合では O
逆FizzBuzz問題 (Inverse FizzBuzz) - 平々毎々（アーカイブ）
just another scala quantを日本語にしました。 ちなみに、私の解はこちらに。 最初の解答 はてブに書いた解答方針、Inverse Fizzbuzz (FizzBuzzの逆関数) - Qiita - 与えられた範囲内のすべての解を数え上げてます。 もっと簡潔な解答 逆FizzBuzz問題 解きなおし - Qiita それでは、問題の日本語訳をどうぞ。 逆Fizzbuzz問題 2012年ではなく、2016年のお話。 世の中は大して変わっていない。 OOPと書き換え可能なオブジェクトによって何度もひどい目にあった後、世界はやっとのことでJohn Hughesの考察が正しかったことに気づき、関数型プログラミングに移行した。GoogleはTypesafe社を買収し、ScalaがAndroid上でネイティブに動作するようになっている。Googleに負けず劣らず、AppleはHas
どんなデータでも(※)線形分離可能にしてしまう技術，Vanishing Component Analysis(ICML 2013)を紹介してきました - a lonely miner
急に蒸し暑くなってきましたね．でぶちんなのでけっこうこたえます．タイトルはちょっと釣り気味．ビビっと来た方は是非論文に目を通してみてください:) 例によって，仲間内でやっている小さな勉強会で論文紹介をしてきましたので，そのご紹介です．ぼくの専門というか興味の中心は自然言語処理なので，ふだんはそっち方面を追っているのですが，勉強会では機械学習方面を中心にいろいろ読んでみてます． 今回は岡野原さんのこのツイートで興味を持った以下の論文を読ませていただきました．名前もかっこいい．ヴァニッシングコンポーネントアナリシス！ ICML2013のbestpaper。データ中の集合（例えば画像中の8の字など）が0になるような生成多項式を求める（=集合のコンパクトな表現）効率的なアルゴリズムを提案し教師有学習時の特徴生成などに使える。すごい http://t.co/DedSoyLaJR — 岡野原 大輔 (
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
ウェーブレット木の世界 - Preferred Networks Research & Development
https://www.hugi.scene.org/online/coding/hugi%2017%20-%20cotriang.htm
integer sqrt and hypot
大規模画像認識とその周辺
418 I'm a teapot: しばらくみないうちにライフゲームもすごいことになってるんだな