(57)【特許請求の範囲】
【請求項１】
ｐを奇素数または奇素数のべき乗とし、ｍを素数でない整数とした場合における、拡大体ＧＦ（ｐｍ  ）上の元が入力され、拡大体ＧＦ（ｐｍ  ）上の元を出力する拡大体上の演算装置であって、
ｑ０  ＝ｐ，ｑ１  ＝ｐｓ１，ｑ２  ＝（ｐｓ１）ｓ２，…，ｑｚ  ＝（（（ｐｓ１）ｓ２）…）ｓｚ＝ｐｍ  とし、ｓ１，ｓ２， …，ｓｚをｍ＝ｓ１  ｓ２  …ｓｚ  を満たす値とし、ｎ＝１，２，．．．，ｚとした場合における、ＧＦ（ｑｎ−１  ）上の元によって表されたＧＦ（ｑｎ）上の元の乗算又は自乗を３／４法を用いて行うＧＦ（ｑｎ  ）演算手段を有し、
上記ＧＦ（ｑｊ  ）演算手段（ｊ＝２，３，．．．，ｚ）における乗算又は自乗結果がＧＦ（ｑｊ−１  ）上の元の乗算又は自乗を含む場合に、この乗算又は自乗をさらに上記ＧＦ（ｑｊ−１  ）演算手段が３／４法を用いて行う処理を繰り返す、
ことを特徴とする逐次拡大を用いた楕円曲線演算装置。
【請求項２】
請求項１記載の演算装置であって、
上記ＧＦ（ｑｎ  ）演算手段は、
既約多項式ｘ２−ｖ１ｎ・ｘ−ｖ０ｎ＝０（ｖ１ｎ及びｖ０ｎはＧＦ（ｑｎ−１）上の元）の根αに対する多項式基底｛１，α｝を用い、ＧＦ（ｑｎ）上の元Ａ，Ｂ及びＡ×Ｂを、ＧＦ（ｑｎ−１）上の元によって表現したものを、それぞれ（Ａ０，Ａ１），（Ｂ０，Ｂ１）及び（Ｃ０，Ｃ１）とした場合における、
入力されたＡ０  およびＢ０  に対してＡ０  ×Ｂ０  を計算してその演算結果Ｌ０  を出力する第１のＧＦ（ｑｎ−１  ）乗算器と、
入力されたＡ０  およびＡ１  に対してＡ０  ＋Ａ１  を計算してその演算結果Ｌ１  を出力する第１のＧＦ（ｑｎ−１  ）加算器と、
入力されたＢ０  およびＢ１  に対してＢ０  ＋Ｂ１  を計算してその演算結果Ｌ２  を出力する第２のＧＦ（ｑｎ−１  ）加算器と、
入力されたＡ１  およびＢ１  に対してＡ１  ×Ｂ１  を計算してその演算結果Ｌ３  を出力する第２のＧＦ（ｑｎ−１  ）乗算器と、
入力されたＬ１  およびＬ２  に対してＬ１  ×Ｌ２  を計算してその演算結果Ｌ４  を出力する第３のＧＦ（ｑｎ−１  ）乗算器と、
入力されたＬ３  に対してｔｎ  ・Ｌ３  を計算してその演算結果Ｌ５  を出力する第１のＧＦ（ｑｎ−１  ）定数倍器と、
入力されたＬ０  およびＬ４  に対してＬ４  −Ｌ０  を計算してその演算結果Ｌ６  を出力するＧＦ（ｑｎ−１  ）減算器と、
入力されたＬ３  に対して（ｓｎ  −１）・Ｌ３  を計算してその演算結果Ｌ７  を出力する第２のＧＦ（ｑｎ−１  ）定数倍器と、
入力されたＬ０  およびＬ５  に対してＬ０  ＋Ｌ５  を計算してその演算結果Ｃ０  を出力する第３のＧＦ（ｑｎ−１  ）加算器と、
入力されたＬ６  およびＬ７  に対してＬ６  ＋Ｌ７  を計算してその演算結果Ｃ１  を出力する第４のＧＦ（ｑｎ−１  ）加算器と、
を有するＧＦ（ｑｎ  ）乗算器であることを特徴とする逐次拡大を用いた楕円曲線演算装置。
【請求項３】
請求項１記載の演算装置であって、
上記ＧＦ（ｑｎ  ）演算手段は、
既約多項式ｘ２−ｖ１ｎ・ｘ−ｖ０ｎ＝０（ｖ１ｎ及びｖ０ｎはＧＦ（ｑｎ−１）上の元）の根αに対する正規基底｛α，αｐ｝を用い、ＧＦ（ｑｎ）上の元Ａ，Ｂ及びＡ×Ｂを、ＧＦ（ｑｎ−１）上の元によって表現したものを、それぞれ（Ａ０，Ａ１），（Ｂ０，Ｂ１）及び（Ｃ０，Ｃ１）とした場合における、
入力されたＡ０  およびＢ０  に対してＡ０  ×Ｂ０  を計算してその演算結果Ｌ０  を出力する第１のＧＦ（ｑｎ−１  ）乗算器と、
入力されたＡ０  およびＡ１  に対してＡ０  −Ａ１  を計算してその演算結果Ｌ１  を出力する第１のＧＦ（ｑｎ−１  ）減算器と、
入力されたＢ０  およびＢ１  に対してＢ０  −Ｂ１  を計算してその演算結果Ｌ２  を出力する第２のＧＦ（ｑｎ−１  ）減算器と、
入力されたＡ１  およびＢ１  に対してＡ１  ×Ｂ１  を計算してその演算結果Ｌ３  を出力する第２のＧＦ（ｑｎ−１  ）乗算器と、
入力されたＬ０  に対してｓｎ  ・Ｌ０  を計算してその演算結果Ｌ４  を出力する第１のＧＦ（ｑｎ−１  ）定数倍器と、
入力されたＬ１  およびＬ２  に対してＬ１  ×Ｌ２  を計算してその演算結果Ｌ５  を出力する第３のＧＦ（ｑｎ−１  ）乗算器と、
入力されたＬ３  に対してｓｎ  ・Ｌ３  を計算してその演算結果Ｌ６  を出力する第２のＧＦ（ｑｎ−１  ）定数倍器と、
入力されたＬ５  に対して（ｓｎ  −１・ｔｎ  ）・Ｌ５  を計算してその演算結果Ｌ７  を出力する第３のＧＦ（ｑｎ−１  ）定数倍器と、
入力されたＬ４  およびＬ７  に対してＬ４  ＋Ｌ７  を計算してその演算結果Ｃ０  を出力する第１のＧＦ（ｑｎ−１  ）加算器と、
入力されたＬ６  およびＬ７  に対してＬ６  ＋Ｌ７  を計算してその演算結果Ｃ１  を出力する第２のＧＦ（ｑｎ−１  ）加算器と、
を有するＧＦ（ｑｎ  ）乗算器であることを特徴とする逐次拡大を用いた楕円曲線演算装置。
【請求項４】
請求項１記載の演算装置であって、
上記ＧＦ（ｑｎ  ）演算手段は、
既約多項式ｘ２−ｖ１ｎ・ｘ−ｖ０ｎ＝０（ｖ１ｎ及びｖ０ｎはＧＦ（ｑｎ−１）上の元）の根αに対する正規基底｛α，αｐ｝を用い、ＧＦ（ｑｎ）上の元Ａ及びＡ２を、ＧＦ（ｑｎ−１）上の元によって表現したものを、それぞれ（Ａ０，Ａ１）及び（Ｃ０，Ｃ１）とした場合における、
入力されたＡ０  に対してＡ０２を計算してその演算結果Ｌ０  を出力する第１のＧＦ（ｑｎ−１  ）自乗器と、
入力されたＡ０  およびＡ１  に対してＡ０  ＋Ａ１  を計算してその演算結果Ｌ１  を出力する第１のＧＦ（ｑｎ−１  ）加算器と、
入力されたＡ１  に対してＡ１２を計算してその演算結果Ｌ２  を出力する第２のＧＦ（ｑｎ−１  ）自乗器と、
入力されたＬ１  に対してＬ１２を計算してその演算結果Ｌ３  を出力する第３のＧＦ（ｑｎ−１  ）自乗器と、
入力されたＬ２  に対してｔｎ  ・Ｌ２  を計算してその演算結果Ｌ４  を出力する第１のＧＦ（ｑｎ−１  ）定数倍器と、
入力されたＬ０  およびＬ３  に対してＬ３  −Ｌ０  を計算してその演算結果Ｌ５  を出力するＧＦ（ｑｎ−１  ）減算器と、
入力されたＬ２  に対して（ｓｎ  −１）・Ｌ２  を計算してその演算結果Ｌ６  を出力する第２のＧＦ（ｑｎ−１  ）定数倍器と、
入力されたＬ０  およびＬ４  に対してＬ０  ＋Ｌ４  を計算してその演算結果Ｃ０  を出力する第２のＧＦ（ｑｎ−１  ）加算器と、
入力されたＬ５  およびＬ６  に対してＬ５  ＋Ｌ６  を計算してその演算結果Ｃ１  を出力する第３のＧＦ（ｑｎ−１  ）加算器と、
を有するＧＦ（ｑｎ  ）自乗器であることを特徴とする逐次拡大を用いた楕円曲線演算装置。
【請求項５】
請求項１記載の演算装置であって、
上記ＧＦ（ｑｎ  ）演算手段は、
既約多項式ｘ２−ｖ１ｎ・ｘ−ｖ０ｎ＝０（ｖ１ｎ及びｖ０ｎはＧＦ（ｑｎ−１）上の元）の根αに対する正規基底｛α，αｐ｝を用い、ＧＦ（ｑｎ）上の元Ａ及びＡ２を、ＧＦ（ｑｎ−１）上の元によって表現したものを、それぞれ（Ａ０，Ａ１）及び（Ｃ０，Ｃ１）とした場合における、
入力されたＡ１  に対してｕ・Ａ１  を計算してその演算結果Ｌ０  を出力する第１のＧＦ（ｑｎ−１  ）定数倍器と、
入力されたＡ０  およびＬ０  に対してＡ０  ＋Ｌ０  を計算してその演算結果Ｌ１  を出力するＧＦ（ｑｎ−１  ）加算器と、
入力されたＡ０  およびＬ０  に対してＡ０  −Ｌ０  を計算してその演算結果Ｌ２  を出力するＧＦ（ｑｎ−１  ）減算器と、
入力されたＡ０  およびＡ１  に対してＡ０  ×Ａ１  を計算してその演算結果Ｌ３  を出力する第１のＧＦ（ｑｎ−１  ）乗算器と、
入力されたＬ１  およびＬ２  に対してＬ１  ×Ｌ２  を計算してその演算結果Ｃ０  を出力する第２のＧＦ（ｑｎ−１  ）乗算器と、
入力されたＬ３  に対して２・Ｌ３  を計算してその演算結果Ｃ１  を出力する第２のＧＦ（ｑｎ−１  ）定数倍器と、
を有するＧＦ（ｑｎ  ）自乗器であることを特徴とする逐次拡大を用いた楕円曲線演算装置。
【請求項６】
請求項１記載の演算装置であって、
上記ＧＦ（ｑｎ  ）演算手段は、
既約多項式ｘ２−ｖ１ｎ・ｘ−ｖ０ｎ＝０（ｖ１ｎ及びｖ０ｎはＧＦ（ｑｎ−１）上の元）の根αに対する多項式基底｛１，α｝を用い、ＧＦ（ｑｎ）上の元Ａ及びＡ２を、ＧＦ（ｑｎ−１）上の元によって表現したものを、それぞれ（Ａ０，Ａ１）及び（Ｃ０，Ｃ１）とした場合における、
入力されたＡ０  に対してＡ０２を計算してその演算結果Ｌ０  を出力する第１のＧＦ（ｑｎ−１  ）自乗器と、
入力されたＡ０  およびＡ１  に対してＡ０  −Ａ１  を計算してその演算結果Ｌ１  を出力するＧＦ（ｑｎ−１  ）減算器と、
入力されたＡ１  に対してＡ１２を計算してその演算結果Ｌ２  を出力する第２のＧＦ（ｑｎ−１  ）自乗器と、
入力されたＬ１  に対してＬ１２を計算してその演算結果Ｌ３  を出力する第３のＧＦ（ｑｎ−１  ）自乗器と、
入力されたＬ０  に対してｓｎ  ・Ｌ０  を計算してその演算結果Ｌ４  を出力する第１のＧＦ（ｑｎ−１  ）定数倍器と、
入力されたＬ３  に対して（ｓｎ  −１・ｔｎ  ）・Ｌ３  を計算してその演算結果Ｌ５  を出力する第２のＧＦ（ｑｎ−１  ）定数倍器と、
入力されたＬ２  に対してｓｎ・ Ｌ２  を計算してその演算結果Ｌ６  を出力する第３のＧＦ（ｑｎ−１  ）定数倍器と、
入力されたＬ４  およびＬ５  に対してＬ４  ＋Ｌ５  を計算してその演算結果Ｃ０  を出力する第１のＧＦ（ｑｎ−１  ）加算器と、
入力されたＬ５  およびＬ６  に対してＬ５  ＋Ｌ６  を計算してその演算結果Ｃ１  を出力する第２のＧＦ（ｑｎ−１  ）加算器と、
を有するＧＦ（ｑｎ  ）自乗器であることを特徴とする逐次拡大を用いた楕円曲線演算装置。
【請求項７】
請求項１から６の何れかに記載の演算装置であって、
ｉ＝ｎ＋１（ｎ≠ｚ）とし、既約多項式ｘ２−ｖ１ｉ・ｘ−ｖ０ｉ＝０（ｖ１ｉ及びｖ０ｉはＧＦ（ｑｉ−１）上の元）の根αに対する正規基底｛α，αｐ｝を用い、ＧＦ（ｑｉ）上の元Ａ及びＡ−１を、ＧＦ（ｑｉ−１）上の元によって表現したものを、それぞれ（Ａ０，Ａ１）及び（Ｃ０，Ｃ１）とした場合における、
入力されたＡ１  に対してｓｉ  ・Ａ１  を計算してその演算結果Ｌ０  を出力する第５のＧＦ（ｑｉ−１  ）定数倍器と、
入力されたＡ１  に対してＡ１２を計算してその演算結果Ｌ１  を出力する第５のＧＦ（ｑｉ−１  ）自乗器と、
入力されたＡ０  およびＬ０  に対してＡ０  ＋Ｌ０  を計算してその演算結果Ｌ２  を出力する第５のＧＦ（ｑｉ−１  ）加算器と、
入力されたＡ０  およびＬ２  に対してＡ０・Ｌ２  を計算してその演算結果Ｌ３  を出力する第５のＧＦ（ｑｉ−１  ）乗算器と、
入力されたＬ１  に対してｔｉ  ・Ｌ１  を計算してＬ４  を出力する第６のＧＦ（ｑｉ−１  ）定数倍器と、
入力されたＬ３  およびＬ４  に対してＬ３  −Ｌ４  を計算してその演算結果Ｌ５  を出力する第５のＧＦ（ｑｉ−１  ）減算器と、
入力されたＬ５  に対してＬ５  −１を計算してその演算結果Ｌ６  を出力する第５のＧＦ（ｑｉ−１  ）逆元器と、
入力されたＬ２  およびＬ６  に対してＬ２  ×Ｌ６  を計算してその演算結果Ｃ０  を出力する第６のＧＦ（ｑｉ−１  ）乗算器と、
入力されたＬ６  およびＡ１  に対してＬ６  ×Ａ１  を計算してその演算結果Ｌ７  を出力する第７のＧＦ（ｑｉ−１  ）乗算器と、
入力されたＬ７  に対して−Ｌ７  を計算してその演算結果Ｃ１  を出力する第７のＧＦ（ｑｉ−１  ）定数倍器と、
を有するＧＦ（ｑｉ  ）逆元器をさらに有し、
上記ＧＦ（ｑｎ  ）演算手段は、
上記第５のＧＦ（ｑｉ−１  ）自乗器或いは上記第５から７のＧＦ（ｑｉ−１  ）乗算器の何れかである、
ことを特徴とする逐次拡大を用いた楕円曲線演算装置。
【請求項８】
請求項１から６の何れかに記載の演算装置であって、
ｉ＝ｎ＋１（ｎ≠ｚ）とし、既約多項式ｘ２−ｖ１ｉ・ｘ−ｖ０ｉ＝０（ｖ１ｉ及びｖ０ｉはＧＦ（ｑｉ−１）上の元）の根αに対する正規基底｛α，αｐ｝を用い、ＧＦ（ｑｉ）上の元Ａ及びＡ−１を、ＧＦ（ｑｉ−１）上の元によって表現したものを、それぞれ（Ａ０，Ａ１）及び（Ｃ０，Ｃ１）とした場合における、
入力されたＡ０  およびＡ１  に対してＡ０  ×Ａ１  を計算してその演算結果Ｌ０  を出力する第５のＧＦ（ｑｉ−１  ）乗算器と、
入力されたＡ０  およびＡ１  に対してＡ０  −Ａ１  を計算してその演算結果Ｌ１  を出力する第５のＧＦ（ｑｉ−１  ）減算器と、
入力されたＬ０  に対してｓｉ  ２  Ｌ０  を計算してその演算結果Ｌ２  を出力する第５のＧＦ（ｑｉ−１  ）定数倍器と、
入力されたＬ１  に対してＬ１２を計算してその演算結果Ｌ３  を出力する第５のＧＦ（ｑｉ−１  ）自乗器と、
入力されたＬ３  に対してｔｉ  ・Ｌ３  を計算してその演算結果Ｌ４  を出力する第６のＧＦ（ｑｉ−１  ）定数倍器と、
入力されたＬ２  およびＬ４  に対してＬ２  −Ｌ４  を計算してその演算結果Ｌ５  を出力する第６のＧＦ（ｑｉ−１  ）減算器と、
入力されたＬ５  に対してＬ５  −１を計算してその演算結果Ｌ６  を出力する第５のＧＦ（ｑｉ−１  ）逆元器と、
入力されたＡ０  およびＬ６  に対してＡ０  ×Ｌ６  を計算してその演算結果Ｃ１  を出力する第６のＧＦ（ｑｉ−１  ）乗算器と、
入力されたＬ６  およびＡ１  に対してＬ６  ×Ａ１  を計算してその演算結果Ｃ０  を出力する第７のＧＦ（ｑｉ−１  ）乗算器と、
を有するＧＦ（ｑｉ  ）逆元器をさらに有し、
上記ＧＦ（ｑｎ  ）演算手段は、
上記第５のＧＦ（ｑｉ−１  ）自乗器或いは上記第５から７のＧＦ（ｑｉ−１  ）乗算器の何れかである、
ことを特徴とする逐次拡大を用いた楕円曲線演算装置。
【請求項９】
請求項１から８の何れかに記載の演算装置としてコンピュータを機能させるためのプログラムを格納したコンピュータ読取り可能なプログラム記録媒体。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
この発明は、楕円曲線上の演算に関わり、特に、情報セキュリティ技術（楕円曲線暗号／署名、素因数分解）を実現するために用いられる装置及びプログラム記録媒体に関する。
【０００２】
【従来の技術】
楕円曲線上で公開鍵暗号やデジタル署名を実現する場合、その処理時間のほとんどは楕円曲線上のｋ倍演算に費やされる。
一般に、暗号や署名には有減体ＧＦ（ｑ）上で定義される楕円曲線を使う。これをＥ／ＧＦ（ｑ）と表記する。ｑは素数または素数のべき乗である。従来の実装法ではｑに素数または２m を用いることが多かったが、この発明は一般の有限体の場合を考える。
【０００３】
楕円曲線上の点Ｐに対する加算を定義できる。通常の加算と区別するためにこれを、「楕円加算」「楕円２倍演算」と呼ぶ。いずれも、有限体ＧＦ（ｑ）上の加減乗除算を組み合わせることで行うことが出来る。
通常、ｋ倍演算を構成するために、「楕円加算」「楕円２倍演算」を組み合わせて行なう方法が用いられている。
【０００４】
したがって、楕円曲線上の演算は、有限体ＧＦ（ｑ）上の加減乗除算に帰着することが出来、これらを高速化することが、楕円曲線上の演算の高速化につながる。
この発明は、有限体ＧＦ（ｑ）上の演算の高速化に関する発明である。
ｐを素数または素数のべき乗として、ｑ＝ｐm とし、上記有限体ＧＦ（ｑ）＝ＧＦ（ｐm ）の元を部分体ＧＦ（ｐ）を用いて表す場合、ＧＦ（ｐm ）は、ＧＦ（ｐ）上のベクトル空間であるので、ｍ対のＧＦ（ｐ）の元と基底との線形結合で表す。
【０００５】
従来、よく用いられてきた基底には、「多項式基底」および「正規基底」があり、それぞれ一長一短がある。
多項式基底を用いる方法は、ＧＦ（ｐ）上のｍ次既約多項式ｆ（ｘ）の根αを用いて、｛１，α，α2 ，…，αm-1 ｝なる基底を用い、ＧＦ（ｐ）（＝ＧＦ（ｐ）［α］）の元ａをあらわす際に、
ａ＝ａ0 ＋ａ1 α＋ａ2 α2 ＋…＋ａm-1 αm-1 
を満たすＧＦ（ｑ）の元の組（ａ0 ，ａ1 ，…，ａm-1 ）によってあらわす。
【０００６】
正規基底を用いる方法は、ＧＦ（ｐm ）上の正規基底の生成元αを用いて、｛α，αp ，（αp ）2 ，…，（αp ）m-1 ｝なる基底を用い、ＧＦ（ｐ）（＝ＧＦ（ｐ）［α］）の元ａをあらわす際に、
【０００７】
【数１１】
0003639153.tif 000002
を満たすＧＦ（ｐi-1 ）の元の組（ａ0 ，ａ1 ，…，ａm-1 ）によってあらわす。
なお、多項式基底と正規基底の生成元αの満たすべき条件は異なるので、必ずしも同じ値を取れるとは限らない。詳細は、平松豊一著、応用代数学、掌華房の３．３と３．６節を参照のこと。
【０００８】
楕円曲線上で定義される要素同士の２項演算である加法を実行する場合、Stinson 著、櫻井監訳、暗号理論の基礎、共立出版のｐ．１９８によれば、標数が５以上の楕円曲線
Ｅ：ｙ2 ＝ｘ3 ＋ａｘ＋ｂ  （ａ，ｂ∈ＧＦ（ｐm ））
上の２点（ｘ1 ，ｙ1 ）と（ｘ2 ，ｙ2 ）の和（ｘ3 ，ｙ3 ）を求める場合
ｘ3 ＝λ2 −ｘ1 −ｘ2 
ｙ3 ＝λ（ｘ1 −ｘ3 ）−ｙ1 
の演算を行なう。但し、λはｘ1 ＝ｘ2 かつｙ1 ＝ｙ2 ならば（３ｘ1 2 ＋ａ）／（２ｙ1 ）であり、それ以外は、（ｙ2 −ｙ1 ）／（ｘ2 −ｘ1 ）で求められる。
【０００９】
以上の様な演算が繰り返されるので、有限体ＧＦ（ｐm ）上での加減剰余算が繰り返し使われる。
【００１０】
【発明が解決しようとする課題】
上記表現のどちらの場合でも、ＧＦ（ｐm ）の元の乗算を行なう場合には、ＧＦ（ｐ）の上でｍ2 回に比例する回数の乗算を行なわなくてはならなかった。また、楕円曲線上でｋ倍演算を行なう場合、ｌｏｇｋに比例する回数、ＧＦ（ｐm ）上の乗算を行なう必要がある。
【００１１】
一般に加算に比べて乗算の方が演算時間がかかるが、演算回数の多いためボトルネックとなっていた。
【００１２】
【課題を解決するための手段】
・３／４法
乗算を効率化するため、以下のような方法が考えられる。例として、ａ，ｂ∈ＧＦ（ｐ4 ）とする。通常の多項式基底を用いて、ＧＦ（ｐ）の元ａ0 ，ａ1 ，ａ2 ，ａ3 とｂ0 ，ｂ1 ，ｂ2 ，ｂ3 によってａとｂを、それぞれ
ａ＝ａ0 ＋ａ1 α＋ａ2 α2 ＋ａ3 α3 
ｂ＝ｂ0 ＋ｂ1 α＋ｂ2 α2 ＋ｂ3 α3 
と表し、ａとｂの乗算を行なう場合を考える。また、αを根に持つＧＦ（ｐ）上の最小多項式をｆ（ｘ）とする。
【００１３】
通常の乗算では、
0003639153.tif 000003
なる演算を行なう。この場合、ＧＦ（ｐ）上の乗算が１６回必要である。ところで、この演算を
0003639153.tif 000004
という手順で行なえば、ＧＦ（ｐ）上の乗算１２回でａｂを求めることができる。
【００１４】
上記手順は一般化することが出来、乗算を３／４に減らすことが出来る。この方法を、この明細書では「３／４法」と呼ぶ。
・逐次拡大を用いる方法
ところで、ｍが合成数の場合、逐次拡大によって有限体ＧＦ（ｐm ）の元を表現することができる。
【００１５】
例えばｍ＝４の場合、逐次拡大では有限体ＧＦ（ｐ2 ）の元をＧＦ（ｐ）によってあらわし、有限体ＧＦ（ｐ4 ）の元をＧＦ（ｐ2 ）によってあらわせる。この表現方法によって、乗算を高速化することが出来る。例として、ａ，ｂ∈ＧＦ（（ｐ2 ）2 ）とし、通常の多項式基底を用いて、ＧＦ（ｐ2 ）の元Ａ0 ，Ａ1 とＢ0 ，Ｂ1 によってａとｂをそれぞれ表し、ＧＦ（ｐ）の元ａ00，ａ01、ａ10，ａ11、ｂ00，ｂ01、ｂ10，ｂ11によってＡ0 、Ａ1 、Ｂ0 、Ｂ1 をそれぞれ表すこととする。
【００１６】
ａ＝Ａ0 ＋Ａ1 α
ｂ＝Ｂ0 ＋Ｂ1 α
Ａ0 ＝ａ00＋ａ01α′
Ａ1 ＝ａ10＋ａ11α′
Ｂ0 ＝ｂ00＋ｂ01α′
Ｂ1 ＝ｂ10＋ｂ11α′
と表し、ａとｂの乗算を行なう場合を考える。また、αを根に持つＧＦ（ｐ2 ）上の最小多項式をｆ（ｘ）とし、α′を根に持つＧＦ（ｐ）上の最小多項式をｇ（ｘ）とする。
【００１７】
ａとｂとの乗算を行う場合、
ａｂ＝Ａ0 Ｂ0 ＋（Ａ1 Ｂ0 ＋Ａ0 Ｂ1 ）α＋Ａ1 Ｂ1 α2 (modｆ（α））なる演算を行なう。この場合、ＧＦ（ｐ2 ）上の乗算を４回行なうことになる。
この演算は「３／４法」で述べたものと同様な方法を適用することにより、
0003639153.tif 000005
と置き換えることが出来る。この場合、ＧＦ（ｐ2 ）上の乗算を３回行なうことになり、乗算の回数を３／４にすることが出来る。
【００１８】
逐次拡大を用いる場合、さらにＡ0 Ｂ0 のようなＧＦ（ｐ2 ）上の演算にも上記の方法を適用することが出来る。すなわち、ＧＦ（ｐ2 ）上の乗算１回に必要なＧＦ（ｐ）上の乗算の回数を４回から３回に減らすことができる。このため、ＧＦ（ｐ4 ）上の乗算１回に必要なＧＦ（ｐ）上の乗算回数は９回となる。
0003639153.tif 000006
この例では、簡単のため逐次拡大を２回行なった場合を説明したが、実際には逐次拡大の回数が多いほど乗算回数削減の効果が高く、ｍが十分に大きければ、乗算の回数を約ｍのｌｏｇ2 3 、つまり約ｍ1.585 に減らすことができる（従来法ではｍ2 回であり、３／４法は３／４ｍ2 回である）。
また、乗算を行う際に必要となる、mod ｆ（α）によって多項式の次数を下げる処理に関しても、逐次拡大を用いることによって演算の効率化を行うことができる。これは、３／４法では、ｆ（ｘ）の次数がｍ次であるのに対して逐次拡大法では、ｍの任意の約数とすることができるためである。ここでは乗算について説明したが、逆元に関しても同様にして演算量を減らすことができる。
【００１９】
【発明の実施の形態】
この発明では高速演算に適した特別な逐次拡大を用いる事によって高速に演算可能な拡大体演算装置を構成する。楕円曲線の有理点群の定義体として、高速に演算可能な逐次拡大体を用いる事によって、楕円曲線の有理点のなす群上の演算の高速化を行なう。
【００２０】
有限体の拡大はＧＦ（ｑ0 ）⊆ＧＦ（ｑ1 ）⊆…⊆ＧＦ（ｑn ）と逐次的に行われる。例えば、この拡大を全て２次で行う場合（逐次２次拡大の場合）、拡大次数はｑi ＝（ｑ0 2 ）i のように２の冪で大きくなる。
この発明では通常、逐次拡大体ＧＦ（ｑi ）上の効率的な演算装置をＧＦ（ｑi-1 ），ＧＦ（ｑi-2 ），…，ＧＦ（ｑ0 ）上の演算装置を用いて構成する。
【００２１】
ＧＦ（ｑ0 ）上の演算装置があれば、上記の様に構成されたＧＦ（ｑi ）演算装置を、図１８に示すようにＧＦ（ｑn ）演算器１８ＡによりＧＦ（ｑn-1 ）上の演算を行い、その結果を用いてＧＦ（ｑn-1 ）演算器１８ＢによりＧＦ（ｑn-2 ）上の演算を行い、以下順次、拡大演算を行って最後にＧＦ（ｑ0 ）演算器１８ＤによりＧＦ（ｑn ）上の演算を行うというようにｉ＝１の場合から次々と用いて効率的なＧＦ（ｑn ）上の演算装置を構成する事ができる。
【００２２】
ＧＦ（ｑ0 ）としては例えば素体ＧＦ（ｐ）（ｐは素数）を用いてよい。また素数ｐとしてMersenne素数ｐ＝２p'−１（ｐ′はｐが素数となるような素数）あるいは擬Mersenne素数ｐ＝２p'±Ｃ（ｐ′はｐが素数となるような整数、Ｃは２p'/2以下の整数）を選んでも良い。そのような場合は素体上の演算は高速化できる。
【００２３】
またｐ′として演算装置の語長に近い数（例えば語長が３２の時はｐ′＝３２，３１等、語長が１６の時はｐ′＝１６，１５等、語長が８の時はｐ′＝８，７等）を選ぶことができるので、効率的な装置を構成できる。
実施例
この発明の実施例で説明を簡単にするため拡大体の表現を多項式基底または正規基底に限定する事もあるが、他の基底でも同様の方法を実現可能である。さらにＧＦ（ｑ0 ）⊆ＧＦ（ｑ1 ）⊆…⊆ＧＦ（ｑn ）と有限体を逐次的に拡大する際に、一貫して同種の基底を使わなくても良い。即ち、装置や速度などの都合と照らし併せて適切な基底を拡大の度に選んで良い。しかし、一つの装置内でのＧＦ（ｑ0 ）⊆ＧＦ（ｑ1 ）⊆…⊆ＧＦ（ｑn ）の拡大に対応する基底およびその種類の列は一貫して全て同じか、あるいは入出力の際に適切な基底に変換されるとする。
【００２４】
この発明の実装ではＧＦ（ｑ0 ）としては例えば素体ＧＦ（ｐ）（ｐは素数）を選んでも良い。その際、素数ｐとしてMersenne素数ｐ＝２p'−１（ｐ′はｐが素数となるような素数）あるいは擬Mersenne素数ｐ＝２p'±Ｃ（Ｃは小さな整数）を選んで良い。そのような場合は素体上の演算は高速化できる。多項式基底の場合、逐次的に拡大する時、拡大ごとに高速演算に適した既約多項式を定義して既約多項式の列を作る。Mersenne素数ｐ＝２p'−１による素体ＧＦ（ｐ）から拡大する場合は次のような事が云える。
【００２５】
・ＧＦ（ｐ）上でｘ2 ＋１は既約、つまりｘ2 ＋１を用いて拡大できる。
・ＧＦ（ｐ）上でｘ2 −ｘ＋１は可約、つまりｘ2 −ｘ＋１を用いて拡大できない。
・ｐ′＝２またはｐ′が奇素数でｐ′≡３（mod ４）の時ＧＦ（ｐ）上でｘ2 −ｘ−１は既約、つまりｘ2 −ｘ−１を用いて拡大できる。
【００２６】
ｐ′が奇素数でｐ′≡１（mod ４）の時ＧＦ（ｐ）上でｘ2 −ｘ−１は可約。
・ｐ′＝２またはｐ′が奇素数でｐ′≡±３（mod ８）の時ＧＦ（ｐ）［α］／（α2 ＋１）上でｘ2 −ｘ±αは既約、つまりｘ2 ＋１を用いて拡大でき、更にｘ2 −ｘ±αを用いて拡大できる。
ｐ′が奇素数でｐ′≡±１（mod ８）の時ＧＦ（ｐ）［α］／（α2 ＋１）上でｘ2 −ｘ±αは可約。つまりｘ2 ＋１を用いて拡大したものを、ｘ2 −ｘ±αを用いて更に拡大することはできない。（但しαはｘ2 ＋１＝０の解。）
例えばＧＦ（ｑ0 ）⊆ＧＦ（ｑ1 ）⊆ＧＦ（ｑ2 ）と拡大を行う場合ｐ＝２p'−１，ｐ′≡±３（mod ８）またはｐ′＝２として
0003639153.tif 000007
（但しｑi ＝ｐ2i，αはｘ2 ＋１＝０のＧＦ（ｑ1 ）上での解。）とすることが出来る。
【００２７】
正規基底の場合、逐次的に拡大する時、拡大ごとに高速演算に適した正規基底の生成元が定義されることによって、全ての基底を解に持つ既約多項式を定義して既約多項式の列を作る。従って、既約多項式を作る際、その解が正規基底になるものでなくてはならないという制限がある。たとえ既約でも例えばｘ2 ＋Ｃ（Ｃは定数項）の様な多項式は拡大には使えるが、その解は正規基底の基底とはならない。Mersenne素数ｐ＝２p'−１による素体ＧＦ（ｐ）から拡大する場合は次のような事が云える。
【００２８】
・ＧＦ（ｐ）上でｘ2 ±ｘ＋１は可約。
・ＧＦ（ｐ）上でｘ2 ±ｘ−２は可約。
・ＧＦ（ｐ）上でｘ2 ±２ｘ＋２は既約。
・ｐ′≠２の時ＧＦ（ｐ）上でｘ2 ±２ｘ−２は可約。
・ｐ′＝２またはｐ′が奇素数でｐ′≡３（mod ４）の時ＧＦ（ｐ）上でｘ2 ±ｘ−１は既約。
【００２９】
ｐ′が奇素数でｐ′≡１（mod ４）の時ＧＦ（ｐ）上でｘ2 ±ｘ−１は可約。
・ｐ′＝３またはｐ′≡２（mod ３）の時ＧＦ（ｐ）上でｘ2 ±ｘ＋２は既約。
ｐ′≡１（mod ３）の時ＧＦ（ｐ）上でｘ2 ±ｘ＋２は可約。
以下に先ず一般的な楕円曲線上の演算について説明し、かつその際にこの発明をどのように適用するかを示す。
【００３０】
楕円曲線上のｋ倍演算装置１Ａ
図１の「楕円曲線上のｋ倍演算装置」に従って説明する。
装置１Ａは楕円曲線Ｅ上の有理点Ｐ及び整数ｋの入力に対して楕円曲線Ｅ上の有理点ｋＰを出力する装置の構成の一例を表している。
【００３１】
この実施例では簡単のため、二進加算法によるｋ倍演算を説明するが、符号付二進加算法やウインドウ法のような他の冪乗テーブル演算法でもこの発明の効果を享受出来る。
装置１Ａは
・メモリ１Ｂ
・制御装置１Ｃ
・楕円加算装置１Ｄ
・楕円倍算装置１Ｅ
からなる。
【００３２】
楕円加算装置１Ｄは図２に示すように構成され、楕円倍算装置１Ｅは図３に示すように構成される。ｋ倍演算装置１Ａの構成と応用によっては、入力や出力、計算途中結果に無限遠点や二等分点が現れない事が保証される場合がある。そのような場合は楕円加算装置１Ｄや楕円倍算装置１Ｅの代わりに、より装置の構成が単純な楕円加算器（図１２，１４，１６）や楕円倍算器（図１３，１５，１７）を使う事も出来る。この実施例では説明を簡単にするため、入力や出力、計算途中結果に無限遠点や二等分点を仮定しても良いとする。
【００３３】
この装置の動作をプログラムで実現する場合は、図３６に示すフロー図に従って実行する。
楕円曲線の無限遠点をΟと表記する。
この装置では、以下のように演算が実行される。
Ｓｔｅｐ１：制御装置１Ｃは、入力ｋ，Ｐに対してｋ＝Σi=0 n-1 ｋi ２i を満たす最小の整数ｎと数列ｋi ∈｛０，１｝を求め、メモリ１Ｂに渡す。ｎは必ずしも最小でなくても良く装置を構成する際ｋの想定され得る最大値から事前に算出しておいても良い。
【００３４】
Ｓｔｅｐ２：制御装置１Ｃは、楕円曲線上の有理点ＲをＲ＝Οとしてメモリ１Ｂに渡す。
Ｓｔｅｐ３：制御装置１Ｃは、カウンター値ｉをｉ＝ｎとしてメモリ１Ｂに渡す。
Ｓｔｅｐ４：制御装置１Ｃは、メモリ１Ｂよりカウンター値ｉを受け取りｉ＝０かどうかを調べる。もしｉ＝０ならＳｔｅｐ１１へ制御転送する。
【００３５】
Ｓｔｅｐ５：制御装置１Ｃは、メモリ１ＢよりＲを受け取り、それを楕円倍算装置１Ｅに渡し、受け取った倍算結果の値を新たなＲとする。
Ｓｔｅｐ６：制御装置１Ｃは、ｉ−１を新たなカウンター値ｉとする。
Ｓｔｅｐ７：制御装置１Ｃは、カウンター値ｉに基づき、メモリ１Ｂより数ｋi を受け取りｋi ＝０かどうかを調べる。もしｋi ＝０ならＳｔｅｐ９へ制御転送する。
【００３６】
Ｓｔｅｐ８：制御装置１Ｃは、ＲとＰを楕円加算装置１Ｄに渡し受け取った、その加算結果の値を新たなＲとする。
Ｓｔｅｐ９：制御装置１Ｃは、Ｒとｉをメモリ１Ｂに渡す。
Ｓｔｅｐ１０：制御装置１Ｃは、Ｓｔｅｐ４へ制御転送する。
Ｓｔｅｐ１１：制御装置１Ｃは、メモリ１ＢよりＲを受け取り、それをｋＰとして出力する。
楕円曲線上の加算装置２Ａ
図２に「楕円曲線上の加算装置」を示す。
【００３７】
装置２Ａは楕円曲線Ｅ上の有理点Ｐ，Ｑの入力に対して楕円曲線Ｅ上の有理点Ｐ＋Ｑを出力する装置の構成の一例を表している。
装置２Ａは
・メモリ２Ｂ
・制御装置２Ｃ
・楕円加算器２Ｄ
・楕円倍算器２Ｅ
・楕円比較装置２Ｆ
・楕円逆元器２Ｇ
からなる。
【００３８】
楕円加算器２Ｄは図１２または図１４または図１６に示すように構成され、楕円倍算器２Ｅは図１３または図１５または図１７に示すように構成され、楕円比較装置２Ｆは図８に示すように構成され、楕円逆元器２Ｇは図６または図７に示すように構成される。
この装置の動作をプログラムで実現する場合は、図３７に示すフロー図に従って実行する。
【００３９】
楕円曲線の無限遠点をΟと表記する。
この装置では、以下のように演算が実行される。
Ｓｔｅｐ１：制御装置２Ｃは、入力のＰとＯを楕円比較装置２Ｆに渡し、楕円比較装置２Ｆから論理式Ｐ＝Ｏの真偽を受け取りもし真ならＲ＝ＱとしてＳｔｅｐ６へ制御転送する。
【００４０】
Ｓｔｅｐ２：制御装置２Ｃは、入力のＱとＯを楕円比較装置２Ｆに渡し、楕円比較装置２Ｆから論理式Ｑ＝Ｏの真偽を受け取りもし真ならＲ＝ＰとしてＳｔｅｐ６へ制御転送する。
Ｓｔｅｐ３：制御装置２Ｃは、入力のＰとＱを楕円比較装置２Ｆに渡し、楕円比較装置２Ｆから論理式Ｐ＝Ｑの真偽を受け取りもし真なら、楕円倍算器２ＥにＰを渡しその出力２Ｐを用いてＲ＝２ＰとしてＳｔｅｐ６へ制御転送する。
【００４１】
Ｓｔｅｐ４：制御装置２Ｃは、入力のＱを楕円逆元器２Ｇに渡しその出力−Ｑと入力のＰとを楕円比較装置２Ｆに渡し、楕円比較装置２Ｆから論理式Ｐ＝−Ｑの真偽を受け取りもし真なら、Ｒ＝ＯとしてＳｔｅｐ６へ制御転送する。
Ｓｔｅｐ５：制御装置２Ｃは、楕円加算器２ＤにＰ，Ｑを渡しその出力Ｐ＋Ｑを用いてＲ＝Ｐ＋Ｑとする。
【００４２】
Ｓｔｅｐ６：制御装置２Ｃは、ＲをＰ＋Ｑとして出力する。
楕円曲線上の倍算装置３Ａ
図３に「楕円曲線上の倍算装置」を示す。
装置３Ａは楕円曲線Ｅ上の有理点Ｐの入力に対して楕円曲線Ｅ上の有理点２Ｐを出力する装置の構成の一例を表している。
【００４３】
装置３Ａは
・メモリ３Ｂ
・制御装置３Ｃ
・楕円二等分点判定器３Ｄ
・楕円倍算器３Ｅ
・楕円比較装置３Ｆ
からなる。
【００４４】
楕円二等分点判定器３Ｄは図４または図５に示すように構成され、楕円倍算器３Ｅは図１３または図１５または図１７に示すように構成され、楕円比較装置３Ｆは図８に示すように構成される。
この装置の動作をプログラムで実現する場合は、図３８に示すフロー図に従って実行する。
【００４５】
楕円曲線の無限遠点をΟと表記する。楕円曲線の二等分点の集合（２Ｐ＝ΟかつＰ≠Οを満たすＰの集合）をＵと表記する。
この装置では、以下のように演算が実行される。
Ｓｔｅｐ１：制御装置３Ｃは、入力のＰとＯを楕円比較装置３Ｆに渡し、楕円比較装置３Ｆから論理式Ｐ＝Ｏの真偽を受け取り、もし真ならＲ＝ＯとしてＳｔｅｐ４へ制御転送する。
【００４６】
Ｓｔｅｐ２：制御装置３Ｃは、入力のＰを楕円二等分点判定器３Ｄに渡し、楕円二等分点判定器３Ｄから、論理式Ｐ∈Ｕの真偽を受け取り、もし真ならＲ＝ＯとしてＳｔｅｐ４へ制御転送する。
Ｓｔｅｐ３：制御装置３Ｃは、楕円倍算器３ＥにＰを渡しその出力２Ｐを用いてＲ＝２Ｐとする。
【００４７】
Ｓｔｅｐ４：制御装置３Ｃは、Ｒを２Ｐとして出力する。
楕円二等分点判定器４Ａ
図４に「楕円二等分点判定器」を示す。
楕円曲線の無限遠点をΟと表記する。楕円曲線の二等分点の集合（２Ｐ＝ΟかつＰ≠Οを満たすＰの集合）をＢと表記する。
【００４８】
装置４Ａは二値座標で表現された楕円曲線Ｅ上の有理点Ｐ＝（ｘ，ｙ）の入力に対して論理式Ｐ∈Ｕの真偽を出力する装置の構成の一例を表している。
装置４Ａは
・メモリ４Ｂ
・制御装置４Ｃ
からなる。
【００４９】
この装置の動作をプログラムで実現する場合は、図３９に示すフロー図に従って実行する。
この装置では、以下のように演算が実行される。
Ｓｔｅｐ１：制御装置４Ｃは、入力のｙを調べｙ＝０ならばｆ＝真とする。ｙ≠０ならばｆ＝偽とする。
【００５０】
Ｓｔｅｐ２：制御装置４Ｃは、ｆを論理式Ｐ∈Ｕの値として出力する。
楕円二等分点判定器５Ａ
図５に「楕円二等分点判定器」の他の例を示す。
楕円曲線の無限遠点をΟと表記する。楕円曲線の二等分点の集合（２Ｐ＝ΟかつＰ≠Οを満たすＰの集合）をＵと表記する。
【００５１】
装置５Ａは三値座標で表現された楕円曲線Ｅ上の有理点Ｐ＝（Ｘ，Ｙ，Ｚ）の入力に対して論理式Ｐ∈Ｕの真偽を出力する装置の構成の一例を表している。
装置５Ａは
・メモリ５Ｂ
・制御装置５Ｃ
からなる。
【００５２】
この装置の動作をプログラムで実現する場合は、図４０に示すフロー図に従って実行する。
この装置では、以下のように演算が実行される。
Ｓｔｅｐ１：制御装置５Ｃは、入力のｙを調べＹ＝０ならばｆ＝真とする。Ｙ≠０ならばｆ＝偽とする。
【００５３】
Ｓｔｅｐ２：制御装置５Ｃは、ｆを論理式Ｐ∈Ｕの値として出力する。
楕円逆元器６Ａ
図６に「楕円逆元器」を示す。
装置６Ａは二値座標で表現された楕円曲線Ｅ上の有理点Ｐ＝（ｘ，ｙ）の入力に対してＰの加法逆元−Ｐを出力する装置の構成の一例を表している。
【００５４】
装置６Ａは
・メモリ６Ｂ
・制御装置６Ｃ
からなる。
この装置の動作をプログラムで実現する場合は、図４１に示すフロー図に従って実行する。
【００５５】
この装置では、以下のように演算が実行される。
Ｓｔｅｐ１：制御装置６Ｃは、入力のＰ＝（ｘ，ｙ）に対してＲ＝（ｘ，−ｙ）とする。
Ｓｔｅｐ２：制御装置６Ｃは、ＲをＰの加法逆元−Ｐとして出力する。
楕円逆元器７Ａ
図７に「楕円逆元器」の他の例を示す。
【００５６】
装置７Ａは三値座標で表現された楕円曲線Ｅ上の有理点Ｐ＝（Ｘ，Ｙ，Ｚ）の入力に対してＰの加法逆元−Ｐを出力する装置の構成の一例を表している。
装置７Ａは
・メモリ７Ｂ
・制御装置７Ｃ
からなる。
【００５７】
この装置の動作をプログラムで実現する場合は、図４２に示すフロー図に従って実行する。
この装置では、以下のように演算が実行される。
Ｓｔｅｐ１：制御装置７Ｃは、入力のＰ＝（Ｘ，Ｙ，Ｚ）に対してＲ＝（Ｘ，−Ｙ，Ｚ）とする。
【００５８】
Ｓｔｅｐ２：制御装置７Ｃは、ＲをＰの加法逆元−Ｐとして出力する。
楕円比較装置８Ａ
図８に「楕円比較装置」を示す。
装置８Ａは楕円曲線Ｅ上の有理点Ｐ，Ｑの入力に対して論理式Ｐ＝Ｑの真偽を出力する装置の構成の一例を表している。
【００５９】
装置８Ａは
・メモリ８Ｂ
・制御装置８Ｃ
・楕円比較器８Ｄ
からなる。
【００６０】
楕円比較器８Ｄは図９または図１０または図１１に示すように構成される。
この装置の動作をプログラムで実現する場合は、図４３に示すフロー図に従って実行する。
楕円曲線の無限遠点をΟと表記する。
この装置では、以下のように演算が実行される。
【００６１】
Ｓｔｅｐ１：制御装置８Ｃは、入力のＰに対してＰがΟと等しいかどうか調べる。
Ｓｔｅｐ２：制御装置８Ｃは、入力のＱに対してＱがΟと等しいかどうか調べる。
Ｓｔｅｐ３：制御装置８Ｃは、もしＰ＝ΟかつＱ＝Οならｆ＝真としてＳｔｅｐ７へ制御転送する。
【００６２】
Ｓｔｅｐ４：制御装置８Ｃは、もしＰ＝ΟかつＱ≠Οならｆ＝偽としてＳｔｅｐ７へ制御転送する。
Ｓｔｅｐ５：制御装置８Ｃは、もしＰ≠ΟかつＱ＝Οならｆ＝偽としてＳｔｅｐ７へ制御転送する。
Ｓｔｅｐ６：制御装置８Ｃは、Ｐ，Ｑを楕円比較器８Ｄへ渡しその結果Ｃｍｐ（Ｐ，Ｑ）を用いてｆ＝Ｃｍｐ（Ｐ，Ｑ）とする。つまりＰ＝Ｑでｆ＝真、Ｐ≠Ｑでｆ＝偽とする。
【００６３】
Ｓｔｅｐ７：制御装置８Ｃは、ｆを論理式Ｐ＝Ｑの値として出力する。
楕円比較器９Ａ
図９に「楕円比較器」を示す。
装置９Ａは二値座標における楕円曲線Ｅ上の有理点Ｐ＝（ｘ1 ，ｙ1 ）およびＱ＝（ｘ2 ，ｙ2 ）の入力に対して論理式Ｐ＝Ｑの真偽を出力する装置の構成の一例を表している。
【００６４】
装置９Ａは
・メモリ９Ｂ
・制御装置９Ｃ
からなる。
この装置の動作をプログラムで実現する場合は、図４４に示すフロー図に従って実行する。
【００６５】
この装置では、以下のように演算が実行される。
Ｓｔｅｐ１：制御装置９Ｃは、入力Ｐ＝（ｘ1 ，ｙ1 ）およびＱ＝（ｘ2 ，ｙ2 ）に対してｘ1 がｘ2 と等しいかどうか調べる。
Ｓｔｅｐ２：制御装置９Ｃは、ｘ1 ＝ｘ2 であれば、入力Ｐ＝（ｘ1 ，ｙ1 ）およびＱ＝（ｘ2 ，ｙ2 ）に対してｙ1 がｙ2 と等しいかどうか調べる。
【００６６】
Ｓｔｅｐ３：制御装置９Ｃは、もしｘ1 ＝ｘ2 かつｙ1 ＝ｙ2 ならｆ＝真としてＳｔｅｐ５へ制御転送する。
Ｓｔｅｐ４：制御装置９Ｃは、ｘ1 ≠ｘ2 又はｙ1 ≠ｙ2 であればｆ＝偽とする。
Ｓｔｅｐ５：制御装置９Ｃは、ｆを論理式Ｐ＝Ｑの値として出力する。
楕円比較器１０Ａ
図１０に「楕円比較器」の他の例を示す。
【００６７】
装置１０Ａは三値座標（ｐｒｏｊｅｃｔｉｖｅ座標）における楕円曲線Ｅ上の有理点Ｐ＝（Ｘ1 ，Ｙ1 ，Ｚ1 ）およびＱ＝（Ｘ2 ，Ｙ2 ，Ｚ2 ）の入力に対して論理式Ｐ＝Ｑの真偽を出力する装置の構成の一例を表している。
装置１０Ａは
・メモリ１０Ｂ
・制御装置１０Ｃ
からなる。
【００６８】
この装置の動作をプログラムで実現する場合は、図４５のフロー図に従って実行する。
この装置では、以下のように演算が実行される。
Ｓｔｅｐ１：制御装置１０Ｃは、入力Ｐ＝（Ｘ1 ，Ｙ1 ，Ｚ1 ）およびＱ＝（Ｘ2 ，Ｙ2 ，Ｚ2 ）に対してＸ1 Ｚ2 がＸ2 Ｚ1 と等しいかどうか調べる。
【００６９】
Ｓｔｅｐ２：制御装置１０Ｃは、Ｘ1 Ｚ2 ＝Ｘ2 Ｚ1 であれば、入力Ｐ＝（Ｘ1 ，Ｙ1 ，Ｚ1 ）およびＱ＝（Ｘ2 ，Ｙ2 ，Ｚ2 ）に対してＹ1 Ｚ2 がＹ2 Ｚ1 と等しいかどうか調べる。
Ｓｔｅｐ３：制御装置１０Ｃは、もしＸ1 Ｚ2 ＝Ｘ2 Ｚ1 かつＹ1 Ｚ2 ＝Ｙ2 Ｚ1 ならｆ＝真としてＳｔｅｐ５へ制御転送する。
【００７０】
Ｓｔｅｐ４：制御装置１０Ｃは、Ｘ1 Ｚ2 ＝Ｘ2 Ｚ1 かつＹ1 Ｚ2 ＝Ｙ2 Ｚ1 でなければｆ＝偽とする。
Ｓｔｅｐ５：制御装置１０Ｃは、ｆを論理式Ｐ＝Ｑの値として出力する。
楕円比較器１１Ａ
図１１に「楕円比較器」の更に他の例を示す。
【００７１】
装置１１Ａは三値座標（Ｊａｃｏｂｉａｎ座標）における楕円曲線Ｅ上の有理点Ｐ＝（Ｘ1 ，Ｙ1 ，Ｚ1 ）およびＱ＝（Ｘ2 ，Ｙ2 ，Ｚ2 ）の入力に対して論理式Ｐ＝Ｑの真偽を出力する装置の構成の一例を表している。
装置１１Ａは
・メモリ１１Ｂ
・制御装置１１Ｃ
からなる。
【００７２】
この装置の動作をプログラムで実現する場合は、図４６に示すフロー図に従って実行する。
この装置では、以下のように演算が実行される。
Ｓｔｅｐ１：制御装置１１Ｃは、入力Ｐ＝（Ｘ1 ，Ｙ1 ，Ｚ1 ）およびＱ＝（Ｘ2 ，Ｙ2 ，Ｚ2 ）に対してＸ1 Ｚ22がＸ2 Ｚ12と等しいかどうか調べる。
【００７３】
Ｓｔｅｐ２：制御装置１１Ｃは、Ｘ1 Ｚ22＝Ｘ2 Ｚ12であれば、入力Ｐ＝（Ｘ1 ，Ｙ1 ，Ｚ1 ）およびＱ＝（Ｘ2 ，Ｙ2 ，Ｚ2 ）に対してＹ1 Ｚ23がＹ2 Ｚ13と等しいかどうか調べる。
Ｓｔｅｐ３：制御装置１１Ｃは、もしＸ1 Ｚ22＝Ｘ2 Ｚ12かつＹ1 Ｚ23＝Ｙ2 Ｚ13ならｆ＝真としてＳｔｅｐ５へ制御転送する。
【００７４】
Ｓｔｅｐ４：制御装置１１Ｃは、Ｘ1 Ｚ22＝Ｘ2 Ｚ12でなければ、あるいはＹ1 Ｚ23＝Ｙ2 Ｚ13でなければｆ＝偽とする。
Ｓｔｅｐ５：制御装置１１Ｃは、ｆを論理式Ｐ＝Ｑの値として出力する。
楕円加算器１２Ａ
図１２に「楕円加算器」の例を示す。
【００７５】
装置１２Ａは二値座標における楕円曲線Ｅ：ｙ2 ＝ｘ3 ＋ａｘ＋ｂ，ａ，ｂ∈ＧＦ（ｑn ），４ａ3 ＋２７ｂ2 ≠０）上の有理点Ｐ＝（ｘ1 ，ｙ1 ）およびＱ＝（ｘ2 ，ｙ2 ）（但しＰ≠±Ｑ）の入力に対して楕円曲線Ｅ上の有理点Ｐ＋Ｑを出力する装置の構成の一例を表している。
装置１２Ａは
・メモリ１２Ｂ
・制御装置１２Ｃ
・ＧＦ（ｑn ）自乗器１２Ｄ
・ＧＦ（ｑn ）減算器１２Ｅ
・ＧＦ（ｑn ）乗算器１２Ｆ
・ＧＦ（ｑn ）逆元器１２Ｇ
からなる。
【００７６】
ＧＦ（ｑn ）自乗器１２Ｄはこの発明を適用して図２４または図２５または図２６または図２７に示すように構成され、ＧＦ（ｑn ）減算器１２Ｅは図２１に示すように構成され、ＧＦ（ｑn ）乗算器１２Ｆも同様に図２２または図２３に示すように構成され、ＧＦ（ｑn ）逆元器１２Ｇは図２８または図２９に示すように構成される。
【００７７】
つまりＧＦ（ｑn ）自乗器１２ＤおよびＧＦ（ｑn ）減算器１２ＥおよびＧＦ（ｑn ）乗算器１２ＦおよびＧＦ（ｑn ）逆元器１２Ｇは図１９に示すＧＦ（ｑi ）演算器（ｉ＝ｎの場合）や図１８に示す逐次拡大演算装置の様な集積装置によって実現される。
この装置の動作をプログラムで実現する場合は、図４７に示すフロー図に従って実行する。
【００７８】
この装置では、以下のように演算が実行される。
Ｓｔｅｐ１：制御装置１２Ｃは、入力Ｐ＝（ｘ1 ，ｙ1 ）およびＱ＝（ｘ2 ，ｙ2 ）に対してＧＦ（ｑn ）減算器１２ＥおよびＧＦ（ｑn ）逆元器１２Ｇを用いてλ＝（ｙ2 −ｙ1 ）／（ｘ2 −ｘ1 ）を計算する。
Ｓｔｅｐ２：制御装置１２Ｃは、ＧＦ（ｑn ）減算器１２ＥおよびＧＦ（ｑn ）自乗器１２Ｄを用いてｘ3 ＝λ2 −ｘ1 −ｘ2 を計算する。
【００７９】
Ｓｔｅｐ３：制御装置１２Ｃは、ＧＦ（ｑn ）減算器１２ＥおよびＧＦ（ｑn ）乗算器１２Ｆを用いてｙ3 ＝λ（ｘ1 −ｘ3 ）−ｙ1 を計算する。
Ｓｔｅｐ４：制御装置１２Ｃは、（ｘ3 ，ｙ3 ）をＰ＋Ｑとして出力する。
楕円倍算器１３Ａ
図１３に「楕円倍算器」の例を示す。
【００８０】
装置１３Ａは二値座標における楕円曲線Ｅ：ｙ2 ＝ｘ3 ＋ａｘ＋ｂ（ａ，ｂ∈ＧＦ（ｑn ），４ａ3 ＋２７ｂ2 ≠０）上の有理点Ｐ＝（ｘ1 ，ｙ1 ）の入力に対して楕円曲線Ｅ上の有理点２Ｐを出力する装置の構成の一例を表している。
装置１３Ａは
・メモリ１３Ｂ
・制御装置１３Ｃ
・ＧＦ（ｑn ）加算器１３Ｄ
・ＧＦ（ｑn ）減算器１３Ｅ
・ＧＦ（ｑn ）乗算器１３Ｆ
・ＧＦ（ｑn ）逆元器１３Ｇ
・ＧＦ（ｑn ）自乗器１３Ｈ
からなる。
【００８１】
ＧＦ（ｑn ）加算器１３Ｄはこの発明を適用して図２０に示すように構成され、ＧＦ（ｑn ）減算器１３Ｅは図２１に示すように構成され、ＧＦ（ｑn ）乗算器１３Ｆも同様に図２２または図２３に示すように構成され、ＧＦ（ｑn ）逆元器１３Ｇも同様に図２８または図２９に示すように構成され、ＧＦ（ｑn ）自乗器１３Ｈも同様に図２４または図２５または図２６または図２７に示すように構成される。
【００８２】
つまりＧＦ（ｑn ）加算器１３ＤおよびＧＦ（ｑn ）減算器１３ＥおよびＧＦ（ｑn ）乗算器１３ＦおよびＧＦ（ｑn ）逆元器１３ＧおよびＧＦ（ｑn ）自乗器１３Ｈは図１９に示すＧＦ（ｑi ）演算器（ｉ＝ｎの場合）や図１８に示す逐次拡大演算装置の様な集積装置によって実現される。
この装置の動作をプログラムで実現する場合は、図４８に示すフロー図に従って実行する。
【００８３】
この装置では、以下のように演算が実行される。
Ｓｔｅｐ１：制御装置１３Ｃは、入力Ｐ＝（ｘ1 ，ｙ1 ）に対してＧＦ（ｑn ）加算器１３ＤおよびＧＦ（ｑn ）逆元器１３ＧおよびＧＦ（ｑn ）自乗器１３Ｈを用いてλ＝（３ｘ12＋ａ）／（２ｙ1 ）を計算する。
Ｓｔｅｐ２：制御装置１３Ｃは、ＧＦ（ｑn ）減算器１３ＥおよびＧＦ（ｑn ）自乗器１３Ｄを用いてｘ3 ＝λ2 −２ｘ1 を計算する。
【００８４】
Ｓｔｅｐ３：制御装置１３Ｃは、ＧＦ（ｑn ）減算器１３ＥおよびＧＦ（ｑn ）乗算器１３Ｄを用いてｙ3 ＝λ（ｘ1 −ｘ3 ）−ｙ1 を計算する。
Ｓｔｅｐ４：制御装置１３Ｃは、（ｘ3 ，ｙ3 ）を２Ｐとして出力する。
楕円加算器１４Ａ
図１４に「楕円加算器」の他の例を示す。
【００８５】
装置１４Ａは三値座標（ｐｒｏｊｅｃｔｉｖｅ座標）における楕円曲線Ｅ（：ｙ2 Ｚ＝ｘ3 ＋ａｘＺ2 ＋ｂＺ3 ，ａ，ｂ∈ＧＦ（ｑn ），４ａ3 ＋２７ｂ2 ≠０）上の有理点Ｐ＝（Ｘ1 ，Ｙ1 ，Ｚ1 ）およびＱ＝（Ｘ2 ，Ｙ2 ，Ｚ2 ）（但しＸ1 Ｚ2 ≠Ｘ2 Ｚ1 ）の入力に対して楕円曲線Ｅ上の有理点Ｐ＋Ｑを出力する装置の構成の一例を表している。
【００８６】
装置１４Ａは
・メモリ１４Ｂ
・制御装置１４Ｃ
・ＧＦ（ｑn ）自乗器１４Ｄ
・ＧＦ（ｑn ）減算器１４Ｅ
・ＧＦ（ｑn ）乗算器１４Ｆ
からなる。
【００８７】
ＧＦ（ｑn ）自乗器１４Ｄはこの発明を適用して図２４または図２５または図２６または図２７に示すように構成され、ＧＦ（ｑn ）減算器１４Ｅも同様に図２１に示すように構成され、ＧＦ（ｑn ）乗算器１４Ｆも同様に図２２または図２３に示すように構成される。
つまりＧＦ（ｑn ）自乗器１４ＤおよびＧＦ（ｑn ）減算器１４ＥおよびＧＦ（ｑn ）乗算器１４Ｆは図１９に示すＧＦ（ｑi ）演算器（ｉ＝ｎの場合）や図１８に示す逐次拡大演算装置の様な集積装置によって実現される。
【００８８】
この装置の動作をプログラムで実現する場合は、図４９に示すフロー図に従って実行する。
この装置では、以下のように演算が実行される。
Ｓｔｅｐ１：制御装置１４Ｃは、入力Ｐ＝（Ｘ1 ，Ｙ1 ，Ｚ1 ）およびＱ＝（Ｘ2 ，Ｙ2 ，Ｚ2 ）に対してＧＦ（ｑn ）減算器１４ＥおよびＧＦ（ｑn ）乗算器１４Ｆを用いてｕ＝Ｙ2 Ｚ1 −Ｙ1 Ｚ2 を計算する。
【００８９】
Ｓｔｅｐ２：制御装置１４Ｃは、ＧＦ（ｑn ）減算器１４ＥおよびＧＦ（ｑn ）乗算器１４Ｆを用いてｖ＝Ｘ2 Ｚ1 −Ｘ1 Ｚ2 を計算する。
Ｓｔｅｐ３：制御装置１４Ｃは、ＧＦ（ｑn ）自乗器１４ＤおよびＧＦ（ｑn ）減算器１４ＥおよびＧＦ（ｑn ）乗算器１４Ｆを用いてＡ＝ｕ2 Ｚ1 Ｚ2 −ｖ3 −２ｖ2 Ｘ1 Ｚ2 を計算する。
【００９０】
Ｓｔｅｐ４：制御装置１４Ｃは、ＧＦ（ｑn ）乗算器１４Ｆを用いてＸ3 ＝ｖＡを計算する。
Ｓｔｅｐ５：制御装置１４Ｃは、ＧＦ（ｑn ）自乗器１４ＤおよびＧＦ（ｑn ）減算器１４ＥおよびＧＦ（ｑn ）乗算器１４Ｆを用いてＹ3 ＝ｕ（ｖ2 Ｘ1 Ｚ2 −Ａ）−ｖ3 Ｙ1 Ｚ2 を計算する。
【００９１】
Ｓｔｅｐ６：制御装置１４Ｃは、ＧＦ（ｑn ）自乗器１４ＤおよびＧＦ（ｑn ）乗算器１４Ｆを用いてＺ3 ＝ｖ3 Ｚ1 Ｚ2 を計算する。
Ｓｔｅｐ７：制御装置１４Ｃは、（Ｘ3 ，Ｙ3 ，Ｚ3 ）をＰ＋Ｑとして出力する。
楕円倍算器１５Ａ
図１５に「楕円倍算器」の他の例を示す。
【００９２】
装置１５Ａは三値座標（ｐｒｏｊｅｃｔｉｖｅ座標）における楕円曲線Ｅ（：Ｙ2 Ｚ＝ｘ3 ＋ａｘＺ2 ＋ｂＺ3 ，ａ，ｂ∈ＧＦ（ｑn ），４ａ3 ＋２７ｂ2 ≠０）上の有理点Ｐ＝（Ｘ1 ，Ｙ1 ，Ｚ1 ）の入力に対して楕円曲線Ｅ上の有理点２Ｐを出力する装置の構成の一例を表している。
装置１５Ａは
・メモリ１５Ｂ
・制御装置１５Ｃ
・ＧＦ（ｑn ）加算器１５Ｄ
・ＧＦ（ｑn ）減算器１５Ｅ
・ＧＦ（ｑn ）乗算器１５Ｆ
・ＧＦ（ｑn ）自乗器１５Ｇ
からなる。
【００９３】
ＧＦ（ｑn ）加算器１５Ｄはこの発明を適用して図２０に示すように構成され、ＧＦ（ｑn ）減算器１５Ｅは図２１に示すように構成され、ＧＦ（ｑn ）乗算器１５Ｆも同様に図２２または図２３に示すように構成され、ＧＦ（ｑn ）自乗器１５Ｇも同様に図２４または図２５または図２６または図２７に示すように構成される。
【００９４】
つまりＧＦ（ｑn ）加算器１５ＤおよびＧＦ（ｑn ）減算器１５ＥおよびＧＦ（ｑn ）乗算器１５ＦおよびＧＦ（ｑn ）自乗器１５Ｇは図１９に示すＧＦ（ｑi ）演算器（ｉ＝ｎの場合）や図１８に示す逐次拡大演算装置の様な集積装置によって実現される。
この装置の動作をプログラムで実現する場合は、図５０に示すフロー図に従って実行する。
【００９５】
この装置では、以下のように演算が実行される。
Ｓｔｅｐ１：制御装置１５Ｃは、入力Ｐ＝（Ｘ1 ，Ｙ1 ，Ｚ1 ）に対してＧＦ（ｑn ）加算器１５ＤおよびＧＦ（ｑn ）自乗器１５Ｇを用いてｗ＝３Ｘ12＋ａＺ12を計算する。
Ｓｔｅｐ２：制御装置１５Ｃは、ＧＦ（ｑn ）乗算器１５Ｆを用いてｓ＝Ｙ1 Ｚ1 を計算する。
【００９６】
Ｓｔｅｐ３：制御装置１５Ｃは、ＧＦ（ｑn ）乗算器１５Ｆを用いてＢ＝Ｘ1 Ｙ1 ｓを計算する。
Ｓｔｅｐ４：制御装置１５Ｃは、ＧＦ（ｑn ）減算器１５ＥおよびＧＦ（ｑn ）乗算器１５ＦおよびＧＦ（ｑn ）自乗器１５Ｇを用いてｈ＝ｗ2 −８Ｂを計算する。
【００９７】
Ｓｔｅｐ５：制御装置１５Ｃは、ＧＦ（ｑn ）乗算器１５Ｆを用いてＸ3 ＝２ｈｓを計算する。
Ｓｔｅｐ６：制御装置１５Ｃは、ＧＦ（ｑn ）減算器１５ＥおよびＧＦ（ｑn ）乗算器１５ＦおよびＧＦ（ｑn ）自乗器１５Ｇを用いてＹ3 ＝ｗ（４Ｂ−ｈ）−８Ｙ12ｓ2 を計算する。
【００９８】
Ｓｔｅｐ７：制御装置１５Ｃは、ＧＦ（ｑn ）乗算器１５ＦおよびＧＦ（ｑn ）自乗器１５Ｇを用いてＺ3 ＝８ｓ3 を計算する。
Ｓｔｅｐ８：制御装置１５Ｃは、（Ｘ3 ，Ｙ3 ，Ｚ3 ）を２Ｐとして出力する。
楕円加算器１６Ａ
図１６に「楕円加算器」の他の例を示す。
【００９９】
装置１６Ａは三値座標（Ｊａｃｏｂｉａｎ座標）における楕円曲線Ｅ（：Ｙ2 ＝ｘ3 ＋ａｘＺ4 ＋ｂＺ6 ，ａ，ｂ∈ＧＦ（ｑn ），４ａ3 ＋２７ｂ2 ≠０）上の有理点Ｐ＝（Ｘ1 ，Ｙ1 ，Ｚ1 ）およびＱ＝（Ｘ2 ，Ｙ2 ，Ｚ2 ）（但し、Ｘ1 Ｚ2 ≠Ｘ2 Ｚ1 ）の入力に対して楕円曲線Ｅ上の有理点Ｐ＋Ｑを出力する装置の構成の一例を表している。
【０１００】
装置１６Ａは
・メモリ１６Ｂ
・制御装置１６Ｃ
・ＧＦ（ｑn ）自乗器１６Ｄ
・ＧＦ（ｑn ）減算器１６Ｅ
・ＧＦ（ｑn ）乗算器１６Ｆ
からなる。
【０１０１】
ＧＦ（ｑn ）自乗器１６Ｄはこの発明を適用して図２４または図２５または図２６または図２７に示すように構成され、ＧＦ（ｑn ）減算器１６Ｅも同様に図２１に示すように構成され、ＧＦ（ｑn ）乗算器１６Ｆも同様に図２２または図２３に示すように構成される。
つまりＧＦ（ｑn ）自乗器１６ＤおよびＧＦ（ｑn ）減算器１６ＥおよびＧＦ（ｑn ）乗算器１６Ｆは図１９に示すＧＦ（ｑi ）演算器（ｉ＝ｎの場合）や図１８に示す逐次拡大演算装置の様な集積装置によって実現される。
【０１０２】
この装置の動作をプログラムで実現する場合は、図５１に示すフロー図に従って実行する。
この装置では、以下のように演算が実行される。
Ｓｔｅｐ１：制御装置１６Ｃは、入力Ｐ＝（Ｘ1 ，Ｙ1 ，Ｚ1 ）およびＱ＝（Ｘ2 ，Ｙ2 ，Ｚ2 ）に対してＧＦ（ｑn ）乗算器１６ＦおよびＧＦ（ｑn ）自乗器１６Ｇを用いてＵ1 ＝Ｘ1 Ｚ22を計算する。
【０１０３】
Ｓｔｅｐ２：制御装置１６Ｃは、ＧＦ（ｑn ）自乗器１６ＤおよびＧＦ（ｑn ）乗算器１６Ｆを用いてＵ2 ＝Ｘ2 Ｚ12を計算する。
Ｓｔｅｐ３：制御装置１６Ｃは、ＧＦ（ｑn ）自乗器１６ＤおよびＧＦ（ｑn ）乗算器１６Ｆを用いてＳ1 ＝Ｙ1 Ｚ23を計算する。
Ｓｔｅｐ４：制御装置１６Ｃは、ＧＦ（ｑn ）自乗器１６ＤおよびＧＦ（ｑn ）乗算器１６Ｆを用いてＳ2 ＝Ｙ2 Ｚ13を計算する。
【０１０４】
Ｓｔｅｐ５：制御装置１６Ｃは、ＧＦ（ｑn ）減算器１６Ｅを用いてＨ＝Ｕ2 −Ｕ1 を計算する。
Ｓｔｅｐ６：制御装置１６Ｃは、ＧＦ（ｑn ）減算器１６Ｅを用いてｒ＝Ｓ2 −Ｓ1 を計算する。
Ｓｔｅｐ７：制御装置１６Ｃは、ＧＦ（ｑn ）自乗器１６ＤおよびＧＦ（ｑn ）減算器１６ＥおよびＧＦ（ｑn ）乗算器１６Ｆを用いてＸ3 ＝ｒ2 −Ｈ3 −２Ｕ1 Ｈ2 を計算する。
【０１０５】
Ｓｔｅｐ８：制御装置１６Ｃは、ＧＦ（ｑn ）自乗器１６ＤおよびＧＦ（ｑn ）減算器１６ＥおよびＧＦ（ｑn ）乗算器１６Ｆを用いてＹ3 ＝ｒ（Ｕ1 Ｈ2 −Ｘ3 ）−Ｓ1 Ｈ3 を計算する。
Ｓｔｅｐ９：制御装置１６Ｃは、ＧＦ（ｑn ）乗算器１６Ｆを用いてＺ3 ＝Ｚ1 Ｚ2 Ｈを計算する。
【０１０６】
Ｓｔｅｐ１０：制御装置１６Ｃは、（Ｘ3 ，Ｙ3 ，Ｚ3 ）をＰ＋Ｑとして出力する。
楕円倍算器１７Ａ
図１７に「楕円倍算器」の他の例を示す。
装置１７Ａは三値座標（Ｊａｃｏｂｉａｎ座標）における楕円曲線Ｅ（：Ｙ2 ＝ｘ3 ＋ａｘＺ4 ＋ｂＺ6 ，ａ，ｂ∈ＧＦ（ｑn ），４ａ3 ＋２７ｂ2 ≠０）上の有理点Ｐ＝（Ｘ1 ，Ｙ1 ，Ｚ1 ）の入力に対して楕円曲線Ｅ上の有理点２Ｐを出力する装置の構成の一例を表している。
【０１０７】
装置１７Ａは
・メモリ１７Ｂ
・制御装置１７Ｃ
・ＧＦ（ｑn ）加算器１７Ｄ
・ＧＦ（ｑn ）減算器１７Ｅ
・ＧＦ（ｑn ）乗算器１７Ｆ
・ＧＦ（ｑn ）自乗器１７Ｇ
からなる。
【０１０８】
ＧＦ（ｑn ）加算器１７Ｄはこの発明を適用して図２０に示すように構成され、ＧＦ（ｑn ）減算器１７Ｅも同様に図２１に示すように構成され、ＧＦ（ｑn ）乗算器１７Ｆも同様に図２２または図２３に示すように構成され、ＧＦ（ｑn ）自乗器１７Ｇも同様に図２４または図２５または図２６または図２７に示すように構成される。
【０１０９】
つまりＧＦ（ｑn ）加算器１７ＤおよびＧＦ（ｑn ）減算器１７ＥおよびＧＦ（ｑn ）乗算器１７ＦおよびＧＦ（ｑn ）自乗器１７Ｇは図１９に示すＧＦ（ｑi ）演算器（ｉ＝ｎの場合）や図１８に示す逐次拡大演算装置の様な集積装置によって実現される。
この装置の動作をプログラムで実現する場合は、図５２に示すフロー図に従って実行する。
【０１１０】
この装置では、以下のように演算が実行される。
Ｓｔｅｐ１：制御装置１７Ｃは、入力Ｐ＝（Ｘ1 ，Ｙ1 ，Ｚ1 ）に対してＧＦ（ｑn ）加算器１７ＤおよびＧＦ（ｑn ）乗算器１７ＦおよびＧＦ（ｑn ）自乗器１７Ｇを用いてＭ＝３Ｘ12＋ａＺ4 を計算する。
Ｓｔｅｐ２：制御装置１７Ｃは、ＧＦ（ｑn ）乗算器１７ＦおよびＧＦ（ｑn ）自乗器１７Ｇを用いてＳ＝４Ｘ1 Ｙ12を計算する。
【０１１１】
Ｓｔｅｐ３：制御装置１７Ｃは、ＧＦ（ｑn ）減算器１７ＥおよびＧＦ（ｑn ）乗算器１７ＦおよびＧＦ（ｑn ）自乗器１７Ｇを用いてＸ3 ＝Ｍ2 −２Ｓを計算する。
Ｓｔｅｐ４：制御装置１７Ｃは、ＧＦ（ｑn ）減算器１７ＥおよびＧＦ（ｑn ）乗算器１７ＦおよびＧＦ（ｑn ）自乗器１７Ｇを用いてＹ3 ＝Ｍ（Ｓ−Ｘ3 ）−８Ｙ14を計算する。
【０１１２】
Ｓｔｅｐ５：制御装置１７Ｃは、ＧＦ（ｑn ）乗算器１７Ｆを用いてＺ3 ＝２Ｙ1 Ｚ1 を計算する。
Ｓｔｅｐ６：制御装置１７Ｃは、（Ｘ3 ，Ｙ3 ，Ｚ3 ）を２Ｐとして出力する。
逐次拡大装置１８Ａ
図１８にこの発明の要部である「逐次拡大装置」を示す。
【０１１３】
装置１８ＡはＧＦ（ｑn ）上の有理式の列Ｒ（ｘ0 ，ｘ1 ，…）及びｘ0 ，ｘ1 ，…の値、またはその値の格納場所を入力として、Ｒ（ｘ0 ，ｘ1 ，…）の値の列を出力する装置の構成の一例を表している。
装置実装を簡単にするため計算可能な有理式の型に制限を設けても良い。
ＧＦ（ｑn-1 ）演算器１８Ｂは図１９（ｉ＝ｎ−１の場合）に示すように構成され、ＧＦ（ｑn-2 ）演算器１８Ｃは図１９（ｉ＝ｎ−２の場合）に示すように構成され、以下順次同様に構成される。
【０１１４】
ＧＦ（ｑi ）演算器においては一度にＧＦ（ｑi ）上演算の列を全部ＧＦ（ｑi-1 ）上演算の列に帰着させてからＧＦ（ｑi-1 ）演算器に渡す必要は無く、部分的に帰着させながら何度もＧＦ（ｑi-1 ）演算器に渡すように装置を構成し、また、部分的に帰着させながら得たＧＦ（ｑi-1 ）演算器の出力結果をＧＦ（ｑi-1 ）演算器の入力として利用できるよう装置を構成する。
【０１１５】
この装置の動作をプログラムで実現する場合は、図５３に示すフロー図に従って実行する。
この装置では、以下のように演算が実行される。
Ｓｔｅｐ１：ＧＦ（ｑn ）演算器１８Ａは、入力Ｒ（ｘ0 ，ｘ1 ，…）及びｘ0 ，ｘ1 ，…の値に対して、この演算の列とデータをＧＦ（ｑn-1 ）上の演算の列とデータに帰着させ、ＧＦ（ｑn-1 ）演算器１８Ｂに渡す。
【０１１６】
Ｓｔｅｐ２：ＧＦ（ｑn-1 ）演算器１８Ｂは、入力をＧＦ（ｑn-2 ）上の演算の列とデータに帰着させ、ＧＦ（ｑn-2 ）演算器１８Ｃに渡す。
Ｓｔｅｐ３：同様にしてＧＦ（ｑo ）まで演算の列とデータを帰着させＧＦ（ｑo ）演算器１８Ｄがこれを計算する。
Ｓｔｅｐ４：計算されたＲ（ｘ0 ，ｘ1 ，…）の値の列を出力する。
一般的にはｑ0 ＝ｐ，ｑ1 ＝ｐs1，ｑ2 ＝（ｐs1）s2，…，ｑz ＝（…（（ｐs1）s2）…）sz＝ｐm を満すようにｍ＝ｓ1 ｓ2 …ｓz と分解し、つまりＧＦ（ｐm ）をＧＦ（（（（ｐs1）s2）…）szとみなし、ＧＦ（ｑ0 ）上のｓ1 個の元によってＧＦ（ｑ1 ）上の元をあらわす演算ＧＦ（ｑ1 ）を行い、ＧＦ（ｑ1 ）上のｓ2 個の元によってＧＦ（ｑ2 ）上の元をあらわす演算ＧＦ（ｑ2 ）を行い、以下同様にして、最終的にＧＦ（ｑz-1 ）＝ＧＦ（ｐm ）上の元をあらわす。ここで、使用される楕円曲線演算においてＧＦ（ｑ）のｑに要求される数、例えば暗号では１６０ビット程度が要求されるが、ｐm が１６０ビット以上になるように、ｓ1 ，ｓ2 ，…，ｓz を適度に決めればよい。
ＧＦ（ｑi ）演算器１９Ａ
図１９に「ＧＦ（ｑi ）演算器」を示す。
【０１１７】
装置１９ＡはＧＦ（ｑi ）上の有理式の列Ｒ（ｘ0 ，ｘ1 ，…）及びｘ0 ，ｘ1 ，…の値、またはその値の格納場所を入力として、Ｒ（ｘ0 ，ｘ1 ，…）の値の列を出力する装置の構成の一例を表している。
装置実装の簡単のため計算可能な有理式の型に制限を設けても良い。
ＧＦ（ｑi ）演算器においては一度にＧＦ（ｑi ）上演算の列を全部ＧＦ（ｑi-1 ）上演算の列に帰着させてからＧＦ（ｑi-1 ）演算器に渡す必要は無く、部分的に帰着させながら何度もＧＦ（ｑi-1 ）演算器に渡すよう装置を構成し、また、部分的に帰着させながら得たＧＦ（ｑi-1 ）演算器の出力結果をＧＦ（ｑi-1 ）演算器の入力として利用できるよう装置を構成する。
【０１１８】
装置１９Ａは
・メモリ１９Ｂ
・制御装置１９Ｃ
・ＧＦ（ｑi ）定数倍器１９Ｄ
・ＧＦ（ｑi ）加算器１９Ｅ
・ＧＦ（ｑi ）減算器１９Ｆ
・ＧＦ（ｑi ）乗算器１９Ｇ
・ＧＦ（ｑi ）自乗器１９Ｈ
・ＧＦ（ｑi ）逆元器１９Ｉ
の全部又はメモリ１９Ｂ、制御装置１９Ｃを除く他の一部からなる。
【０１１９】
ＧＦ（ｑi ）定数倍器１９Ｄは図３０または図３１または図３２または図３３または図３４または図３５に示すように構成され、ＧＦ（ｑi ）加算器１９Ｅは図２０（ｎ＝ｉの場合）に示すように構成され、ＧＦ（ｑi ）減算器１９Ｆは図２１（ｎ＝ｉの場合）に示すように構成され、ＧＦ（ｑi ）乗算器１９Ｇは図２２（ｎ＝ｉの場合）または図２３（ｎ＝ｉの場合）に示すように構成され、ＧＦ（ｑi ）自乗器１９Ｈは図２４（ｎ＝ｉの場合）または図２５（ｎ＝ｉの場合）または図２６（ｎ＝ｉの場合）または図２７（ｎ＝ｉの場合）に示すように構成され、ＧＦ（ｑi ）逆元器１９Ｉは図２８（ｎ＝ｉの場合）または図２９（ｎ＝ｉの場合）に示すように構成される。
【０１２０】
この装置の動作をプログラムで実現する場合は、図５４に示すフロー図に従って実行する。
この装置では、以下のように演算が実行される。
Ｓｔｅｐ１：制御装置１９Ｃは、入力Ｒ（ｘ0 ，ｘ1 ，…）及びｘ0 ，ｘ1 ，…の値に対して、この演算の列とデータをＧＦ（ｑi-1 ）上の加算、減算、乗算、自乗、逆元、定数倍演算の列とデータに帰着させる。
【０１２１】
Ｓｔｅｐ２：制御装置１９Ｃは、メモリ１９ＢおよびＧＦ（ｑi ）定数倍器１９ＤおよびＧＦ（ｑi ）加算器１９ＥおよびＧＦ（ｑi ）減算器１９ＦおよびＧＦ（ｑi ）乗算器１９ＧおよびＧＦ（ｑi ）自乗器１９ＨおよびＧＦ（ｑi ）逆元器１９Ｉを用いて帰着の結果得られたＧＦ（ｑi-1 ）上演算の列を実行する。
Ｓｔｅｐ３：制御装置１９Ｃは、計算されたＲ（ｘ0 ，ｘ1 ，…）の値の列を出力する。
ＧＦ（ｑn ）加算器２０Ａ
図２０に「ＧＦ（ｑn ）加算器」を示す。
【０１２２】
この装置はＧＦ（ｑn-1 ）のｍ次拡大ＧＦ（ｑn ）＝ＧＦ（ｑn-1 m ）上の加算器のＧＦ（ｑn-1 ）上演算装置による一構成例である。この説明では簡単のためｍ＝２の場合を記述するが、同様の方法を一般のｍでも実現できる。
この説明および、図２０におけるＡ＝（Ａ0 ，Ａ1 ）およびＢ＝（Ｂ0 ，Ｂ1 ）およびＡ＋Ｂ＝（Ｃ0 ，Ｃ1 ）等の記述はＧＦ（ｑn ）＝ＧＦ（ｑn-1 m ）上の元、Ａ，Ｂ，Ａ＋Ｂ等のＧＦ（ｑn-1 ）上の元Ａ0 ，Ａ1 ，Ｂ0 ，Ｂ1 ，Ｃ0 ，Ｃ1 等による表現である。
【０１２３】
装置２０ＡはＧＦ（ｑn ）上の元Ａ＝（Ａ0 ，Ａ1 ）およびＢ＝（Ｂ0 ，Ｂ1 ）の入力に対してＧＦ（ｑn ）上の元Ａ＋Ｂを出力する装置の構成の一例を表している。
装置２０Ａは
・ＧＦ（ｑn-1 ）加算器２０Ｂ
・ＧＦ（ｑn-1 ）加算器２０Ｃ
からなる。
【０１２４】
この装置の動作をプログラムで実現する場合は、図５５に示すフロー図に従って実行する。
この装置では、以下のように演算が実行されるが、同時実行可能なステップは、並列に実行しても良い。また実行順序が交換可能なステップは実行順序を交換して良い。また同じ機能を持つ複数の装置による複数の演算は、装置を一元化して、順次演算を実行しても良い。
【０１２５】
Ｓｔｅｐ１：ＧＦ（ｑn-1 ）加算器２０Ｂは、入力のＡ0 およびＢ0 に対してＣ0 ←Ａ0 ＋Ｂ0 を計算してＣ0 を出力する。
Ｓｔｅｐ２：ＧＦ（ｑn-1 ）加算器２０Ｃは、入力のＡ1 およびＢ1 に対してＣ1 ←Ａ1 ＋Ｂ1 を計算してＣ1 を出力する。
Ｓｔｅｐ３：（Ｃ0 ，Ｃ1 ）をＡ＋Ｂとして出力する。
【０１２６】
一般にｓi 個のＧＦ（ｑi-1 ）の元の組であらわされたＧＦ（ｑi ）の元ａ＝（ａ0 ，ａ1 ，…，ａsi-1）およびｂ＝（ｂ0 ，ｂ1 ，…，ｂsi-1）が入力されると、ａ＋ｂ＝（ａ0 ＋ｂ0 ，ａ1 ＋ｂ1 ，…，ａsi-1＋ｂsi-1）を演算して出力する。
ＧＦ（ｑn ）減算器２１Ａ
図２１に「ＧＦ（ｑn ）減算器」を示す。
【０１２７】
この装置はＧＦ（ｑn-1 ）のｍ次拡大ＧＦ（ｑn ）＝ＧＦ（ｑn-1 m ）上の減算器のＧＦ（ｑn-1 ）上演算装置による一構成例である。この説明では簡単のためｍ＝２の場合を記述するが、同様の方法を一般のｍでも実現できる。
この説明および、図２１におけるＡ＝（Ａ0 ，Ａ1 ）およびＢ＝（Ｂ0 ，Ｂ1 ）およびＡ−Ｂ＝（Ｃ0 ，Ｃ1 ）等の記述はＧＦ（ｑn ）＝ＧＦ（ｑn-1 m ）上の元、Ａ，Ｂ，Ａ−Ｂ等のＧＦ（ｑn-1 ）上の元Ａ0 ，Ａ1 ，Ｂ0 ，Ｂ1 ，Ｃ0 ，Ｃ1 等による表現である。
【０１２８】
装置２１ＡはＧＦ（ｑn ）上の元Ａ＝（Ａ0 ，Ａ1 ）およびＢ＝（Ｂ0 ，Ｂ1 ）の入力に対してＧＦ（ｑn ）上の元Ａ−Ｂを出力する装置の構成の一例を表している。
装置２１Ａは
・ＧＦ（ｑn-1 ）減算器２１Ｂ
・ＧＦ（ｑn-1 ）減算器２１Ｃ
からなる。
【０１２９】
この装置の動作をプログラムで実現する場合は、図５６に示すフロー図に従って実行する。
この装置では、以下のように演算が実行されるが、同時実行可能なステップは、並列に実行しても良い。また実行順序が交換可能なステップは実行順序を交換して良い。また同じ機能を持つ複数の装置による複数の演算は、装置を一元化して、順次演算を実行しても良い。
【０１３０】
Ｓｔｅｐ１：ＧＦ（ｑn-1 ）減算器２１Ｂは、入力のＡ0 およびＢ0 に対してＣ0 ←Ａ0 −Ｂ0 を計算してＣ0 を出力する。
Ｓｔｅｐ２：ＧＦ（ｑn-1 ）減算器２１Ｃは、入力のＡ1 およびＢ1 に対してＣ1 ←Ａ1 −Ｂ1 を計算してＣ1 を出力する。
Ｓｔｅｐ３：（Ｃ0 ，Ｃ1 ）をＡ−Ｂとして出力する。
【０１３１】
一般にｓi 個のＧＦ（ｑi-1 ）の元の組であらわされたＧＦ（ｑi ）の元ａ＝（ａ0 ，ａ1 ，…，ａsi-1）およびｂ＝（ｂ0 ，ｂ1 ，…，ｂsi-1）が入力されると、ａ−ｂ＝（ａ0 −ｂ0 ，ａ1 −ｂ1 ，…，ａsi-1−ｂsi-1）を演算して出力する。
ＧＦ（ｑn ）乗算器２２Ａ
図２２に「ＧＦ（ｑn ）乗算器」を示す。
【０１３２】
この装置はＧＦ（ｑn-1 ）のｍ次既約多項式ｆ（ｘ）による拡大ＧＦ（ｑn ）＝ＧＦ（ｑn-1 m ）＝ＧＦ（ｑn-1 ）〔ｘ〕／（ｆ（ｘ））上の乗算器のＧＦ（ｑn-1 ）上演算装置による一構成例である。この説明では簡単のためｍ＝２の場合を記述するが、同様の方法を一般のｍでも実現できる。
この説明および、図２２においてＡ＝（Ａ0 ，Ａ1 ）およびＢ＝（Ｂ0 ，Ｂ1 ）およびＡ×Ｂ＝（Ｃ0 ，Ｃ1 ）は多項式基底によるＧＦ（ｑn ）＝ＧＦ（ｑn-1 m ）＝ＧＦ（ｑn-1 ）〔ｘ〕／（ｆ（ｘ））上の元のＧＦ（ｑn-1 ）上の元による表現であり、１およびα（但しｆ（α）＝０）を基底とするとそれぞれＡ＝Ａ0 ＋Ａ1 αおよびＢ＝Ｂ0 ＋Ｂ1 αおよびＡ×Ｂ＝Ｃ0 ＋Ｃ1 αを意味している。
【０１３３】
装置２２ＡはＧＦ（ｑn ）＝ＧＦ（ｑn-1 ）〔ｘ〕／（ｘ2 −ｓn ｘ−ｔn ）（ｆ（ｘ）＝ｘ2 −ｓn ｘ−ｔn ）上の元Ａ＝（Ａ0 ，Ａ1 ）およびＢ＝（Ｂ0 ，Ｂ1 ）の入力に対してＧＦ（ｑn ）上の元Ａ×Ｂを出力する装置の構成の一例を表している。
Ａ×Ｂ＝（Ａ0 ＋Ａ1 ）（Ｂ0 ＋Ｂ1 α）＝Ｃ0 ＋Ｃ1 αに対し３／４法を適用すると、
Ａ×Ｂ＝Ａ0 Ｂ0 ＋（（Ａ0 ＋Ａ1 ）（Ｂ0 ＋Ｂ1 ）−Ａ0 Ｂ0 −Ａ1 Ｂ1 ）α＋Ａ1 Ｂ1 α2 となり、ｆ（α）＝０、つまりα2 −ｓn α−ｔn ＝０であるからα2 ＝ｓn α＋ｔn を３／４法を適用したＡ×Ｂのα2 の項に代入すると、つまりｆ（α）の剰余をとることにより、
Ａ×Ｂ＝Ａ0 Ｂ0 ＋Ａ1 Ｂ1 ｔn ＋（（Ａ0 ＋Ａ1 ）（Ｂ0 ＋Ｂ1 ）−Ａ0 Ｂ0 ＋（ｓn −１）Ａ1 Ｂ1 ）α
となり、
Ｃ0 ＝Ａ0 Ｂ0 ＋Ａ1 Ｂ1 ｔn 
Ｃ1 ＝（Ａ0 ＋Ａ1 ）（Ｂ0 ＋Ｂ1 ）−Ａ0 Ｂ0 ＋（ｓn −１）Ａ1 Ｂ1 
を演算すればよい。この演算を行う装置２２Ａは
・ＧＦ（ｑn-1 ）乗算器２２Ｂ
・ＧＦ（ｑn-1 ）乗算器２２Ｃ
・ＧＦ（ｑn-1 ）加算器２２Ｄ
・ＧＦ（ｑn-1 ）加算器２２Ｅ
・ＧＦ（ｑn-1 ）乗算器２２Ｆ
・ＧＦ（ｑn-1 ）定数倍器２２Ｇ
・ＧＦ（ｑn-1 ）減算器２２Ｈ
・ＧＦ（ｑn-1 ）定数倍器２２Ｉ
・ＧＦ（ｑn-1 ）加算器２２Ｊ
・ＧＦ（ｑn-1 ）加算器２２Ｋ
からなる。
【０１３４】
ＧＦ（ｑn-1 ）定数倍器２２Ｇは図３０（ｉ＝ｎ−１の場合）または図３１（ｉ＝ｎ−１の場合）または図３２（ｉ＝ｎ−１の場合）または図３３（ｉ＝ｎ−１の場合）または図３４（ｉ＝ｎ−１の場合）または図３５（ｉ＝ｎ−１の場合）に示すように構成されＧＦ（ｑn-1 ）上のｔn 倍を加減算程度の速度か、それよりも高速に計算できる。
【０１３５】
ＧＦ（ｑn-1 ）定数倍器２２Ｉは図３０（ｉ＝ｎ−１の場合）または図３１（ｉ＝ｎ−１の場合）または図３２（ｉ＝ｎ−１の場合）または図３３（ｉ＝ｎ−１の場合）または図３４（ｉ＝ｎ−１の場合）または図３５（ｉ＝ｎ−１の場合）に示すように構成され、ＧＦ（ｑn-1 ）上の（ｓn −１）倍を加減算程度の速度か、それよりも高速に計算できる。
【０１３６】
この装置の動作をプログラムで実現する場合は、図５７に示すフロー図に従って実行する。
この装置では、以下のように演算が実行されるが、同時実行可能なステップは、並列に実行しても良い。また実行順序が交換可能なステップは実行順序を交換して良い。また同じ機能を持つ複数の装置による複数の演算は、装置を一元化して、順次演算を実行しても良い。
【０１３７】
Ｓｔｅｐ１：ＧＦ（ｑn-1 ）乗算器２２Ｂは入力のＡ0 およびＢ0 に対してＬ0 ←Ａ0 ×Ｂ0 を計算してＬ0 を出力する。
Ｓｔｅｐ２：ＧＦ（ｑn-1 ）加算器２２Ｄは入力のＡ0 およびＡ1 に対してＬ1 ←Ａ0 ＋Ａ1 を計算してＬ1 を出力する。
Ｓｔｅｐ３：ＧＦ（ｑn-1 ）加算器２２Ｅは入力のＢ0 およびＢ1 に対してＬ2 ←Ｂ0 ＋Ｂ1 を計算してＬ2 を出力する。
【０１３８】
Ｓｔｅｐ４：ＧＦ（ｑn-1 ）乗算器２２Ｃは入力のＡ1 およびＢ1 に対してＬ3 ←Ａ1 ×Ｂ1 を計算してＬ3 を出力する。
Ｓｔｅｐ５：ＧＦ（ｑn-1 ）乗算器２２Ｆは入力のＬ1 およびＬ2 に対してＬ4 ←Ｌ1 ×Ｌ2 を計算してＬ4 を出力する。
Ｓｔｅｐ６：ＧＦ（ｑn-1 ）定数倍器２２Ｇは入力のＬ3 に対してＬ5 ←ｔn Ｌ3 を計算してＬ5 を出力する。
【０１３９】
Ｓｔｅｐ７：ＧＦ（ｑn-1 ）減算器２２Ｈは入力のＬ0 およびＬ4 に対してＬ6 ←Ｌ4 −Ｌ0 を計算してＬ6 を出力する。
Ｓｔｅｐ８：ＧＦ（ｑn-1 ）定数倍器２２Ｉは入力のＬ3 に対してＬ7 ←（ｓn −１）Ｌ3 を計算してＬ7 を出力する。
Ｓｔｅｐ９：ＧＦ（ｑn-1 ）加算器２２Ｊは入力のＬ0 およびＬ5 に対してＣ0 ←Ｌ0 ＋Ｌ5 を計算してＣ0 を出力する。
【０１４０】
Ｓｔｅｐ１０：ＧＦ（ｑn-1 ）加算器２２Ｋは入力のＬ6 およびＬ7 に対してＣ1 ←Ｌ6 ＋Ｌ7 を計算してＣ1 を出力する。
Ｓｔｅｐ１１：（Ｃ0 ，Ｃ1 ）をＡ×Ｂとして出力する。
なお、一般的にａ＝（ａ0 ，ａ1 ，…，ａs-1 ）、ｂ＝（ｂ0 ，ｂ1 ，…，ｂs-1 ）が入力され、ａ（α）＝ａ0 ＋ａ1 α＋ａ2 α2 ＋…＋ａs-1 αsi-1＝Ａ0 （α）＋Ａ1 （α）αs'
ｂ（α）＝ｂ0 ＋ｂ1 α＋ｂ2 α2 ＋…＋ｂs-1 αsi-1＝Ｂ0 （α）＋Ｂ1 （α）αs'
ｃ（α）＝ｃ0 ＋ｃ1 α＋ｃ2 α2 ＋…＋ｃsi-1αsi-1
とし、ただしｓ1 はｓi ／２に近い整数でＡi ，Ｂi はｓ＋１次以下の多項式である。この時、
0003639153.tif 000008
）を演算する。
【０１４１】
この際３／４法を適用し、かつmod ｆ（α）をとることによりα2s' の項はαs'の項となり、ｆ（ｘ）が２次式の場合と同様にＧＦ（ｑi-1 ）上の乗算回数を約３／４にすることができる。
ＧＦ（ｑn ）乗算器２３Ａ
図２３に「ＧＦ（ｑn ）乗算器」（正規基底）の例を示す。
【０１４２】
この装置はＧＦ（ｑn-1 ）のｍ次拡大ＧＦ（ｑn ）＝ＧＦ（ｑn-1 m ）上の乗算器のＧＦ（ｑn-1 ）上演算装置による一構成例である。
この説明では特にｍ＝２の場合を記述するが、同様の方法を一般のｍでも実現できる。
この説明および、図２３においてＡ＝（Ａ0 ，Ａ1 ）およびＢ＝（Ｂ0 ，Ｂ1 ）およびＡ×Ｂ＝（Ｃ0 ，Ｃ1 ）は正規基底によるＧＦ（ｑn ）＝ＧＦ（ｑn-1 m ）上の元のＧＦ（ｑn-1 ）上の元による表現であり、基底をα0 およびα1 とするとそれぞれＡ＝Ａ0 α0 ＋Ａ1 α1 およびＢ＝Ｂ0 α0 ＋Ｂ1 α1 およびＡ×Ｂ＝Ｃ0 α0 ＋Ｃ1 α1 を意味している。
【０１４３】
全ての基底を解にもつＧＦ（ｑn-1 ）上ｍ次既約多項式をｆ（ｘ）＝ｘ2 −ｓn ｘ−ｔn とする。
装置２３ＡはＧＦ（ｑn ）＝ＧＦ（ｑn-1 m ）上の元Ａ＝（Ａ0 ，Ａ1 ）およびＢ＝（Ｂ0 ，Ｂ1 ）の入力に対してＧＦ（ｑn ）上の元Ａ×Ｂを出力する装置の構成の一例を表している。
【０１４４】
装置２３Ａは
・ＧＦ（ｑn-1 ）乗算器２３Ｂ
・ＧＦ（ｑn-1 ）乗算器２３Ｃ
・ＧＦ（ｑn-1 ）減算器２３Ｄ
・ＧＦ（ｑn-1 ）減算器２３Ｅ
・ＧＦ（ｑn-1 ）定数倍器２３Ｆ
・ＧＦ（ｑn-1 ）乗算器２３Ｇ
・ＧＦ（ｑn-1 ）定数倍器２３Ｈ
・ＧＦ（ｑn-1 ）定数倍器２３Ｉ
・ＧＦ（ｑn-1 ）加算器２３Ｊ
・ＧＦ（ｑn-1 ）加算器２３Ｋ
からなる。
【０１４５】
ＧＦ（ｑn-1 ）定数倍器２３ＦおよびＧＦ（ｑn-1 ）定数倍器２３Ｈは図３０（ｉ＝ｎ−１の場合）または図３１（ｉ＝ｎ−１の場合）または図３２（ｉ＝ｎ−１の場合）または図３３（ｉ＝ｎ−１の場合）または図３４（ｉ＝ｎ−１の場合）または図３５（ｉ＝ｎ−１の場合）に示すように構成され、ＧＦ（ｑn-1 ）上のｓn 倍を加減算程度の速度か、それよりも高速に計算できる。
【０１４６】
ＧＦ（ｑn-1 ）定数倍器２３Ｉは図３０（ｉ＝ｎ−１の場合）または図３１（ｉ＝ｎ−１の場合）または図３２（ｉ＝ｎ−１の場合）または図３３（ｉ＝ｎ−１の場合）または図３４（ｉ＝ｎ−１の場合）または図３５（ｉ＝ｎ−１の場合）に示すように構成され、ＧＦ（ｑn-1 ）上の（ｓn -1ｔn ）倍を加減算程度の速度か、それよりも高速に計算できる。
【０１４７】
この装置の動作をプログラムで実現する場合は、図５８に示すフロー図に従って実行する。
この装置では、以下のように演算が実行されるが、同時実行可能なステップは、並列に実行しても良い。また実行順序が交換可能なステップは実行順序を交換して良い。また同じ機能を持つ複数の装置による複数の演算は、装置を一元化して、順次演算を実行しても良い。
【０１４８】
Ｓｔｅｐ１：ＧＦ（ｑn-1 ）乗算器２３Ｂは入力のＡ0 およびＢ0 に対してＬ0 ←Ａ0 ×Ｂ0 を計算してＬ0 を出力する。
Ｓｔｅｐ２：ＧＦ（ｑn-1 ）減算器２３Ｄは入力のＡ0 およびＡ1 に対してＬ1 ←Ａ0 −Ａ1 を計算してＬ1 を出力する。
Ｓｔｅｐ３：ＧＦ（ｑn-1 ）減算器２３Ｅは入力のＢ0 およびＢ1 に対してＬ2 ←Ｂ0 −Ｂ1 を計算してＬ2 を出力する。
【０１４９】
Ｓｔｅｐ４：ＧＦ（ｑn-1 ）乗算器２３Ｃは入力のＡ1 およびＢ1 に対してＬ3 ←Ａ1 ×Ｂ1 を計算してＬ3 を出力する。
Ｓｔｅｐ５：ＧＦ（ｑn-1 ）定数倍器２３Ｆは入力のＬ0 に対してＬ4 ←ｓn Ｌ0 を計算してＬ4 を出力する。
Ｓｔｅｐ６：ＧＦ（ｑn-1 ）乗算器２３Ｇは入力のＬ1 およびＬ2 に対してＬ5 ←Ｌ1 ×Ｌ2 を計算してＬ5 を出力する。
【０１５０】
Ｓｔｅｐ７：ＧＦ（ｑn-1 ）定数倍器２３Ｈは入力のＬ3 に対してＬ6 ←ｓn Ｌ3 を計算してＬ6 を出力する。
Ｓｔｅｐ８：ＧＦ（ｑn-1 ）定数倍器２３Ｉは入力のＬ5 に対してＬ7 ←（ｓn -1ｔn ）Ｌ5 を計算してＬ7 を出力する。
Ｓｔｅｐ９：ＧＦ（ｑn-1 ）加算器２３Ｊは入力のＬ4 およびＬ7 に対してＣ0 ←Ｌ4 ＋Ｌ7 を計算してＣ0 を出力する。
【０１５１】
Ｓｔｅｐ１０：ＧＦ（ｑn-1 ）加算器２３Ｋは入力のＬ6 およびＬ7 に対してＣ1 ←Ｌ6 ＋Ｌ7 を計算してＣ1 を出力する。
Ｓｔｅｐ１１：（Ｃ0 ，Ｃ1 ）をＡ×Ｂとして出力する。
一般にａ＝（ａ0 ，ａ1 ，…，ａsi-1）、ｂ＝（ｂ0 ，ｂ1 ，…，ｂsi-1）が入力された場合は、
【０１５２】
【数１２】
0003639153.tif 000009
とし、ただしｓ’はｑsi/2に近い整数、Ａi ，Ｂi はｓ’次以下の多項式とし、
0003639153.tif 000010
を演算する。
【０１５３】
この場合もこの式にｆ（α）の剰余をとり、α2s'-1 の項をαs'の項として乗算回数を減らすことができる。
ＧＦ（ｑn ）自乗器２４Ａ
図２４に「ＧＦ（ｑn ）自乗器」の例を示す。
この装置はＧＦ（ｑn-1 ）上のｍ次既約多項式ｆ（ｘ）による拡大ＧＦ（ｑn ）＝ＧＦ（ｑn-1 m ）＝ＧＦ（ｑn-1 ）〔ｘ〕／（ｆ（ｘ））上の自乗器のＧＦ（ｑn-1 ）上演算装置による一構成例である。この説明では簡単のためｍ＝２の場合を記述するが、同様の方法を一般のｍでも実現できる。
【０１５４】
この説明および、図２４においてＡ＝（Ａ0 ，Ａ1 ）およびＡ2 ＝（Ｃ0 ，Ｃ1 ）は多項式基底によるＧＦ（ｑn ）＝ＧＦ（ｑn-1 m ）＝ＧＦ（ｑn-1 ）〔ｘ〕／（ｆ（ｘ））上の元のＧＦ（ｑn-1 ）上の元による表現であり、１およびα（但しｆ（α）＝０）を基底とするとそれぞれＡ＝Ａ0 ＋Ａ1 αおよびＡ2 ＝Ｃ0 ＋Ｃ1 αを意味している。
【０１５５】
装置２４ＡはＧＦ（ｑn ）＝ＧＦ（ｑn-1 ）〔ｘ〕／（ｘ2 −ｓn ｘ−ｔn ）（ｆ（ｘ）＝ｘ2 −ｓn ｘ−ｔn ）上の元Ａ＝（Ａ0 ，Ａ1 ）の入力に対してＧＦ（ｑn ）上の元Ａ2 を出力する装置の構成の一例を表している。Ａ2 ＝Ｃ0 ＋Ｃ1 α＝Ａ02＋Ａ12α2 ＋２Ａ0 Ａ1 α（mod ｆ（α））に対しα2 ＝ｓn α＋ｔn の関係を代入するとＡ2 ＝（Ａ02＋ｔn Ａ12）＋（２Ａ0 Ａ1 ＋ｓn Ａ12）αとなり、ＧＦ（ｑn-1 ）の元でＡ2 を演算することができる。
【０１５６】
装置２４Ａは
・ＧＦ（ｑn-1 ）自乗器２４Ｂ
・ＧＦ（ｑn-1 ）乗算器２４Ｃ
・ＧＦ（ｑn-1 ）自乗器２４Ｄ
・ＧＦ（ｑn-1 ）定数倍器２４Ｅ
・ＧＦ（ｑn-1 ）定数倍器２４Ｆ
・ＧＦ（ｑn-1 ）定数倍器２４Ｇ
・ＧＦ（ｑn-1 ）加算器２４Ｈ
・ＧＦ（ｑn-1 ）加算器２４Ｉ
からなる。
【０１５７】
ＧＦ（ｑn-1 ）定数倍器２４Ｅは図３０（ｉ＝ｎ−１の場合）または図３１（ｉ＝ｎ−１の場合）または図３２（ｉ＝ｎ−１の場合）または図３３（ｉ＝ｎ−１の場合）または図３４（ｉ＝ｎ−１の場合）または図３５（ｉ＝ｎ−１の場合）に示すように構成され、ＧＦ（ｑn-1 ）上のｔn 倍を加減算程度の速度か、それよりも高速に計算できる。
【０１５８】
ＧＦ（ｑn-1 ）定数倍器２４Ｆは図３０（ｉ＝ｎ−１の場合）または図３１（ｉ＝ｎ−１の場合）または図３２（ｉ＝ｎ−１の場合）または図３３（ｉ＝ｎ−１の場合）または図３４（ｉ＝ｎ−１の場合）または図３５（ｉ＝ｎ−１の場合）に示すように構成され、ＧＦ（ｑn-1 ）上の２倍を加減算程度の速度か、それよりも高速に計算できる。
【０１５９】
ＧＦ（ｑn-1 ）定数倍器２４Ｇは図３０（ｉ＝ｎ−１の場合）または図３１（ｉ＝ｎ−１の場合）または図３２（ｉ＝ｎ−１の場合）または図３３（ｉ＝ｎ−１の場合）または図３４（ｉ＝ｎ−１の場合）または図３５（ｉ＝ｎ−１の場合）に示すように構成され、ＧＦ（ｑn-1 ）上のｓn 倍を加減算程度の速度か、それよりも高速に計算できる。
【０１６０】
この装置の動作をプログラムで実現する場合は、図５９に示すフロー図に従って実行する。
この装置では、以下のように演算が実行されるが、同時実行可能なステップは、並列に実行しても良い。また実行順序が交換可能なステップは実行順序を交換して良い。また同じ機能を持つ複数の装置による複数の演算は、装置を一元化して、順次演算を実行しても良い。
【０１６１】
Ｓｔｅｐ１：ＧＦ（ｑn-1 ）自乗器２４Ｂは入力のＡ0 に対してＬ0 ←Ａ02を計算してＬ0 を出力する。
Ｓｔｅｐ２：ＧＦ（ｑn-1 ）乗算器２４Ｃは入力のＡ0 およびＡ1 に対してＬ1 ←Ａ0 ×Ａ1 を計算してＬ1 を出力する。
Ｓｔｅｐ３：ＧＦ（ｑn-1 ）自乗器２４Ｄは入力のＡ1 に対してＬ2 ←Ａ12を計算してＬ2 を出力する。
【０１６２】
Ｓｔｅｐ４：ＧＦ（ｑn-1 ）定数倍器２４Ｅは入力のＬ2 に対してＬ3 ←ｔn Ｌ2 を計算してＬ3 を出力する。
Ｓｔｅｐ５：ＧＦ（ｑn-1 ）定数倍器２４Ｆは入力のＬ1 に対してＬ4 ←２Ｌ1 を計算してＬ4 を出力する。
Ｓｔｅｐ６：ＧＦ（ｑn-1 ）定数倍器２４Ｇは入力のＬ2 に対してＬ5 ←ｓn Ｌ2 を計算してＬ5 を出力する。
【０１６３】
Ｓｔｅｐ７：ＧＦ（ｑn-1 ）加算器２４Ｈは入力のＬ0 およびＬ3 に対してＣ0 ←Ｌ0 ＋Ｌ3 を計算してＣ0 を出力する。
Ｓｔｅｐ８：ＧＦ（ｑn-1 ）加算器２４Ｉは入力のＬ4 およびＬ5 に対してＣ1 ←Ｌ4 ＋Ｌ5 を計算してＣ1 を出力する。
Ｓｔｅｐ９：（Ｃ0 ，Ｃ1 ）をＡ2 として出力する。
【０１６４】
一般的にはａ＝（ａ0 ，ａ1 ，…，ａsi-1）が入力され、
【０１６５】
【数１３】
0003639153.tif 000011
の演算を行ない、ｆ（α）により剰余をとることによりｃを求め、乗算装置で自乗を行なう場合にくらべて少ない回数のＧＦ（ｑi-1 ）上の乗算で自乗を演算することができる。
ＧＦ（ｑn ）自乗器２５Ａ
図２５に「ＧＦ（ｑn ）自乗器」（多項式規定）の例を示す。
【０１６６】
この装置はＧＦ（ｑn-1 ）上のｍ次既約多項式ｆ（ｘ）による拡大ＧＦ（ｑn ）＝ＧＦ（ｑn-1 m ）＝ＧＦ（ｑn-1 ）〔ｘ〕／（ｆ（ｘ））上の自乗器のＧＦ（ｑn-1 ）上演算装置による一構成例である。この説明では簡単のためｍ＝２の場合を記述するが、同様の方法を一般のｍでも実現できる。
この説明および、図２５においてＡ＝（Ａ0 ，Ａ1 ）およびＡ2 ＝（Ｃ0 ，Ｃ1 ）は多項式基底によるＧＦ（ｑn ）＝ＧＦ（ｑn-1 m ）＝ＧＦ（ｑn-1 ）〔ｘ〕／（ｆ（ｘ））上の元のＧＦ（ｑn-1 ）上の元による表現であり、１およびα（但しｆ（α）＝０）を基底とするとそれぞれＡ＝Ａ0 ＋Ａ1 αおよびＡ2 ＝Ｃ0 ＋Ｃ1 αを意味している。
【０１６７】
装置２５ＡはＧＦ（ｑn ）＝ＧＦ（ｑn-1 ）〔ｘ〕／（ｘ2 −ｓn ｘ−ｔn ）（ｆ（ｘ）＝ｘ2 −ｓn ｘ−ｔn ）上の元Ａ＝（Ａ0 ，Ａ1 ）の入力に対してＧＦ（ｑn ）上の元Ａ2 を出力する装置の構成の一例を表している。つまりＡ＝Ａ0 ＋Ａ1 αとしてＡ2 ＝Ｃ0 ＋Ｃ1 αなる自乗に対し３／４法を適用し、かつα2 ＝ｓn α＋ｔn の関係を用い、つまりｆ（α）の剰余演算を用いることによりこのＧＦ（ｑn ）自乗算器はＧＦ（ｑn-1 ）定数倍器およびＧＦ（ｑn-1 ）加算器およびＧＦ（ｑn-1 ）減算器およびＧＦ（ｑn-1 ）自乗器のみで構成されＧＦ（ｑn-1 ）乗算器を必要としない。
【０１６８】
装置２５Ａは
・ＧＦ（ｑn-1 ）自乗器２５Ｂ
・ＧＦ（ｑn-1 ）加算器２５Ｃ
・ＧＦ（ｑn-1 ）自乗器２５Ｄ
・ＧＦ（ｑn-1 ）自乗器２５Ｅ
・ＧＦ（ｑn-1 ）定数倍器２５Ｆ
・ＧＦ（ｑn-1 ）減算器２５Ｇ
・ＧＦ（ｑn-1 ）定数倍器２５Ｈ
・ＧＦ（ｑn-1 ）加算器２５Ｉ
・ＧＦ（ｑn-1 ）加算器２５Ｊ
からなる。
【０１６９】
ＧＦ（ｑn-1 ）定数倍器２５Ｆは図３０（ｉ＝ｎ−１の場合）または図３１（ｉ＝ｎ−１の場合）または図３２（ｉ＝ｎ−１の場合）または図３３（ｉ＝ｎ−１の場合）または図３４（ｉ＝ｎ−１の場合）または図３５（ｉ＝ｎ−１の場合）に示すように構成され、ＧＦ（ｑn-1 ）上のｔn 倍を加減算程度の速度か、それよりも高速に計算できる。
【０１７０】
ＧＦ（ｑn-1 ）定数倍器２５Ｈは図３０（ｉ＝ｎ−１の場合）または図３１（ｉ＝ｎ−１の場合）または図３２（ｉ＝ｎ−１の場合）または図３３（ｉ＝ｎ−１の場合）または図３４（ｉ＝ｎ−１の場合）または図３５（ｉ＝ｎ−１の場合）に示すように構成され、ＧＦ（ｑn-1 ）上の（ｓn −１）倍を加減算程度の速度か、それよりも高速に計算できる。
【０１７１】
この装置の動作をプログラムで実現する場合は、図６０に示すフロー図に従って実行する。
この装置では、以下のように演算が実行されるが、同時実行可能なステップは、並列に実行しても良い。また実行順序が交換可能なステップは実行順序を交換して良い。また同じ機能を持つ複数の装置による複数の演算は、装置を一元化して、順次演算を実行しても良い。
【０１７２】
Ｓｔｅｐ１：ＧＦ（ｑn-1 ）自乗器２５Ｂは入力のＡ0 に対してＬ0 ←Ａ02を計算してＬ0 を出力する。
Ｓｔｅｐ２：ＧＦ（ｑn-1 ）加算器２５Ｃは入力のＡ0 およびＡ1 に対してＬ1 ←Ａ0 ＋Ａ1 を計算してＬ1 を出力する。
Ｓｔｅｐ３：ＧＦ（ｑn-1 ）自乗器２５Ｄは入力のＡ1 に対してＬ2 ←Ａ12を計算してＬ2 を出力する。
【０１７３】
Ｓｔｅｐ４：ＧＦ（ｑn-1 ）自乗器２５Ｅは入力のＬ1 に対してＬ3 ←Ｌ12を計算してＬ3 を出力する。
Ｓｔｅｐ５：ＧＦ（ｑn-1 ）定数倍器２５Ｆは入力のＬ2 に対してＬ4 ←ｔn Ｌ2 を計算してＬ4 を出力する。
Ｓｔｅｐ６：ＧＦ（ｑn-1 ）減算器２５Ｇは入力のＬ0 およびＬ3 に対してＬ5 ←Ｌ3 −Ｌ0 を計算してＬ5 を出力する。
【０１７４】
Ｓｔｅｐ７：ＧＦ（ｑn-1 ）定数倍器２５Ｈは入力のＬ2 に対してＬ6 ←（ｓn −１）Ｌ2 を計算してＬ6 を出力する。
Ｓｔｅｐ８：ＧＦ（ｑn-1 ）加算器２５Ｉは入力のＬ0 およびＬ4 に対してＣ0 ←Ｌ0 ＋Ｌ4 を計算してＣ0 を出力する。
Ｓｔｅｐ９：ＧＦ（ｑn-1 ）加算器２５Ｊは入力のＬ5 およびＬ6 に対してＣ1 ←Ｌ5 ＋Ｌ6 を計算してＣ1 を出力する。
【０１７５】
Ｓｔｅｐ１０：（Ｃ0 ，Ｃ1 ）をＡ2 として出力する。
一般的にはａ＝（ａ0 ，ａ1 ，…，ａsi-1）が入力される場合は、
0003639153.tif 000012
とし、ただしｓ’はｓi ／２に近い整数で、Ａi はｓ’＋１次以下の多項式とし、
0003639153.tif 000013
の演算を行い、ｆ（α）により剰余をとることによりＧＦ（ｑi-1 ）上の乗算の自乗におきかえ、かつ、３／４法を適用して演算回数を減少することができる。ＧＦ（ｑn ）自乗器２６Ａ
図２６に「ＧＦ（ｑn ）自乗器」（多項式基底）の他の例を示す。
【０１７６】
この装置はＧＦ（ｑn-1 ）上のｍ次既約多項式ｆ（ｘ）による拡大ＧＦ（ｑn ）＝ＧＦ（ｑn-1 m ）＝ＧＦ（ｑn-1 ）〔ｘ〕／（ｆ（ｘ））上の自乗器のＧＦ（ｑn-1 ）上演算装置による一構成例である。この説明ではｍ＝２の場合を記述する。
この説明および、図２６においてＡ＝（Ａ0 ，Ａ1 ）およびＡ2 ＝（Ｃ0 ，Ｃ1 ）は多項式基底によるＧＦ（ｑn ）＝ＧＦ（ｑn-1 m ）＝ＧＦ（ｑn-1 ）〔ｘ〕／（ｆ（ｘ））上の元のＧＦ（ｑn-1 ）上の元による表現であり、１およびα（但しｆ（α）＝０）を基底とするとそれぞれＡ＝Ａ0 ＋Ａ1 αおよびＡ2 ＝Ｃ0 ＋Ｃ1 αを意味している。
【０１７７】
装置２６ＡはＧＦ（ｑn ）＝ＧＦ（ｑn-1 ）〔ｘ〕／（ｘ2 −ｓn ｘ−ｔn ）（ｆ（ｘ）＝ｘ2 −ｓn ｘ−ｔn ）上の元Ａ＝（Ａ0 ，Ａ1 ）の入力に対してＧＦ（ｑn ）上の元Ａ2 を出力する装置の構成の一例を表している。この説明ではｓn ＝０，ｔn ＝−ｕ2 の場合を記述する。つまりＡ2 ＝Ａ02＋２Ａ1 Ａ0 α＋Ａ12α2 （mod ｆ（α））にα2 ＝ｓn α＋ｔn ，ｓn ＝０，ｔn ＝−ｕ2 の関係を代入するとＡ2 ＝Ａ02−ｕ2 Ａ12＋２Ａ0 Ａ1 α＝（Ａ0 −ｕＡ1 ）（Ａ0 ＋ｕＡ1 ）＋２Ａ0 Ａ1 αとなり、これを演算すればよい。
【０１７８】
装置２６Ａは
・ＧＦ（ｑn-1 ）定数倍器２６Ｂ
・ＧＦ（ｑn-1 ）加算器２６Ｃ
・ＧＦ（ｑn-1 ）減算器２６Ｄ
・ＧＦ（ｑn-1 ）乗算器２６Ｅ
・ＧＦ（ｑn-1 ）乗算器２６Ｆ
・ＧＦ（ｑn-1 ）定数倍器２６Ｇ
からなる。
【０１７９】
ＧＦ（ｑn-1 ）定数倍器２６Ｂは図３０（ｉ＝ｎ−１の場合）または図３１（ｉ＝ｎ−１の場合）または図３２（ｉ＝ｎ−１の場合）または図３３（ｉ＝ｎ−１の場合）または図３４（ｉ＝ｎ−１の場合）または図３５（ｉ＝ｎ−１の場合）に示すように構成され、ＧＦ（ｑn-1 ）上のｔn 倍を加減算程度の速度か、それよりも高速に計算できる。
【０１８０】
ＧＦ（ｑn-1 ）定数倍器２６Ｇは図３０（ｉ＝ｎ−１の場合）または図３１（ｉ＝ｎ−１の場合）または図３２（ｉ＝ｎ−１の場合）または図３３（ｉ＝ｎ−１の場合）または図３４（ｉ＝ｎ−１の場合）または図３５（ｉ＝ｎ−１の場合）に示すように構成され、ＧＦ（ｑn-1 ）上の（ｓn −１）倍を加減算程度の速度か、それよりも高速に計算できる。
【０１８１】
この装置の動作をプログラムで実現する場合は、図６１に示すフロー図に従って実行する。
この装置では、以下のように演算が実行されるが、同時実行可能なステップは、並列に実行しても良い。また実行順序が交換可能なステップは実行順序を交換して良い。また同じ機能を持つ複数の装置による複数の演算は、装置を一元化して、順次演算を実行しても良い。
【０１８２】
Ｓｔｅｐ１：ＧＦ（ｑn-1 ）定数倍器２６Ｂは入力のＡ1 に対してＬ0 ←ｕＡ1 を計算してＬ0 を出力する。
Ｓｔｅｐ２：ＧＦ（ｑn-1 ）加算器２６Ｃは入力のＡ0 およびＬ0 に対してＬ1 ←Ａ0 ＋Ｌ0 を計算してＬ1 を出力する。
Ｓｔｅｐ３：ＧＦ（ｑn-1 ）減算器２６Ｄは入力のＡ0 およびＬ0 に対してＬ2 ←Ａ0 −Ｌ0 を計算してＬ2 を出力する。
【０１８３】
Ｓｔｅｐ４：ＧＦ（ｑn-1 ）乗算器２６Ｅは入力のＡ0 およびＡ1 に対してＬ3 ←Ａ0 ×Ａ1 を計算してＬ3 を出力する。
Ｓｔｅｐ５：ＧＦ（ｑn-1 ）乗算器２６Ｆは入力のＬ1 およびＬ2 に対してＣ0 ←Ｌ1 ×Ｌ2 を計算してＣ0 を出力する。
Ｓｔｅｐ６：ＧＦ（ｑn-1 ）定数倍器２６Ｇは入力のＬ3 に対してＣ1 ←２Ｌ3 を計算してＣ1 を出力する。
【０１８４】
Ｓｔｅｐ７：（Ｃ0 ，Ｃ1 ）をＡ2 として出力する。
ＧＦ（ｑn ）自乗器２７Ａ
図２７に「ＧＦ（ｑn ）自乗器」（正規基底）の他の例を示す。
この装置はＧＦ（ｑn-1 ）のｍ次拡大ＧＦ（ｑn ）＝ＧＦ（ｑn-1 m ）上の自乗器のＧＦ（ｑn-1 ）上演算装置による一構成例である。
【０１８５】
この説明では特にｍ＝２の場合を記述するが、同様の方法を一般のｍでも実現できる。
この説明および、図２７においてＡ＝（Ａ0 ，Ａ1 ）およびＡ2 ＝（Ｃ0 ，Ｃ1 ）は正規基底によるＧＦ（ｑn ）＝ＧＦ（ｑn-1 m ）上の元のＧＦ（ｑn-1 ）上の元による表現であり、基底をα0 およびα1 とするとそれぞれＡ＝Ａ0 α0 ＋Ａ1 α1 およびＡ2 ＝Ｃ0 α0 ＋Ｃ1 α1 を意味している。
【０１８６】
全ての基底を解にもつＧＦ（ｑn-1 ）上ｍ次既約多項式をｆ（ｘ）＝ｘ2 −ｓn ｘ−ｔn とする。
装置２７ＡはＧＦ（ｑn ）＝ＧＦ（ｑn-1 m ）上の元Ａ＝（Ａ0 ，Ａ1 ）の入力に対してＧＦ（ｑn ）上の元Ａ2 を出力する装置の構成の一例を表している。この装置は（Ａ02ｓn ＋（Ａ0 −Ａ1 ）2 ｔn ／ｓn ）α0 ＋（Ａ12ｓn ＋（Ａ0 −Ａ1 ）2 ｔn ／ｓn ）α1 を演算し、ＧＦ（ｑn ）自乗算器はＧＦ（ｑn-1 ）定数倍器およびＧＦ（ｑn-1 ）加算器およびＧＦ（ｑn-1 ）減算器およびＧＦ（ｑn-1 ）自乗器のみで構成されＧＦ（ｑn-1 ）乗算器を必要としない。
【０１８７】
装置２７Ａは
・ＧＦ（ｑn-1 ）自乗器２７Ｂ
・ＧＦ（ｑn-1 ）減算器２７Ｃ
・ＧＦ（ｑn-1 ）自乗器２７Ｄ
・ＧＦ（ｑn-1 ）自乗器２７Ｅ
・ＧＦ（ｑn-1 ）定数倍器２７Ｆ
・ＧＦ（ｑn-1 ）定数倍器２７Ｇ
・ＧＦ（ｑn-1 ）定数倍器２７Ｈ
・ＧＦ（ｑn-1 ）加算器２７Ｉ
・ＧＦ（ｑn-1 ）加算器２７Ｊ
からなる。
【０１８８】
ＧＦ（ｑn-1 ）定数倍器２７ＦおよびＧＦ（ｑn-1 ）定数倍器２７Ｈは図３０（ｉ＝ｎ−１の場合）または図３１（ｉ＝ｎ−１の場合）または図３２（ｉ＝ｎ−１の場合）または図３３（ｉ＝ｎ−１の場合）または図３４（ｉ＝ｎ−１の場合）または図３５（ｉ＝ｎ−１の場合）に示すように構成され、ＧＦ（ｑn-1 ）上のｓn 倍を加減算程度の速度か、それよりも高速に計算できる。
【０１８９】
ＧＦ（ｑn-1 ）定数倍器２７Ｇは図３０（ｉ＝ｎ−１の場合）または図３１（ｉ＝ｎ−１の場合）または図３２（ｉ＝ｎ−１の場合）または図３３（ｉ＝ｎ−１の場合）または図３４（ｉ＝ｎ−１の場合）または図３５（ｉ＝ｎ−１の場合）に示すように構成され、ＧＦ（ｑn-1 ）上の（ｓn -1ｔn ）倍を加減算程度の速度か、それよりも高速に計算できる。
【０１９０】
この装置の動作をプログラムで実現する場合は、図６２に示すフロー図に従って実行する。
この装置では、以下のように演算が実行されるが、同時実行可能なステップは、並列に実行しても良い。また実行順序が交換可能なステップは実行順序を交換して良い。また同じ機能を持つ複数の装置による複数の演算は、装置を一元化して、順次演算を実行しても良い。
【０１９１】
Ｓｔｅｐ１：ＧＦ（ｑn-1 ）自乗器２７Ｂは入力のＡ0 に対してＬ0 ←Ａ02を計算してＬ0 を出力する。
Ｓｔｅｐ２：ＧＦ（ｑn-1 ）減算器２７Ｃは入力のＡ0 およびＡ1 に対してＬ1 ←Ａ0 −Ａ1 を計算してＬ1 を出力する。
Ｓｔｅｐ３：ＧＦ（ｑn-1 ）自乗器２７Ｄは入力のＡ1 に対してＬ2 ←Ａ12を計算してＬ2 を出力する。
【０１９２】
Ｓｔｅｐ４：ＧＦ（ｑn-1 ）自乗器２７Ｅは入力のＬ1 に対してＬ3 ←Ｌ12を計算してＬ3 を出力する。
Ｓｔｅｐ５：ＧＦ（ｑn-1 ）定数倍器２７Ｆは入力のＬ0 に対してＬ4 ←ｓn Ｌ0 を計算してＬ4 を出力する。
Ｓｔｅｐ６：ＧＦ（ｑn-1 ）定数倍器２７Ｇは入力のＬ3 に対してＬ5 ←（ｓn -1ｔn ）Ｌ3 を計算してＬ5 を出力する。
【０１９３】
Ｓｔｅｐ７：ＧＦ（ｑn-1 ）定数倍器２７Ｈは入力のＬ2 に対してＬ6 ←ｓn Ｌ2 を計算してＬ6 を出力する。
Ｓｔｅｐ８：ＧＦ（ｑn-1 ）加算器２７Ｉは入力のＬ4 およびＬ5 に対してＣ0 ←Ｌ4 ＋Ｌ5 を計算してＣ0 を出力する。
Ｓｔｅｐ９：ＧＦ（ｑn-1 ）加算器２７Ｊは入力のＬ5 およびＬ6 に対してＣ1 ←Ｌ5 ＋Ｌ6 を計算してＣ1 を出力する。
【０１９４】
Ｓｔｅｐ１０：（Ｃ0 ，Ｃ1 ）をＡ2 として出力する。
このようにＧＦ（ｑi-1 ）上の自乗３回と定数倍（ｔn ／ｓn 倍およびｓn 倍）によってＡ2 を求めることができる。
なお一般的にａ＝（ａ0 ，ａ1 ，…，ａsi-1）が入力された場合、
【０１９５】
【数１４】
0003639153.tif 000014
とし、ただしｓ’＝ｑsi/2に近い整数で、Ａi はｓ’次以下の多項式とし、
0003639153.tif 000015
を演算して、つまりＧＦ（ｑi-1 ）上の乗算を自乗で置きかえることができる。
【０１９６】
ＧＦ（ｑn ）逆元器２８Ａ
図２８に「ＧＦ（ｑn ）逆元器」（多項式基底）の例を示す。
この装置はＧＦ（ｑn-1 ）上のｍ次既約多項式ｆ（ｘ）による拡大ＧＦ（ｑn ）＝ＧＦ（ｑn-1 m ）＝ＧＦ（ｑn-1 ）〔ｘ〕／（ｆ（ｘ））上の逆元器のＧＦ（ｑn-1 ）上演算装置による一構成例である。本説明では簡単のためｍ＝２の場合を記述するが、同様の方法を一般のｍでも実現できる。
【０１９７】
この説明および、図２８においてＡ＝（Ａ0 ，Ａ1 ）およびＡ-1＝（Ｃ0 ，Ｃ1 ）は多項式基底によるＧＦ（ｑn ）＝ＧＦ（ｑn-1 m ）＝ＧＦ（ｑn-1 ）〔ｘ〕／（ｆ（ｘ））上の元のＧＦ（ｑn-1 ）上の元による表現であり、１およびα（但しｆ（α）＝０）を基底とするとそれぞれＡ＝Ａ0 ＋Ａ1 αおよびＡ-1＝Ｃ0 ＋Ｃ1 αを意味している。
【０１９８】
装置２８ＡはＧＦ（ｑn ）＝ＧＦ（ｑn-1 ）〔ｘ〕／（ｘ2 −ｓn ｘ−ｔn ）（ｆ（ｘ）＝ｘ2 −ｓn ｘ−ｔn ）上の元Ａ＝（Ａ0 ，Ａ1 ）の入力に対してＧＦ（ｑn ）上の元Ａ-1を出力する装置の構成の一例を表している。いま多項式基底でＧＦ（ｑi ）の任意の元Ｂ＝（Ｂ0 ，Ｂ1 ）＝Ｂ0 ＋Ｂ1 αとし、Ａ×Ｂ＝Ｃ＝Ａ0 Ｂ0 ＋（Ａ0 Ｂ1 ＋Ａ1 Ｂ0 ）α＋Ａ1 Ｂ1 α2 となり、ｆ（α）の剰余をとり、つまりα2 ＝ｓn α＋ｔn を代入すると、
Ａ×Ｂ＝（Ａ0 Ｂ0 ＋ｔn Ａ1 Ｂ1 ）＋（Ａ0 Ｂ1 ＋Ａ1 Ｂ0 ＋ｓn Ａ1 Ｂ1 ）α
となり、
Ｃ0 ＝Ａ0 Ｂ0 ＋ｔn Ａ1 Ｂ1 
Ｃ1 ＝Ａ0 Ｂ1 ＋Ａ1 Ｂ0 ＋ｓn Ａ1 Ｂ1 
となる。これを行列で表わすと、
即ち
0003639153.tif 000016
となり、
0003639153.tif 000017
とすると、
【０１９９】
【数１５】
0003639153.tif 000018
となり、
0003639153.tif 000019
を計算することによりＡ-1を求めることができる。
【０２００】
装置２８Ａは
・ＧＦ（ｑn-1 ）定数倍器２８Ｂ
・ＧＦ（ｑn-1 ）自乗器２８Ｃ
・ＧＦ（ｑn-1 ）加算器２８Ｄ
・ＧＦ（ｑn-1 ）乗算器２８Ｅ
・ＧＦ（ｑn-1 ）定数倍器２８Ｆ
・ＧＦ（ｑn-1 ）減算器２８Ｇ
・ＧＦ（ｑn-1 ）逆元器２８Ｈ
・ＧＦ（ｑn-1 ）乗算器２８Ｉ
・ＧＦ（ｑn-1 ）乗算器２８Ｊ
・ＧＦ（ｑn-1 ）定数倍器２８Ｋ
からなる。
【０２０１】
ＧＦ（ｑn-1 ）定数倍器２８Ｂは図３０（ｉ＝ｎ−１の場合）または図３１（ｉ＝ｎ−１の場合）または図３２（ｉ＝ｎ−１の場合）または図３３（ｉ＝ｎ−１の場合）または図３４（ｉ＝ｎ−１の場合）または図３５（ｉ＝ｎ−１の場合）に示すように構成され、ＧＦ（ｑn-1 ）上のｓn 倍を加減算程度の速度か、それよりも高速に計算できる。
【０２０２】
ＧＦ（ｑn-1 ）定数倍器２８Ｆは図３０（ｉ＝ｎ−１の場合）または図３１（ｉ＝ｎ−１の場合）または図３２（ｉ＝ｎ−１の場合）または図３３（ｉ＝ｎ−１の場合）または図３４（ｉ＝ｎ−１の場合）または図３５（ｉ＝ｎ−１の場合）に示すように構成され、ＧＦ（ｑn-1 ）上のｔn 倍を加減算程度の速度か、それよりも高速に計算できる。
【０２０３】
ＧＦ（ｑn-1 ）定数倍器２８Ｋは図３０（ｉ＝ｎ−１の場合）または図３１（ｉ＝ｎ−１の場合）または図３２（ｉ＝ｎ−１の場合）または図３３（ｉ＝ｎ−１の場合）または図３４（ｉ＝ｎ−１の場合）または図３５（ｉ＝ｎ−１の場合）に示すように構成され、ＧＦ（ｑn-1 ）上の−１倍を加減算程度の速度か、それよりも高速に計算できる。
【０２０４】
この装置の動作をプログラムで実現する場合は、図６３に示すフロー図に従って実行する。
この装置では、以下のように演算が実行されるが、同時実行可能なステップは、並列に実行しても良い。また実行順序が交換可能なステップは実行順序を交換して良い。また同じ機能を持つ複数の装置による複数の演算は、装置を一元化して、順次演算を実行しても良い。
【０２０５】
Ｓｔｅｐ１：ＧＦ（ｑn-1 ）定数倍器２８Ｂは入力のＡ1 に対してＬ0 ←ｓn Ａ1 を計算してＬ0 を出力する。
Ｓｔｅｐ２：ＧＦ（ｑn-1 ）自乗器２８Ｃは入力のＡ1 に対してＬ1 ←Ａ12を計算してＬ1 を出力する。
Ｓｔｅｐ３：ＧＦ（ｑn-1 ）加算器２８Ｄは入力のＡ0 およびＬ0 に対してＬ2 ←Ａ0 ＋Ｌ0 を計算してＬ2 を出力する。
【０２０６】
Ｓｔｅｐ４：ＧＦ（ｑn-1 ）乗算器２８Ｅは入力のＡ0 およびＬ2 に対してＬ3 ←Ａ0 Ｌ2 を計算してＬ3 を出力する。
Ｓｔｅｐ５：ＧＦ（ｑn-1 ）定数倍器２８Ｆは入力のＬ1 に対してＬ4 ←ｔn Ｌ1 を計算してＬ4 を出力する。
Ｓｔｅｐ６：ＧＦ（ｑn-1 ）減算器２８Ｇは入力のＬ3 およびＬ4 に対してＬ5 ←Ｌ3 −Ｌ4 を計算してＬ5 を出力する。
【０２０７】
Ｓｔｅｐ７：ＧＦ（ｑn-1 ）逆元器２８Ｈは入力のＬ5 に対してＬ6 ←Ｌ5 -1を計算してＬ6 を出力する。
Ｓｔｅｐ８：ＧＦ（ｑn-1 ）乗算器２８Ｉは入力のＬ2 およびＬ6 に対してＣ0 ←Ｌ2 ×Ｌ6 を計算してＣ0 を出力する。
Ｓｔｅｐ９：ＧＦ（ｑn-1 ）乗算器２８Ｊは入力のＬ6 およびＡ1 に対してＬ7 ←Ｌ6 ×Ａ1 を計算してＬ7 を出力する。
【０２０８】
Ｓｔｅｐ１０：ＧＦ（ｑn-1 ）定数倍器２８Ｊは入力のＬ7 に対してＣ1 ←−Ｌ7 を計算してＣ1 を出力する。
Ｓｔｅｐ１１：（Ｃ0 ，Ｃ1 ）をＡ-1として出力する。
一般的にＡ＝（Ａ1 ，Ａ2 ，…，Ａsi-1）が入力された場合は、任意のＧＦ（ｑi ）の元Ｂ＝（Ｂ0 ，Ｂ1 ，…，Ｂsi-1）に対しＣ＝ＡＢ＝（Ｃ0 ，Ｃ1 ，…，Ｃsi-1）として
0003639153.tif 000020
意のｂに対してなりたつような行列ＧをＡおよび最小多項式ｆ（ｘ）を用いて構成し、
0003639153.tif 000021
を演算してＡ-1を求める。
ＧＦ（ｑn ）逆元器２９Ａ
図２９に「ＧＦ（ｑn ）逆元器」（正規基底）を示す。
【０２０９】
この装置はＧＦ（ｑn-1 ）のｍ次拡大ＧＦ（ｑn ）＝ＧＦ（ｑn-1 m ）上の逆元器のＧＦ（ｑn-1 ）上演算装置による一構成例である。
この説明では特にｍ＝２の場合を記述するが、同様の方法を一般のｍでも実現できる。
この説明および、図２９においてＡ＝（Ａ0 ，Ａ1 ）およびＡ-1＝（Ｃ0 ，Ｃ1 ）は正規基底によるＧＦ（ｑn ）＝ＧＦ（ｑn-1 m ）上の元のＧＦ（ｑn-1 ）上の元による表現であり、基底をα0 およびα1 とするとそれぞれＡ＝Ａ0 α0 ＋Ａ1 α1 およびＡ-1＝Ｃ0 α0 ＋Ｃ1 α1 を意味している。
【０２１０】
全ての基底を解にもつＧＦ（ｑn-1 ）上ｍ次既約多項式をｆ（ｘ）＝ｘ2 −ｓn ｘ−ｔn とする。
装置２９ＡはＧＦ（ｑn ）＝ＧＦ（ｑn-1 m ）上の元Ａ＝（Ａ0 ，Ａ1 ）の入力に対してＧＦ（ｑn ）上の元Ａ-1を出力する装置の構成の一例を表している。またＡの共役元Ａ′＝Ａ1 α0 ＋Ａ0 α1 とＡの積、つまりノルムＮ＝Ａ×Ａ′を求めるとＮ＝Ａ0 Ａ1 α02＋（Ａ12＋Ａ02）α0 α1 ＋Ａ0 Ａ1 α12α0 、α1 はｆ（ｘ）＝ｘ2 −ｓn ｘ−ｔn の根であるから、α02＝ｓn α0 ＋ｔn 、α12＝ｓn α1 ＋ｔn の関係をＮの式に代入すると、
Ｎ＝Ａ0 Ａ1 （ｓn α0 ＋ｓn α1 ＋２ｔn ）＋（Ａ12＋Ａ02）α1 α2 
ｆ（ｘ）＝（ｘ−α1 ）（ｘ−α0 ）の関係からｔn ＝α1 α0 であり、これをＮの式に代入すると
Ｎ＝Ａ0 Ａ1 ｓn 2 −（Ａ0 −Ａ1 ）2 ｔn 
となる。Ａ×Ａ′＝ＮであるからＡ-1＝Ａ′／Ｎであり、Ｎ＝（（Ａ0 Ａ1 ｓn 2 ＋（Ａ0 −Ａ1 ）2 ｔn ）-1を求め、Ａ-1＝（Ａ1 Ｎ，Ａ0 Ｎ）を求めればよい。
【０２１１】
装置２９Ａは
・ＧＦ（ｑn-1 ）乗算器２９Ｂ
・ＧＦ（ｑn-1 ）減算器２９Ｃ
・ＧＦ（ｑn-1 ）定数倍器２９Ｄ
・ＧＦ（ｑn-1 ）自乗器２９Ｅ
・ＧＦ（ｑn-1 ）定数倍器２９Ｆ
・ＧＦ（ｑn-1 ）減算器２９Ｇ
・ＧＦ（ｑn-1 ）逆元器２９Ｈ
・ＧＦ（ｑn-1 ）乗算器２９Ｉ
・ＧＦ（ｑn-1 ）乗算器２９Ｊ
からなる。
【０２１２】
ＧＦ（ｑn-1 ）定数倍器２９Ｄは図３０（ｉ＝ｎ−１の場合）または図３１（ｉ＝ｎ−１の場合）または図３２（ｉ＝ｎ−１の場合）または図３３（ｉ＝ｎ−１の場合）または図３４（ｉ＝ｎ−１の場合）または図３５（ｉ＝ｎ−１の場合）に示すように構成され、ＧＦ（ｑn-1 ）上のｓn 2 倍を加減算程度の速度か、それよりも高速に計算できる。
【０２１３】
ＧＦ（ｑn-1 ）定数倍器２９Ｆは図３０（ｉ＝ｎ−１の場合）または図３１（ｉ＝ｎ−１の場合）または図３２（ｉ＝ｎ−１の場合）または図３３（ｉ＝ｎ−１の場合）または図３４（ｉ＝ｎ−１の場合）または図３５（ｉ＝ｎ−１の場合）に示すように構成され、ＧＦ（ｑn-1 ）上のｔn 倍を加減算程度の速度か、それよりも高速に計算できる。
【０２１４】
この装置の動作をプログラムで実現する場合は、図６４を示すフロー図に従って実行する。
この装置では、以下のように演算が実行されるが、同時実行可能なステップは、並列に実行しても良い。また実行順序が交換可能なステップは実行順序を交換して良い。また同じ機能を持つ複数の装置による複数の演算は、装置を一元化して、順次演算を実行しても良い。
【０２１５】
Ｓｔｅｐ１：ＧＦ（ｑn-1 ）乗算器２９Ｂは入力のＡ0 およびＡ1 に対してＬ0 ←Ａ0 ×Ａ1 を計算してＬ0 を出力する。
Ｓｔｅｐ２：ＧＦ（ｑn-1 ）減算器２９Ｃは入力のＡ0 およびＡ1 に対してＬ1 ←Ａ0 −Ａ1 を計算してＬ1 を出力する。
Ｓｔｅｐ３：ＧＦ（ｑn-1 ）定数倍器２９Ｄは入力のＬ0 に対してＬ2 ←ｓn 2 Ｌ0 を計算してＬ2 を出力する。
【０２１６】
Ｓｔｅｐ４：ＧＦ（ｑn-1 ）自乗器２９Ｅは入力のＬ1 に対してＬ3 ←Ｌ12を計算してＬ3 を出力する。
Ｓｔｅｐ５：ＧＦ（ｑn-1 ）定数倍器２９Ｆは入力のＬ3 に対してＬ4 ←ｔn Ｌ3 を計算してＬ4 を出力する。
Ｓｔｅｐ６：ＧＦ（ｑn-1 ）減算器２９Ｇは入力のＬ2 およびＬ4 に対してＬ5 ←Ｌ2 −Ｌ4 を計算してＬ5 を出力する。
【０２１７】
Ｓｔｅｐ７：ＧＦ（ｑn-1 ）逆元器２９Ｈは入力のＬ5 に対してＬ6 ←Ｌ5 -1を計算してＬ6 を出力する。
Ｓｔｅｐ８：ＧＦ（ｑn-1 ）乗算器２９Ｉは入力のＡ0 およびＬ6 に対してＣ1 ←Ａ0 ×Ｌ6 を計算してＣ1 を出力する。
Ｓｔｅｐ９：ＧＦ（ｑn-1 ）乗算器２９Ｊは入力のＬ6 およびＡ1 に対してＣ0 ←Ｌ6 ×Ａ1 を計算してＣ0 を出力する。
【０２１８】
Ｓｔｅｐ１０：（Ｃ0 ，Ｃ1 ）をＡ-1として出力する。
一般にａ＝（ａ0 ，ａ1 ，…，ａsi-1）が入力された場合はａのノルムＮ（ａ）を求めその逆数Ｎ（ａ）-1にａの共役元
【０２１９】
【数１６】
0003639153.tif 000022
を乗算すればａの逆元ａ-1が求まる。
ＧＦ（ｑi ）定数倍器３０Ａ
図３０に「ＧＦ（ｑi ）定数倍器」を示す。
この装置はＧＦ（ｑi-1 ）のｍ次拡大ＧＦ（ｑi ）＝ＧＦ（ｑi-1 m ）上の定数倍器のＧＦ（ｑi-1 ）上演算装置による一構成例である。
【０２２０】
ＢをＧＦ（ｑi ）上の定数とする。
この説明では簡単のためｍ＝２の場合を記述するが、同様の方法を一般のｍでも実現できる。
この説明および、図３０におけるＡ＝（Ａ0 ，Ａ1 ）およびＢ×Ａ＝（Ｃ0 ，Ｃ1 ）等の記述はＧＦ（ｑi ）＝ＧＦ（ｑi-1 m ）上の元ＡおよびＢ×Ａ等のＧＦ（ｑi-1 ）上の元Ａ0 ，Ａ1 ，Ｃ0 ，Ｃ1 等による表現である。
【０２２１】
装置３０ＡはＧＦ（ｑi ）上の元Ａ＝（Ａ0 ，Ａ1 ）の入力に対してＧＦ（ｑi ）上の元Ｂ×Ａ（但しＢ∈ＧＦ（ｑi-1 ））を出力する装置の構成の一例を表している。
装置３０Ａは
・ＧＦ（ｑi-1 ）定数倍器３０Ｂ
・ＧＦ（ｑi-1 ）定数倍器３０Ｃ
からなる。
【０２２２】
ＧＦ（ｑi-1 ）上のＢ倍はＧＦ（ｑi-1 ）定数倍器３０ＢおよびＧＦ（ｑi-1 ）定数倍器３０Ｃによって高速に実行可能であるとする。
この装置の動作をプログラムで実現する場合は、図６５に示すフロー図に従って実行する。
この装置では、以下のように演算が実行されるが、同時実行可能なステップは、並列に実行しても良い。また実行順序が交換可能なステップは実行順序を交換して良い。また同じ機能を持つ複数の装置による複数の演算は、装置を一元化して、順次演算を実行しても良い。
【０２２３】
Ｓｔｅｐ１：ＧＦ（ｑi-1 ）定数倍器３０Ｂは、入力のＡ0 に対してＣ0 ←Ｂ×Ａ0 を計算してＣ0 を出力する。
Ｓｔｅｐ２：ＧＦ（ｑi-1 ）定数倍器３０Ｃは、入力のＡ1 に対してＣ1 ←Ｂ×Ａ1 を計算してＣ1 を出力する。
Ｓｔｅｐ３：（Ｃ0 ，Ｃ1 ）をＢ×Ａとして出力する。
ＧＦ（ｑi ）定数倍器３１Ａ
図３１に「ＧＦ（ｑi ）定数倍器」（多項式基底）を示す。
【０２２４】
この装置はＧＦ（ｑi-1 ）上のｍ次既約多項式ｆ（ｘ）による拡大ＧＦ（ｑi ）＝ＧＦ（ｑi-1 m ）＝ＧＦ（ｑi-1 ）〔ｘ〕／（ｆ（ｘ））上の定数倍器のＧＦ（ｑi-1 ）上演算装置による一構成例である。
ＢをＧＦ（ｑi ）上の定数とする。
この説明では簡単のためｍ＝２の場合を記述するが、同様の方法を一般のｍでも実現できる。
【０２２５】
この説明および、図３１においてＡ＝（Ａ0 ，Ａ1 ）およびＢ×Ａ＝（Ｃ0 ，Ｃ1 ）は多項式基底によるＧＦ（ｑi ）＝ＧＦ（ｑi-1 m ）＝ＧＦ（ｑi-1 ）〔ｘ〕／（ｆ（ｘ））上の元のＧＦ（ｑi-1 ）上の元による表現であり、１およびα（但しｆ（α）＝０）を基底とするとそれぞれＡ＝Ａ0 ＋Ａ1 αおよびＢ×Ａ＝Ｃ0 ＋Ｃ1 αを意味している。
【０２２６】
装置３１ＡはＧＦ（ｑi ）＝ＧＦ（ｑi-1 ）〔ｘ〕／（ｘ2 −ｓi ｘ−ｔi ）上の元Ａ＝（Ａ0 ，Ａ1 ）の入力に対してＧＦ（ｑi ）上の元Ｂ×Ａ（但しＢ＝α）を出力する装置の構成の一例を表している。
装置３１Ａは
・ＧＦ（ｑi-1 ）定数倍器３１Ｂ
・ＧＦ（ｑi-1 ）定数倍器３１Ｃ
・ＧＦ（ｑi-1 ）加算器３１Ｄ
からなる。
【０２２７】
この装置の動作をプログラムで実現する場合は、図６６に示すフロー図に従って実行する。
この装置では、以下のように演算が実行されるが、同時実行可能なステップは、並列に実行しても良い。また実行順序が交換可能なステップは実行順序を交換して良い。また同じ機能を持つ複数の装置による複数の演算は、装置を一元化して、順次演算を実行しても良い。
【０２２８】
Ｓｔｅｐ１：ＧＦ（ｑi-1 ）定数倍器３１Ｂは入力のＡ1 に対してＬ0 ←ｓi Ａ1 を計算してＬ0 を出力する。
Ｓｔｅｐ２：ＧＦ（ｑi-1 ）定数倍器３１Ｃは入力のＡ1 に対してＣ0 ←ｔi Ａ1 を計算してＣ0 を出力する。
Ｓｔｅｐ３：ＧＦ（ｑi-1 ）加算器３１Ｄは入力のＡ0 およびＬ0 に対してＣ1 ←Ａ0 ＋Ｌ0 を計算してＣ1 を出力する。
【０２２９】
Ｓｔｅｐ４：（Ｃ0 ，Ｃ1 ）をＢ×Ａとして出力する。
ＧＦ（ｑi ）定数倍器３２Ａ
図３２に「ＧＦ（ｑi ）定数倍器」（多項式基底）の他の例を示す。
この装置はＧＦ（ｑi-1 ）上のｍ次既約多項式ｆ（ｘ）による拡大ＧＦ（ｑi ）＝ＧＦ（ｑi-1 m ）＝ＧＦ（ｑi-1 ）〔ｘ〕／（ｆ（ｘ））上の定数倍器のＧＦ（ｑi-1 ）上演算装置による一構成例である。
【０２３０】
ＢをＧＦ（ｑi ）上の定数とする。
この説明では簡単のためｍ＝２の場合を記述するが、同様の方法を一般のｍでも実現できる。
この説明および、図３２においてＡ＝（Ａ0 ，Ａ1 ）およびＢ×Ａ＝（Ｃ0 ，Ｃ1 ）は多項式基底によるＧＦ（ｑi ）＝ＧＦ（ｑi-1 m ）＝ＧＦ（ｑi-1 ）〔ｘ〕／（ｆ（ｘ））上の元のＧＦ（ｑi-1 ）上の元による表現であり、１およびα（但しｆ（α）＝０）を基底とするとそれぞれＡ＝Ａ0 ＋Ａ1 αおよびＢ×Ａ＝Ｃ0 ＋Ｃ1 αを意味している。
【０２３１】
装置３２ＡはＧＦ（ｑi ）＝ＧＦ（ｑi-1 ）〔ｘ〕／（ｘ2 −ｓi ｘ−ｔi ）上の元Ａ＝（Ａ0 ，Ａ1 ）の入力に対してＧＦ（ｑi ）上の元Ｂ×Ａ（但しＢ＝α* ；α* はαの共役元）を出力する装置の構成の一例を表している。
装置３２Ａは
・ＧＦ（ｑi-1 ）定数倍器３２Ｂ
・ＧＦ（ｑi-1 ）定数倍器３２Ｃ
・ＧＦ（ｑi-1 ）定数倍器３２Ｄ
・ＧＦ（ｑi-1 ）減算器３２Ｅ
からなる。
【０２３２】
この装置の動作をプログラムで実現する場合は、図６７に示すフロー図に従って実行する。
この装置では、以下のように演算が実行されるが、同時実行可能なステップは、並列に実行しても良い。また実行順序が交換可能なステップは実行順序を交換して良い。また同じ機能を持つ複数の装置による複数の演算は、装置を一元化して、順次演算を実行しても良い。
【０２３３】
Ｓｔｅｐ１：ＧＦ（ｑi-1 ）定数倍器３２Ｂは入力のＡ0 に対してＣ1 ←−Ａ0 を計算してＣ1 を出力する。
Ｓｔｅｐ２：ＧＦ（ｑi-1 ）定数倍器３２Ｃは入力のＡ0 に対してＬ0 ←ｓi Ａ0 を計算してＬ0 を出力する。
Ｓｔｅｐ３：ＧＦ（ｑi-1 ）定数倍器３２Ｄは入力のＡ1 に対してＬ1 ←ｔi Ａ1 を計算してＬ1 を出力する。
【０２３４】
Ｓｔｅｐ４：ＧＦ（ｑi-1 ）減算器３２Ｄは入力のＬ0 およびＬ1 に対してＣ0 ←Ｌ0 −Ｌ1 を計算してＣ0 を出力する。
Ｓｔｅｐ５：（Ｃ0 ，Ｃ1 ）をＢ×Ａとして出力する。
ＧＦ（ｑi ）定数倍器３３Ａ
図３３に「ＧＦ（ｑi ）定数倍器」（正規基底）を示す。
【０２３５】
この装置はＧＦ（ｑi-1 ）のｍ次拡大ＧＦ（ｑi ）＝ＧＦ（ｑi-1 m ）上の定数倍器のＧＦ（ｑi-1 ）上演算装置による一構成例である。
ＢをＧＦ（ｑi ）上の定数とする。
この説明では特にｍ＝２の場合を記述するが、同様の方法を一般のｍでも実現できる。
【０２３６】
この説明および、図３３においてＡ＝（Ａ0 ，Ａ1 ）およびＢ×Ａ＝（Ｃ0 ，Ｃ1 ）は正規基底によるＧＦ（ｑi ）＝ＧＦ（ｑi-1 m ）上の元のＧＦ（ｑi-1 ）上の元による表現であり、基底をα0 およびα1 とするとそれぞれＡ＝Ａ0 α0 ＋Ａ1 α1 およびＢ×Ａ＝Ｃ0 α0 ＋Ｃ1 α1 を意味している。
全ての基底を解にもつＧＦ（ｑi-1 ）上ｍ次既約多項式をｆ（ｘ）＝ｘ2 −ｓi ｘ−ｔi とする。
【０２３７】
装置３３ＡはＧＦ（ｑi ）＝ＧＦ（ｑi-1 m ）上の元Ａ＝（Ａ0 ，Ａ1 ）の入力に対してＧＦ（ｑi ）上の元Ｂ×Ａ（但しＢ＝α0 ）を出力する装置の構成の一例を表している。
装置３３Ａは
・ＧＦ（ｑi-1 ）定数倍器３３Ｂ
・ＧＦ（ｑi-1 ）減算器３３Ｃ
・ＧＦ（ｑi-1 ）定数倍器３３Ｄ
・ＧＦ（ｑi-1 ）加算器３３Ｅ
からなる。
【０２３８】
この装置の動作をプログラムで実現する場合は、図６８に示すフロー図に従って実行する。
この装置では、以下のように演算が実行されるが、同時実行可能なステップは、並列に実行しても良い。また実行順序が交換可能なステップは実行順序を交換して良い。また同じ機能を持つ複数の装置による複数の演算は、装置を一元化して、順次演算を実行しても良い。
【０２３９】
Ｓｔｅｐ１：ＧＦ（ｑi-1 ）定数倍器３３Ｂは入力のＡ0 に対してＬ0 ←ｓi Ａ0 を計算してＬ0 を出力する。
Ｓｔｅｐ２：ＧＦ（ｑi-1 ）減算器３３Ｃは入力のＡ0 およびＡ1 に対してＬ1 ←Ａ0 −Ａ1 を計算してＬ1 を出力する。
Ｓｔｅｐ３：ＧＦ（ｑi-1 ）定数倍器３３Ｄは入力のＬ1 に対してＣ1 ←（ｓi -1ｔi ）Ｌ1 を計算してＣ1 を出力する。
【０２４０】
Ｓｔｅｐ４：ＧＦ（ｑi-1 ）加算器３３Ｅは入力のＬ0 およびＣ1 に対してＣ0 ←Ｌ0 ＋Ｃ1 を計算してＣ0 を出力する。
Ｓｔｅｐ５：（Ｃ0 ，Ｃ1 ）をＢ×Ａとして出力する。
ＧＦ（ｑi ）定数倍器３４Ａ
図３４に「ＧＦ（ｑi ）定数倍器」の他の例を示す。
【０２４１】
この装置はＧＦ（ｑi-1 ）のｍ次拡大ＧＦ（ｑi ）＝ＧＦ（ｑi-1 m ）上の定数倍器の一構成例である。
ＢをＧＦ（ｑi ）上の定数とする。
装置３４ＡはＧＦ（ｑi ）上の元Ａの入力に対してＧＦ（ｑi ）上の元Ｂ×Ａ（但しＢ＝Ｂ0 ×Ｂ1 ）を出力する装置の構成の一例を表している。
【０２４２】
装置３４Ａは
・ＧＦ（ｑi-1 ）定数倍器３４Ｂ
・ＧＦ（ｑi-1 ）定数倍器３４Ｃ
からなる。
ＧＦ（ｑi ）定数倍器３４ＢおよびＧＦ（ｑi ）定数倍器３４Ｃは図３０または図３１または図３２または図３３または図３４または図３５に示すように構成されており、ＧＦ（ｑi ）上のＢ0 倍およびＢ1 倍は高速に計算できるとする。（但し、ＧＦ（ｑi ）定数倍器３４ＢおよびＧＦ（ｑi ）定数倍器３４Ｃの基底は全て同じか、あるいは入出力の際に適切な基底に変換されるとする。）
この装置の動作をプログラムで実現する場合は、図６９に示すフロー図に従って実行する。
【０２４３】
この装置では、以下のように演算が実行されるが、同時実行可能なステップは、並列に実行しても良い。また実行順序が交換可能なステップは実行順序を交換して良い。また同じ機能を持つ複数の装置による複数の演算は、装置を一元化して、順次演算を実行しても良い。
Ｓｔｅｐ１：ＧＦ（ｑi ）定数倍器３４Ｂは、入力のＡに対してＬ0 ←Ｂ0 ×Ａを計算してＬ0 を出力する。
【０２４４】
Ｓｔｅｐ２：ＧＦ（ｑi ）定数倍器３４Ｃは、入力のＬ0 に対してＣ←Ｂ1 ×Ｌ0 を計算してＣを出力する。
Ｓｔｅｐ３：ＣをＢ×Ａとして出力する。
ＧＦ（ｑi ）定数倍器３５Ａ
図３５に「ＧＦ（ｑi ）定数倍器」の更に他の例を示す。
【０２４５】
この装置はＧＦ（ｑi-1 ）のｍ次拡大ＧＦ（ｑi ）＝ＧＦ（ｑi-1 m ）上の定数倍器の一構成例である。
ＢをＧＦ（ｑi ）上の定数とする。
装置３５ＡはＧＦ（ｑi ）上の元Ａの入力に対してＧＦ（ｑi ）上の元Ｂ×Ａ（但しＢ＝Ｂ0 ＋Ｂ1 ）を出力する装置の構成の一例を表している。
【０２４６】
装置３５Ａは
・ＧＦ（ｑi-1 ）定数倍器３５Ｂ
・ＧＦ（ｑi-1 ）定数倍器３５Ｃ
・ＧＦ（ｑi-1 ）加算器３５Ｄ
からなる。
【０２４７】
ＧＦ（ｑi-1 ）加算器３５Ｄは図２０に示すように構成されており、ＧＦ（ｑi ）定数倍器３５ＢおよびＧＦ（ｑi ）定数倍器３５Ｃは図３０または図３１または図３２または図３３または図３４または図３５に示すように構成されており、ＧＦ（ｑi ）上のＢ0 倍およびＢ1 倍は高速に計算出来るとする。（但し、ＧＦ（ｑi ）定数倍器３５ＢおよびＧＦ（ｑi ）定数倍器３５Ｃ、ＧＦ（ｑi ）加算器３５Ｄの各基底は全て同じか、あるいは入出力の際に適切な基底に変換されるとする。）
この装置の動作をプログラムで実現する場合は、図７０に示すフロー図に従って実行する。
【０２４８】
この装置では、以下のように演算が実行されるが、同時実行可能なステップは、並列に実行しても良い。また実行順序が交換可能なステップは実行順序を交換して良い。また同じ機能を持つ複数の装置による複数の演算は、装置を一元化して、順次演算を実行しても良い。
Ｓｔｅｐ１：ＧＦ（ｑi ）定数倍器３５Ｂは、入力のＡに対してＬ0 ←Ｂ0 ×Ａを計算してＬ0 を出力する。
【０２４９】
Ｓｔｅｐ２：ＧＦ（ｑi ）定数倍器３５Ｃは、入力のＡに対してＬ1 ←Ｂ1 ×Ａを計算してＬ1 を出力する。
Ｓｔｅｐ３：ＧＦ（ｑi ）加算器３５ＤがＣ←Ｌ0 ＋Ｌ1 を計算してＣを出力する。
Ｓｔｅｐ４：ＣをＢ×Ａとして出力する。
ＧＦ（ｑn ）乗算器７１Ａ
図７１に「ＧＦ（ｑn ）乗算器」（多項式基底）の他の例を示す。
【０２５０】
この装置はＧＦ（ｑn-1 ）上のｍ次既約多項式ｆ（ｘ）による拡大ＧＦ（ｑn ）＝ＧＦ（ｑn-1 m ）＝ＧＦ（ｑn-1 ）〔ｘ〕／（ｆ（ｘ））上の乗算器のＧＦ（ｑn-1 ）上演算装置による一構成例である。この説明では簡単のためｍ＝２の場合を記述するが、同様の方法を一般のｍでも実現できる。
この説明および、図７１においてＡ＝（Ａ0 ，Ａ1 ）およびＢ＝（Ｂ0 ，Ｂ1 ）およびＡ×Ｂ＝（Ｃ0 ，Ｃ1 ）は多項式基底によるＧＦ（ｑn ）＝ＧＦ（ｑn-1 m ）＝ＧＦ（ｑn-1 ）〔ｘ〕／（ｆ（ｘ））上の元のＧＦ（ｑn-1 ）上の元による表現であり、１およびα（但しｆ（α）＝０）を基底とするとそれぞれＡ＝Ａ0 ＋Ａ1 αおよびＢ＝Ｂ0 ＋Ｂ1 αおよびＡ×Ｂ＝Ｃ0 ＋Ｃ1 αを意味している。
【０２５１】
装置７１ＡはＧＦ（ｑn ）＝ＧＦ（ｑn-1 ）〔ｘ〕／（ｘ2 −ｓn ｘ−ｔn ）上の元Ａ＝（Ａ0 ，Ａ1 ）およびＢ＝（Ｂ0 ，Ｂ1 ）の入力に対してＧＦ（ｑn ）上の元Ａ×Ｂを出力する装置の構成の一例を表している。
装置７１Ａは特にｓn ＝１の場合を記述している。
装置７１Ａは
・ＧＦ（ｑn-1 ）乗算器７１Ｂ
・ＧＦ（ｑn-1 ）乗算器７１Ｃ
・ＧＦ（ｑn-1 ）加算器７１Ｄ
・ＧＦ（ｑn-1 ）加算器７１Ｅ
・ＧＦ（ｑn-1 ）乗算器７１Ｆ
・ＧＦ（ｑn-1 ）定数倍器７１Ｇ
・ＧＦ（ｑn-1 ）減算器７１Ｈ
・ＧＦ（ｑn-1 ）加算器７１Ｊ
からなる。
【０２５２】
ＧＦ（ｑn-1 ）定数倍器７１Ｇは図３０（ｉ＝ｎ−１の場合）または図３１（ｉ＝ｎ−１の場合）または図３２（ｉ＝ｎ−１の場合）または図３３（ｉ＝ｎ−１の場合）または図３４（ｉ＝ｎ−１の場合）または図３５（ｉ＝ｎ−１の場合）に示すように構成され、ＧＦ（ｑn-1 ）上のｔn 倍を加減算程度の速度か、それよりも高速に計算できる。
【０２５３】
この装置の動作をプログラムで実現する場合は、図７２に示すフロー図に従って実行する。
この装置では、以下のように演算が実行されるが、同時実行可能なステップは、並列に実行しても良い。また実行順序が交換可能なステップは実行順序を交換して良い。また同じ機能を持つ複数の装置による複数の演算は、装置を一元化して、順次演算を実行しても良い。
【０２５４】
Ｓｔｅｐ１：ＧＦ（ｑn-1 ）乗算器７１Ｂは入力のＡ0 およびＢ0 に対してＬ0 ←Ａ0 ×Ｂ0 を計算してＬ0 を出力する。
Ｓｔｅｐ２：ＧＦ（ｑn-1 ）加算器７１Ｄは入力のＡ0 およびＡ1 に対してＬ1 ←Ａ0 ＋Ａ1 を計算してＬ1 を出力する。
Ｓｔｅｐ３：ＧＦ（ｑn-1 ）加算器７１Ｅは入力のＢ0 およびＢ1 に対してＬ2 ←Ｂ0 ＋Ｂ1 を計算してＬ2 を出力する。
【０２５５】
Ｓｔｅｐ４：ＧＦ（ｑn-1 ）乗算器７１Ｃは入力のＡ1 およびＢ1 に対してＬ3 ←Ａ1 ×Ｂ1 を計算してＬ2 を出力する。
Ｓｔｅｐ５：ＧＦ（ｑn-1 ）乗算器７１Ｆは入力のＬ1 およびＬ2 に対してＬ1 ←Ｌ1 ×Ｌ2 を計算してＬ4 を出力する。
Ｓｔｅｐ６：ＧＦ（ｑn-1 ）定数倍器７１Ｇは入力のＬ3 に対してＬ5 ←ｔn Ｌ3 を計算してＬ5 を出力する。
【０２５６】
Ｓｔｅｐ７：ＧＦ（ｑn-1 ）減算器７１Ｈは入力のＬ0 およびＬ4 に対してＣ1 ←Ｌ4 −Ｌ0 を計算してＣ1 を出力する。
Ｓｔｅｐ８：ＧＦ（ｑn-1 ）加算器７１Ｊは入力のＬ0 およびＬ5 に対してＣ0 ←Ｌ0 ＋Ｌ5 を計算してＣ0 を出力する。
Ｓｔｅｐ９：（Ｃ0 ，Ｃ1 ）をＡ×Ｂとして出力する。
ＧＦ（ｑn ）除算器７３Ａ
図７３に「ＧＦ（ｑn ）除算器」の例を示す。
【０２５７】
この装置はＧＦ（ｑn ）上の除算器の一構成例である。
ＧＦ（ｑn ）上の元Ａ，Ｂの入力に対してＧＦ（ｑn ）上の元Ａ／Ｂを出力する装置の構成の一例を表している。
装置７３Ａは
・ＧＦ（ｑn ）逆元器７３Ｂ
・ＧＦ（ｑn ）乗算器７３Ｃ
からなる。
【０２５８】
この装置の動作をプログラムで実現する場合は、図７４に示すフロー図に従って実行する。
この装置では、以下のように演算が実行されるが、同時実行可能なステップは、並列に実行しても良い。また実行順序が交換可能なステップは実行順序を交換して良い。また同じ機能を持つ複数の装置による複数の演算は、装置を一元化して、順次演算を実行しても良い。
Ｓｔｅｐ１：ＧＦ（ｑn ）逆元器７３Ｂは、入力のＢに対してＬ0 ←Ｂ-1を計算してＬ0 を出力する。
【０２５９】
Ｓｔｅｐ２：ＧＦ（ｑn ）乗算器７３Ｃは、入力のＡおよびＬ0 に対してＣ←Ａ×Ｌ0 を計算してＣを出力する。
Ｓｔｅｐ３：ＣをＡ／Ｂとして出力する。
上述の各実施例において、各機能をコンピュータによりプログラムを解読実行させて作用させることができる。
【０２６０】
【発明の効果】
ＧＦ（ｑ0 ）上の加減算および定数倍演算が乗算に比べて無視できる場合は、ｍ次拡大体上の乗算を演算する場合、従来ｍ2 回のＧＦ（ｑ0 ）上乗算が必要であったのに対して、この発明（逐次２次拡大の場合）によりｍのlog2３乗、つまり約ｍ1.585 回に減らす事ができた。従ってｍ＝４の場合４３．７５％、ｍ＝８の場合５７．８１％、ｍ＝１６の場合６８．３６％のＧＦ（ｑ0 ）上乗算を削減する効果がある。また、ｍ次拡大体上の逆元を演算する場合、従来、ＧＦ（ｑ0 ）上多項式に対する拡張Ｅｕｃｌｉｄ互除法により約２（ｍ2 −１）回のＧＦ（ｑ0 ）上乗算が必要であったのに対してこの発明（逐次２次拡大の場合）によりｍ2 回に減らす事ができた。従って約５０％のＧＦ（ｑ0 ）上乗算を削減する効果がある。
【０２６１】
ＧＦ（ｑ0 ）上の逆元演算が高速には実行できない場合でも、必要なＧＦ（ｑ0 ）上の逆元演算の回数が１回で済むため、ＧＦ（ｑ0 ）上の逆元演算の回数が約ｍ回必要なＧＦ（ｑ0 ）上多項式に対する拡張Ｅｕｃｌｉｄ互除法と比較して約ｍ倍速である。
これらを楕円曲線上の演算に適用すれば、ｍ＝４〜１６の場合全体で約５０％のＧＦ（ｑ0 ）上乗算の削減を見込める。
【図面の簡単な説明】
【図１】楕円曲線上のｋ倍演算装置を示す図。
【図２】楕円曲線上の加算装置を示す図。
【図３】楕円曲線上の倍算装置を示す図。
【図４】楕円二等分点判定器（２値座標）を示す図。
【図５】楕円二等分点判定器（３値座標）を示す図。
【図６】楕円逆元器（２値座標）を示す図。
【図７】楕円逆元器（３値座標）を示す図。
【図８】楕円比較装置を示す図。
【図９】楕円比較器（ａｆｆｉｎｅ座標）を示す図。
【図１０】楕円比較器（ｐｒｏｊｅｃｔｉｖｅ座標）を示す図。
【図１１】楕円比較器（ｊａｃｏｂｉａｎ座標）を示す図。
【図１２】楕円加算器（ａｆｆｉｎｅ座標）を示す図。
【図１３】楕円倍算器（ａｆｆｉｎｅ座標）を示す図。
【図１４】楕円加算器（ｐｒｏｊｅｃｔｉｖｅ座標）を示す図。
【図１５】楕円倍算器（ｐｒｏｊｅｃｔｉｖｅ座標）を示す図。
【図１６】楕円加算器（ｊａｃｏｂｉａｎ座標）を示す図。
【図１７】楕円倍算器（ｊａｃｏｂｉａｎ座標）を示す図。
【図１８】この発明の要部である逐次拡大装置を示す図。
【図１９】ＧＦ（ｑi ）演算器の一般構成を示す図。
【図２０】ＧＦ（ｑn ）加算器示す図。
【図２１】ＧＦ（ｑn ）減算器示す図。
【図２２】ＧＦ（ｑn ）乗算器（多項式基底）を示す図。
【図２３】ＧＦ（ｑn ）乗算器（正規基底）を示す図。
【図２４】ＧＦ（ｑn ）自乗器（多項式基底）を示す図。
【図２５】ＧＦ（ｑn ）自乗器（多項式基底）の他の例を示す図。
【図２６】ＧＦ（ｑn ）自乗器（多項式基底）の更に他の例を示す図。
【図２７】ＧＦ（ｑn ）自乗器（正規基底）を示す図。
【図２８】ＧＦ（ｑn ）逆元器（多項式基底）を示す図。
【図２９】ＧＦ（ｑn ）逆元器（正規基底）を示す図。
【図３０】ＧＦ（ｑi ）定数倍器を示す図。
【図３１】ＧＦ（ｑi ）定数倍器（多項式基底）を示す図。
【図３２】ＧＦ（ｑi ）定数倍器（多項式基底）の他の例を示す図。
【図３３】ＧＦ（ｑi ）定数倍器（正規基底）の例を示す図。
【図３４】ＧＦ（ｑi ）定数倍器（直列）の例を示す図。
【図３５】ＧＦ（ｑi ）定数倍器（並列）の例を示す図。
【図３６】楕円曲線上のｋ倍演算処理の流れ図。
【図３７】楕円曲線上の加算処理の流れ図。
【図３８】楕円曲線上の倍算処理の流れ図。
【図３９】楕円二等分点判定処理（２値座標）の流れ図。
【図４０】楕円二等分点判定処理（３値座標）の流れ図。
【図４１】楕円逆元処理（２値座標）の流れ図。
【図４２】楕円逆元処理（３値座標）の流れ図。
【図４３】楕円比較処理の流れ図。
【図４４】楕円比較処理（ａｆｆｉｎｅ座標）の流れ図。
【図４５】楕円比較処理（ｐｒｏｊｅｃｔｉｖｅ座標）の流れ図。
【図４６】楕円比較処理（ｊａｃｏｂｉａｎ座標）の流れ図。
【図４７】楕円加算処理（ａｆｆｉｎｅ座標）の流れ図。
【図４８】楕円倍算処理（ａｆｆｉｎｅ座標）の流れ図。
【図４９】楕円加算処理（ｐｒｏｊｅｃｔｉｖｅ座標）の流れ図。
【図５０】楕円倍算処理（ｐｒｏｊｅｃｔｉｖｅ座標）の流れ図。
【図５１】楕円加算処理（ｊａｃｏｂｉａｎ座標）の流れ図。
【図５２】楕円倍算処理（ｊａｃｏｂｉａｎ座標）の流れ図。
【図５３】逐次拡大処理の流れ図。
【図５４】ＧＦ（ｑi ）演算処理の流れ図。
【図５５】ＧＦ（ｑn ）加算処理の流れ図。
【図５６】ＧＦ（ｑn ）減算処理の流れ図。
【図５７】ＧＦ（ｑn ）乗算処理（多項式基底）の流れ図。
【図５８】ＧＦ（ｑn ）乗算処理（正規基底）の流れ図。
【図５９】ＧＦ（ｑn ）自乗処理（多項式基底）の流れ図。
【図６０】ＧＦ（ｑn ）自乗処理（多項式基底）の流れ図。
【図６１】ＧＦ（ｑn ）自乗処理（多項式基底）の流れ図。
【図６２】ＧＦ（ｑn ）自乗処理（正規基底）の流れ図。
【図６３】ＧＦ（ｑn ）逆元処理（多項式基底）の流れ図。
【図６４】ＧＦ（ｑn ）逆元処理（正規基底）の流れ図。
【図６５】ＧＦ（ｑi ）定数倍処理の流れ図。
【図６６】ＧＦ（ｑi ）定数倍処理（多項式基底）の流れ図。
【図６７】ＧＦ（ｑi ）定数倍処理（多項式基底）の流れ図。
【図６８】ＧＦ（ｑi ）定数倍処理（正規基底）の流れ図。
【図６９】ＧＦ（ｑi ）定数倍処理（直列）の流れ図。
【図７０】ＧＦ（ｑi ）定数倍処理（並列）の流れ図。
【図７１】ＧＦ（ｑn ）乗算器（ｓn ＝１）の構成を示す図。
【図７２】ＧＦ（ｑn ）乗算器（ｓn ＝１）の処理の流れ図。
【図７３】ＧＦ（ｑn ）除算器の構成を示す図。
【図７４】ＧＦ（ｑn ）除算器の処理の流れを示す図。
【図１】
0003639153.tif 000023
【図２】
0003639153.tif 000024
【図３】
0003639153.tif 000025
【図４】
0003639153.tif 000026
【図５】
0003639153.tif 000027
【図６】
0003639153.tif 000028
【図７】
0003639153.tif 000029
【図８】
0003639153.tif 000030
【図９】
0003639153.tif 000031
【図１０】
0003639153.tif 000032
【図１１】
0003639153.tif 000033
【図１２】
0003639153.tif 000034
【図１３】
0003639153.tif 000035
【図１４】
0003639153.tif 000036
【図１５】
0003639153.tif 000037
【図１６】
0003639153.tif 000038
【図１７】
0003639153.tif 000039
【図１８】
0003639153.tif 000040
【図１９】
0003639153.tif 000041
【図２０】
0003639153.tif 000042
【図２１】
0003639153.tif 000043
【図２２】
0003639153.tif 000044
【図２３】
0003639153.tif 000045
【図２４】
0003639153.tif 000046
【図２５】
0003639153.tif 000047
【図２６】
0003639153.tif 000048
【図２７】
0003639153.tif 000049
【図２８】
0003639153.tif 000050
【図２９】
0003639153.tif 000051
【図３０】
0003639153.tif 000052
【図３１】
0003639153.tif 000053
【図３２】
0003639153.tif 000054
【図３３】
0003639153.tif 000055
【図３４】
0003639153.tif 000056
【図３５】
0003639153.tif 000057
【図３６】
0003639153.tif 000058
【図３７】
0003639153.tif 000059
【図３８】
0003639153.tif 000060
【図３９】
0003639153.tif 000061
【図４０】
0003639153.tif 000062
【図４１】
0003639153.tif 000063
【図４２】
0003639153.tif 000064
【図４３】
0003639153.tif 000065
【図４４】
0003639153.tif 000066
【図４５】
0003639153.tif 000067
【図４６】
0003639153.tif 000068
【図４７】
0003639153.tif 000069
【図４８】
0003639153.tif 000070
【図４９】
0003639153.tif 000071
【図５０】
0003639153.tif 000072
【図５１】
0003639153.tif 000073
【図５２】
0003639153.tif 000074
【図５３】
0003639153.tif 000075
【図５４】
0003639153.tif 000076
【図５５】
0003639153.tif 000077
【図５６】
0003639153.tif 000078
【図５７】
0003639153.tif 000079
【図５８】
0003639153.tif 000080
【図５９】
0003639153.tif 000081
【図６０】
0003639153.tif 000082
【図６１】
0003639153.tif 000083
【図６２】
0003639153.tif 000084
【図６３】
0003639153.tif 000085
【図６４】
0003639153.tif 000086
【図６５】
0003639153.tif 000087
【図６６】
0003639153.tif 000088
【図６７】
0003639153.tif 000089
【図６８】
0003639153.tif 000090
【図６９】
0003639153.tif 000091
【図７０】
0003639153.tif 000092
【図７１】
0003639153.tif 000093
【図７２】
0003639153.tif 000094
【図７３】
0003639153.tif 000095
【図７４】
0003639153.tif 000096