(57)【特許請求の範囲】
【請求項１】
以下の式で表わされ、素体Ｆp上定義された楕円曲線Ｅ上の点Ｐ1＝（ｘ1，ｙ1）を、アファイン座標系において２k倍（ｋは２以上の整数）した点Ｐ2k＝（ｘ2k，ｙ2k）を求める演算装置であって、以下の要素を有する演算装置
Ｅ：ｙ2＝ｘ3＋ａｘ＋ｂ  ｍｏｄ  ｐ
（１）素数ｐと、素体Ｆp上の元ａ及び元ｂと、点Ｐ1の座標ｘ1及び座標ｙ1と、整数ｋとを入力する入力手段、
（２）入力された素数ｐと、元ａと、元ｂと、座標ｘ1と、座標ｙ1と、整数ｋとを記憶する記憶手段、
（３）座標ｘ1と、素数ｐとを読み出し、以下の式により、配列要素Ａ1を求めるＡ1演算手段、
Ａ1＝ｘ1  ｍｏｄ  ｐ
（４）求めた配列要素Ａ1を記憶するＡ1記憶手段、
（５）座標ｘ1と、元ａと、素数ｐとを読み出し、以下の式により、配列要素Ｂ1を求めるＢ1演算手段、
Ｂ1＝３ｘ12＋ａ  ｍｏｄ  ｐ
（６）求めた配列要素Ｂ1を記憶するＢ1記憶手段、
（７）座標ｙ1と、素数ｐとを読み出し、以下の式により、配列要素Ｃ1を求めるＣ1演算手段、
Ｃ1＝−ｙ1  ｍｏｄ  ｐ
（８）求めた配列要素Ｃ1を記憶するＣ1記憶手段、
（９）変数ｉを記憶するｉ記憶手段、
（１０）ｉ記憶手段に、変数ｉの初期値２を設定するｉ初期値設定手段、
（１１）整数ｋと、変数ｉとを読み出し、変数ｉが整数ｋに達するまで変数ｉに順次１を加えて、ｉ記憶手段に設定するｉインクリメント手段、
（１２）ｉ記憶手段に変数ｉが設定される度に、変数ｉと、素数ｐとを読み出し、更に、読み出した変数ｉにより特定される配列要素Ａi-1と、配列要素Ｂi-1と、配列要素Ｃi-1とを読み出し、以下の式により、配列要素Ａiを求めるＡi演算手段、
Ａi＝Ｂi-12−８Ａi-1Ｃi-12  ｍｏｄ  ｐ
（１３）求めた配列要素Ａiを記憶するＡi記憶手段、
（１４）ｉ記憶手段に変数ｉが設定される度に、変数ｉと、元ａと、素数Ｐとを読み出し、更に読み出した変数ｉにより特定される配列要素Ａiと、配列要素Ｃ1からＣi-1を読み出し、以下の式により、配列要素Ｂiを求めるＢi演算手段、
【数１】
0004550232.tif 000011
（１５）求めた配列要素Ｂiを記憶するＢi記憶手段、
（１６）ｉ記憶手段に変数ｉが設定される度に、変数ｉと、素数Ｐとを読み出し、更に読み出した変数ｉにより特定される配列要素ＡiとＡi-1と、配列要素Ｂi-1と、配列要素Ｃi-1とを読み出し、以下の式により、配列要素Ｃiを求めるＣi演算手段、
Ｃi＝−８Ｃi-14−Ｂi-1（Ａi−４Ａi-1Ｃi-12）  ｍｏｄ  ｐ
（１７）求めた配列要素Ｃiを記憶するＣi記憶手段、
（１８）整数ｋと、素数Ｐとを読み出し、更に読み出した整数ｋにより特定される配列要素Ａkと、配列要素Ｂkと、配列要素Ｃkとを読み出し、以下の式により、数値Ｄkを求めるＤk演算手段、
Ｄk＝１２ＡkＣk2−Ｂk2  ｍｏｄ  ｐ
（１９）求めた数値Ｄｋを記憶するＤｋ記憶手段、
（２０）整数ｋと、素数Ｐとを読み出し、更に読み出した整数ｋにより特定される配列要素Ａkと、配列要素Ｂkと、配列要素Ｃ1からＣkとを読み出し、以下の式により、座標ｘ2kを求めるｘ2k演算手段、
【数２】
0004550232.tif 000012
（２１）整数ｋと、素数Ｐとを読み出し、更に読み出した整数ｋにより特定される配列要素Ｂkと、配列要素Ｃ1からＣkと、配列要素Ｄkとを読み出し、以下の式により、座標ｙ2kを求めるｙ2k演算手段、
【数３】
0004550232.tif 000013
（２２）求めた座標ｘ2kと、座標ｙ2kとを出力する出力手段。
【請求項２】
以下の式で表わされ、素体Ｆp上定義された楕円曲線Ｅ上の点Ｐ1＝（Ｘ1，Ｙ1，Ｚ1）を、重み付き射影座標系において４倍した点Ｐ4＝（Ｘ4，Ｙ4，Ｚ4）を求める演算装置であって、以下の要素を有する演算装置
Ｅ：ｙ2＝ｘ3＋ａｘ＋ｂ  ｍｏｄ  ｐ
（１）素数ｐと、素体Ｆp上の元ａ及び元ｂと、点Ｐ1の座標Ｘ1、座標Ｙ1及び座標Ｚ1とを入力する入力手段、
（２）入力された素数ｐと、元ａと、元ｂと、座標Ｘ1と、座標Ｙ1と、座標Ｚ1とを記憶する記憶手段、
（３）元ａと、座標Ｘ1と、座標Ｚ1と、素数ｐとを読み出し、以下の式により、数値Ａを求めるＡ演算手段、
Ａ＝  ３Ｘ12＋ａＺ14  ｍｏｄ  ｐ
（４）求めた数値Ａを記憶するＡ記憶手段、
（５）数値Ａと、座標Ｘ1と、座標Ｙ1と、素数ｐとを読み出し、以下の式により、数値Ｂを求めるＢ演算手段、
Ｂ＝Ａ2−８Ｘ1Ｙ12  ｍｏｄ  ｐ
（６）求めた数値Ｂを記憶するＢ記憶手段、
（７）数値Ａと、座標Ｘ1と、座標Ｙ1と、素数ｐとを読み出し、以下の式により、数値Ｃを求めるＣ演算手段、
Ｃ＝−８Ｙ14＋Ａ（１２Ｘ1Ｙ12−Ａ2）  ｍｏｄ  ｐ
（８）求めた数値Ｃを記憶するＣ記憶手段、
（９）元ａと、数値Ｂと、座標Ｙ1と、座標Ｚ1と、素数ｐとを読み出し、以下の式により、数値Ｄを求めるＤ演算手段、
Ｄ＝１６ａＹ14Ｚ14＋３Ｂ2  ｍｏｄ  ｐ
（１０）求めた数値Ｄを記憶するＤ記憶手段、
（１１）数値Ｂ、数値Ｃ、数値Ｄと、素数ｐとを読み出し、以下の式により、座標Ｘ4を求めるＸ4演算手段、
Ｘ4＝−８ＢＣ2＋Ｄ2  ｍｏｄ  ｐ
（１２）数値Ｂ、数値Ｃ、数値Ｄと、素数ｐを読み出し、以下の式により、座標Ｙ4を求めるＹ4演算手段、
Ｙ4＝−８Ｃ4＋Ｄ（１２ＢＣ2−Ｄ2）  ｍｏｄ  ｐ
（１３）座標Ｙ1と、座標Ｚ1と、数値Ｃと、素数ｐとを読み出し、以下の式により、座標Ｚ4を求めるＺ4演算手段、
Ｚ4＝４Ｙ1Ｚ1Ｃ  ｍｏｄ  ｐ
（１４）求めた座標Ｘ4と、座標Ｙ4と、座標Ｚ4を出力する出力手段。
【請求項３】
以下の式で表わされ、素体Ｆp上定義された楕円曲線Ｅ上の点Ｐ1＝（ｘ1，ｙ1）を、アファイン座標系において２k倍（ｋは２以上の整数）した点Ｐ2k＝（ｘ2k，ｙ2k）を求める演算方法であって、以下の要素を有する演算方法
Ｅ：ｙ2＝ｘ3＋ａｘ＋ｂ  ｍｏｄ  ｐ
（１）素数ｐと、素体Ｆp上の元ａ及び元ｂと、点Ｐ1の座標ｘ1及び座標ｙ1と、整数ｋとを入力する入力工程、
（２）入力された素数ｐと、元ａと、元ｂと、座標ｘ1と、座標ｙ1と、整数ｋとを記憶する記憶工程、
（３）座標ｘ1と、素数ｐとを読み出し、以下の式により、配列要素Ａ1を求めるＡ1演算工程、
Ａ1＝ｘ1  ｍｏｄ  ｐ
（４）求めた配列要素Ａ1を記憶するＡ1記憶工程、
（５）座標ｘ1と、元ａと、素数ｐとを読み出し、以下の式により、配列要素Ｂ1を求めるＢ1演算工程、
Ｂ1＝３ｘ12＋ａ  ｍｏｄ  ｐ
（６）求めた配列要素Ｂ1を記憶するＢ1記憶工程、
（７）座標ｙ1と、素数ｐとを読み出し、以下の式により、配列要素Ｃ1を求めるＣ1演算工程、
Ｃ1＝−ｙ1  ｍｏｄ  ｐ
（８）求めた配列要素Ｃ1を記憶するＣ1記憶工程、
（９）変数ｉの初期値２を設定するｉ初期値設定工程、
（１０）整数ｋと、変数ｉとを読み出し、変数ｉが整数ｋに達するまで変数ｉに順次１を加えて、設定するｉインクリメント工程、
（１１）変数ｉが設定される度に、変数ｉと、素数ｐとを読み出し、更に、読み出した変数ｉにより特定される配列要素Ａi-1と、配列要素Ｂi-1と、配列要素Ｃi-1とを読み出し、以下の式により、配列要素Ａiを求めるＡi演算工程、
Ａi＝Ｂi-12−８Ａi-1Ｃi-12  ｍｏｄ  ｐ
（１２）求めた配列要素Ａiを記憶するＡi記憶工程、
（１３）変数ｉが設定される度に、変数ｉと、元ａと、素数Ｐとを読み出し、更に読み出した変数ｉにより特定される配列要素Ａiと、配列要素Ｃ1からＣi-1を読み出し、以下の式により、配列要素Ｂiを求めるＢi演算工程、
【数４】
0004550232.tif 000014
（１４）求めた配列要素Ｂiを記憶するＢi記憶工程、
（１５）変数ｉが設定される度に、変数ｉと、素数Ｐとを読み出し、更に読み出した変数ｉにより特定される配列要素ＡiとＡi-1と、配列要素Ｂi-1と、配列要素Ｃi-1とを読み出し、以下の式により、配列要素Ｃiを求めるＣi演算工程、
Ｃi＝−８Ｃi-14−Ｂi-1（Ａi−４Ａi-1Ｃi-12）  ｍｏｄ  ｐ
（１６）求めた配列要素Ｃiを記憶するＣi記憶工程、
（１７）整数ｋと、素数Ｐとを読み出し、更に読み出した整数ｋにより特定される配列要素Ａkと、配列要素Ｂkと、配列要素Ｃkとを読み出し、以下の式により、数値Ｄkを求めるＤk演算工程、
Ｄk＝１２ＡkＣk2−Ｂk2  ｍｏｄ  ｐ
（１８）求めた数値Ｄｋを記憶するＤｋ記憶工程、
（１９）整数ｋと、素数Ｐとを読み出し、更に読み出した整数ｋにより特定される配列要素Ａkと、配列要素Ｂkと、配列要素Ｃ1からＣkとを読み出し、以下の式により、座標ｘ2kを求めるｘ2k演算工程、
【数５】
0004550232.tif 000015
（２０）整数ｋと、素数Ｐとを読み出し、更に読み出した整数ｋにより特定される配列要素Ｂkと、配列要素Ｃ1からＣkと、配列要素Ｄkとを読み出し、以下の式により、座標ｙ2kを求めるｙ2k演算工程、
【数６】
0004550232.tif 000016
（２１）求めた座標ｘ2kと、座標ｙ2kとを出力する出力工程。
【請求項４】
以下の式で表わされ、素体Ｆp上定義された楕円曲線Ｅ上の点Ｐ1＝（Ｘ1，Ｙ1，Ｚ1）を、重み付き射影座標系において４倍した点Ｐ4＝（Ｘ4，Ｙ4，Ｚ4）を求める演算方法であって、以下の要素を有する演算方法
Ｅ：ｙ2＝ｘ3＋ａｘ＋ｂ  ｍｏｄ  ｐ
（１）素数ｐと、素体Ｆp上の元ａ及び元ｂと、点Ｐ1の座標Ｘ1、座標Ｙ1及び座標Ｚ1とを入力する入力工程、
（２）入力された素数ｐと、元ａと、元ｂと、座標Ｘ1と、座標Ｙ1と、座標Ｚ1とを記憶する記憶工程、
（３）元ａと、座標Ｘ1と、座標Ｚ1と、素数ｐとを読み出し、以下の式により、数値Ａを求めるＡ演算工程、
Ａ＝  ３Ｘ12＋ａＺ14  ｍｏｄ  ｐ
（４）求めた数値Ａを記憶するＡ記憶工程、
（５）数値Ａと、座標Ｘ1と、座標Ｙ1と、素数ｐとを読み出し、以下の式により、数値Ｂを求めるＢ演算工程、
Ｂ＝Ａ2−８Ｘ1Ｙ12  ｍｏｄ  ｐ
（６）求めた数値Ｂを記憶するＢ記憶工程、
（７）数値Ａと、座標Ｘ1と、座標Ｙ1と、素数ｐとを読み出し、以下の式により、数値Ｃを求めるＣ演算工程、
Ｃ＝−８Ｙ14＋Ａ（１２Ｘ1Ｙ12−Ａ2）  ｍｏｄ  ｐ
（８）求めた数値Ｃを記憶するＣ記憶工程、
（９）元ａと、数値Ｂと、座標Ｙ1と、座標Ｚ1と、素数ｐとを読み出し、以下の式により、数値Ｄを求めるＤ演算工程、
Ｄ＝１６ａＹ14Ｚ14＋３Ｂ2  ｍｏｄ  ｐ
（１０）求めた数値Ｄを記憶するＤ記憶工程、
（１１）数値Ｂ、数値Ｃ、数値Ｄと、素数ｐとを読み出し、以下の式により、座標Ｘ4を求めるＸ4演算工程、
Ｘ4＝−８ＢＣ2＋Ｄ2  ｍｏｄ  ｐ
（１２）数値Ｂ、数値Ｃ、数値Ｄと、素数ｐを読み出し、以下の式により、座標Ｙ4を求めるＹ4演算工程、
Ｙ4＝−８Ｃ4＋Ｄ（１２ＢＣ2−Ｄ2）  ｍｏｄ  ｐ
（１３）座標Ｙ1と、座標Ｚ1と、数値Ｃと、素数ｐとを読み出し、以下の式により、座標Ｚ4を求めるＺ4演算工程、
Ｚ4＝４Ｙ1Ｚ1Ｃ  ｍｏｄ  ｐ
（１４）求めた座標Ｘ4と、座標Ｙ4と、座標Ｚ4を出力する出力工程。
【請求項５】
以下の式で表わされ、素体Ｆp上定義された楕円曲線Ｅ上の点Ｐ1＝（ｘ1，ｙ1）を、アファイン座標系において２k倍（ｋは２以上の整数）した点Ｐ2k＝（ｘ2k，ｙ2k）を求める演算装置となるコンピュータに、以下の処理を実行させるためのプログラムを記録したコンピュータ読み取り可能な記録媒体
Ｅ：ｙ2＝ｘ3＋ａｘ＋ｂ  ｍｏｄ  ｐ
（１）素数ｐと、素体Ｆp上の元ａ及び元ｂと、点Ｐ1の座標ｘ1及び座標ｙ1と、整数ｋとを入力する入力処理、
（２）入力された素数ｐと、元ａと、元ｂと、座標ｘ1と、座標ｙ1と、整数ｋとを記憶する記憶処理、
（３）座標ｘ1と、素数ｐとを読み出し、以下の式により、配列要素Ａ1を求めるＡ1演算処理、
Ａ1＝ｘ1  ｍｏｄ  ｐ
（４）求めた配列要素Ａ1を記憶するＡ1記憶処理、
（５）座標ｘ1と、元ａと、素数ｐとを読み出し、以下の式により、配列要素Ｂ1を求めるＢ1演算処理、
Ｂ1＝３ｘ12＋ａ  ｍｏｄ  ｐ
（６）求めた配列要素Ｂ1を記憶するＢ1記憶処理、
（７）座標ｙ1と、素数ｐとを読み出し、以下の式により、配列要素Ｃ1を求めるＣ1演算処理、
Ｃ1＝−ｙ1  ｍｏｄ  ｐ
（８）求めた配列要素Ｃ1を記憶するＣ1記憶処理、
（９）変数ｉの初期値２を設定するｉ初期値設定処理、
（１０）整数ｋと、変数ｉとを読み出し、変数ｉが整数ｋに達するまで変数ｉに順次１を加えて、設定するｉインクリメント処理、
（１１）変数ｉが設定される度に、変数ｉと、素数ｐとを読み出し、更に、読み出した変数ｉにより特定される配列要素Ａi-1と、配列要素Ｂi-1と、配列要素Ｃi-1とを読み出し、以下の式により、配列要素Ａiを求めるＡi演算処理、
Ａi＝Ｂi-12−８Ａi-1Ｃi-12  ｍｏｄ  ｐ
（１２）求めた配列要素Ａiを記憶するＡi記憶処理、
（１３）変数ｉが設定される度に、変数ｉと、元ａと、素数Ｐとを読み出し、更に読み出した変数ｉにより特定される配列要素Ａiと、配列要素Ｃ1からＣi-1を読み出し、以下の式により、配列要素Ｂiを求めるＢi演算処理、
【数７】
0004550232.tif 000017
（１４）求めた配列要素Ｂiを記憶するＢi記憶処理、
（１５）変数ｉが設定される度に、変数ｉと、素数Ｐとを読み出し、更に読み出した変数ｉにより特定される配列要素ＡiとＡi-1と、配列要素Ｂi-1と、配列要素Ｃi-1とを読み出し、以下の式により、配列要素Ｃiを求めるＣi演算処理、
Ｃi＝−８Ｃi-14−Ｂi-1（Ａi−４Ａi-1Ｃi-12）  ｍｏｄ  ｐ
（１６）求めた配列要素Ｃiを記憶するＣi記憶処理、
（１７）整数ｋと、素数Ｐとを読み出し、更に読み出した整数ｋにより特定される配列要素Ａkと、配列要素Ｂkと、配列要素Ｃkとを読み出し、以下の式により、数値Ｄkを求めるＤk演算処理、
Ｄk＝１２ＡkＣk2−Ｂk2  ｍｏｄ  ｐ
（１８）求めた数値Ｄｋを記憶するＤｋ記憶処理、
（１９）整数ｋと、素数Ｐとを読み出し、更に読み出した整数ｋにより特定される配列要素Ａkと、配列要素Ｂkと、配列要素Ｃ1からＣkとを読み出し、以下の式により、座標ｘ2kを求めるｘ2k演算処理、
【数８】
0004550232.tif 000018
（２０）整数ｋと、素数Ｐとを読み出し、更に読み出した整数ｋにより特定される配列要素Ｂkと、配列要素Ｃ1からＣkと、配列要素Ｄkとを読み出し、以下の式により、座標ｙ2kを求めるｙ2k演算処理、
【数９】
0004550232.tif 000019
（２１）求めた座標ｘ2kと、座標ｙ2kとを出力する出力処理。
【請求項６】
以下の式で表わされ、素体Ｆp上定義された楕円曲線Ｅ上の点Ｐ1＝（Ｘ1，Ｙ1，Ｚ1）を、重み付き射影座標系において４倍した点Ｐ4＝（Ｘ4，Ｙ4，Ｚ4）を求める演算装置となるコンピュータに、以下の処理を実行させるためのプログラムを記録したコンピュータ読み取り可能な記録媒体
Ｅ：ｙ2＝ｘ3＋ａｘ＋ｂ  ｍｏｄ  ｐ
（１）素数ｐと、素体Ｆp上の元ａ及び元ｂと、点Ｐ1の座標Ｘ1、座標Ｙ1及び座標Ｚ1とを入力する入力処理、
（２）入力された素数ｐと、元ａと、元ｂと、座標Ｘ1と、座標Ｙ1と、座標Ｚ1とを記憶する記憶処理、
（３）元ａと、座標Ｘ1と、座標Ｚ1と、素数ｐとを読み出し、以下の式により、数値Ａを求めるＡ演算処理、
Ａ＝  ３Ｘ12＋ａＺ14  ｍｏｄ  ｐ
（４）求めた数値Ａを記憶するＡ記憶処理、
（５）数値Ａと、座標Ｘ1と、座標Ｙ1と、素数ｐとを読み出し、以下の式により、数値Ｂを求めるＢ演算処理、
Ｂ＝Ａ2−８Ｘ1Ｙ12  ｍｏｄ  ｐ
（６）求めた数値Ｂを記憶するＢ記憶処理、
（７）数値Ａと、座標Ｘ1と、座標Ｙ1と、素数ｐとを読み出し、以下の式により、数値Ｃを求めるＣ演算処理、
Ｃ＝−８Ｙ14＋Ａ（１２Ｘ1Ｙ12−Ａ2）  ｍｏｄ  ｐ
（８）求めた数値Ｃを記憶するＣ記憶処理、
（９）元ａと、数値Ｂと、座標Ｙ1と、座標Ｚ1と、素数ｐとを読み出し、以下の式により、数値Ｄを求めるＤ演算処理、
Ｄ＝１６ａＹ14Ｚ14＋３Ｂ2  ｍｏｄ  ｐ
（１０）求めた数値Ｄを記憶するＤ記憶処理、
（１１）数値Ｂ、数値Ｃ、数値Ｄと、素数ｐとを読み出し、以下の式により、座標Ｘ4を求めるＸ4演算処理、
Ｘ4＝−８ＢＣ2＋Ｄ2  ｍｏｄ  ｐ
（１２）数値Ｂ、数値Ｃ、数値Ｄと、素数ｐを読み出し、以下の式により、座標Ｙ4を求めるＹ4演算処理、
Ｙ4＝−８Ｃ4＋Ｄ（１２ＢＣ2−Ｄ2）  ｍｏｄ  ｐ
（１３）座標Ｙ1と、座標Ｚ1と、数値Ｃと、素数ｐとを読み出し、以下の式により、座標Ｚ4を求めるＺ4演算処理、
Ｚ4＝４Ｙ1Ｚ1Ｃ  ｍｏｄ  ｐ
（１４）求めた座標Ｘ4と、座標Ｙ4と、座標Ｚ4を出力する出力処理。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、楕円曲線上の点の演算方法およびそれを用いた暗号化方法に関する。
【０００２】
【従来の技術】
従来の楕円曲線上の点の演算方法について説明する。従来の楕円曲線上の点の演算方法は、Ｋｏｂｌｉｔｚ著、“Ａ  Ｃｏｕｒｓｅ  ｉｎ  Ｎｕｍｂｅｒ  Ｔｈｅｏｒｙ  ａｎｄ  Ｃｒｙｐｔｏｇｒａｐｈｙ”、ｓｐｒｉｎｇｅｒ、（１９９４）に記載されている。また、楕円曲線を用いた暗号化方法については、岡本龍明、山本博資著、“現代暗号”、産業図書（１９９７）に記載されている。
【０００３】
まず本発明の技術的背景である公開鍵暗号、離散対数問題および楕円曲線について簡単に説明する。公開鍵暗号通信においては、利用者ごとに秘密鍵ｘと公開鍵ｙの組が用意され、秘密鍵ｘは、各利用者が秘密に保持しておく。公開鍵ｙは利用者自身以外の一般に公開する。利用者Ｂが利用者Ａに秘密にデータを送りたい時は、利用者Ｂは利用者Ａに対応する公開鍵ｙを用いてデータを暗号化する。
この暗号文は、秘密鍵ｘを知る利用者Ａにしか復号できない。
離散対数問題とは群Ｇ（加法が定義されているものとする）の２つの要素ｇ1，ｇ2に対して、ｇ1＝ｍｇ2を満たすようなｍを求める問題である。群Ｇの要素の数が大きい場合、離散対数問題を解くことは、計算量的に非常に困難になることが知られている。この事実を利用して公開鍵暗号を設計することができる。
素体Ｆp上の楕円曲線Ｅとは、ｙ2＝ｘ3＋ａｘ＋ｂ  ｍｏｄ  ｐと表される方程式である。楕円曲線上の有理点集合Ｅ（Ｆp）には加法が定義され、群となる。
【０００４】
図５、図６は、従来の楕円曲線の演算方法を示すフローチャートである。図５は、素体上定義された楕円曲線において、アファイン座標系で２倍点を計算する方法、図６は、素体上定義された楕円曲線において、重み付き射影座標系で２倍点を計算する方法を示すフローチャートである。図５において、まず楕円曲線（のパラメータ）と曲線上の点Ｐ1が入力される。Ｓ５０１はλを計算するステップ、Ｓ５０２はｘ2を計算するステップ、Ｓ５０３はｙ2を計算するステップであり、Ｐ1の２倍点Ｐ2が出力される。図６において、まず楕円曲線（のパラメータ）と曲線上の点Ｐ1が入力される。Ｓ６０１はＭを計算するステップ、Ｓ６０２はＺ2を計算するステップ、Ｓ６０３はＳを計算するステップ、Ｓ６０４はＸ2を計算するステップ、Ｓ６０５はＴを計算するステップ、Ｓ６０６はＹ2を計算するステップであり、Ｐ1の２倍点Ｐ2が出力される。
【０００５】
次に動作を説明する。まずアファイン座標系における２倍点の計算方法を図５に基づいて説明する。素体Ｆp上の楕円曲線Ｅ：ｙ2＝ｘ3＋ａｘ＋ｂ  ｍｏｄ  ｐとＥ上の点Ｐ1＝（ｘ1，ｙ1）がまず入力される。各ステップにおける演算は全て定義体Ｆp上の演算となる。この方法の演算量は、自乗算２回、乗算２回、逆元算１回である。
次に重み付き射影座標系における２倍点の計算方法を図６に基づいて説明する。素体Ｆp上の楕円曲線Ｅ：ｙ2＝ｘ3＋ａｘ＋ｂ  ｍｏｄ  ｐとＥ上の点Ｐ1＝（Ｘ1，Ｙ1，Ｚ1）がまず入力される。各ステップにおける演算は全て定義体Ｆp上の演算となる。この方法の演算量は、自乗算６回、乗算４回である。
【０００６】
【発明が解決しようとする課題】
従来の素体Ｆp上の楕円曲線の２倍点の計算方法は、以上のように構成されており、４倍点や８倍点、一般に２k倍点を直接計算する方法が与えられていない。従って、例えば４倍点を計算するためには、２倍算を２回繰り返さなければならず、演算量が多いという課題があった。特に、アファイン座標系における演算では、２倍算１回に対して定義体上の逆元算が１回必要である。一般に逆元算は乗算と比較して計算量が多い。
【０００７】
本発明の目的は、係る課題を解決するためになされたもので、２k倍点計算する時に、２倍算をｋ回繰り返すことなく直接計算し、高速な演算方法を得ることにある。
【０００８】
【課題を解決するための手段】
この発明に係る演算装置は、以下の式で表わされ、素体Ｆp上定義された楕円曲線Ｅ上の点Ｐ1＝（ｘ1，ｙ1）を、アファイン座標系において２k倍（ｋは２以上の整数）した点Ｐ2k＝（ｘ2k，ｙ2k）を求める演算装置であって、以下の要素を有することを特徴とする。
Ｅ：ｙ2＝ｘ3＋ａｘ＋ｂ  ｍｏｄ  ｐ
（１）素数ｐと、素体Ｆp上の元ａ及び元ｂと、点Ｐ1の座標ｘ1及び座標ｙ1と、整数ｋとを入力する入力手段、
（２）入力された素数ｐと、元ａと、元ｂと、座標ｘ1と、座標ｙ1と、整数ｋとを記憶する記憶手段、
（３）座標ｘ1と、素数ｐとを読み出し、以下の式により、配列要素Ａ1を求めるＡ1演算手段、
Ａ1＝ｘ1  ｍｏｄ  ｐ
（４）求めた配列要素Ａ1を記憶するＡ1記憶手段、
（５）座標ｘ1と、元ａと、素数ｐとを読み出し、以下の式により、配列要素Ｂ1を求めるＢ1演算手段、
Ｂ1＝３ｘ12＋ａ  ｍｏｄ  ｐ
（６）求めた配列要素Ｂ1を記憶するＢ1記憶手段、
（７）座標ｙ1と、素数ｐとを読み出し、以下の式により、配列要素Ｃ1を求めるＣ1演算手段、
Ｃ1＝−ｙ1  ｍｏｄ  ｐ
（８）求めた配列要素Ｃ1を記憶するＣ1記憶手段、
（９）変数ｉを記憶するｉ記憶手段、
（１０）ｉ記憶手段に、変数ｉの初期値２を設定するｉ初期値設定手段、
（１１）整数ｋと、変数ｉとを読み出し、変数ｉが整数ｋに達するまで変数ｉに順次１を加えて、ｉ記憶手段に設定するｉインクリメント手段、
（１２）ｉ記憶手段に変数ｉが設定される度に、変数ｉと、素数ｐとを読み出し、更に、読み出した変数ｉにより特定される配列要素Ａi-1と、配列要素Ｂi-1と、配列要素Ｃi-1とを読み出し、以下の式により、配列要素Ａiを求めるＡi演算手段、
Ａi＝Ｂi-12−８Ａi-1Ｃi-12  ｍｏｄ  ｐ
（１３）求めた配列要素Ａiを記憶するＡi記憶手段、
（１４）ｉ記憶手段に変数ｉが設定される度に、変数ｉと、元ａと、素数Ｐとを読み出し、更に読み出した変数ｉにより特定される配列要素Ａiと、配列要素Ｃ1からＣi-1を読み出し、以下の式により、配列要素Ｂiを求めるＢi演算手段、
【数１０】
0004550232.tif 000002
（１５）求めた配列要素Ｂiを記憶するＢi記憶手段、
（１６）ｉ記憶手段に変数ｉが設定される度に、変数ｉと、素数Ｐとを読み出し、更に読み出した変数ｉにより特定される配列要素ＡiとＡi-1と、配列要素Ｂi-1と、配列要素Ｃi-1とを読み出し、以下の式により、配列要素Ｃiを求めるＣi演算手段、
Ｃi＝−８Ｃi-14−Ｂi-1（Ａi−４Ａi-1Ｃi-12）  ｍｏｄ  ｐ
（１７）求めた配列要素Ｃiを記憶するＣi記憶手段、
（１８）整数ｋと、素数Ｐとを読み出し、更に読み出した整数ｋにより特定される配列要素Ａkと、配列要素Ｂkと、配列要素Ｃkとを読み出し、以下の式により、数値Ｄkを求めるＤk演算手段、
Ｄk＝１２ＡkＣk2−Ｂk2  ｍｏｄ  ｐ
（１９）求めた数値Ｄｋを記憶するＤｋ記憶手段、
（２０）整数ｋと、素数Ｐとを読み出し、更に読み出した整数ｋにより特定される配列要素Ａkと、配列要素Ｂkと、配列要素Ｃ1からＣkとを読み出し、以下の式により、座標ｘ2kを求めるｘ2k演算手段、
【数１１】
0004550232.tif 000003
（２１）整数ｋと、素数Ｐとを読み出し、更に読み出した整数ｋにより特定される配列要素Ｂkと、配列要素Ｃ1からＣkと、配列要素Ｄkとを読み出し、以下の式により、座標ｙ2kを求めるｙ2k演算手段、
【数１２】
0004550232.tif 000004
（２２）求めた座標ｘ2kと、座標ｙ2kとを出力する出力手段。
【０００９】
この発明に係る演算装置は、以下の式で表わされ、素体Ｆp上定義された楕円曲線Ｅ上の点Ｐ1＝（Ｘ1，Ｙ1，Ｚ1）を、重み付き射影座標系において４倍した点Ｐ4＝（Ｘ4，Ｙ4，Ｚ4）を求める演算装置であって、以下の要素を有することを特徴とする。
Ｅ：ｙ2＝ｘ3＋ａｘ＋ｂ  ｍｏｄ  ｐ
（１）素数ｐと、素体Ｆp上の元ａ及び元ｂと、点Ｐ1の座標Ｘ1、座標Ｙ1及び座標Ｚ1とを入力する入力手段、
（２）入力された素数ｐと、元ａと、元ｂと、座標Ｘ1と、座標Ｙ1と、座標Ｚ1とを記憶する記憶手段、
（３）元ａと、座標Ｘ1と、座標Ｚ1と、素数ｐとを読み出し、以下の式により、数値Ａを求めるＡ演算手段、
Ａ＝  ３Ｘ12＋ａＺ14  ｍｏｄ  ｐ
（４）求めた数値Ａを記憶するＡ記憶手段、
（５）数値Ａと、座標Ｘ1と、座標Ｙ1と、素数ｐとを読み出し、以下の式により、数値Ｂを求めるＢ演算手段、
Ｂ＝Ａ2−８Ｘ1Ｙ12  ｍｏｄ  ｐ
（６）求めた数値Ｂを記憶するＢ記憶手段、
（７）数値Ａと、座標Ｘ1と、座標Ｙ1と、素数ｐとを読み出し、以下の式により、数値Ｃを求めるＣ演算手段、
Ｃ＝−８Ｙ14＋Ａ（１２Ｘ1Ｙ12−Ａ2）  ｍｏｄ  ｐ
（８）求めた数値Ｃを記憶するＣ記憶手段、
（９）元ａと、数値Ｂと、座標Ｙ1と、座標Ｚ1と、素数ｐとを読み出し、以下の式により、数値Ｄを求めるＤ演算手段、
Ｄ＝１６ａＹ14Ｚ14＋３Ｂ2  ｍｏｄ  ｐ
（１０）求めた数値Ｄを記憶するＤ記憶手段、
（１１）数値Ｂ、数値Ｃ、数値Ｄと、素数ｐとを読み出し、以下の式により、座標Ｘ4を求めるＸ4演算手段、
Ｘ4＝−８ＢＣ2＋Ｄ2  ｍｏｄ  ｐ
（１２）数値Ｂ、数値Ｃ、数値Ｄと、素数ｐを読み出し、以下の式により、座標Ｙ4を求めるＹ4演算手段、
Ｙ4＝−８Ｃ4＋Ｄ（１２ＢＣ2−Ｄ2）  ｍｏｄ  ｐ
（１３）座標Ｙ1と、座標Ｚ1と、数値Ｃと、素数ｐとを読み出し、以下の式により、座標Ｚ4を求めるＺ4演算手段、
Ｚ4＝４Ｙ1Ｚ1Ｃ  ｍｏｄ  ｐ
（１４）求めた座標Ｘ4と、座標Ｙ4と、座標Ｚ4を出力する出力手段。
【００１０】
この発明に係る演算方法は、以下の式で表わされ、素体Ｆp上定義された楕円曲線Ｅ上の点Ｐ1＝（ｘ1，ｙ1）を、アファイン座標系において２k倍（ｋは２以上の整数）した点Ｐ2k＝（ｘ2k，ｙ2k）を求める演算方法であって、以下の要素を有することを特徴とする。
Ｅ：ｙ2＝ｘ3＋ａｘ＋ｂ  ｍｏｄ  ｐ
（１）素数ｐと、素体Ｆp上の元ａ及び元ｂと、点Ｐ1の座標ｘ1及び座標ｙ1と、整数ｋとを入力する入力工程、
（２）入力された素数ｐと、元ａと、元ｂと、座標ｘ1と、座標ｙ1と、整数ｋとを記憶する記憶工程、
（３）座標ｘ1と、素数ｐとを読み出し、以下の式により、配列要素Ａ1を求めるＡ1演算工程、
Ａ1＝ｘ1  ｍｏｄ  ｐ
（４）求めた配列要素Ａ1を記憶するＡ1記憶工程、
（５）座標ｘ1と、元ａと、素数ｐとを読み出し、以下の式により、配列要素Ｂ1を求めるＢ1演算工程、
Ｂ1＝３ｘ12＋ａ  ｍｏｄ  ｐ
（６）求めた配列要素Ｂ1を記憶するＢ1記憶工程、
（７）座標ｙ1と、素数ｐとを読み出し、以下の式により、配列要素Ｃ1を求めるＣ1演算工程、
Ｃ1＝−ｙ1  ｍｏｄ  ｐ
（８）求めた配列要素Ｃ1を記憶するＣ1記憶工程、
（９）変数ｉの初期値２を設定するｉ初期値設定工程、
（１０）整数ｋと、変数ｉとを読み出し、変数ｉが整数ｋに達するまで変数ｉに順次１を加えて、設定するｉインクリメント工程、
（１１）変数ｉが設定される度に、変数ｉと、素数ｐとを読み出し、更に、読み出した変数ｉにより特定される配列要素Ａi-1と、配列要素Ｂi-1と、配列要素Ｃi-1とを読み出し、以下の式により、配列要素Ａiを求めるＡi演算工程、
Ａi＝Ｂi-12−８Ａi-1Ｃi-12  ｍｏｄ  ｐ
（１２）求めた配列要素Ａiを記憶するＡi記憶工程、
（１３）変数ｉが設定される度に、変数ｉと、元ａと、素数Ｐとを読み出し、更に読み出した変数ｉにより特定される配列要素Ａiと、配列要素Ｃ1からＣi-1を読み出し、以下の式により、配列要素Ｂiを求めるＢi演算工程、
【数１３】
0004550232.tif 000005
（１４）求めた配列要素Ｂiを記憶するＢi記憶工程、
（１５）変数ｉが設定される度に、変数ｉと、素数Ｐとを読み出し、更に読み出した変数ｉにより特定される配列要素ＡiとＡi-1と、配列要素Ｂi-1と、配列要素Ｃi-1とを読み出し、以下の式により、配列要素Ｃiを求めるＣi演算工程、
Ｃi＝−８Ｃi-14−Ｂi-1（Ａi−４Ａi-1Ｃi-12）  ｍｏｄ  ｐ
（１６）求めた配列要素Ｃiを記憶するＣi記憶工程、
（１７）整数ｋと、素数Ｐとを読み出し、更に読み出した整数ｋにより特定される配列要素Ａkと、配列要素Ｂkと、配列要素Ｃkとを読み出し、以下の式により、数値Ｄkを求めるＤk演算工程、
Ｄk＝１２ＡkＣk2−Ｂk2  ｍｏｄ  ｐ
（１８）求めた数値Ｄｋを記憶するＤｋ記憶工程、
（１９）整数ｋと、素数Ｐとを読み出し、更に読み出した整数ｋにより特定される配列要素Ａkと、配列要素Ｂkと、配列要素Ｃ1からＣkとを読み出し、以下の式により、座標ｘ2kを求めるｘ2k演算工程、
【数１４】
0004550232.tif 000006
（２０）整数ｋと、素数Ｐとを読み出し、更に読み出した整数ｋにより特定される配列要素Ｂkと、配列要素Ｃ1からＣkと、配列要素Ｄkとを読み出し、以下の式により、座標ｙ2kを求めるｙ2k演算工程、
【数１５】
0004550232.tif 000007
（２１）求めた座標ｘ2kと、座標ｙ2kとを出力する出力工程。
【００１１】
この発明に係る演算方法は、以下の式で表わされ、素体Ｆp上定義された楕円曲線Ｅ上の点Ｐ1＝（Ｘ1，Ｙ1，Ｚ1）を、重み付き射影座標系において４倍した点Ｐ4＝（Ｘ4，Ｙ4，Ｚ4）を求める演算方法であって、以下の要素を有することを特徴とする。
Ｅ：ｙ2＝ｘ3＋ａｘ＋ｂ  ｍｏｄ  ｐ
（１）素数ｐと、素体Ｆp上の元ａ及び元ｂと、点Ｐ1の座標Ｘ1、座標Ｙ1及び座標Ｚ1とを入力する入力工程、
（２）入力された素数ｐと、元ａと、元ｂと、座標Ｘ1と、座標Ｙ1と、座標Ｚ1とを記憶する記憶工程、
（３）元ａと、座標Ｘ1と、座標Ｚ1と、素数ｐとを読み出し、以下の式により、数値Ａを求めるＡ演算工程、
Ａ＝  ３Ｘ12＋ａＺ14  ｍｏｄ  ｐ
（４）求めた数値Ａを記憶するＡ記憶工程、
（５）数値Ａと、座標Ｘ1と、座標Ｙ1と、素数ｐとを読み出し、以下の式により、数値Ｂを求めるＢ演算工程、
Ｂ＝Ａ2−８Ｘ1Ｙ12  ｍｏｄ  ｐ
（６）求めた数値Ｂを記憶するＢ記憶工程、
（７）数値Ａと、座標Ｘ1と、座標Ｙ1と、素数ｐとを読み出し、以下の式により、数値Ｃを求めるＣ演算工程、
Ｃ＝−８Ｙ14＋Ａ（１２Ｘ1Ｙ12−Ａ2）  ｍｏｄ  ｐ
（８）求めた数値Ｃを記憶するＣ記憶工程、
（９）元ａと、数値Ｂと、座標Ｙ1と、座標Ｚ1と、素数ｐとを読み出し、以下の式により、数値Ｄを求めるＤ演算工程、
Ｄ＝１６ａＹ14Ｚ14＋３Ｂ2  ｍｏｄ  ｐ
（１０）求めた数値Ｄを記憶するＤ記憶工程、
（１１）数値Ｂ、数値Ｃ、数値Ｄと、素数ｐとを読み出し、以下の式により、座標Ｘ4を求めるＸ4演算工程、
Ｘ4＝−８ＢＣ2＋Ｄ2  ｍｏｄ  ｐ
（１２）数値Ｂ、数値Ｃ、数値Ｄと、素数ｐを読み出し、以下の式により、座標Ｙ4を求めるＹ4演算工程、
Ｙ4＝−８Ｃ4＋Ｄ（１２ＢＣ2−Ｄ2）  ｍｏｄ  ｐ
（１３）座標Ｙ1と、座標Ｚ1と、数値Ｃと、素数ｐとを読み出し、以下の式により、座標Ｚ4を求めるＺ4演算工程、
Ｚ4＝４Ｙ1Ｚ1Ｃ  ｍｏｄ  ｐ
（１４）求めた座標Ｘ4と、座標Ｙ4と、座標Ｚ4を出力する出力工程。
【００１２】
この発明に係るプログラムを記録したコンピュータ読み取り可能な記録媒体は、以下の式で表わされ、素体Ｆp上定義された楕円曲線Ｅ上の点Ｐ1＝（ｘ1，ｙ1）を、アファイン座標系において２k倍（ｋは２以上の整数）した点Ｐ2k＝（ｘ2k，ｙ2k）を求める演算装置となるコンピュータに、以下の処理を実行させるためのプログラムを記録したコンピュータ読み取り可能な記録媒体であることを特徴とする。
Ｅ：ｙ2＝ｘ3＋ａｘ＋ｂ  ｍｏｄ  ｐ
（１）素数ｐと、素体Ｆp上の元ａ及び元ｂと、点Ｐ1の座標ｘ1及び座標ｙ1と、整数ｋとを入力する入力処理、
（２）入力された素数ｐと、元ａと、元ｂと、座標ｘ1と、座標ｙ1と、整数ｋとを記憶する記憶処理、
（３）座標ｘ1と、素数ｐとを読み出し、以下の式により、配列要素Ａ1を求めるＡ1演算処理、
Ａ1＝ｘ1  ｍｏｄ  ｐ
（４）求めた配列要素Ａ1を記憶するＡ1記憶処理、
（５）座標ｘ1と、元ａと、素数ｐとを読み出し、以下の式により、配列要素Ｂ1を求めるＢ1演算処理、
Ｂ1＝３ｘ12＋ａ  ｍｏｄ  ｐ
（６）求めた配列要素Ｂ1を記憶するＢ1記憶処理、
（７）座標ｙ1と、素数ｐとを読み出し、以下の式により、配列要素Ｃ1を求めるＣ1演算処理、
Ｃ1＝−ｙ1  ｍｏｄ  ｐ
（８）求めた配列要素Ｃ1を記憶するＣ1記憶処理、
（９）変数ｉの初期値２を設定するｉ初期値設定処理、
（１０）整数ｋと、変数ｉとを読み出し、変数ｉが整数ｋに達するまで変数ｉに順次１を加えて、設定するｉインクリメント処理、
（１１）変数ｉが設定される度に、変数ｉと、素数ｐとを読み出し、更に、読み出した変数ｉにより特定される配列要素Ａi-1と、配列要素Ｂi-1と、配列要素Ｃi-1とを読み出し、以下の式により、配列要素Ａiを求めるＡi演算処理、
Ａi＝Ｂi-12−８Ａi-1Ｃi-12  ｍｏｄ  ｐ
（１２）求めた配列要素Ａiを記憶するＡi記憶処理、
（１３）変数ｉが設定される度に、変数ｉと、元ａと、素数Ｐとを読み出し、更に読み出した変数ｉにより特定される配列要素Ａiと、配列要素Ｃ1からＣi-1を読み出し、以下の式により、配列要素Ｂiを求めるＢi演算処理、
【数１６】
0004550232.tif 000008
（１４）求めた配列要素Ｂiを記憶するＢi記憶処理、
（１５）変数ｉが設定される度に、変数ｉと、素数Ｐとを読み出し、更に読み出した変数ｉにより特定される配列要素ＡiとＡi-1と、配列要素Ｂi-1と、配列要素Ｃi-1とを読み出し、以下の式により、配列要素Ｃiを求めるＣi演算処理、
Ｃi＝−８Ｃi-14−Ｂi-1（Ａi−４Ａi-1Ｃi-12）  ｍｏｄ  ｐ
（１６）求めた配列要素Ｃiを記憶するＣi記憶処理、
（１７）整数ｋと、素数Ｐとを読み出し、更に読み出した整数ｋにより特定される配列要素Ａkと、配列要素Ｂkと、配列要素Ｃkとを読み出し、以下の式により、数値Ｄkを求めるＤk演算処理、
Ｄk＝１２ＡkＣk2−Ｂk2  ｍｏｄ  ｐ
（１８）求めた数値Ｄｋを記憶するＤｋ記憶処理、
（１９）整数ｋと、素数Ｐとを読み出し、更に読み出した整数ｋにより特定される配列要素Ａkと、配列要素Ｂkと、配列要素Ｃ1からＣkとを読み出し、以下の式により、座標ｘ2kを求めるｘ2k演算処理、
【数１７】
0004550232.tif 000009
（２０）整数ｋと、素数Ｐとを読み出し、更に読み出した整数ｋにより特定される配列要素Ｂkと、配列要素Ｃ1からＣkと、配列要素Ｄkとを読み出し、以下の式により、座標ｙ2kを求めるｙ2k演算処理、
【数１８】
0004550232.tif 000010
（２１）求めた座標ｘ2kと、座標ｙ2kとを出力する出力処理。
【００１３】
この発明に係るプログラムを記録したコンピュータ読み取り可能な記録媒体は、以下の式で表わされ、素体Ｆp上定義された楕円曲線Ｅ上の点Ｐ1＝（Ｘ1，Ｙ1，Ｚ1）を、重み付き射影座標系において４倍した点Ｐ4＝（Ｘ4，Ｙ4，Ｚ4）を求める演算装置となるコンピュータに、以下の処理を実行させるためのプログラムを記録したコンピュータ読み取り可能な記録媒体であることを特徴とする。
Ｅ：ｙ2＝ｘ3＋ａｘ＋ｂ  ｍｏｄ  ｐ
（１）素数ｐと、素体Ｆp上の元ａ及び元ｂと、点Ｐ1の座標Ｘ1、座標Ｙ1及び座標Ｚ1とを入力する入力処理、
（２）入力された素数ｐと、元ａと、元ｂと、座標Ｘ1と、座標Ｙ1と、座標Ｚ1とを記憶する記憶処理、
（３）元ａと、座標Ｘ1と、座標Ｚ1と、素数ｐとを読み出し、以下の式により、数値Ａを求めるＡ演算処理、
Ａ＝  ３Ｘ12＋ａＺ14  ｍｏｄ  ｐ
（４）求めた数値Ａを記憶するＡ記憶処理、
（５）数値Ａと、座標Ｘ1と、座標Ｙ1と、素数ｐとを読み出し、以下の式により、数値Ｂを求めるＢ演算処理、
Ｂ＝Ａ2−８Ｘ1Ｙ12  ｍｏｄ  ｐ
（６）求めた数値Ｂを記憶するＢ記憶処理、
（７）数値Ａと、座標Ｘ1と、座標Ｙ1と、素数ｐとを読み出し、以下の式により、数値Ｃを求めるＣ演算処理、
Ｃ＝−８Ｙ14＋Ａ（１２Ｘ1Ｙ12−Ａ2）  ｍｏｄ  ｐ
（８）求めた数値Ｃを記憶するＣ記憶処理、
（９）元ａと、数値Ｂと、座標Ｙ1と、座標Ｚ1と、素数ｐとを読み出し、以下の式により、数値Ｄを求めるＤ演算処理、
Ｄ＝１６ａＹ14Ｚ14＋３Ｂ2  ｍｏｄ  ｐ
（１０）求めた数値Ｄを記憶するＤ記憶処理、
（１１）数値Ｂ、数値Ｃ、数値Ｄと、素数ｐとを読み出し、以下の式により、座標Ｘ4を求めるＸ4演算処理、
Ｘ4＝−８ＢＣ2＋Ｄ2  ｍｏｄ  ｐ
（１２）数値Ｂ、数値Ｃ、数値Ｄと、素数ｐを読み出し、以下の式により、座標Ｙ4を求めるＹ4演算処理、
Ｙ4＝−８Ｃ4＋Ｄ（１２ＢＣ2−Ｄ2）  ｍｏｄ  ｐ
（１３）座標Ｙ1と、座標Ｚ1と、数値Ｃと、素数ｐとを読み出し、以下の式により、座標Ｚ4を求めるＺ4演算処理、
Ｚ4＝４Ｙ1Ｚ1Ｃ  ｍｏｄ  ｐ
（１４）求めた座標Ｘ4と、座標Ｙ4と、座標Ｚ4を出力する出力処理。
【００１４】
【発明の実施の形態】
実施の形態１．
図１は、実施の形態１における素体上定義された楕円曲線の、アファイン座標系における２k倍点の演算方法を示したフローチャートである。図において、まず楕円曲線（のパラメータ）と曲線上の点Ｐ1が入力される。Ｓ１０１はＡ1、Ｂ1、Ｃ1を演算するステップ、Ｓ１０２は２≦ｉ≦ｋに対してＡi、Ｂi、Ｃiを演算するステップ、Ｓ１０３はＤkを演算するステップ、Ｓ１０４はｘ2k、ｙ2kを演算するステップであり、Ｐ1のｋ倍点Ｐ2kが出力される。
【００１５】
次に動作を説明する。まず、１６０ビット程度の大きな素数ｐと、有限体Ｆp上の２つの元ａ、ｂを選択する。その際、楕円曲線の有理点群Ｅ（Ｆp）の位数＃Ｅ（Ｆp）が大きな素数で割り切れるようにｐ、ａ、ｂを選択する。以上により楕円曲線Ｅ：ｙ2＝ｘ3＋ａｘ＋ｂ  ｍｏｄ  ｐが選択されたことになる。この楕円曲線Ｅと、Ｅ上の点Ｐ1＝（ｘ1，ｙ1）を入力し、Ｐ1の２k倍点Ｐ2k＝（ｘ2k，ｙ2k）を演算する。図の各ステップにおける演算は全て定義体Ｆp上の演算となる。この方法の演算量は、自乗算４ｋ＋１回、乗算４ｋ＋２回、逆元算１回である。
【００１６】
以上のように演算すれば、定義体上の逆元演算を１回行うだけで、２k倍点を計算することができ、高速に計算できる。尚、従来の演算方法では、２倍算をｋ回繰り返していたために、逆元演算がｋ回必要であった。
【００１７】
本演算方法を、楕円曲線を用いた暗号化やディジタル署名に使用することもできる。
【００１８】
実施の形態２．
図２は、実施の形態２における素体上定義された楕円曲線の重み付き射影座標系における４倍点の演算方法を示したフローチャートである。図において、まず楕円曲線（のパラメータ）と曲線上の点Ｐ1が入力される。Ｓ２０１はＡ、Ｂ、Ｃ、Ｄを演算するステップ、Ｓ２０２はＸ4、Ｙ4、Ｚ4を演算するステップであり、Ｐ1の４倍点Ｐ4が出力される。
【００１９】
次に動作を説明する。まず、１６０ビット程度の大きな素数ｐと、有限体Ｆp上の２つの元ａ，ｂを選択する。その際、楕円曲線の有理点群Ｅ（Ｆp）の位数＃Ｅ（Ｆp）が大きな素数で割り切れるようにｐ、ａ、ｂを選択する。以上により楕円曲線Ｅ：ｙ2＝ｘ3＋ａｘ＋ｂ  ｍｏｄ  ｐが選択されたことになる。この楕円曲線Ｅと、Ｅ上の点Ｐ1＝（Ｘ1，Ｙ1，Ｚ1）を入力し、Ｐ1の４倍点Ｐ4＝（ｘ4，ｙ4）を演算する。図の各ステップにおける演算は全て定義体Ｆp上の演算となる。この方法の演算量は、自乗算１０回、乗算９回である。
【００２０】
従来の演算方法では、４倍点を計算するために２倍算を２回繰り返していたため、自乗算１２回、乗算８回の演算が必要であった。したがって、本発明の演算方法の方が高速に演算できる。
【００２１】
本演算方法を、楕円曲線を用いた暗号化やディジタル署名に使用することもできる。
【００２２】
実施の形態３．
図３は、実施の形態３による素体上定義された楕円曲線のアファイン座標系における２k倍点の演算装置を示した図である。本実施の形態における演算装置は、実施の形態１における演算方法を用いた装置である。図において、３０１は入力手段、３０２は記憶手段、３０３は法ｐでの乗算手段、３０４は法ｐでの自乗算手段、３０５は法ｐでの加算手段、３０６は法ｐでの減算手段、３０７は法ｐでの単精度整数との乗算手段、３０８は法ｐでの逆元算手段、３０９と３１０と３１１と３１２は演算手段、３１３は出力手段、３１４は装置全体を制御する制御手段である。３０２はメモリ、３０３〜３１２及び３１４はＣＰＵである。
【００２３】
次に動作を説明する。まず、楕円曲線Ｅのパラメータ（１６０ビット程度の大きな素数ｐと、有限体Ｆp上の２つの元ａ、ｂ）と、Ｅ上の点Ｐ1＝（ｘ1，ｙ1）と、正整数ｋが入力手段３０１に入力される。その際、楕円曲線の有理点群Ｅ（Ｆp）の位数＃Ｅ（Ｆp）が大きな素数で割り切れるようにｐ、ａ、ｂはあらかじめ選択されている。この装置では、点Ｐ1＝（ｘ1，ｙ1）の２k倍点Ｐ2k＝（ｘ2k，ｙ2k）が演算される。
【００２４】
まず、演算手段３０９において、Ａ1、Ｂ1、Ｃ1が演算される。各演算において、自乗算は法ｐ自乗算手段３０４、加算は法ｐ加算手段３０５、減算は法ｐ減算手段３０６、整数３との乗算は法ｐ単精度乗算手段３０７を用いて演算される。演算されたＡ1、Ｂ1、Ｃ1は、記憶手段３０２に記憶される。
【００２５】
次に、演算手段３１０において、Ａi、Ｂi、Ｃiが、ｉ＝２からｋの順に演算される。Ａj、Ｂj、Ｃjを演算する際、Ａj-1、Ｂj-1、Ｃj-1を適宜記憶手段３０２から読み出して演算する。また、演算されたＡj、Ｂj、Ｃjは、記憶手段３０２に記憶される。また、各演算において、法ｐ乗算手段３０３、法ｐ自乗算手段３０４、法ｐ加算手段３０５、法ｐ減算手段３０６、法ｐ単精度演算手段３０７が使用される。演算手段３１０において最終的に演算されたＡk、Ｂk、Ｃkは、記憶手段３０２に記憶される。
【００２６】
次に、演算手段３１１において、Ｄkが演算される。Ａk、Ｂk、Ｃkは記憶手段３０２から読み出され、整数“１２”との乗算は法ｐ単精度乗算手段３０７が使用され、乗算は法ｐ乗算手段３０３が使用され、自乗算は法ｐ自乗算手段３０４が使用され、減算は法ｐ減算手段３０６が使用される。演算されたＤkは記憶手段３０２に記憶される。
【００２７】
次に、演算手段３１２において、ｘ2k、ｙ2kが演算される。これまでと同様、各演算では、３０３〜３０７が使用される。なお、ｋΠki=1Ｃiの法ｐでの逆元は、法ｐ逆元算手段３０８を用いて演算される。本装置において法ｐ逆元算手段３０８が使用されるのは、この１回だけである。
【００２８】
最後に、演算されたｘ2k、ｙ2kは出力手段３１３から出力される。
【００２９】
以上のようにｘ2k、ｙ2kを演算すれば、定義体上Ｆpの逆元演算を１回行うだけで、２k倍点を演算することができ、高速に計算できる。尚、従来の演算方法では、２倍算をｋ回繰り返していたために、逆元演算がｋ回必要であった。
【００３０】
本演算装置を、楕円曲線を用いた暗号化やディジタル署名に使用することもできる。
【００３１】
実施の形態４．
図４は、実施の形態４による素体上定義された楕円曲線の重み付き射影座標系における４倍点の演算装置を示した図である。本実施の形態における演算装置は、実施の形態２における演算方法を用いた装置である。図において、４０１は入力手段、４０２は記憶手段、４０３は法ｐでの乗算手段、４０４は法ｐでの自乗算手段、４０５は法ｐでの加算手段、４０６は法ｐでの減算手段、４０７は法ｐでの単精度整数との乗算手段、４０８と４０９は演算手段、４１０は出力手段、４１１は装置全体を制御する制御手段である。４０２はメモリ、４０３〜４０９及び４１１はＣＰＵである。
【００３２】
次に動作を説明する。まず、楕円曲線Ｅのパラメータ（１６０ビット程度の大きな素数ｐと、有限体Ｆp上の２つの元ａ、ｂ）と、Ｅ上の点Ｐ1＝（Ｘ1，Ｙ1，Ｚ1）が入力手段４０１に入力される。その際、楕円曲線の有理点群Ｅ（Ｆp）の位数＃Ｅ（Ｆp）が大きな素数で割り切れるようにｐ、ａ、ｂはあらかじめ選択されている。この装置では、点Ｐ1＝（Ｘ1，Ｙ1，Ｚ1）の４倍点Ｐ4＝（Ｘ4，Ｙ4，Ｚ4）が演算される。
【００３３】
まず、演算手段４０８において、Ａ、Ｂ、Ｃ、Ｄが演算される。各演算において、乗算は法ｐ乗算手段４０３、自乗算は法ｐ自乗算手段４０４、加算は法ｐ加算手段４０５、減算は法ｐ減算手段４０６、単精度整数との乗算は法ｐ単精度乗算手段４０７を用いて演算される。演算されたＡ、Ｂ、Ｃ、Ｄは、記憶手段４０２に記憶される。
【００３４】
次に、演算手段４０９において、Ｘ4、Ｙ4、Ｚ4が演算される。演算する際、Ａ、Ｂ、Ｃ、Ｄを適宜記憶手段４０２から読み出して演算する。また、各演算において、乗算は法ｐ乗算手段４０３、自乗算は法ｐ自乗算手段４０４、加算は法ｐ加算手段４０５、減算は法ｐ減算手段４０６、単精度整数との乗算は法ｐ単精度乗算手段４０７を用いて演算される。
【００３５】
最後に、演算されたＸ4、Ｙ4、Ｚ4は出力手段４１０から出力される。
【００３６】
以上のように演算すれば、法ｐによる自乗算１０回、乗算９回で４倍点が計算できる。尚、従来の演算方法では、４倍点を計算するために２倍算を２回繰り返していたため、自乗算１２回、乗算８回の演算が必要であった。したがって、本発明の演算方法の方が高速に計算できる。
【００３７】
本演算装置を、楕円曲線を用いた暗号化やディジタル署名に使用することもできる。
【００３８】
各実施の形態に関し、入力処理、記憶処理、読み出し処理、演算処理、初期値設定処理、出力処理等の処理を、コンピュータ読み取り可能なプログラムとして記録媒体に記録し、演算装置となるコンピュータがそのプログラムを読み取り、プログラムを記憶するメモリにロードし、プログラムに含まれる処理を順次読み出し実行することにより実現することが可能である。
また、入力手段、及び出力手段は、モジュールのインターフェースとして用いられる記憶手段であっても構わない。
【００３９】
【発明の効果】
以上のように、本発明による演算方法は、楕円曲線演算を高速に行うことができる。
また、本発明による演算方法を利用することにより、楕円曲線を用いた暗号化やディジタル署名を高速に行うことができる。
【００４０】
以上のようにｘ2k、ｙ2kを演算すれば、定義体上Ｆpの逆元演算を１回行うだけで、２k倍点を演算することができ、高速に計算できる。尚、従来の演算方法では、２倍算をｋ回繰り返していたために、逆元演算がｋ回必要であった。
【００４１】
以上のように演算すれば、法ｐによる自乗算１０回、乗算９回で４倍点が計算できる。尚、従来の演算方法では、４倍点を計算するために２倍算を２回繰り返していたため、自乗算１２回、乗算８回の演算が必要であった。したがって、本発明の演算方法の方が高速に計算できる。
【図面の簡単な説明】
【図１】  本発明の演算方法を説明するフローチャートである。
【図２】  本発明の演算方法を説明するフローチャートである。
【図３】  本発明の演算装置を説明する図である。
【図４】  本発明の演算装置を説明する図である。
【図５】  従来の演算方法を説明するフローチャートである。
【図６】  従来の演算方法を説明するフローチャートである。
【符号の説明】
３０１，４０１  入力手段、３０２，４０２  記憶手段、３０３，４０３  法ｐ乗算手段、３０４，４０４  法ｐ自乗算手段、３０５，４０５  法ｐ加算手段、３０６，４０６  法ｐ減算手段、３０７，４０７  法ｐ単精度乗算手段、３０８  法ｐ逆元算手段、３０９，３１０，３１１，３１２，４０８，４０９  演算手段、３１３，４１０  出力手段、３１４，４１１  制御手段。
【図１】
0004550232.tif 000020
【図２】
0004550232.tif 000021
【図３】
0004550232.tif 000022
【図４】
0004550232.tif 000023
【図５】
0004550232.tif 000024
【図６】
0004550232.tif 000025