Re:ゼロから始める長期署名 - Qiita
はじめに 長期署名（先進電子署名）と言えば今から10～15年程前に最初のブームがありましたがベンダーの期待に反してあまり注目されたと言うイメージがありません。ところが新型コロナの影響だと思いますが最近具体的に長期署名を使いたいと言うご相談を多く受けるようになりました。しかし長期署名について今更説明している最近の書籍や情報が無く、また10年経つと電子署名業界での見方も微妙にアップデートされていて色々分からないとのこと…と言うことで… 「ここから始めましょう。イチから…いいえゼロから！」 by レム え～と私ですが一応ISO等で長期署名関連仕様の標準化にも携わりつつ、自社製品として長期署名ライブラリの開発もしているプログラマです。では始めましょう。 目次 はじめに 1. 長期署名とは 1-1. 電子証明書の有効期限 1-2. 暗号アルゴリズムの危殆化 1-3. 長期だけじゃ無い先進電子署名 1
コーディングインタビューの対策とその意義 (1/2) - 16bitのメモランダム
１．コーディングインタビューとは何か コーディングインタビュー（Coding Interview、またはProgramming Interview）とは、1時間ほどの制限時間内に小さなプログラミング問題を解かせる面接形式のことをいう。プログラマー、またはデータサイエンティストなどの採用試験として、米国を含むいくつかの国で用いられている。「物理的なホワイトボード上にプログラムを書く」という形式で実施されることが多い。「オンライン上の共有エディタで書く」といった形式のこともある。Googleなどは自社のYoutubeチャンネル動画でも説明している。 出題される問題としては、例えば、「複数の数字numbersと整数kが与えられたとき、合計がkとなる数字の組を1つ出力せよ」といったものがある。この問題は有名なので通称が付いており、Two Sumと呼ばれる。 Two Sumの一例。与えられた数値の並
hashアルゴリズムとハッシュ値の長さ一覧
「ハッシュ値の衝突」（コリジョン）や「データの改ざん防止」など、複数のハッシュ・アルゴリムを組み合わせるために、ハッシュ値の「長さ」と「速度の目安」一覧が欲しい。 ... ってか、ハッシュって、そんなにおいしいの？圧縮された暗号とちゃうん？ TL; DR （今北産業） この記事はハッシュ関数の出力結果を桁数ごとに、まとめたものです。 ハッシュ関数の各々の「アルゴリズムが最大何文字・・の 16 進数で返してくるか」の事前確認に利用ください。 マスター、一番強いヤツをくれ。 バランス優先 👉 sha3-512（64 Byte, 128桁, 2020/12/22 現在） OS やプログラム言語間の互換性・強度・速度で、一番バランスが取れているハッシュ・アルゴリズム。使いやすさなら、SHA3-256。 互換性？ここでいう互換性とは「どの言語でも標準・・で大抵は実装しているアルゴリズム」のことです
CS50 for Japanese: コンピュータサイエンスの入門 – 当ウェブサイトは、Creative Commons ライセンスに基づいて管理されています。
お知らせ: 2022/9/1 CS50 を活用した非営利／協賛企業による「コロナ学生支援」プロジェクトを実施中 ▼ 学生の方へ：CS50 の学習（履修証明書の取得）を一緒に取り組むプロジェクト CS50日本語版の翻訳コントリビューターである CODEGYM が主催する、非営利／無償のプロジェクト「CODEGYM Academy (外部リンク)」は、昨年に続き2022年度（春/秋）も、キャリア選択を控えた学生に対し、以下の企業の協賛により無償で17週間のプログラミング教育カリキュラムを提供します。 CODEGYM Academy 協賛企業（2022年） https://codegym.jp/academy/ 今年度のエントリーは締め切りました — ようこそ！ このページは、ハーバード大学 CS50 の日本語版翻訳プロジェクトのページです。当サイトのドメインに掲載されているコンテンツは、Cre
FFT（高速フーリエ変換）を完全に理解する話 - Qiita
となります。 この $C_i$ を、$0\leq i\leq 2N$ を満たすすべての $i$ について求めるのが今回の目標です。 それぞれ愚直に求めると、$f,g$ の全項を組み合わせて参照することになるので、 $O(N^2)$ です。これをどうにかして高速化します。 多項式補間 愚直な乗算は難しそうなので、$C_i$ の値を、多項式補間を用いて算出することを考えます。 多項式補間とは、多項式の変数に実際にいくつかの値を代入し、多項式を計算した値から、多項式の係数を決定する手法です。 たとえば、$f(x)=ax+b$ という $1$ 次関数があるとします。 $a$ と $b$ の値は分かりませんが、$f(3)=5,f(7)=-3$ がわかっているものとします。 実際に $3,7$ を代入してみると、 $3a+b=5$ $7a+b=-3$ と、連立方程式が立ち、$a,b$ の値が求められま
最短経路問題総特集！！！～BFSから拡張ダイクストラまで～ - Qiita
基本的アルゴリズム（幅優先探索など）から応用（経路復元、拡張ダイクストラなど）まで、最短経路問題に関するアルゴリズムを総特集しました。 基本的なグラフ理論の用語については、次を参考にしてください。 グラフ理論 用語集 queueなどのデータ構造の用語については、次のスライドの後半を参考にしてください。 C++ STL講習会 by @e869120 最短経路問題とは 一般的に、次のような問題とされます。 $V$ 頂点と $E$ 辺からなるグラフが与えられる。頂点 $u$ と 頂点 $v$ を結ぶパスのうち、重みの総和が最も小さいものはどれか。 始点を固定して他のすべての頂点との対について最短経路問題を解く場合や、任意の2頂点の対について解く場合などが実際には多いです。 実社会とも強く密着した問題のため、古くからたくさん効率的な解法が考えられてきました。 今回はそれらを紹介しつつ、細かいテクニ
XGBoostのお気持ちをちょっとだけ理解するためのメモ - Qiita
現在、Kaggleにてよく使われる手法の一つにGBDT(Gradient Boosting Decision Tree)があります。さらにその種類の１つXGBoostはKagglerによりその効果を検証され非常に人気の高いアルゴリズム・実装です。このブログでは、XGBoostの論文からアルゴリズムを理解するための主要な部分、 TREE BOOSTING IN A NUTSHELL 2.1 Regularized Learning Objective 2.2 Gradient Tree Boosting を丁寧に解説することを目的に書いています。 また、ここで解説した理論、アルゴリズムについてはLightGBMにおいてもほぼ同じと思いますので、合わせて参考になるかと思います。 おことわり しかしながら、最初におことわりをさせていただくのですが、markdownやtexでキレイにまとめる余裕が
差分検出アルゴリズム三種盛り - Object.create(null)
こんばんは. 気がつけばもうずいぶんと涼しくなってきました. 勢い余って凍ってしまったりせぬよう, くれぐれも普段の言動にはお気をつけください. はじめに さて, 我々人類にはどうしても二つの文字列 (あるいは行ごとに区切られたテキスト) 間の差分を求めなければいけない瞬間が発生します. 先人たちはそういった時のために diff のようなツールを開発し, それを利用することで文明はめざましい発展を遂げてきました. しかしながら, 使用するアルゴリズムを比較検討したい場合, 「差分」の定義を変えるなどして既存のアルゴリズムに変更を加えたい場合, diff のない異世界に飛ばされて自分で実装しなければいけない時などにおいては, 差分検出アルゴリズムについての理解が必要不可欠です. というわけで, この記事では文字列間の差分検出とは何かということと, 差分を求める三種類のアルゴリズムの紹介・解説
Google、TCPのスループットとレイテンシを改善する輻輳制御アルゴリズム「TCP BBR」をGoogle Cloudで利用開始
Google、TCPのスループットとレイテンシを改善する輻輳制御アルゴリズム「TCP BBR」をGoogle Cloudで利用開始 Googleは、同社が開発したTCPの輻輳制御アルゴリズム「TCP BBR」をGoogle Cloud Platformで利用可能にしたと発表しました。 インターネットにおける通信にはTCPを用いる場合とUDPを用いる場合に分かれますが、BBRはTCPにおける輻輳制御アルゴリズムを改善したもの。すでにGoogleはTCP BBRをYouTubeのネットワークで利用しており、従来のパケットロスをベースにした輻輳制御アルゴリズムであるCUBICを用いた場合と比較して、スループットが平均で4％、最大で14％以上改善したことを明らかにしています。 TCP BBRは現在の高速なネットワークに適した輻輳制御アルゴリズム TCP BBRのBBRは「Bottleneck Ba
興味深いデータ構造：BK木 | POSTD
BK木とは、 距離空間 内のデータをインデックス化する目的に特化した、木構造を指します。距離空間は基本的に、要素の組 $ (a,b) $ 全てについて距離関数 $ d(a,b) $ を持つオブジェクトの集合です。この距離関数は正しく動作することを保証するために、一連の公理を満たしていなければなりません。これが必要になる理由は、後述の「検索」のセクションできちんと説明します。 BK木のデータ構造は、一連のキーを検索し、与えられた検索キーの値に最も近いキーを見つける問題の解決策として、 1973年にBurkhardとKellerが提案したもの です。この問題を解決する素朴な方法は、要素の組に含まれる各要素と検索キーの値を単純に比較することです。一定の時間内に比較が完了した場合、この検索の解は $ O(n) $ となります。一方、BK木を採用すると、この時実行する比較の回数を減らせる可能性が高く
父「40割る5は？」九九を知らない息子「5＋5が10、4＋4が8だから答えは8」→子供の高度なアルゴリズムが面白い
ロボ太 @kaityo256 まだ九九を知らない息子に割り算を出題しているのだが、その解法が面白い。 「16わる2は？」 「えっと、6が2つで12でしょ。あと4たりなくて、4を2でわると2でしょ。だから6に2足して、こたえは8」 「お前すごいな」 2017-04-21 20:25:45
素因数分解アルゴリズム(特にSQUFOF)のこと - 再帰の反復blog
主要な素因数分解アルゴリズム SQUFOFについて 目次 主要な素因数分解アルゴリズム 素因数の性質に依存するアルゴリズム(ρ法、p-1法、楕円曲線法) 素因数の性質に依存しないアルゴリズム(SQUFOF、二次ふるい法、一般数体ふるい法) SQUFOFについて 連分数をもちいた素因数分解 シャンクスの改良 アルゴリズムの説明 例 アルゴリズムの改良 Schemeによるプログラム例 主要な素因数分解アルゴリズム ここでいう素因数分解アルゴリズムは完全に素因数分解をするアルゴリズムではなく因数(約数)をひとつ見つけ出すアルゴリズムなので、完全な分解が必要なら再帰的に実行したり試し割り法と組み合わせる必要がある。 素因数の性質に依存するアルゴリズム(ρ法、p-1法、楕円曲線法) 都合のよい性質を持った素因数を含んでいる場合に成功するアルゴリズム。都合のよい素因数を含んでいる場合は、汎用のアルゴリ
累乗計算の高速化 - へなちょここーだー
HackerRankのAntiPalindromic Stringsを解くときにどうしても累乗計算がO(n)になってしまいタイムアウトになってしまっていたところ、凄くキレイで高速なアルゴリズムを発見！ 高速な累乗計算 - あどけない話 これを使ってみました。 単純なxのn乗をmを法として求めるアルゴリズム long myPow(long x, long n, long m){ long result = 1; for(int i = 0; i < n; i++){ result *= x; result = result % m; } return result; } 改善後のアルゴリズム ここから、累乗計算の方法を改良していきましょう。その例として、を計算してみます。 1. まずは19を2進法であらわす。 2. これを利用して累乗を計算する。 3. これを計算できる漸化式を考える。 4.
ソートアルゴリズム高速化への道 - kivantium活動日記
先日、アルゴリズムの授業でソートのアルゴリズムをいくつか習いました。ソートアルゴリズムの名前と原理くらいは聞いたことがありましたが、実装したことはなかったのでいい機会だと思い実装してみることにしてみました。ただ実装するだけでは面白くないので高速化の限界に挑戦してみたいと思います。 計測用プログラム 今回の計測では、ランダム値が入った配列のソートを100回行い、平均時間を各アルゴリズムに競わせるというシンプルなルールにしました。プログラムは以下の通りです。 C++11で入ったメルセンヌ・ツイスタなどの機能を使っているので、ビルド時には-std=c++11を指定する必要があります。 実験に使用したパソコンのCPUはCore i3-3227U@1.90GHz、コンパイラはgcc version 4.8.4で最適化オプションには-O3を指定しました。 #include <iostream> #in
ハクビシンにもわかる全文検索 - Qiita
高速な全文検索アルゴリズムであるFM-indexについて解説する。理解しがたい点や間違っている点があれば是非コメントで指摘してほしい。 概要 FM-indexはリニアな文字列に対して検索をするアルゴリズムで、主に簡潔データ構造とBWT(およびLF mapping)という二つのアイデアから成り立っている。BWTはBurrows-Wheeler変換のことで、文字列を特殊な並び順に変換するという可逆関数である。BWTされた文字列を簡潔データ構造固有の操作をすることで、クエリ文字列の長さに比例した短い時間で文字列を探し出すのがFM-indexだ。 簡潔データ構造 簡潔データ構造に関してはFM-indexで必要となる二つの関数だけ説明して、詳細は次の機会に譲るとする。さて、二つの関数はともに文字列のある位置より前の部分に含まれている文字の数を数え上げるというものでrank()とrankLessTha
機械学習概論 講義テキスト
2015/04/14 初期バージョン 2015/04/16 ver1.4（参考資料追加、k平均法の解説追加など） 2015/04/20 ver1.5（最大対数尤度関数の評価、混合分布によるクラスタリングを追加） 2015/04/21 ver1.6（EM法のアルゴリズム説明を追加） 2015/04/24 ver1.7（その他の性能指標を追加） 2015/05/19 ver1.8（ギリシャ文字ベクトルフォントの修正、その他リファクタリング） 2015/05/25 ver1.9（EM法の初期データ画像を追加） 2015/06/07 ver2.1（セミナー用に修正） 2015/06/24 ver2.2（EM法の説明を追加） 2016/09/01 ver2.3（誤字修正） 2016/12/27 ver1.0 タイトルを変更 2016/07/07 ver1.4 Update
人工知能を実現する学習アルゴリズムに必要な能力 - 人工知能に関する断創録
今年は、Deep Learningを研究する予定（2014/1/4）だったのだけれど、多層パーセプトロンまで到達した（2014/2/5）ところで少々（？）足踏みしている。Deep Learningの構成要素であるボルツマンマシンを理解するのに手間取っているためだ。ボルツマンマシンの理解には、マルコフ確率場やMCMCの理解が必要なことがわかったので少し廻り道してモンテカルロ法を先に勉強（2014/6/20）していたというわけ。 ただ、そればかりでは少々退屈になってきたので少し先回りして Deep Learning の先駆者のBengioさんが書いた論文 Learning Deep Architectures for AI を勉強している。示唆に富む見解が多いのであとで振り返られるように記録しておきたい。 まずは、1.1節のDesiderate for Learning AIの部分。人工知能を
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
技術計算用Ｃプログラム ソース
大規模グラフデータ処理
CRC-16-CCITT をテーブルを使わないで計算するソースコード