(57)【要約】  本発明は、２ｎビットの数を使用してモジュラ乗算を行う方法に関する。本発明の方法は、数（Ａ，Ｂ）を２ｎ基数、または適当な整数であるＵ基数に分解するステップと、その後で、第１のステップからのｎビットの前記数に対して、ＭｕｌｔＭｏｄＤｉｖおよび／またはＭｕｌｔＭｏｄＤｉｖＩｎｉｔタイプの基本演算を行うステップとからなる。本発明は、また、ユークリッド乗算／除算を計算する方法にも関する。本発明は、暗号計算にも使用することができる。【特許請求の範囲】
【請求項１】
Ａ×Ｂ  ｍｏｄ  Ｎタイプのモジュラ乗算を行うための暗号化方法であって、
もしこれらが分解された形になっていない場合には、２×ｎビットの数Ａ、Ｂ、Ｎを、Ａ＝Ａ１×Ｕ＋Ａ０、Ｂ＝Ｂ１×Ｕ＋Ｂ０、Ｎ＝Ｎ１×Ｕ＋Ｎ０になるように、またＡ１、Ａ０、Ｂ１、Ｂ０、Ｎ１およびＮ０がｎビットの語になるように基数Ｕに分解し、次に、
前記数Ａ１、Ａ０、Ｂ１、Ｂ０、Ｎ１およびＮ０に対してＭｕｌｔＭｏｄＤｉｖタイプの演算を行い、前記ＭｕｌｔＭｏｄＤｉｖの基本演算が、ＭｕｌｔＭｏｄＤｉｖ（Ｘ，Ｙ，Ｚ）＝（｜＿（Ｘ×Ｙ）／Ｚ＿｜），（Ｘ×Ｙ）ｍｏｄ  Ｚ）により定義され、Ｘ、Ｙ、Ｚが最大ｎビットの整数である方法。
【請求項２】
Ｕが、２ｎ以外のものである請求項１に記載の方法。
【請求項３】
下記の演算を行い、
（Ｑ１，Ｒ１）＝ＭｕｌｔＭｏｄＤｉｖ（Ａ０，Ｂ０，Ｕ）
（Ｑ２，Ｒ２）＝ＭｕｌｔＭｏｄＤｉｖ（Ａ１＋Ａ０，Ｂ１＋Ｂ０，Ｕ）
（Ｑ３，Ｒ３）＝ＭｕｌｔＭｏｄＤｉｖ（Ａ１，Ｂ１，Ｕ）
（Ｑ４，Ｒ４）＝ＭｕｌｔＭｏｄＤｉｖ（α，Ｑ３，Ｕ）
（Ｑ５，Ｒ５）＝ＭｕｌｔＭｏｄＤｉｖ（α，−Ｑ１＋Ｑ２−Ｑ３＋Ｑ４＋Ｒ３，Ｕ）
Ｒ１乃至Ｒ５、Ｑ１乃至Ｑ５がｎビットの中間結果であり、
αが式α＝Ｕ２  ｍｏｄ  Ｎにより定義され、次に、
下記の結果、すなわち、
（Ｒ５＋Ｒ１）＋（Ｒ４−Ｒ１＋Ｑ１＋Ｒ２−Ｒ３＋Ｑ５）×Ｕ
が戻される請求項２に記載の方法。
【請求項４】
前記数Ｕが、｜￣√Ｎ￣｜に等しくなるように選択される請求項３に記載の方法。
【請求項５】
前記数Ｕが、｜￣√（ｋ．Ｎ）￣｜（ここで、ｋは整数である）に等しくなるように選択される、請求項３に記載の方法。
【請求項６】
αができるだけ小さくなるように前記数ｋが選択される請求項５に記載の方法。
【請求項７】
前記数Ｕが、式Ｕ２  ηＮ  α＋δ×Ｕ（ここで、αおよびδは整数である）により最初に計算され、次に、
下記の演算が行われ、
（Ｑ１，Ｒ１）＝ＭｕｌｔＭｏｄＤｉｖ（Ａ０，Ｂ０，Ｕ）
（Ｑ２，Ｒ２）＝ＭｕｌｔＭｏｄＤｉｖ（Ａ１＋Ａ０，Ｂ１＋Ｂ０，Ｕ）
（Ｑ３，Ｒ３）＝ＭｕｌｔＭｏｄＤｉｖ（Ａ１，Ｂ１，Ｕ）
Ｒ１乃至Ｒ５、Ｑ１乃至Ｑ５がｎビットの中間結果であり、次に、
下記の結果、すなわち、
α×（−Ｑ１＋Ｑ２−Ｑ３＋Ｒ３＋δ×Ｑ３）＋Ｒ１
＋Ｕ×［（−Ｒ１−Ｒ３＋Ｑ１＋Ｒ２＋Ｑ３（α＋δ２）＋（−Ｑ３＋Ｒ３−Ｑ１＋Ｑ２）×δ］
が戻される請求項２に記載の方法。
【請求項８】
前記数αおよびδが、できるだけ小さな定数となるように、またα＋δ２も一定で小さな整数になるように選択される請求項７に記載の方法。
【請求項９】
下記演算が行われ、
（Ｘ１，Ｙ１，Ｚ１，Ｒ１）＝係数（Ａ，Ｂ，Ｕ）
（Ｑ２，Ｒ２）＝ＭｕｌｔＭｏｄＤｉｖ（α，Ｘ１，Ｕ）
（Ｑ３，Ｒ３）＝ＭｕｌｔＭｏｄＤｉｖ（α，Ｙ１＋Ｑ２，Ｕ）
αがα＝Ｕ２  ｍｏｄ  Ｎにより定義される整数であり、係数の基本演算が：
Ｃ３＝ｆ；Ｃ２＝ｄ＋３ｆ；Ｃ１＝ｅ＋２ｆ；Ｃ０＝Ｒ０、ここで、
Ｒ０＝（Ａ  ｍｏｄ  Ｕ）（Ｂ  ｍｏｄ  Ｕ）ｍｏｄ  Ｕ
Ｒ１＝（Ａ  ｍｏｄ（Ｕ＋１））（Ｂ  ｍｏｄ（Ｕ＋１））ｍｏｄ（Ｕ＋１）
Ｒ２＝（Ａ  ｍｏｄ（Ｕ＋２））（Ｂ  ｍｏｄ（Ｕ＋２））ｍｏｄ（Ｕ＋２）
Ｒ３＝（Ａ  ｍｏｄ（２Ｕ＋３））（Ｂ  ｍｏｄ（２Ｕ＋３））ｍｏｄ（２Ｕ＋３）、および
ａ＝（Ｒ０−Ｒ２＋（（Ｒ０−Ｒ２）ｍｏｄ  ２）（Ｕ＋２））／２  ｍｏｄ  Ｕ＋２
ｂ＝Ｒ０−Ｒ１  ｍｏｄ（Ｕ＋１）
ｃ＝（２（Ｒ０−Ｒ３）＋（２（Ｒ０−Ｒ３）ｍｏｄ  ３）（２Ｕ＋３））／３  ｍｏｄ（２Ｕ＋３）
ｄ＝（（ｂ−ａ）ｍｏｄ（Ｕ＋１））
ｅ＝ａ＋２ｄ
ｆ＝−６ｄ＋４ｅ−４ｃ  ｍｏｄ（２Ｕ＋３）
であり、下記の結果、すなわち、
Ｒ１＋Ｒ３＋（Ｒ２＋Ｚ１＋Ｑ３）×Ｕ
が戻されるように係数（Ａ，Ｂ，Ｕ）＝（Ｃ３，Ｃ２，Ｃ１，Ｃ０）により定義される請求項２に記載の方法。
【請求項１０】
下記の演算が行われ、
（Ｘ１，Ｙ１，Ｚ１，Ｒ１）＝係数（Ａ，Ｂ，Ｕ）
（Ｑ２，Ｒ２）＝ＭｕｌｔＭｏｄＤｉｖ（α，Ｘ１，Ｕ）
（Ｑ３，Ｒ３）＝ＭｕｌｔＭｏｄＤｉｖ（α，Ｙ１＋Ｑ２，Ｕ）
αが、α＝Ｕ２  ｍｏｄ  Ｎにより定義される整数であり、係数の基本演算が、
Ｃ３＝ｆ；Ｃ２＝ｄ＋３ｆ；Ｃ１＝ｅ＋２ｆ；Ｃ０＝Ｒ０、ここで、
Ｒ０＝Ａ０Ｂ０  ｍｏｄ  Ｕ
Ｒ１＝（Ａ０−Ａ１）（Ｂ０−Ｂ１）ｍｏｄ（Ｕ＋１）
Ｒ２＝（Ａ０−２Ａ１）（Ｂ０−２Ｂ１）ｍｏｄ（Ｕ＋２）
Ｒ３＝（Ａ０＋（Ａ１  ｍｏｄ  ２）Ｕ−３（Ａ１  ｄｉｖ  ２））×（Ｂ０＋（Ｂ１  ｍｏｄ  ２）Ｕ−３（Ｂ１  ｄｉｖ  ２））ｍｏｄ（２Ｕ＋３）
および、
ａ＝（Ｒ０−Ｒ２＋（（Ｒ０−Ｒ２）ｍｏｄ  ２）（Ｕ＋２））／２  ｍｏｄ  Ｕ＋２
ｂ＝Ｒ０−Ｒ１  ｍｏｄ（Ｕ＋１）
ｃ＝（２（Ｒ０−Ｒ３）＋（２（Ｒ０−Ｒ３）ｍｏｄ  ３）（２Ｕ＋３））／３  ｍｏｄ（２Ｕ＋３）
ｄ＝（（ｂ−ａ）ｍｏｄ（Ｕ＋１））
ｅ＝ａ＋２ｄ
ｆ＝−６ｄ＋４ｅ−４ｃ  ｍｏｄ（２Ｕ＋３）
であり、下記の結果、すなわち、
Ｒ１＋Ｒ３＋（Ｒ２＋Ｚ１＋Ｑ３）×Ｕ
が戻されるように、係数（Ａ，Ｂ，Ｕ）＝（Ｃ３，Ｃ２，Ｃ１，Ｃ０）により定義される請求項２に記載の方法。
【請求項１１】
｜￣√Ｎ￣｜に等しくなるように前記数Ｕが選択される請求項９または１０に記載の方法。
【請求項１２】
｜￣√（ｋ．Ｎ）￣｜（ここで、ｋは整数）に等しくなるように、前記数Ｕが選択される請求項９または１０に記載の方法。
【請求項１３】
Ｕが奇数になり、３で割ることができないように、ｋができるだけ小さくなるように選択される請求項１２に記載の方法。
【請求項１４】
αができるだけ小さくなるように、前記数ｋが選択される請求項１３に記載の方法。
【請求項１５】
Ｕが２ｎに等しく、
下記の演算が行われ、
（Ｑ１，Ｒ１）＝ＭｕｌｔＭｏｄＤｉｖ（Ａ１，Ｂ１，Ｎ１）
（Ｑ２，Ｒ２）＝ＭｕｌｔＭｏｄＤｉｖ（Ｑ１，Ｎ０，２ｎ）
（Ｑ３，Ｒ３）＝ＭｕｌｔＭｏｄＤｉｖ（Ａ１＋Ａ０，Ｂ１＋Ｂ０，２ｎ−１）
（Ｑ４，Ｒ４）＝ＭｕｌｔＭｏｄＤｉｖ（Ａ０，Ｂ０，２ｎ）
（Ｑ５，Ｒ５）＝ＭｕｌｔＭｏｄＤｉｖ（２ｎ−１，Ｒ１＋Ｑ３−Ｑ２−Ｑ４，Ｎ１）
（Ｑ６，Ｒ６）＝ＭｕｌｔＭｏｄＤｉｖ（Ｑ５，Ｎ０，２ｎ）
Ｒ１乃至Ｒ６、Ｑ１乃至Ｑ６がｎビットの中間結果であり、ＭｕｌｔＭｏｄＤｉｖの基本演算が、ＭｕｌｔＭｏｄＤｉｖ（Ｘ，Ｙ，Ｚ）＝（｜＿（Ｘ×Ｙ）／Ｚ＿｜），（Ｘ×Ｙ）  ｍｏｄ  Ｚ）により定義され、Ｘ、Ｙ、Ｚが最大ｎビットの整数であり、次に、
下記の結果、すなわち、
（Ｒ３＋Ｒ５−Ｑ６−Ｒ２−Ｒ４）×２ｎ＋（Ｒ２＋Ｒ４−Ｒ６）
が戻される請求項１に記載の方法。
【請求項１６】
Ｕが２ｎに等しく、
下記の演算が行われ、
（Ｑ１，Ｒ１）＝ＭｕｌｔＭｏｄＤｉｖ（Ａ１，Ｂ１，Ｎ１）
（Ｑ２，Ｒ２）＝ＭｕｌｔＭｏｄＤｉｖ（Ａ１＋Ａ０，Ｂ１＋Ｂ０，２ｎ−１）
（Ｑ３，Ｒ３）＝ＭｕｌｔＭｏｄＤｉｖ（Ａ０，Ｂ０，２ｎ）
（Ｑ４，Ｒ４）＝ＭｕｌｔＭｏｄＤｉｖＩｎｉｔ（Ｑ１，Ｎ０，Ｑ３−Ｒ１−Ｑ２，Ｎ１）
（Ｑ５，Ｒ５）＝ＭｕｌｔＭｏｄＤｉｖ（Ｎ０＋Ｎ１，Ｑ４，２ｎ）
Ｒ１乃至Ｒ５、Ｑ１乃至Ｑ５がｎビットの中間結果であり、ＭｕｌｔＭｏｄＤｉｖの基本演算が、ＭｕｌｔＭｏｄＤｉｖ（Ｘ，Ｙ，Ｚ）＝（｜＿（Ｘ×Ｙ）／Ｚ＿｜，（Ｘ×Ｙ）  ｍｏｄ  Ｚ）により定義され、ＭｕｌｔＭｏｄＤｉｖＩｎｉｔの基本演算が、ＭｕｌｔＭｏｄＤｉｖＩｎｉｔ（Ｘ，Ｙ，Ｔ，Ｚ）＝（｜＿（Ｘ×Ｙ＋Ｔ×２ｎ）／Ｚ＿｜），（Ｘ×Ｙ）＋Ｔ×２ｎ）ｍｏｄ  Ｚ）により定義され、Ｘ、Ｙ、ＺおよびＴが最大ｎビットの整数であり、次に、
下記の結果、すなわち、
（Ｒ２＋Ｑ５−Ｒ３−Ｒ４）×２ｎ＋（Ｒ３＋Ｒ４＋Ｒ５）ＡＵＴＯＮＵＭＡＵＴＯＮＵＭ
が戻される請求項１に記載の方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、ｎビットの数を扱うことができる処理装置により、２×ｎビットの数Ａ、Ｂ、Ｎを使用して、Ａ×Ｂ  ｍｏｄ  Ｎタイプのモジュラ乗算を行うための方法に関する。本発明は、また、本発明によるモジュラ乗算を行うための方法を実施するのに適しているｎビットの数Ｘ、Ｙ、Ｚを使用して、（Ｘ×Ｙ）／Ｚタイプの演算を行うための方法に関する。本発明は、例えば、暗号計算を行うために使用する大きな数（例えば、約２０４８ビットのｎ）に対して演算を行う場合に特に役に立つ。
【背景技術】
【０００２】
ｎより大きいサイズを有する数に対してモジュラ演算を行う際には、かなりの問題に遭遇するし、この演算は、通常例えば、大きな数がｎビットの語に切り捨てられ、次に、ｎビットの語に対して基本演算が行われるＭｏｎｔｇｏｍｅｒｙ、Ｂａｒｒｅｔｔ、ＱｕｉｓｑｕａｔｅｒまたはＷａｌｔｅｒの方法のような複雑なアルゴリズムの使用を含む。
【０００３】
しかし、このようなアルゴリズムは、装置の観点からいって、最大ｎビットの数の処理に限定されるモジュラ演算処理装置により行うことができない。例えば、乗算の結果が、上記処理装置により処理することができない２×ｎの数になるという簡単な理由で、ｎビットの２つの数の簡単な乗算をある種の処理装置により行うことができない。
【０００４】
それ故、大きな数に対して演算を行うことができるように、ソフトウェアの観点からこの装置をエミュレートしなければならない。そのために、ＦｉｓｈｅｒおよびＳｅｉｆｅｒｔは、最近、ｎビットの数を扱う２つの基本関数をベースとして、２×ｎ（ｎは使用した処理装置により処理した語のサイズ）のサイズの数Ａ、Ｂ、Ｎに対して、Ａ×Ｂ  ｍｏｄ  Ｎタイプのモジュラ乗算を行うことを可能にする２つの解決方法をＤ１（２００３年、Ｂｅｒｌｉｎ  ＨｅｉｄｅｌｂｅｒｇのＳｐｒｉｎｇｅｒ−Ｖｅｒｌａｇ発行の、ＣＨＥＳ２００２、ＬＮＣＳ２５２３、７１〜８１ページ掲載のＷｉｅｌａｎｄ  ＦＩＳＨＥＲおよびＪｅａｎ  Ｐｉｅｒｒｅ  ＳＥＩＦＥＲＴの、「暗号処理装置のビット長の増大」（Ｉｎｃｒｅａｓｉｎｇ  ｔｈｅ  Ｂｉｔｌｅｎｇｔｈ  ｏｆ  ａ  Ｃｒｙｐｔｏ−ｐｒｏｃｅｓｓｏｒ））に発表した。
【０００５】
２つの基本関数ＭｕｌｔＭｏｄＤｉｖおよびＭｕｌｔＭｏｄＤｉｖＩｎｉｔは下記のように定義される。
ＭｕｌｔＭｏｄＤｉｖ（Ｘ，Ｙ，Ｚ）＝（Ｑａ，Ｒａ）
＝（｜＿（Ｘ×Ｙ）／ｚ＿｜，（Ｘ×Ｙ）ｍｏｄ  Ｚ）
ＭｕｌｔＭｏｄＤｉｖＩｎｉｔ（Ｘ，Ｙ，Ｔ，Ｚ）＝（Ｑｂ，Ｒｂ）
＝（｜＿（Ｘ×Ｙ＋Ｔ×２ｎ）／Ｚ＿｜），（Ｘ×Ｙ＋Ｔ×２ｎ）ｍｏｄ  Ｚ）
【０００６】
Ｘ、Ｙ、Ｔ、Ｚは、最大ｎビットの整数であり、Ｘ、Ｙ、Ｔは正の数または負の数であり、Ｚは正の数であり、Ｑａ、Ｑｂ、Ｒａ、Ｒｂは、ｎビットの結果である。各ＭｕｌｔＭｏｄＤｉｖおよびＭｕｌｔＭｏｄＤｉｖＩｎｉｔ演算は、とりわけ、ｎビットの数に対して２回の乗算を行う。
【０００７】
「｜＿Ａ＿｜」という記号は、「Ａの整数部」である（すなわち、Ａは最も近い整数に切り捨てられる）。「ｍｏｄ」という記号は、「ｍｏｄｕｌｏ」の通常の略語である。「×」という記号は、ユークリッド乗算を示すために使用する。
【０００８】
それ故、各ＭｕｌｔＭｏｄＤｉｖ関数またはＭｕｌｔＭｏｄＤｉｖＩｎｉｔ関数は、実際に、ｎビットの数Ｘ、Ｙ、Ｚに対して２回の基本演算を行う。すなわち、その結果がデフォルトによりその整数値に切り捨てられる１つのユークリッド乗算（Ｑ＝｜＿（Ｘ×Ｙ）／Ｚ＿｜または｜＿（Ｘ×Ｙ＋Ｔ×２ｎ）／Ｚ＿｜）、および１つのモジュラ乗算（Ｒ＝（Ｘ×Ｙ）ｍｏｄ  Ｚ）または（Ｘ×Ｙ＋Ｔ×２ｎ）ｍｏｄ  Ｚ）を行う。
【０００９】
関数（Ｑ，Ｒ）＝ＭｕｌｔＭｏｄＤｉｖ（Ｘ，Ｙ，Ｚ）という定義から、すぐに下記の結論を導き出すことができる。
Ｘ×Ｙ＝Ｑ×Ｚ＋Ｒ
同様に、関数（Ｑ，Ｒ）＝ＭｕｌｔＭｏｄＤｉｖ（Ｘ，Ｙ，Ｚ，Ｔ）という定義から下記の結論を導き出すことができる。
Ｘ×Ｙ＋Ｔ×２ｎ＝Ｑ×Ｚ＋Ｒ
【００１０】
これらの関数、およびもっと一般的に以下に説明する方法を実施するために必要なすべての算術演算は、最大ｎビットの数を扱うことができ、最大ｎビットの数を生み出すことができるモジュラ演算処理装置で行われる。
【００１１】
この場合および以下の説明において、分かりやすくするために、処理装置のレジスタおよびそれが含むｎビットの語または数の両方を示すために同じ名称を使用する。例えば、「Ｃ＝Ａ×Ｂ」は、特に、この方法の場合、「レジスタＡの内容に乗算回路内のレジスタＢの内容を掛けて、乗算の結果をレジスタＣ内に記憶すること」を意味する。
【００１２】
Ａ、Ｂ、Ｎが２ｎビットの数である場合の、演算Ａ×Ｂ  ｍｏｄ  Ｎを行うために、ＦｉｓｈｅｒおよびＳｅｉｆｅｒｔが提案した解決方法は、数Ａ、Ｂ、Ｎをｎビットの２つの語、すなわち、高い加重のＡ１、Ｂ１、Ｎ１の１つの語および低い加重のＡ０、Ｂ０、Ｎ０の１つの語に分解する。
【００１３】
第１の解決方法は、７つのＭｕｌｔＭｏｄＤｉｖ関数を使用し、下記のアルゴリズムＦＳ１（ＦｉｓｈｅｒおよびＳｅｉｆｅｒｔのモジュラ乗算アルゴリズムの第１のバージョン）により要約することができる。
入力：Ａ、Ｂ、Ｎ（２ｎビットの整数）
以下の形に分解する： 
Ａ＝Ａ１×２ｎ＋Ａ０；Ｂ＝Ｂ１×２ｎ＋Ｂ０；Ｎ＝Ｎ１×２ｎ＋Ｎ０
出力：Ａ×Ｂ  ｍｏｄ  Ｎ
演算内容：
（Ｑ１，Ｒ１）＝ＭｕｌｔＭｏｄＤｉｖ（Ｂ１，２ｎ，Ｎ１）
（Ｑ２，Ｒ２）＝ＭｕｌｔＭｏｄＤｉｖ（Ｑ１，Ｎ０，２ｎ）
（Ｑ３，Ｒ３）＝ＭｕｌｔＭｏｄＤｉｖ（Ａ１，Ｒ１−Ｑ２＋Ｂ０，Ｎ１）
（Ｑ４，Ｒ４）＝ＭｕｌｔＭｏｄＤｉｖ（Ａ０，Ｂ１，Ｎ１）
（Ｑ５，Ｒ５）＝ＭｕｌｔＭｏｄＤｉｖ（Ｑ３＋Ｑ４，Ｎ０，２ｎ）
（Ｑ６，Ｒ６）＝ＭｕｌｔＭｏｄＤｉｖ（Ａ１，Ｒ２，２ｎ）
（Ｑ７，Ｒ７）＝ＭｕｌｔＭｏｄＤｉｖ（Ａ０，Ｂ０，２ｎ）
戻り（Ｒ３＋Ｒ４−Ｑ５−Ｑ６＋Ｑ７）×２ｎ＋（Ｒ７−Ｒ６−Ｒ５）
Ｒ１乃至Ｒ７、Ｑ１乃至Ｑ７は、最終結果を入手するために必要なｎビットの中間変数である。
ＦｉｓｈｅｒおよびＳｅｉｆｅｒｔが提案した第２の解決方法は、ＭｕｌｔＭｏｄＤｉｖタイプの５つの関数および１つのＭｕｌｔＭｏｄＤｉｖＩｎｉｔ関数を使用する。この第２の解決方法は、下記のアルゴリズムＦＳ２（ＦｉｓｈｅｒおよびＳｅｉｆｅｒｔのモジュラ乗算アルゴリズムの第２のバージョン）により要約することができる。
【００１４】
入力：Ａ、Ｂ、Ｎ（２ｎビットの整数）
以下の形に分解する：
Ａ＝Ａ１×２ｎ＋Ａ０；Ｂ＝Ｂ１×２ｎ＋Ｂ０；Ｎ＝Ｎ１×２ｎ＋Ｎ０
出力：Ａ×Ｂ  ｍｏｄ  Ｎ
演算内容：
（Ｑ１，Ｒ１）＝ＭｕｌｔＭｏｄＤｉｖ（Ａ１，Ｂ１，Ｎ１）
（Ｑ２，Ｒ２）＝ＭｕｌｔＭｏｄＤｉｖＩｎｉｔ（Ｎ０，−Ｑ１，Ｒ１，Ｎ１）
（Ｑ３，Ｒ３）＝ＭｕｌｔＭｏｄＤｉｖ（Ａ１，Ｂ０，Ｎ１）
（Ｑ４，Ｒ４）＝ＭｕｌｔＭｏｄＤｉｖ（Ａ０，Ｂ１，Ｎ１）
（Ｑ５，Ｒ５）＝ＭｕｌｔＭｏｄＤｉｖ（Ａ０，Ｂ０，２ｎ）
（Ｑ６，Ｒ６）＝ＭｕｌｔＭｏｄＤｉｖ（Ｑ２＋Ｑ３＋Ｑ４，Ｎ０，２ｎ）
戻り（Ｒ２＋Ｒ３＋Ｒ４＋Ｑ５−Ｑ６）×２ｎ＋（Ｒ５−Ｒ６）
ＦｉｓｈｅｒおよびＳｅｉｆｅｒｔが提案した２つの解決方法の実施モードに関する詳細および追加情報は、Ｄ１に掲載されている。
【００１５】
すでに説明したように、これら２つの解決方法を使用すれば、ｎビットの数に元来限定されている処理装置を使用して、最大２×ｎビットの数に対してモジュラ演算を行うことができる。しかし、これら２つの解決方法は、大きな電力を消費する。何故なら、各ＭｕｌｔＭｏｄＤｉｖ関数またはＭｕｌｔＭｏｄＤｉｖＩｎｉｔ関数は、ある数の基本演算（レジスタの内容の加算、減算、レジスタ内でのビットのシフト等）を必要とするからである。
【００１６】
ＭｕｌｔＭｏｄＤｉｖＩｎｉｔ関数の実施は、通常、ＭｕｌｔＭｏｄＤｉｖ関数の実施よりももっと多くの基本演算を必要とすることに留意されたい。（例えば、ＭｕｌｔＭｏｄＤｉｖ関数およびＭｕｌｔＭｏｄＤｉｖＩｎｉｔ関数の実施の例については、Ｄ１を参照されたい）。せいぜい、ある種の処理装置を使用した場合には、ＭｕｌｔＭｏｄＤｉｖＩｎｉｔ演算の実施のコストは、ＭｕｌｔＭｏｄＤｉｖ演算のコストと同じになるくらいのものである（例えば、Ｓｅｄｌａｋのアルゴリズムを参照されたい）。
【００１７】
ＭｕｌｔＭｏｄＤｉｖまたはＭｕｌｔＭｏｄＤｉｖＩｎｉｔタイプの関数の実施は、ｎビットの数に対してＱ＝｜＿（Ｘ×Ｙ）／Ｚ＿｜およびＲ＝（Ｘ×Ｙ）ｍｏｄ  Ｚタイプの基本演算の性能を必要とする。暗号計算専用の処理装置は、通常、Ｒ＝（Ｘ×Ｙ）ｍｏｄ  Ｚタイプのモジュラ演算を計算するための集積ハードウェア手段を有しているが、いつでも、Ｑ＝｜＿（Ｘ×Ｙ）／Ｚ＿｜タイプのユークリッド演算を実行するためのハードウェア手段であるとは限らない。この場合、モジュラ基本演算のセットをベースとして、ユークリッド演算を実行するためのエミュレーション手段（ソフトウェア）が通常使用される。
【００１８】
例えば、Ｄ１は、Ｒ１＝（Ｘ×Ｙ）ｍｏｄ  ＺおよびＲ２＝（Ｘ×Ｙ）ｍｏｄ（Ｚ＋１）のタイプの演算をベースにして、Ｑ＝｜＿（Ｘ×Ｙ）／Ｚ＿｜を計算することができる方法を記述している。より詳細に説明すると、Ｄ１においては、Ｑは下式により計算される。
Ｑ＝（（Ｘ＊Ｙ）ｍｏｄ  Ｚ）−（（Ｘ＊Ｙ）ｍｏｄ（Ｚ＋１）（この値が正である場合）、または
Ｑ＝（（Ｘ＊Ｙ）ｍｏｄ  Ｚ）−（（Ｘ＊Ｙ）ｍｏｄ（Ｚ＋１））＋（Ｚ＋１）
演算Ｒ＝（Ｘ×Ｙ）ｍｏｄ  Ｚは、周知のモンゴメリ・アルゴリズムにより行われる。しかし、このアルゴリズムは、ｍｏｄｕｌｏ  Ｚが奇数である場合には、（正確さおよび計算時間の点で）特に効果的であるが、Ｚが偶数の場合には効果的ではない。このことは、Ｄ１に提案されている方法は効果的でないことを意味する。何故なら、数ＺおよびＺ＋１の一方または他方が必ず偶数であるからである。
【非特許文献１】２００３年、Ｂｅｒｌｉｎ  ＨｅｉｄｅｌｂｅｒｇのＳｐｒｉｎｇｅｒ−Ｖｅｒｌａｇ発行の、ＣＨＥＳ２００２、ＬＮＣＳ２５２３、７１〜８１ページ掲載のＷｉｅｌａｎｄ  ＦＩＳＨＥＲおよびＪｅａｎ  Ｐｉｅｒｒｅ  ＳＥＩＦＥＲＴの、「Ｉｎｃｒｅａｓｉｎｇ  ｔｈｅ  Ｂｉｔｌｅｎｇｔｈ  ｏｆ  ａ  Ｃｒｙｐｔｏ−ｐｒｏｃｅｓｓｏｒ」
【発明の開示】
【発明が解決しようとする課題】
【００１９】
本発明の１つの目的は、ＦｉｓｈｅｒおよびＳｅｉｆｅｒｔが提案したアルゴリズムと同じであるが、もっと少ない電力でもっと迅速に結果が得られるように、ＭｕｌｔＭｏｄＤｉｖまたはＭｕｌｔＭｏｄＤｉｖＩｎｉｔタイプのもっと少ない数の基本関数により、演算（Ａ、Ｂ、Ｎが２×ｎビットである、Ａ×Ｂ  ｍｏｄ  Ｎ）を行うことである。
【００２０】
本発明のもう１つの目的は、Ｄ１で提案された方法よりもっと効果的な、ｎビットの数に対して、Ｓ＝｜＿（Ｘ×Ｙ）／Ｚ＿｜タイプの演算を実行する方法を提供することである。本発明による方法は、本発明によるモジュラ乗算を行うために使用することができる。
【００２１】
それ故、本発明は、Ａ、Ｂ、Ｎが２×ｎビットの数である、Ａ×Ｂ  ｍｏｄ  Ｎタイプのモジュラ乗算を行うための方法に関する。本発明による方法の実施モードが何であろうとも、数Ａ、Ｂ、Ｎはｎビットの語に分解される。その場合、この方法を実行している間、演算は、ｎビットの数Ａ１、Ａ０、Ｂ１、Ｂ０、Ｎ１およびＮ０に対して行われる。
【課題を解決するための手段】
【００２２】
本発明の第１の実施形態によれば、数Ａ、Ｂ、Ｎは、Ａ＝Ａ１×２ｎ＋Ａ０、Ｂ＝Ｂ１×２ｎ＋Ｂ０、Ｎ＝Ｎ１＊２ｎ＋Ｎ０の形をしている基数２ｎに分解される。すなわち、Ａ、Ｂ、Ｎの高い加重のｎビットは、それぞれ語Ａ１、Ｂ１、Ｎ１をそれぞれ形成し、Ａ、Ｂ、Ｎの低い加重のｎビットは、それぞれ語Ａ０、Ｂ０、Ｎ０をそれぞれ形成する。次に、ＭｕｌｔＭｏｄＤｉｖタイプの６つの基本関数が実行されるが、６番目のものはモジュラ乗算の結果を提供する。
【発明を実施するための最良の形態】
【００２３】
より詳細に説明すると、下記の方法Ａ１が実行される。
【００２４】
入力：Ａ、Ｂ、Ｎ（２×ｎビットの整数）
以下の形に分解する：
Ａ＝Ａ１×２ｎ＋Ａ０；Ｂ＝Ｂ１×２ｎ＋Ｂ０；Ｎ＝Ｎ１×２ｎ＋Ｎ０
出力：Ａ×Ｂ  ｍｏｄ  Ｎ
演算内容：
（Ｑ１，Ｒ１）＝ＭｕｌｔＭｏｄＤｉｖ（Ａ１，Ｂ１，Ｎ１）
（Ｑ２，Ｒ２）＝ＭｕｌｔＭｏｄＤｉｖ（Ｑ１，Ｎ０，２ｎ）
（Ｑ３，Ｒ３）＝ＭｕｌｔＭｏｄＤｉｖ（Ａ１＋Ａ０，Ｂ１＋Ｂ０，２ｎ−１）
（Ｑ４，Ｒ４）＝ＭｕｌｔＭｏｄＤｉｖ（Ａ０，Ｂ０，２ｎ）
（Ｑ５，Ｒ５）＝ＭｕｌｔＭｏｄＤｉｖ（２ｎ−１，Ｒ１＋Ｑ３−Ｑ２−Ｑ４，Ｎ１）
（Ｑ６，Ｒ６）＝ＭｕｌｔＭｏｄＤｉｖ（Ｑ５，Ｎ０，２ｎ）
戻り（Ｒ３＋Ｒ５−Ｑ６−Ｒ２−Ｒ４）×２ｎ＋（Ｒ２＋Ｒ４−Ｒ６）
【００２５】
上記アルゴリズムＡ１は、実際に、モジュラ乗算Ａ×Ｂ  ｍｏｄ  Ｎを行う。Ｋａｒａｔｓｕｂａの補助定理（特に、Ｄ２：１９６３年のＳｏｖｉｅｔ  Ｐｈｙｓｉｃｓ  −  Ｄｏｋｌａｄｙ、第７巻、５９５〜５９６ページ掲載の「オートメーション上での複数桁の数の乗算」（Ｍｕｌｔｉｐｌｉｃａｔｉｏｎ  Ｏｆ  Ｍｕｌｔｉｄｉｇｉｔ  Ｎｕｍｂｅｒｓ  Ｏｎ  Ａｕｔｏｍａｔａ）参照）により下記の結果が得られる。
Ａ×Ｂ＝２ｎ（２ｎ−１）Ａ１×Ｂ１＋２ｎ（Ａ１＋Ａ０）×（Ｂ１＋Ｂ０）−（２ｎ−１）Ａ０×Ｂ０
Ｎ＝Ｎ１×２ｎ＋Ｎ０であるから、Ｎ１×２ｎ  ηＮ  −Ｎ０となる。ここで、ηＮは等価関係ｍｏｄｕｌｏ  Ｎである。
アルゴリズムＡ１のＱ１乃至Ｑ６、Ｒ１乃至Ｒ６の定義から、またＭｕｌｔＭｏｄＤｉｖ関数の定義から、下記の結果を導き出すことができる。
【００２６】
２ｎ（２ｎ−１）×Ａ１×Ｂ１
ηＮ  ２ｎ（２ｎ−１）（Ｑ１×Ｎ１＋Ｒ１）
ηＮ  −（２ｎ−１）×（Ｑ１×Ｎ０）＋２ｎ（２ｎ−１）×Ｒ１
ηＮ  −（２ｎ−１）×（Ｑ２×２ｎ＋Ｒ２）＋２ｎ（２ｎ−１）Ｒ１
ηＮ  ２ｎ（２ｎ−１）（Ｒ１−Ｑ２）−（２ｎ−１）×Ｒ２
２ｎ（Ａ１＋Ａ０）（Ｂ１＋Ｂ０）＝２ｎ（（２ｎ−１）Ｑ３＋Ｒ３）＝２ｎ（２ｎ−１）Ｑ３＋２ｎ×Ｒ３
（２ｎ−１）×Ａ０×Ｂ０＝（２ｎ−１）（２ｎ×Ｑ４＋Ｒ４）＝２ｎ（２ｎ−１）Ｑ４＋（２ｎ−１）Ｒ４
これから下記の結果が最終的に導き出される。
Ａ×Ｂ  ηＮ  ２ｎ（２ｎ−１）（Ｒ１＋Ｑ３−Ｑ２−Ｑ４）＋２ｎ×Ｒ３−（２ｎ−１）（Ｒ２＋Ｒ４）
ηＮ  ２ｎ（Ｑ５×Ｎ１＋Ｒ５）＋２ｎ×Ｒ３−（２ｎ−１）（Ｒ２＋Ｒ４）
ηＮ  −Ｑ５×Ｎ０＋２ｎ（Ｒ３＋Ｒ５）−（２ｎ−１）（Ｒ２＋Ｒ４）
ηＮ  −（Ｑ６×２ｎ＋Ｒ６）＋２ｎ（Ｒ３＋Ｒ５）−（２ｎ−１）（Ｒ２＋Ｒ４）
ηＮ  ２ｎ（Ｒ３＋Ｒ５−Ｑ６−Ｒ２−Ｒ４）＋（Ｒ２＋Ｒ４−Ｒ６）
それ故、
Ａ×Ｂ  ｍｏｄ  Ｎ＝２ｎ（Ｒ３＋Ｒ５−Ｑ６−Ｒ２−Ｒ４）＋（Ｒ２＋Ｒ４−Ｒ６）
となる。これがアルゴリズムＡ１による結果である。
【００２７】
本発明による方法Ａ１は、従来技術により周知の方法ＦＳ１よりも１つ少ないＭｕｌｔＭｏｄＤｉｖ関数を使用することが分かるだろう。それ故、同じ結果に対して、実行する演算の全数が少なくなり、そのためこの方法を実行するために使用する全時間および全電力が少なくなる。より詳細に説明すると、１つのＭｕｌｔＭｏｄＤｉｖ演算が、ｎビットの数に対して２回モジュラ乗算を行うので、この場合、アルゴリズムＡ１は、アルゴリズムＦＳ１の場合の１４回のモジュラ乗算の代わりに、ｎビットの数に対して１２回のモジュラ乗算を行うので、計算時間の利得は、（１４−１２）／１４＝１４％になる。
【００２８】
本発明の第２の実施形態によれば、数Ａ、Ｂ、Ｎは、同様に、Ａ＝Ａ１×２ｎ＋Ａ０、Ｂ＝Ｂ１×２ｎ＋Ｂ０、Ｎ＝Ｎ１＊２ｎ＋Ｎ０の形をしている基数２ｎに分解される。次に、ＭｕｌｔＭｏｄＤｉｖＩｎｉｔタイプの１つの関数、およびＭｕｌｔＭｏｄＤｉｖタイプの４つの基本関数が実行される。４番目の関数は、モジュラ乗算の結果を提供する。
【００２９】
より詳細に説明すると、下記の方法Ａ２が実行される。
【００３０】
入力：Ａ、Ｂ、Ｎ（２×ｎビットの整数）
以下の形に分解する：
Ａ＝Ａ１×２ｎ＋Ａ０；Ｂ＝Ｂ１×２ｎ＋Ｂ０；Ｎ＝Ｎ１×２ｎ＋Ｎ０
出力：Ａ×Ｂ  ｍｏｄ  Ｎ
演算内容：
（Ｑ１，Ｒ１）＝ＭｕｌｔＭｏｄＤｉｖ（Ａ１，Ｂ１，Ｎ１）
（Ｑ２，Ｒ２）＝ＭｕｌｔＭｏｄＤｉｖ（Ａ１＋Ａ０，Ｂ１＋Ｂ０，２ｎ−１）
（Ｑ３，Ｒ３）＝ＭｕｌｔＭｏｄＤｉｖ（Ａ０，Ｂ０，２ｎ）
（Ｑ４，Ｒ４）＝ＭｕｌｔＭｏｄＤｉｖＩｎｉｔ（Ｑ１，Ｎ０，Ｑ３−Ｒ１−Ｑ２，Ｎ１）
（Ｑ５，Ｒ５）＝ＭｕｌｔＭｏｄＤｉｖ（Ｎ０＋Ｎ１，Ｑ４，２ｎ）
戻り（Ｒ２＋Ｑ５−Ｒ３−Ｒ４）×２ｎ＋（Ｒ３＋Ｒ４＋Ｒ５）
このアルゴリズムＡ２は、実際に、モジュラ乗算Ａ×Ｂ  ｍｏｄ  Ｎを行う。Ｑ１乃至Ｑ５、Ｒ１乃至Ｒ５の定義により、下記のようになる。
２ｎ（２ｎ−１）×Ａ１×Ｂ１  ηＮ  ２ｎ（２ｎ−１）Ｑ１×Ｎ１＋Ｒ１）
（２ｎ−１）（−Ｑ１×Ｎ０＋Ｒ１×２ｎ）
２ｎ（Ａ１＋Ａ０）（Ｂ１＋Ｂ０）＝２ｎ（（２ｎ−１）Ｑ２＋Ｒ２）＝２ｎ（２ｎ−１）Ｑ２＋２ｎ×Ｒ２
（２ｎ−１）Ａ０×Ｂ０＝（２ｎ−１）（２ｎ×Ｑ３＋Ｒ３）＝２ｎ（２ｎ−１）Ｑ３＋（２ｎ−１）×Ｒ３
Ｋａｒａｔｓｕｂａの補助定理（Ｄ２）から、下記のようになる。
Ａ×Ｂ＝２ｎ（２ｎ−１）Ａ１×Ｂ１＋２ｎ（Ａ１＋Ａ０）×（Ｂ１＋Ｂ０）−（２ｎ−１）Ａ０×Ｂ０
【００３１】
それ故、これから下記の結果が導き出される（何故なら、Ｎ１（２ｎ−１）ηＮ−Ｎ０−Ｎ１であるからである）。
Ａ×Ｂ  ηＮ  −（２ｎ−１）（Ｑ１×Ｎ０＋（Ｑ３−Ｒ１−Ｑ２）×２ｎ）＋２ｎ×Ｒ２−（２ｎ−１）Ｒ３
（２ｎ−１）（Ｑ４×Ｎ１＋Ｒ４）＋２ｎ×Ｒ２−（２ｎ−１）Ｒ３
（Ｎ０＋Ｎ１）Ｑ４＋２ｎ×Ｒ２−（２ｎ−１）（Ｒ３＋Ｒ４）
（２ｎ×Ｑ５＋Ｒ５）＋２ｎ×Ｒ２−（２ｎ−１）（Ｒ３＋Ｒ４）
２ｎ（Ｒ２＋Ｑ５−Ｒ３−Ｒ４）＋（Ｒ３＋Ｒ４＋Ｒ５）
最終的に、
Ａ×Ｂ  ｍｏｄ  Ｎ＝２ｎ（Ｒ２＋Ｑ５−Ｒ３−Ｒ４）＋（Ｒ３＋Ｒ４＋Ｒ５）
になる。これがアルゴリズムＡ２による結果である。
【００３２】
本発明による方法Ａ２は、従来技術により周知の方法ＦＳ２よりも１つ少ないＭｕｌｔＭｏｄＤｉｖ関数を使用することが分かるだろう。それ故、この場合も、同じ結果に対して、実行する演算の全数が少なくなり、そのためこの方法を実行するために使用する全時間および全電力が少なくなる。より詳細に説明すると、１つのＭｕｌｔＭｏｄＤｉｖ演算、または１つのＭｕｌｔＭｏｄＤｉｖＩｎｉｔ演算は、ｎビットの数に対して２回モジュラ乗算を行うので、この場合、アルゴリズムＡ２は、アルゴリズムＦＳ２の場合の１２回のモジュラ乗算の代わりに、ｎビットの数に対して１０回のモジュラ乗算を行うので、Ｄ１の同じ方法ＦＳ２と比較した場合、計算時間の利得は（１２−１０）／１２＝１６％になる。
【００３３】
本発明の第３の実施形態によれば、数Ａ、Ｂ、Ｎは、Ａ＝Ａ１×Ｕ＋Ａ０、Ｂ＝Ｂ１×Ｕ＋Ｂ０、Ｎ＝Ｎ１×Ｕ＋Ｎ０になるように、２ｎ以外の基数Ｕに分解される。Ａ１、Ａ０、Ｂ１、Ｂ０、Ｎ１およびＮ０はｎビットの語である。次に、語Ａ１、Ａ０、Ｂ１、Ｂ０、Ｎ１およびＮ０に対してＭｕｌｔＭｏｄＤｉｖタイプの基本演算が行われる。
【００３４】
第１の例の場合には、下記の方法Ａ３が実行される。
【００３５】
入力：Ａ、Ｂ、Ｎ（２×ｎビットの整数）
以下の形に分解する：
Ａ＝Ａ１×Ｕ＋Ａ０；Ｂ＝Ｂ１×Ｕ＋Ｂ０；Ｎ＝Ｎ１×Ｕ＋Ｎ０
出力：Ａ×Ｂ  ｍｏｄ  Ｎ
演算内容：
（Ｑ１，Ｒ１）＝ＭｕｌｔＭｏｄＤｉｖ（Ａ０，Ｂ０，Ｕ）
（Ｑ２，Ｒ２）＝ＭｕｌｔＭｏｄＤｉｖ（Ａ１＋Ａ０，Ｂ１＋Ｂ０，Ｕ）
（Ｑ３，Ｒ３）＝ＭｕｌｔＭｏｄＤｉｖ（Ａ１，Ｂ１，Ｕ）
（Ｑ４，Ｒ４）＝ＭｕｌｔＭｏｄＤｉｖ（α，Ｑ３，Ｕ）
（Ｑ５，Ｒ５）＝ＭｕｌｔＭｏｄＤｉｖ（α，−Ｑ１＋Ｑ２−Ｑ３＋Ｑ４＋Ｒ３，Ｕ）
戻り（Ｒ５＋Ｒ１）＋（Ｒ４−Ｒ１＋Ｑ１＋Ｒ２−Ｒ３＋Ｑ５）×Ｕ
ここで、α＝Ｕ２  ｍｏｄ  Ｎ
である。
この第１の例の場合、アルゴリズムＡ３は、実際に、モジュラ乗算Ａ×Ｂ  ｍｏｄ  Ｎを行う。α＝Ｕ２  ｍｏｄ  Ｎであるので、Ｕ２  ηＮ  αとなる。さらに、Ｑ１乃至Ｑ５、Ｒ１乃至Ｒ５の定義から下記のようになる。
（Ｕ−１）×Ａ０×Ｂ０  ηＮ  （Ｕ−１）（Ｑ１×Ｕ＋Ｒ１）
ηＮ  Ｑ１×α−Ｒ１＋（Ｒ１−Ｑ１）×Ｕ
Ｕ×（Ａ１＋Ａ０）（Ｂ１＋Ｂ０）  ηＮ  Ｕ（Ｑ２×Ｕ＋Ｒ２）
ηＮ  Ｑ２×α＋Ｒ２×Ｕ
Ｕ（Ｕ−１）×Ａ１×Ｂ１  ηＮ  Ｕ２×Ａ１×Ｂ１−Ｕ×Ａ１×Ｂ１
ηＮ  Ｕ×（Ｒ３×Ｕ＋Ｑ３×α）−Ｕ×（Ｑ３×Ｕ＋Ｒ３）
ηＮ  Ｒ３×α＋Ｑ３×α×Ｕ−Ｑ３×α＋Ｒ３×Ｕ
ηＮ  （−Ｑ３＋Ｒ３）×α＋（−Ｒ３＋Ｑ３×α）×Ｕ
Ｋａｒａｔｓｕｂａの補助定理（Ｄ２）から、下記のようになる。
Ａ×Ｂ＝Ｕ（Ｕ−１）Ａ１×Ｂ１＋Ｕ×（Ａ１＋Ａ０）×（Ｂ１＋Ｂ０）−（Ｕ−１）Ａ０×Ｂ０
すなわち、
Ａ×Ｂ  ηＮ  （−Ｑ３＋Ｒ３）×α＋（−Ｒ３＋Ｑ３×α）×Ｕ
＋Ｑ２×α＋Ｒ２×Ｕ−Ｑ１×α＋Ｒ１−（Ｒ１−Ｑ１）×Ｕ
ηＮ  α（−Ｑ１＋Ｑ２−Ｑ３＋Ｒ３）＋Ｒ１
＋Ｕ（−Ｒ１＋Ｑ１＋Ｒ２−Ｒ３＋Ｑ３×α）
ηＮ  α（−Ｑ１＋Ｑ２−Ｑ３＋Ｒ３）＋Ｒ１
＋Ｕ（Ｑ４×Ｕ＋Ｒ４−Ｒ１＋Ｑ１＋Ｒ２−Ｒ３）
ηＮ  α（−Ｑ１＋Ｑ２−Ｑ３＋Ｑ４＋Ｒ３）＋Ｒ１
＋Ｕ（Ｒ４−Ｒ１＋Ｑ１＋Ｒ２−Ｒ３）
ηＮ  （Ｒ５＋Ｒ１）＋Ｕ（Ｒ４−Ｒ１＋Ｑ１＋Ｒ２−Ｒ３＋Ｑ５）
これは、アルゴリズムＡ３による結果である。
【００３６】
この第１の例の場合、本発明による方法Ａ３は、周知の方法または本発明の第１の実施形態または第２の実施形態より、もっと少ない数のＭｕｌｔＭｏｄＤｉｖ関数を使用することが分かるだろう。それ故、この場合も、同じ結果に対して、実行する演算の全数がさらにもっと少なくなり、そのためこの方法を実行するために使用する全時間および全電力が少なくなる。より詳細に説明すると、１つのＭｕｌｔＭｏｄＤｉｖ演算または１つのＭｕｌｔＭｏｄＤｉｖＩｎｉｔ演算が、ｎビットの数に対して２回モジュラ乗算を行うので、この場合、アルゴリズムＡ３は、アルゴリズムＦＳ１の場合の１４回のモジュラ乗算の代わりに、ｎビットの数に対して１０回のモジュラ乗算を行う。それ故、Ｄ１の同じ方法ＦＳ１と比較した場合、計算時間の利得は（１４−１０）／１４＝２８％になる。
【００３７】
この第１の例を実行するために、例えば、Ｕ＝｜￣√Ｎ￣｜を選択することができる。ここで、√Ｎは、Ｎの平方根であり、｜￣√Ｎ￣｜は、√Ｎの切り上げた整数部である（すなわち、Ｕは、√Ｎより少し大きい丸めた整数である）。Ｕ＝｜￣√（ｋ．Ｎ）￣｜を選択することもできる。ここで、ｋは整数である。好適には、α＝Ｕ２  ｍｏｄ  Ｎができるだけ小さくなるようにｋを選択することが好ましい。
【００３８】
第２の例の場合、Ｕは、式Ｕ２  ηＮ  α＋δ×Ｕにより定義される。αおよびδは、好適には定数であり、できるだけ小さい（２５６ビットより小さい）整数であることが好ましい。好適には、αおよびδは、α＋δ２も定数であり、小さな整数になるように選択することが好ましい。
【００３９】
理想的には、δ＝１、およびα＝−１、２または３であることが望ましい。このような値のα、δは、適当な数Ｎを選択することにより入手することができる。すなわち、適当なキー発生方法を選択することにより入手することができる（この場合、Ｎは、暗号アルゴリズムのためのキーの素子であることを思い起こされたい）。
【００４０】
下記の方法Ａ４を得るために方法Ａ３を簡単にすることができる。
【００４１】
入力：Ａ、Ｂ、Ｎ（２ｎビットの整数）
以下の形に分解する：
Ａ＝Ａ１×Ｕ＋Ａ０；Ｂ＝Ｂ１×Ｕ＋Ｂ０；Ｎ＝Ｎ１×Ｕ＋Ｎ０
出力：Ａ×Ｂ  ｍｏｄ  Ｎ
演算内容：
（Ｑ１，Ｒ１）＝ＭｕｌｔＭｏｄＤｉｖ（Ａ０，Ｂ０，Ｕ）
（Ｑ２，Ｒ２）＝ＭｕｌｔＭｏｄＤｉｖ（Ａ１＋Ａ０，Ｂ１＋Ｂ０，Ｕ）
（Ｑ３，Ｒ３）＝ＭｕｌｔＭｏｄＤｉｖ（Ａ１，Ｂ１，Ｕ）
戻りα×（−Ｑ１＋Ｑ２−Ｑ３＋Ｒ３＋δ×Ｑ３）＋Ｒ１
＋Ｕ×［（−Ｒ１−Ｒ３＋Ｑ１＋Ｒ２＋Ｑ３（α＋δ２）＋（−Ｑ３＋Ｒ３−Ｑ１＋Ｑ２）×δ］
アルゴリズムＡ４は、実際に、モジュラ乗算Ａ×Ｂ  ｍｏｄ  Ｎを行う。Ｕ２  ηＮ  α＋δ×ＵおよびＫａｒａｔｓｕｂａの補助定理を使用することにより、下記のようになる。
（Ｕ−１）×Ａ０×Ｂ０  ηＮ  （Ｕ−１）（Ｑ１×Ｕ＋Ｒ１）
ηＮ  −Ｑ１×Ｕ−Ｒ１＋Ｒ１×Ｕ＋Ｑ１（α＋δ×Ｕ）
ηＮ  Ｑ１×α−Ｒ１＋（Ｒ１−Ｑ１＋Ｑ１×δ）×Ｕ
Ｕ×（Ａ１＋Ａ０）（Ｂ１＋Ｂ０）  ηＮ  Ｕ（Ｑ２×Ｕ＋Ｒ２）
ηＮ  Ｒ２×Ｕ＋Ｑ２×（α＋δＵ）
ηＮ  α×Ｑ２＋（Ｒ２＋δ×Ｑ２）Ｕ
Ｕ×Ａ１×Ｂ１  ηＮ  Ｕ（Ｑ３×Ｕ＋Ｒ３）  ηＮ  αＱ３＋（Ｒ３＋δ×Ｑ３）Ｕ
Ｕ２×Ａ１×Ｂ１  ηＮ  Ｕ（α×Ｑ３＋（Ｒ３＋δ×Ｑ３）×Ｕ）
ηＮ  α×Ｕ×Ｑ３＋（Ｒ３＋δ×Ｑ３）×（α＋δ×Ｕ）
ηＮ  α×（Ｒ３＋δ×Ｑ３）＋（（δ×（Ｒ３＋δ×Ｑ３）＋α×Ｑ３）×Ｕ
Ｕ（Ｕ−１）×Ａ１×Ｂ１  ηＮ  α×（Ｒ３−Ｑ３＋δ×Ｑ３）
＋（（Ｒ３＋δ×Ｑ３）×（δ−１）＋α×Ｑ３）×Ｕ
ηＮ  α×（Ｒ３−Ｑ３＋δ×Ｑ３）
＋［−Ｒ３＋δ×（−Ｑ３＋Ｒ３）＋Ｑ３×（δ２＋α）］×Ｕ
それ故、
Ａ×Ｂ  ηＮ  α×（−Ｑ１＋Ｑ２−Ｑ３＋Ｒ３＋δ×Ｑ３）＋Ｒ１
＋Ｕ×（−Ｒ１−Ｒ３＋Ｑ１＋Ｒ２＋Ｑ３×（α＋δ２）
＋δ×（−Ｑ３＋Ｒ３−Ｑ１＋Ｑ２）
【００４２】
本発明による方法Ａ４は、周知の方法または本発明の第１の実施形態または第２の実施形態より、もっと少ない数のＭｕｌｔＭｏｄＤｉｖ関数を使用することが分かるだろう。それ故、この場合も、同じ結果に対して、実行する演算の全数がさらにもっと少なくなり、そのためこの方法を実行するために使用する全時間および全電力が少なくなる。
【００４３】
第３の例の場合には、下記の方法Ａ５が実行される。
【００４４】
入力：Ａ、Ｂ、Ｎ（２ｎビットの整数）
以下の形に分解する：
Ａ＝Ａ１×Ｕ＋Ａ０；Ｂ＝Ｂ１×Ｕ＋Ｂ０；Ｎ＝Ｎ１×Ｕ＋Ｎ０
出力：Ａ×Ｂ  ｍｏｄ  Ｎ
演算内容：
（Ｘ１，Ｙ１，Ｚ１，Ｒ１）＝係数（Ａ，Ｂ，Ｕ）
（Ｑ２，Ｒ２）＝ＭｕｌｔＭｏｄＤｉｖ（α，Ｘ１，Ｕ）
（Ｑ３，Ｒ３）＝ＭｕｌｔＭｏｄＤｉｖ（α，Ｙ１＋Ｑ２，Ｕ）
戻りＲ１＋Ｒ３＋（Ｒ２＋Ｚ１＋Ｑ３）×Ｕ
係数関数は、基数Ｕで計算を行う。２つの整数Ａ、Ｂからの多項式の係数は、基数Ｕ（Ａ＝Ａ１×Ｘ＋Ａ０およびＢ＝Ｂ１×Ｘ＋Ｂ０）に分解する。
Ｃ３＝ｆ；Ｃ２＝ｄ＋３ｆ；Ｃ１＝ｅ＋２ｆ；Ｃ０＝Ｒ０
のような係数（Ａ，Ｂ，Ｕ）＝（Ｃ３，Ｃ２，Ｃ１，Ｃ０）、ここで、
Ｒ０＝（Ａ  ｍｏｄ  Ｕ）（Ｂ  ｍｏｄ  Ｕ）ｍｏｄ  Ｕ
Ｒ１＝（Ａ  ｍｏｄ（Ｕ＋１））（Ｂ  ｍｏｄ（Ｕ＋１））ｍｏｄ（Ｕ＋１）
Ｒ２＝（Ａ  ｍｏｄ（Ｕ＋２））（Ｂ  ｍｏｄ（Ｕ＋２））ｍｏｄ（Ｕ＋２）
Ｒ３＝（Ａ  ｍｏｄ（２Ｕ＋３））（Ｂ  ｍｏｄ（２Ｕ＋３））ｍｏｄ（２Ｕ＋３）、および
ａ＝（Ｒ０−Ｒ２＋（（Ｒ０−Ｒ２）ｍｏｄ  ２）（Ｕ＋２））／２  ｍｏｄ  Ｕ＋２
ｂ＝Ｒ０−Ｒ１  ｍｏｄ（Ｕ＋１）
ｃ＝（２（Ｒ０−Ｒ３）＋（２（Ｒ０−Ｒ３）ｍｏｄ  ３）（２Ｕ＋３））／３  ｍｏｄ（２Ｕ＋３）
ｄ＝（（ｂ−ａ）ｍｏｄ（Ｕ＋１））
ｅ＝ａ＋２ｄ
ｆ＝−６ｄ＋４ｅ−４ｃ  ｍｏｄ（２Ｕ＋３）
Ｃ３、Ｃ２、Ｃ１、Ｃ０は、Ａ×Ｂ＝Ｃ３×Ｕ３＋Ｃ２×Ｕ２＋Ｃ１×Ｕ＋Ｃ０を確認する。
Ａ＝Ａ１×Ｕ＋Ａ０およびＢ＝Ｂ１×Ｕ＋Ｂ０であるので、Ｒ０、Ｒ１、Ｒ２、Ｒ３は、下式から簡単に計算することができることに留意されたい。
Ｒ０＝Ａ０Ｂ０  ｍｏｄ  Ｕ
Ｒ１＝（Ａ０−Ａ１）（Ｂ０−Ｂ１）ｍｏｄ（Ｕ＋１）
Ｒ２＝（Ａ０−２Ａ１）（Ｂ０−２Ｂ１）ｍｏｄ（Ｕ＋２）
Ｒ３＝（Ａ０＋（Ａ１  ｍｏｄ  ２）Ｕ−３（Ａ１  ｄｉｖ  ２））×（Ｂ０＋（Ｂ１  ｍｏｄ  ２）Ｕ−３（Ｂ１  ｄｉｖ  ２））ｍｏｄ（２Ｕ＋３）
【００４５】
すでに説明したように、計算時間の点では、加算、減算等の補助演算のコストは無視することができる。
【００４６】
アルゴリズムＡ５は、実際に、モジュラ乗算Ａ×Ｂ  ｍｏｄ  Ｎを行う。係数関数の定義を使用することにより、下記のようになる。
【００４７】
Ａ×Ｂ＝Ｘ１×Ｕ３＋Ｙ１×Ｕ２＋Ｚ１×Ｕ＋Ｒ１
ηＮ  Ｒ１＋α×Ｙ１＋（α×Ｘ１＋Ｚ１）×Ｕ
ηＮ  Ｒ１＋α×Ｙ１＋（Ｑ２×Ｕ＋Ｒ２＋Ｚ１）×Ｕ
ηＮ  Ｒ１＋α×（Ｙ１＋Ｑ２）＋（Ｒ２＋Ｚ１）×Ｕ
ηＮ  Ｒ１＋Ｒ３＋（Ｒ２＋Ｚ１＋Ｑ３）×Ｕ
この第３の例の場合、Ｕ＝｜￣√Ｎ￣｜を選択することができる。また、Ｕ＝｜￣√（ｋ．Ｎ）￣｜を選択することもできる。ここで、ｋは整数である。
好適には、Ｕが奇数になり、３で割ることができないようにできるだけ小さいｋを選択することが好ましい。そのため、例えば、Ｕの満足のゆく値が得られるまで、ｋの多数の増大する値を試験する。また、Ｕが奇数になり、３で割ることができないように、またα＝Ｕ２  ｍｏｄ  Ｎができるだけ小さくなるように、できるだけ小さいｋを選択することもできる。
【００４８】
最後に、本発明は、Ｓ＝｜＿（Ｘ×Ｙ）／Ｚ＿｜タイプの演算を行う方法に関する。ここで、Ｘ、Ｙ、Ｚは、ｎビットの数である。この方法は、上記のようなモジュラ乗算を実行するために、またもっと一般的にＭｕｌｔＭｏｄＤｉｖ関数を実行するために使用することができる。この方法を実行している間、下記のステップが実行される。
Ｅ１：変数Δβがゼロに初期化され、２つのデータ項目が計算される。
Ｃ＝Ｘ×Ｙ  ｍｏｄ  ＺおよびＣβ＝Ｘ×Ｙ  ｍｏｄ（Ｚ＋β）（βはｎビットの予め定めた正の整数）。
Ｅ２：結果Ｓ＝［Ｃ−Ｃβ−Δβ（Ｚ＋β）］／βが計算される。
Ｅ３：中間データ項目が整数でない場合には、変数Δβが１だけ増大し、ステップＥ２および次にステップＥ３が反復される。
【００４９】
この方法を上記のように正当化するために、下記のテキストが、最初に、Ｓ＝｜＿ＸＹ／Ｚ＿｜＝［Ｃ−Ｃβ−Δβ（Ｚ＋β）］／βのような整数Δβが存在することを証明する。次に、上記方法によりΔβおよびＳの正しい値を発見することができることが証明される。
βをｎビットの正の整数と仮定して、下記のように定義する。
Ｃ＝Ｘ×Ｙ  ｍｏｄ  Ｚ
Ｃβ＝Ｘ×Ｙ  ｍｏｄ（Ｚ＋β）
Δβ＝｜＿ＸＹ／Ｚ＿｜−｜＿ＸＹ／（Ｚ＋β）＿｜
Δβは、０≦Δβ≦βであることを確認する。実際には、Ｚ＜Ｚ＋βであるので、ＸＹ／（Ｚ＋β）＜ＸＹ／Ｚとなり、ここから、｜＿ＸＹ／（Ｚ＋β）＿｜＜｜＿ＸＹ／Ｚ＿｜が導き出される。さらに、下記のようになる。
ＸＹ／Ｚ＝［ＸＹ／（Ｚ＋β）］×（１＋β／Ｚ）
≦ＸＹ／（Ｚ＋β）＋［（Ｚ−１）２／（（Ｚ＋β）Ｚ）］＜ＸＹ／（Ｚ＋β）＋β
βは整数であるので、｜￣β￣｜＝βとなり、それ故、下記のようになる。
｜＿ＸＹ／Ｚ＿｜≦｜＿ＸＹ／（Ｚ＋β）＿｜＋｜￣β￣｜＝｜＿ＸＹ／（Ｚ＋β）＿｜＋β
【００５０】
これら最後の２つの不等式から下記のように結論することができる。
｜＿ＸＹ／（Ｚ＋β）＿｜≦｜＿ＸＹ／Ｚ＿｜≦｜＿ＸＹ／（Ｚ＋β）＿｜＋β、すなわち、
０≦Δβ≦β
それ故、ＣおよびＣβの定義により、下記のようになる。
ＸＹ＝｜＿ＸＹ／Ｚ＿｜×Ｚ＋Ｃ＝｜＿ＸＹ／（Ｚ＋β）＿｜×（Ｚ＋β）＋Ｃβ
＝（Δβ＋｜＿ＸＹ／Ｚ＿｜）×（Ｚ＋β）＋Ｃβ
すなわち、Ｃ＝｜＿ＸＹ／Ｚ＿｜×β＋Δβ×（Ｚ＋β）＋Ｃβ、およびそれ故、
｜＿ＸＹ／Ｚ＿｜＝［Ｃ−Ｃβ−Δβ×（Ｚ＋β）］／β
（この方法のステップＥ３の計算）
最後の式から、｜＿ＸＹ／Ｚ＿｜は、修正項Δβ（Ｚ＋β）／βを含まない（Ｃ−Ｃβ）／βに等しいと推論することができる。さらに、定義により、βおよびΔβのように、｜＿ＸＹ／Ｚ＿｜は整数である。それ故、Δβの種々の可能な値を使用して組織的に＝［Ｃ−Ｃβ−Δβ×（Ｚ＋β）］／βを計算することにより、また、結果が整数であるかどうかを確認することにより、βの正しい値が計算され、そのため｜＿ＸＹ／Ｚ＿｜の正しい値が計算される。
【００５１】
すでに説明したように、０≦Δβ≦βである。それ故、小さなパラメータβを選択することにより、Δβに対する可能な値の数を制限することができ、それ故、｜＿ＸＹ／Ｚ＿｜の正しい値を入手するために必要な試みの回数を制限することができる。
経験により、（特に計算速度の点で）最善の結果は、ｂの値を２のべき乗と等しくなるように選択した場合に得られることが分かっている。その中でも、β＝２の場合に最善の結果が得られる。その理由は、β＝２の場合、モジュラ減算（Ｃ＝Ｘ×Ｙ  ｍｏｄ  ＺおよびＣβ＝Ｘ×Ｙ  ｍｏｄ（Ｚ＋β））が、Ｚと同じ奇偶性を有するモジュラス（ＺおよびＺ＋２）によってだけ行われ、そのため、偶数のモジュロを使用するモジュラ乗算の計算に関連するすべての困難を避けることができるからである。さらに、β＝２による除算は、計算時間の点でコストが安い。何故なら、このような演算は、レジスタの内容を１ビット右にシフトすることになるからである。最後に、Δβの最大の２つの値（０および１）を試験しなければならない。
【国際調査報告】
2007503036.tif 000002
2007503036.tif 000003
2007503036.tif 000004
2007503036.tif 000005
2007503036.tif 000006
2007503036.tif 000007