12個の事前計算点を用いた共同疎形式

概要

論文の詳細を見る
楕円曲線暗号におけるマルチスカラー倍算の高速化手法として、スカラーの対を共同疎形式(Joint Sparse From,JSF)を用いて表現する方法が知られている。SolinasのJSF提案論文では、三つの拡張形式の構成が未解決問題として提示された。そのうちの二つは解決済みであるが、残りの一つが未解決として残されていた。その未解決問題とは、通常のJSFが0,±1によって定まる桁集合(digit set)を用いて整数対を表現するのに対して、±3などのより大きな値の桁集合を用いた場合への拡張表現の構成である。本稿では、この未解決となっていたJSFの拡張について考察する。事前計算する点の個数を12個とした場合、既存の結果では非ゼロ密度が0.3615が最小であった。本稿の結果では0.3577となることを示す。さらに、通常のJSFが満たすいくつかの性質について、拡張JSFも満足することを確認する。例えば、拡張JSFはいくつかのルールを満たす表現として定義できることや、存在性、一意性、(ハミング重みの)最小性などである。
2009-05-15