(57)【特許請求の範囲】
【請求項１】
ｎより小さい整数ｘに関して法ｎの剰余演算ｘ２ ｍｏｄ ｎを実行するための剰余演算装置であって、
０以外の整数ａ，ｂ（但し、ａ−ｂ≧２）を用い、前記整数ｘを（ｂ−ａ）で割った商ｙと剰余εを求める手段と、
前記商ｙをｈ個の整数ｐｉ（但し、ｉ＝１，…，ｈ、且つ、ｎ＋ａ＝ｐ１・ｐ２・…・ｐｈ）及び第１式ｙｉ＝ｙ ｍｏｄ ｐｉに基づいて、第１剰余系表現ｙｉ（但し、ｉ＝１，…，ｈ）に変換する手段と、
前記第１剰余系表現ｙｉを中国人剰余定理により法ｎ＋ａの２進数表現ｘａ＝（ｂ−ａ）ｙｉ２＋２εｙｉ ｍｏｄ （ｎ＋ａ）に変換する手段と、
前記商ｙをｍ個の整数ｑｊ（但し、ｊ＝１，…，ｍ、且つ、ｎ＋ｂ＝ｑ１・ｑ２・…・ｑｍ）及び第２式ｙｊ＝ｙ ｍｏｄ ｑｊに基づいて、第２剰余系表現ｙｊ（但し、ｊ＝１，…，ｍ）に変換する手段と、
前記第２剰余系表現ｙｊを中国人剰余定理により法ｎ＋ｂの２進数表現ｘｂ＝（ｂ−ａ）ｙｊ２＋２εｙｊ ｍｏｄ （ｎ＋ｂ）に変換する手段と、
前記２進数表現ｘａ，ｘｂ及び前記整数ａ，ｂに基づく値ｂｘａ−ａｘｂを法ｎで割り、商ｑと剰余ｒを得る手段と、
前記商ｑ及び前記２進数表現ｘａ，ｘｂに関する条件式ｘａ−ｘｂ＋ｑに基づいて、前記条件式ｘａ−ｘｂ＋ｑ≧０のとき、整数ｓｎ＝ｒを得る手段と、
前記条件式ｘａ−ｘｂ＋ｑ＜０且つｒ＋ａｂ＜ｎのとき、整数ｓｎ＝ｒ＋ａｂを得る手段と、
前記条件式ｘａ−ｘｂ＋ｑ＜０且つｒ＋ａｂ＞ｎのとき、整数ｓｎ＝ｒ＋ａｂ−ｎを得る手段と、
前記条件式により得られた整数ｓｎに対し、前記整数ｘを（ｂ−ａ）で割った剰余εの二乗ε２を加え、前記ｘ２の候補ｓｎ’を得る手段と、
この候補ｓｎ’を法ｎで調整し、前記ｘ２ ｍｏｄ ｎ の値を得る手段と、
を備えたことを特徴とする剰余演算装置。
【請求項２】
ｎより小さい整数ｘ，ｕに関して法ｎの剰余演算ｘｕ ｍｏｄ ｎを実行するための剰余演算装置であって、
０以外の整数ａ，ｂ（但し、ａ−ｂ≧２）を用い、前記整数ｘを（ｂ−ａ）で割った商ｙと剰余εを求める手段と、
前記整数ａ，ｂを用い、前記整数ｕを（ｂ−ａ）で割った商μと剰余σを求める手段と、
前記商ｙをｈ個の整数ｐｉ（但し、ｉ＝１，…，ｈ、且つ、ｎ＋ａ＝ｐ１・ｐ２・…・ｐｈ）及び第１式ｙｉ＝ｙ ｍｏｄ ｐｉに基づいて、第１剰余系表現ｙｉ（但し、ｉ＝１，…，ｈ）に変換する手段と、
前記商μを前記ｈ個の整数ｐｉ及び第２式μｉ＝μ ｍｏｄ ｐｉに基づいて、第２剰余系表現μｉ（但し、ｉ＝１，…，ｈ）に変換する手段と、
前記第１及び第２剰余系表現ｙｉ，μｉを中国人剰余定理により法ｎ＋ａの２進数表現ｘａ＝（ｂ−ａ）ｙｉμｉ＋εμｉ＋σｙｉ ｍｏｄ （ｎ＋ａ）に変換する手段と、
前記商ｙをｍ個の整数ｑｊ（但し、ｊ＝１，…，ｍ、且つ、ｎ＋ｂ＝ｑ１・ｑ２・…・ｑｍ）及び第３式ｙｊ＝ｙ ｍｏｄ ｑｊに基づいて、第３剰余系表現ｙｊ（但し、ｊ＝１，…，ｍ）に変換する手段と、
前記商μを前記ｍ個の整数ｑｊ及び第４式μｊ＝μ ｍｏｄ ｑｊに基づいて、第４剰余系表現μｊ（但し、ｊ＝１，…，ｍ）に変換する手段と、
前記第３及び第４剰余系表現ｙｊ，μｊを中国人剰余定理により法ｎ＋ｂの２進数表現ｘｂ＝（ｂ−ａ）ｙｊμｊ＋εμｊ＋σｙｊ ｍｏｄ （ｎ＋ｂ）に変換する手段と、
前記２進数表現ｘａ，ｘｂ及び前記整数ａ，ｂに基づく値ｂｘａ−ａｘｂを法ｎで割り、商ｑと剰余ｒを得る手段と、
前記商ｑ及び前記２進数表現ｘａ，ｘｂに関する条件式ｘａ−ｘｂ＋ｑに基づいて、前記条件式ｘａ−ｘｂ＋ｑ≧０のとき、整数ｓｎ＝ｒを得る手段と、
前記条件式ｘａ−ｘｂ＋ｑ＜０且つｒ＋ａｂ＜ｎのとき、整数ｓｎ＝ｒ＋ａｂを得る手段と、
前記条件式ｘａ−ｘｂ＋ｑ＜０且つｒ＋ａｂ＞ｎのとき、整数ｓｎ＝ｒ＋ａｂ−ｎを得る手段と、
前記条件式により得られた整数ｓｎに対し、前記整数ｘを（ｂ−ａ）で割った剰余εの二乗ε２を加え、前記ｘｕの候補ｓｎ’を得る手段と、
この候補ｓｎ’を法ｎで調整し、前記ｘｕ ｍｏｄ ｎ の値を得る手段と、
を備えたことを特徴とする剰余演算装置。
【請求項３】
ｎより小さい整数ｘに関して法ｎの剰余演算ｘ２ ｍｏｄ ｎを実行するための剰余演算装置であって、
０以外の整数ａ，ｂ（但し、ａ−ｂ≧２）を用い、前記整数ｘを整数ｂ−ａで割り、商ｙと剰余εを得る手段と、
前記商ｙをｈ個の整数ｐｉ（但し、ｉ＝１，…，ｈ、且つ、ｎ＋ａ＝ｐ１・ｐ２・…・ｐｈ）及び第１式ｙｉ＝ｙ ｍｏｄ ｐｉに基づいて、剰余系表現ｙｉ（但し、ｉ＝１，…，ｈ）に変換する手段と、
前記ｘ２＝（ｂ−ａ）｛（ｂ−ａ）ｙ２＋２εｙ｝＋ε２＝（ｂ−ａ）ｓ＋ε２の関係式に基づき、この整数ｓを法ｎ＋ａの第１剰余系表現ｓｉ＝（ｂ−ａ）ｙｉ２＋２εｙｉ ｍｏｄ ｐｉに変換し、得られた第１剰余系表現ｓｉを中国人剰余定理により法ｎ＋ａの２進数表現ｘａ＝ｓｉ ｍｏｄ（ｎ＋ａ）に変換する手段と、
前記商ｙをｍ個の整数ｑｊ（但し、ｊ＝１，…，ｍ、且つ、ｎ＋ｂ＝ｑ１・ｑ２・…・ｑｍ）及び第２式ｙｊ＝ｙ ｍｏｄ ｑｊに基づいて、剰余系表現ｙｊ（但し、ｊ＝１，…，ｍ）に変換する手段と、
前記整数ｓを法ｎ＋ｂの第２剰余系表現ｓｊ’＝（ｂ−ａ）ｙｊ２＋２εｙｊ ｍｏｄ ｑｊに変換し、得られた第２剰余系表現ｓｊ’を中国人剰余定理により法ｎ＋ｂの２進数表現ｘｂ＝ｓｊ’ ｍｏｄ（ｎ＋ｂ）に変換する手段と、
前記２進数表現ｘａ，ｘｂに基づいて、法ｎの整数ｓｎ＝（ｂ−ａ）ｓ ｍｏｄ ｎを得る手段と、
この整数ｓｎと前記ｘ２の関係式ｘ２＝（ｂ−ａ）ｓ＋ε２とに基づいて、前記ｘ２の候補ｓｎ’＝ｓｎ＋ε２を得ると、この候補ｓｎ’を法ｎで調整し、前記ｘ２ ｍｏｄ ｎ の値を得る手段と、
を備えたことを特徴とする剰余演算装置。
【請求項４】
ｎより小さい整数ｘ，ｕに関して法ｎの剰余演算ｘｕ ｍｏｄ ｎを実行するための剰余演算装置であって、
０以外の整数ａ，ｂ（但し、ａ−ｂ≧２）を用い、前記整数ｘを整数ｂ−ａで割り、商ｙと剰余εを得る手段と、
前記整数ａ，ｂ（但し、ａ−ｂ≧２）を用い、前記整数ｕを整数ｂ−ａで割り、商μと剰余σを得る手段と、
前記商ｙ，μをｈ個の整数ｐｉ（但し、ｉ＝１，…，ｈ、且つ、ｎ＋ａ＝ｐ１・ｐ２・…・ｐｈ）、式ｙｉ＝ｙ ｍｏｄ ｐｉ及び式μｉ＝μ ｍｏｄ ｐｉに基づいて、剰余系表現ｙｉ，μｉ（但し、ｉ＝１，…，ｈ）に変換する手段と、
前記ｘｕ＝（ｂ−ａ）｛（ｂ−ａ）ｙμ＋εμ＋σｙ｝＋εσ＝（ｂ−ａ）ｓ＋εσの関係式に基づき、この整数ｓを法ｎ＋ａの第１剰余系表現ｓｉ＝（ｂ−ａ）ｙｉμｉ＋εμｉ＋σｙｉ ｍｏｄ ｐｉに変換し、得られた第１剰余系表現ｓｉを中国人剰余定理により法ｎ＋ａの２進数表現ｘａ＝ｓｉ ｍｏｄ（ｎ＋ａ）に変換する手段と、
前記商ｙ，μをｍ個の整数ｑｊ（但し、ｊ＝１，…，ｍ、且つ、ｎ＋ｂ＝ｑ１・ｑ２・…・ｑｍ）、式ｙｊ＝ｙ ｍｏｄ ｑｊ及び式μｊ＝μ ｍｏｄ ｑｊに基づいて、剰余系表現ｙｊ，μｊ（但し、ｊ＝１，…，ｍ）に変換する手段と、
前記整数ｓを法ｎ＋ｂの第２剰余系表現ｓｊ’＝（ｂ−ａ）ｙｊμｊ＋εμｊ＋σｙｊ ｍｏｄ ｑｊに変換し、得られた第２剰余系表現ｓｊ’を中国人剰余定理により法ｎ＋ｂの２進数表現ｘｂ＝ｓｊ’ ｍｏｄ（ｎ＋ｂ）に変換する手段と、
前記２進数表現ｘａ，ｘｂに基づいて、法ｎの整数ｓｎ＝（ｂ−ａ）ｓ ｍｏｄ ｎを得る手段と、
この整数ｓｎと前記ｘｕの関係式ｘｕ＝（ｂ−ａ）ｓ＋εσとに基づいて、前記ｘ２の候補ｓｎ’＝ｓｎ＋εσを得ると、この候補ｓｎ’を法ｎで調整し、前記ｘｕ ｍｏｄ ｎ の値を得る手段と、
を備えたことを特徴とする剰余演算装置。
【請求項５】
ｎより小さい整数ｘに関して法ｎの剰余演算ｘ２ ｍｏｄ ｎを実行するための剰余演算装置に用いられる剰余演算プログラムであって、
前記剰余演算装置のコンピュータを、
０以外の整数ａ，ｂ（但し、ａ−ｂ≧２）を用い、前記整数ｘを（ｂ−ａ）で割った商ｙと剰余εを求める手段、
前記商ｙをｈ個の整数ｐｉ（但し、ｉ＝１，…，ｈ、且つ、ｎ＋ａ＝ｐ１・ｐ２・…・ｐｈ）及び第１式ｙｉ＝ｙ ｍｏｄ ｐｉに基づいて、第１剰余系表現ｙｉ（但し、ｉ＝１，…，ｈ）に変換する手段、
前記第１剰余系表現ｙｉを中国人剰余定理により法ｎ＋ａの２進数表現ｘａ＝（ｂ−ａ）ｙｉ２＋２εｙｉ ｍｏｄ （ｎ＋ａ）に変換する手段、
前記商ｙをｍ個の整数ｑｊ（但し、ｊ＝１，…，ｍ、且つ、ｎ＋ｂ＝ｑ１・ｑ２・…・ｑｍ）及び第２式ｙｊ＝ｙ ｍｏｄ ｑｊに基づいて、第２剰余系表現ｙｊ（但し、ｊ＝１，…，ｍ）に変換する手段、
前記第２剰余系表現ｙｊを中国人剰余定理により法ｎ＋ｂの２進数表現ｘｂ＝（ｂ−ａ）ｙｊ２＋２εｙｊ ｍｏｄ （ｎ＋ｂ）に変換する手段、
前記２進数表現ｘａ，ｘｂ及び前記整数ａ，ｂに基づく値ｂｘａ−ａｘｂを法ｎで割り、商ｑと剰余ｒを得る手段、
前記商ｑ及び前記２進数表現ｘａ，ｘｂに関する条件式ｘａ−ｘｂ＋ｑに基づいて、前記条件式ｘａ−ｘｂ＋ｑ≧０のとき、整数ｓｎ＝ｒを得る手段、
前記条件式ｘａ−ｘｂ＋ｑ＜０且つｒ＋ａｂ＜ｎのとき、整数ｓｎ＝ｒ＋ａｂを得る手段、
前記条件式ｘａ−ｘｂ＋ｑ＜０且つｒ＋ａｂ＞ｎのとき、整数ｓｎ＝ｒ＋ａｂ−ｎを得る手段、
前記条件式により得られた整数ｓｎに対し、前記整数ｘを（ｂ−ａ）で割った剰余εの二乗ε２を加え、前記ｘ２の候補ｓｎ’を得る手段、
この候補ｓｎ’を法ｎで調整し、前記ｘ２ ｍｏｄ ｎ の値を得る手段、
として機能させるための剰余演算プログラム。
【請求項６】
ｎより小さい整数ｘ，ｕに関して法ｎの剰余演算ｘｕ ｍｏｄ ｎを実行するための剰余演算装置に用いられる剰余演算プログラムであって、
前記剰余演算装置のコンピュータを、
０以外の整数ａ，ｂ（但し、ａ−ｂ≧２）を用い、前記整数ｘを（ｂ−ａ）で割った商ｙと剰余εを求める手段、
前記整数ａ，ｂを用い、前記整数ｕを（ｂ−ａ）で割った商μと剰余σを求める手段、
前記商ｙをｈ個の整数ｐｉ（但し、ｉ＝１，…，ｈ、且つ、ｎ＋ａ＝ｐ１・ｐ２・…・ｐｈ）及び第１式ｙｉ＝ｙ ｍｏｄ ｐｉに基づいて、第１剰余系表現ｙｉ（但し、ｉ＝１，…，ｈ）に変換する手段、
前記商μを前記ｈ個の整数ｐｉ及び第２式μｉ＝μ ｍｏｄ ｐｉに基づいて、第２剰余系表現μｉ（但し、ｉ＝１，…，ｈ）に変換する手段、
前記第１及び第２剰余系表現ｙｉ，μｉを中国人剰余定理により法ｎ＋ａの２進数表現ｘａ＝（ｂ−ａ）ｙｉμｉ＋εμｉ＋σｙｉ ｍｏｄ （ｎ＋ａ）に変換する手段、
前記商ｙをｍ個の整数ｑｊ（但し、ｊ＝１，…，ｍ、且つ、ｎ＋ｂ＝ｑ１・ｑ２・…・ｑｍ）及び第３式ｙｊ＝ｙ ｍｏｄ ｑｊに基づいて、第３剰余系表現ｙｊ（但し、ｊ＝１，…，ｍ）に変換する手段、
前記商μを前記ｍ個の整数ｑｊ及び第４式μｊ＝μ ｍｏｄ ｑｊに基づいて、第４剰余系表現μｊ（但し、ｊ＝１，…，ｍ）に変換する手段、
前記第３及び第４剰余系表現ｙｊ，μｊを中国人剰余定理により法ｎ＋ｂの２進数表現ｘｂ＝（ｂ−ａ）ｙｊμｊ＋εμｊ＋σｙｊ ｍｏｄ （ｎ＋ｂ）に変換する手段、
前記２進数表現ｘａ，ｘｂ及び前記整数ａ，ｂに基づく値ｂｘａ−ａｘｂを法ｎで割り、商ｑと剰余ｒを得る手段、
前記商ｑ及び前記２進数表現ｘａ，ｘｂに関する条件式ｘａ−ｘｂ＋ｑに基づいて、前記条件式ｘａ−ｘｂ＋ｑ≧０のとき、整数ｓｎ＝ｒを得る手段、
前記条件式ｘａ−ｘｂ＋ｑ＜０且つｒ＋ａｂ＜ｎのとき、整数ｓｎ＝ｒ＋ａｂを得る手段、
前記条件式ｘａ−ｘｂ＋ｑ＜０且つｒ＋ａｂ＞ｎのとき、整数ｓｎ＝ｒ＋ａｂ−ｎを得る手段、
前記条件式により得られた整数ｓｎに対し、前記整数ｘを（ｂ−ａ）で割った剰余εの二乗ε２を加え、前記ｘｕの候補ｓｎ’を得る手段、
この候補ｓｎ’を法ｎで調整し、前記ｘｕ ｍｏｄ ｎ の値を得る手段、
として機能させるための剰余演算プログラム。
【請求項７】
ｎより小さい整数ｘに関して法ｎの剰余演算ｘ２ ｍｏｄ ｎを実行するための剰余演算装置に用いられる剰余演算プログラムであって、
前記剰余演算装置のコンピュータを、
０以外の整数ａ，ｂ（但し、ａ−ｂ≧２）を用い、前記整数ｘを整数ｂ−ａで割り、商ｙと剰余εを得る手段、
前記商ｙをｈ個の整数ｐｉ（但し、ｉ＝１，…，ｈ、且つ、ｎ＋ａ＝ｐ１・ｐ２・…・ｐｈ）及び第１式ｙｉ＝ｙ ｍｏｄ ｐｉに基づいて、剰余系表現ｙｉ（但し、ｉ＝１，…，ｈ）に変換する手段、
前記ｘ２＝（ｂ−ａ）｛（ｂ−ａ）ｙ２＋２εｙ｝＋ε２＝（ｂ−ａ）ｓ＋ε２の関係式に基づき、この整数ｓを法ｎ＋ａの第１剰余系表現ｓｉ＝（ｂ−ａ）ｙｉ２＋２εｙｉ ｍｏｄ ｐｉに変換し、得られた第１剰余系表現ｓｉを中国人剰余定理により法ｎ＋ａの２進数表現ｘａ＝ｓｉ ｍｏｄ（ｎ＋ａ）に変換する手段、
前記商ｙをｍ個の整数ｑｊ（但し、ｊ＝１，…，ｍ、且つ、ｎ＋ｂ＝ｑ１・ｑ２・…・ｑｍ）及び第２式ｙｊ＝ｙ ｍｏｄ ｑｊに基づいて、剰余系表現ｙｊ（但し、ｊ＝１，…，ｍ）に変換する手段、
前記整数ｓを法ｎ＋ｂの第２剰余系表現ｓｊ’＝（ｂ−ａ）ｙｊ２＋２εｙｊ ｍｏｄ ｑｊに変換し、得られた第２剰余系表現ｓｊ’を中国人剰余定理により法ｎ＋ｂの２進数表現ｘｂ＝ｓｊ’ ｍｏｄ（ｎ＋ｂ）に変換する手段、
前記２進数表現ｘａ，ｘｂに基づいて、法ｎの整数ｓｎ＝（ｂ−ａ）ｓ ｍｏｄ ｎを得る手段、
この整数ｓｎと前記ｘ２の関係式ｘ２＝（ｂ−ａ）ｓ＋ε２とに基づいて、前記ｘ２の候補ｓｎ’＝ｓｎ＋ε２を得ると、この候補ｓｎ’を法ｎで調整し、前記ｘ２ ｍｏｄ ｎ の値を得る手段、
として機能させるための剰余演算プログラム。
【請求項８】
ｎより小さい整数ｘ，ｕに関して法ｎの剰余演算ｘｕ ｍｏｄ ｎを実行するための剰余演算装置に用いられる剰余演算プログラムであって、
前記剰余演算装置のコンピュータを、
０以外の整数ａ，ｂ（但し、ａ−ｂ≧２）を用い、前記整数ｘを整数ｂ−ａで割り、商ｙと剰余εを得る手段、
前記整数ａ，ｂ（但し、ａ−ｂ≧２）を用い、前記整数ｕを整数ｂ−ａで割り、商μと剰余σを得る手段、
前記商ｙ，μをｈ個の整数ｐｉ（但し、ｉ＝１，…，ｈ、且つ、ｎ＋ａ＝ｐ１・ｐ２・…・ｐｈ）、式ｙｉ＝ｙ ｍｏｄ ｐｉ及び式μｉ＝μ ｍｏｄ ｐｉに基づいて、剰余系表現ｙｉ，μｉ（但し、ｉ＝１，…，ｈ）に変換する手段、
前記ｘｕ＝（ｂ−ａ）｛（ｂ−ａ）ｙμ＋εμ＋σｙ｝＋εσ＝（ｂ−ａ）ｓ＋εσの関係式に基づき、この整数ｓを法ｎ＋ａの第１剰余系表現ｓｉ＝（ｂ−ａ）ｙｉμｉ＋εμｉ＋σｙｉ ｍｏｄ ｐｉに変換し、得られた第１剰余系表現ｓｉを中国人剰余定理により法ｎ＋ａの２進数表現ｘａ＝ｓｉ ｍｏｄ（ｎ＋ａ）に変換する手段、
前記商ｙ，μをｍ個の整数ｑｊ（但し、ｊ＝１，…，ｍ、且つ、ｎ＋ｂ＝ｑ１・ｑ２・…・ｑｍ）、式ｙｊ＝ｙ ｍｏｄ ｑｊ及び式μｊ＝μ ｍｏｄ ｑｊに基づいて、剰余系表現ｙｊ，μｊ（但し、ｊ＝１，…，ｍ）に変換する手段、
前記整数ｓを法ｎ＋ｂの第２剰余系表現ｓｊ’＝（ｂ−ａ）ｙｊμｊ＋εμｊ＋σｙｊ ｍｏｄ ｑｊに変換し、得られた第２剰余系表現ｓｊ’を中国人剰余定理により法ｎ＋ｂの２進数表現ｘｂ＝ｓｊ’ ｍｏｄ（ｎ＋ｂ）に変換する手段、
前記２進数表現ｘａ，ｘｂに基づいて、法ｎの整数ｓｎ＝（ｂ−ａ）ｓ ｍｏｄ ｎを得る手段、
この整数ｓｎと前記ｘｕの関係式ｘｕ＝（ｂ−ａ）ｓ＋εσとに基づいて、前記ｘ２の候補ｓｎ’＝ｓｎ＋εσを得ると、この候補ｓｎ’を法ｎで調整し、前記ｘｕ ｍｏｄ ｎ の値を得る手段、
として機能させるための剰余演算プログラム。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、ｘ２（ｍｏｄ  ｎ）あるいはｘ・ｕ(ｍｏｄ ｎ) の演算を高速に実行する剰余演算装置及びプログラムに関する。
【０００２】
【従来の技術】
例えば情報通信ネットワークや計算機システムでは、情報の盗聴や改ざんを阻止するため、通常、公開鍵暗号方式が用いられている。
ここで、公開鍵暗号方式は、ＲＳＡ暗号やエルガマル（ElGamal）暗号などのように暗号方式それ自体と、デジタル署名方式や鍵配送方式などのように暗号方式を適用したものとが含まれる。また、ＲＳＡ暗号やエルガマル暗号を含む著名な公開鍵暗号方式の説明は、例えば文献１（A. J. Menezes, P. C. van Oorschot and S. A. Vanstone, “Handbook of Applied Cryptography”, CRC Press LLC, 1997.）のpp.283-312に詳しい。
【０００３】
この種の公開鍵暗号方式では、一般に、べき乗剰余算や剰余乗算を扱うことが多い。よって、暗号方式の高速化を図る観点から、べき乗剰余算や剰余乗算の高速化が古くより研究され、数々の手法が提案されている。
【０００４】
一例として、べき乗剰余算や剰余乗算のうち、べき乗剰余算の高速化について説明する。なお、べき乗剰余算ｇｅ ｍｏｄ ｎに含まれる,べき乗算ｇｅを高速に行なう種々の手法は、例えば文献１のpp.613-627に詳しい。但し、ここでは、平方と乗算との効果的な組合せにより、べき乗算ｇｅの乗算回数を削減する一般的な手法を述べる。この乗算回数の削減手法は、固定される値に応じ、異なる方法が有効となっている。
【０００５】
例えばＲＳＡ暗号のように、べき乗算ｇｅの,べき数ｅが固定される場合には、加算鎖（addition chain）を用いて,べき乗算ｇｅに必要な乗算回数を減らす方法が有効である。
【０００６】
また、エルガマル暗号やディフィー−ヘルマン（Diffie-Hellman）鍵交換のように、べき乗算ｇｅの底ｇが固定される場合には、乗算の一部を事前計算してテーブルに登録し、演算時に適宜参照することにより、乗算回数を減らす方法が有効である。なお、ディフィー−ヘルマン鍵交換については、例えば文献１のpp.515-524に詳しい。
【０００７】
さて、このように演算の高速化を図る研究の中で、法ｎでの平方及び乗算を２つの法ｎ＋１，ｎ＋２に関する剰余で補間する新しい手法（以下、林法と呼ぶ）が提案されている。この林法は、法ｎより大きい整数ｎ＋１，ｎ＋２がそれぞれ互いに素な整数に因数分解できる時に、これらｎ＋１，ｎ＋２を法とする剰余算を中国人剰余定理により高速に算出できることを利用し、法ｎでの平方及び乗算を高速化する手法である。なお、林法は、文献２（林彬、“新しい乗算剰余算の高速化法とべき剰余形暗号への応用”、電子情報通信学会論文誌、Vol.J81-A、No.10、pp.1372-1376, 1998.）に詳しい。
【０００８】
さらに、林法における法ｎ＋１，ｎ＋２等のパラメータの設定を容易にする手法が清水により提案されている。この清水の手法は、林法の拡張により、２つの法ｎ＋ａ，ｎ＋ａ＋１を用いて、法ｎでの平方及び乗算を高速化するものである。なお、清水の手法は、文献３（清水秀夫、“並列剰余乗算のための林法の拡張”、1999年電子情報通信学会基礎・境界ソサイエティ大会、p.114、1999.）に詳しい。
【０００９】
これら林法及び清水の手法は、従来とは異なり、平方剰余算や剰余乗算を中国人剰余定理により高速化するものであり、また、それぞれ他の高速化の手法との組合せが可能となっている。
【００１０】
ここで、林法では、ＲＳＡ暗号の法ｎの場合、公開鍵（ｅ，ｎ）を定めた段階で、補間する２つの法ｎ＋１，ｎ＋２が定まる。また、林法における演算速度は、補間する２つの法ｎ＋１，ｎ＋２の最大素因数がどれだけ小さいか、またどれだけ多くの互いに素な整数に分解できるか、という２つの期待する条件に依存する。よって、林法では、演算速度をより高めたい場合、これら２つの期待する条件に見合う方向で、予め法ｎの鍵生成に何らかの制約を加える必要がある。
【００１１】
一方、清水の手法は、法ｎが定まった後でも２つの法ｎ＋ａ，ｎ＋ａ＋１を高速に設定可能な理論的な演算アルゴリズムが動作する。従って、清水の手法は、林法に比べ、補間する２つの法の設定が柔軟かつ容易になっている。
【００１２】
【発明が解決しようとする課題】
しかしながら、以上のような清水の手法では、特に問題は無いようであるが、本発明者の考察によれば、林法と同様に２つの法の差を１とする制約がある。このため、清水の手法は、前述した２つの期待する条件に見合う２つの法ｎ＋ａ，ｎ＋ａ＋１を設定することが実用的に困難であると考えられ、実用性の向上の余地のあることが推察される。
【００１３】
本発明は上記実情を考慮してなされたもので、本来の法とは別の２つの法を補助的に用いる剰余演算に関し、別の２つの法を容易に設定でき、実用性を向上し得る剰余演算装置及びプログラムを提供することを目的とする。
【００１４】
【課題を解決するための手段】
第１の発明は、整数Ｘを対象として法ｎの剰余演算Ｘ ｍｏｄ ｎを実行するための剰余演算装置であって、０以外の整数ａを用い、前記整数Ｘに対する法ｎ＋ａの剰余演算Ｘ ｍｏｄ （ｎ＋ａ）を実行する手段と、０以外の整数ｂ（但し、ａ−ｂ≧２）を用い、前記整数Ｘに対する法ｎ＋ｂの剰余演算Ｘ ｍｏｄ （ｎ＋ｂ）を実行する手段と、前記法ｎ＋ａの剰余演算結果と、前記法ｎ＋ｂの剰余演算結果とに基づいて、前記法ｎの剰余演算Ｘ ｍｏｄ ｎの値を求める手段と、を備えた剰余演算装置である。
ここで、第１の発明は、以下の各局面のように表現できる。
第１の発明の第１の局面は、ｎより小さい整数ｘに関して法ｎの剰余演算ｘ２ ｍｏｄ ｎを実行するための剰余演算装置であって、０以外の整数ａ，ｂ（但し、ａ−ｂ≧２）を用い、前記整数ｘを（ｂ−ａ）で割った商ｙと剰余εを求める手段と、前記商ｙをｈ個の整数ｐｉ（但し、ｉ＝１，…，ｈ、且つ、ｎ＋ａ＝ｐ１・ｐ２・…・ｐｈ）及び第１式ｙｉ＝ｙ ｍｏｄ ｐｉに基づいて、第１剰余系表現ｙｉ（但し、ｉ＝１，…，ｈ）に変換する手段と、前記第１剰余系表現ｙｉを中国人剰余定理により法ｎ＋ａの２進数表現ｘａ＝（ｂ−ａ）ｙｉ２＋２εｙｉ ｍｏｄ （ｎ＋ａ）に変換する手段と、前記商ｙをｍ個の整数ｑｊ（但し、ｊ＝１，…，ｍ、且つ、ｎ＋ｂ＝ｑ１・ｑ２・…・ｑｍ）及び第２式ｙｊ＝ｙ ｍｏｄ ｑｊに基づいて、第２剰余系表現ｙｊ（但し、ｊ＝１，…，ｍ）に変換する手段と、前記第２剰余系表現ｙｊを中国人剰余定理により法ｎ＋ｂの２進数表現ｘｂ＝（ｂ−ａ）ｙｊ２＋２εｙｊ ｍｏｄ （ｎ＋ｂ）に変換する手段と、前記２進数表現ｘａ，ｘｂ及び前記整数ａ，ｂに基づく値ｂｘａ−ａｘｂを法ｎで割り、商ｑと剰余ｒを得る手段と、前記商ｑ及び前記２進数表現ｘａ，ｘｂに関する条件式ｘａ−ｘｂ＋ｑに基づいて、前記条件式ｘａ−ｘｂ＋ｑ≧０のとき、整数ｓｎ＝ｒを得る手段と、前記条件式ｘａ−ｘｂ＋ｑ＜０且つｒ＋ａｂ＜ｎのとき、整数ｓｎ＝ｒ＋ａｂを得る手段と、前記条件式ｘａ−ｘｂ＋ｑ＜０且つｒ＋ａｂ＞ｎのとき、整数ｓｎ＝ｒ＋ａｂ−ｎを得る手段と、前記条件式により得られた整数ｓｎに対し、前記整数ｘを（ｂ−ａ）で割った剰余εの二乗ε２を加え、前記ｘ２の候補ｓｎ’を得る手段と、この候補ｓｎ’を法ｎで調整し、前記ｘ２ ｍｏｄ ｎ の値を得る手段と、を備えた剰余演算装置である。
第１の発明の第２の局面は、ｎより小さい整数ｘ，ｕに関して法ｎの剰余演算ｘｕ ｍｏｄ ｎを実行するための剰余演算装置であって、０以外の整数ａ，ｂ（但し、ａ−ｂ≧２）を用い、前記整数ｘを（ｂ−ａ）で割った商ｙと剰余εを求める手段と、前記整数ａ，ｂを用い、前記整数ｕを（ｂ−ａ）で割った商μと剰余σを求める手段と、前記商ｙをｈ個の整数ｐｉ（但し、ｉ＝１，…，ｈ、且つ、ｎ＋ａ＝ｐ１・ｐ２・…・ｐｈ）及び第１式ｙｉ＝ｙ ｍｏｄ ｐｉに基づいて、第１剰余系表現ｙｉ（但し、ｉ＝１，…，ｈ）に変換する手段と、前記商μを前記ｈ個の整数ｐｉ及び第２式μｉ＝μ ｍｏｄ ｐｉに基づいて、第２剰余系表現μｉ（但し、ｉ＝１，…，ｈ）に変換する手段と、前記第１及び第２剰余系表現ｙｉ，μｉを中国人剰余定理により法ｎ＋ａの２進数表現ｘａ＝（ｂ−ａ）ｙｉμｉ＋εμｉ＋σｙｉ ｍｏｄ （ｎ＋ａ）に変換する手段と、前記商ｙをｍ個の整数ｑｊ（但し、ｊ＝１，…，ｍ、且つ、ｎ＋ｂ＝ｑ１・ｑ２・…・ｑｍ）及び第３式ｙｊ＝ｙ ｍｏｄ ｑｊに基づいて、第３剰余系表現ｙｊ（但し、ｊ＝１，…，ｍ）に変換する手段と、前記商μを前記ｍ個の整数ｑｊ及び第４式μｊ＝μ ｍｏｄ ｑｊに基づいて、第４剰余系表現μｊ（但し、ｊ＝１，…，ｍ）に変換する手段と、前記第３及び第４剰余系表現ｙｊ，μｊを中国人剰余定理により法ｎ＋ｂの２進数表現ｘｂ＝（ｂ−ａ）ｙｊμｊ＋εμｊ＋σｙｊ ｍｏｄ （ｎ＋ｂ）に変換する手段と、前記２進数表現ｘａ，ｘｂ及び前記整数ａ，ｂに基づく値ｂｘａ−ａｘｂを法ｎで割り、商ｑと剰余ｒを得る手段と、前記商ｑ及び前記２進数表現ｘａ，ｘｂに関する条件式ｘａ−ｘｂ＋ｑに基づいて、前記条件式ｘａ−ｘｂ＋ｑ≧０のとき、整数ｓｎ＝ｒを得る手段と、前記条件式ｘａ−ｘｂ＋ｑ＜０且つｒ＋ａｂ＜ｎのとき、整数ｓｎ＝ｒ＋ａｂを得る手段と、前記条件式ｘａ−ｘｂ＋ｑ＜０且つｒ＋ａｂ＞ｎのとき、整数ｓｎ＝ｒ＋ａｂ−ｎを得る手段と、前記条件式により得られた整数ｓｎに対し、前記整数ｘを（ｂ−ａ）で割った剰余εの二乗ε２を加え、前記ｘｕの候補ｓｎ’を得る手段と、この候補ｓｎ’を法ｎで調整し、前記ｘｕ ｍｏｄ ｎ の値を得る手段と、を備えた剰余演算装置である。
第１の発明の第３の局面は、ｎより小さい整数ｘに関して法ｎの剰余演算ｘ２ ｍｏｄ ｎを実行するための剰余演算装置であって、０以外の整数ａ，ｂ（但し、ａ−ｂ≧２）を用い、前記整数ｘを整数ｂ−ａで割り、商ｙと剰余εを得る手段と、前記商ｙをｈ個の整数ｐｉ（但し、ｉ＝１，…，ｈ、且つ、ｎ＋ａ＝ｐ１・ｐ２・…・ｐｈ）及び第１式ｙｉ＝ｙ ｍｏｄ ｐｉに基づいて、剰余系表現ｙｉ（但し、ｉ＝１，…，ｈ）に変換する手段と、前記ｘ２＝（ｂ−ａ）｛（ｂ−ａ）ｙ２＋２εｙ｝＋ε２＝（ｂ−ａ）ｓ＋ε２の関係式に基づき、この整数ｓを法ｎ＋ａの第１剰余系表現ｓｉ＝（ｂ−ａ）ｙｉ２＋２εｙｉ ｍｏｄ ｐｉに変換し、得られた第１剰余系表現ｓｉを中国人剰余定理により法ｎ＋ａの２進数表現ｘａ＝ｓｉ ｍｏｄ（ｎ＋ａ）に変換する手段と、前記商ｙをｍ個の整数ｑｊ（但し、ｊ＝１，…，ｍ、且つ、ｎ＋ｂ＝ｑ１・ｑ２・…・ｑｍ）及び第２式ｙｊ＝ｙ ｍｏｄ ｑｊに基づいて、剰余系表現ｙｊ（但し、ｊ＝１，…，ｍ）に変換する手段と、前記整数ｓを法ｎ＋ｂの第２剰余系表現ｓｊ’＝（ｂ−ａ）ｙｊ２＋２εｙｊ ｍｏｄ ｑｊに変換し、得られた第２剰余系表現ｓｊ’を中国人剰余定理により法ｎ＋ｂの２進数表現ｘｂ＝ｓｊ’ ｍｏｄ（ｎ＋ｂ）に変換する手段と、前記２進数表現ｘａ，ｘｂに基づいて、法ｎの整数ｓｎ＝（ｂ−ａ）ｓ ｍｏｄ ｎを得る手段と、この整数ｓｎと前記ｘ２の関係式ｘ２＝（ｂ−ａ）ｓ＋ε２とに基づいて、前記ｘ２の候補ｓｎ’＝ｓｎ＋ε２を得ると、この候補ｓｎ’を法ｎで調整し、前記ｘ２ ｍｏｄ ｎ の値を得る手段と、を備えた剰余演算装置である。
第１の発明の第４の局面は、ｎより小さい整数ｘ，ｕに関して法ｎの剰余演算ｘｕ ｍｏｄ ｎを実行するための剰余演算装置であって、０以外の整数ａ，ｂ（但し、ａ−ｂ≧２）を用い、前記整数ｘを整数ｂ−ａで割り、商ｙと剰余εを得る手段と、前記整数ａ，ｂ（但し、ａ−ｂ≧２）を用い、前記整数ｕを整数ｂ−ａで割り、商μと剰余σを得る手段と、前記商ｙ，μをｈ個の整数ｐｉ（但し、ｉ＝１，…，ｈ、且つ、ｎ＋ａ＝ｐ１・ｐ２・…・ｐｈ）、式ｙｉ＝ｙ ｍｏｄ ｐｉ及び式μｉ＝μ ｍｏｄ ｐｉに基づいて、剰余系表現ｙｉ，μｉ（但し、ｉ＝１，…，ｈ）に変換する手段と、前記ｘｕ＝（ｂ−ａ）｛（ｂ−ａ）ｙμ＋εμ＋σｙ｝＋εσ＝（ｂ−ａ）ｓ＋εσの関係式に基づき、この整数ｓを法ｎ＋ａの第１剰余系表現ｓｉ＝（ｂ−ａ）ｙｉμｉ＋εμｉ＋σｙｉ ｍｏｄ ｐｉに変換し、得られた第１剰余系表現ｓｉを中国人剰余定理により法ｎ＋ａの２進数表現ｘａ＝ｓｉ ｍｏｄ（ｎ＋ａ）に変換する手段と、前記商ｙ，μをｍ個の整数ｑｊ（但し、ｊ＝１，…，ｍ、且つ、ｎ＋ｂ＝ｑ１・ｑ２・…・ｑｍ）、式ｙｊ＝ｙ ｍｏｄ ｑｊ及び式μｊ＝μ ｍｏｄ ｑｊに基づいて、剰余系表現ｙｊ，μｊ（但し、ｊ＝１，…，ｍ）に変換する手段と、前記整数ｓを法ｎ＋ｂの第２剰余系表現ｓｊ’＝（ｂ−ａ）ｙｊμｊ＋εμｊ＋σｙｊ ｍｏｄ ｑｊに変換し、得られた第２剰余系表現ｓｊ’を中国人剰余定理により法ｎ＋ｂの２進数表現ｘｂ＝ｓｊ’ ｍｏｄ（ｎ＋ｂ）に変換する手段と、前記２進数表現ｘａ，ｘｂに基づいて、法ｎの整数ｓｎ＝（ｂ−ａ）ｓ ｍｏｄ ｎを得る手段と、この整数ｓｎと前記ｘｕの関係式ｘｕ＝（ｂ−ａ）ｓ＋εσとに基づいて、前記ｘ２の候補ｓｎ’＝ｓｎ＋εσを得ると、この候補ｓｎ’を法ｎで調整し、前記ｘｕ ｍｏｄ ｎ の値を得る手段と、を備えた剰余演算装置である。
【００１５】
このように、本来の法とは別の２つの法を補助的に用いる剰余演算に関し、別の２つの法の差を１とする制約が無いので、これら別の２つの法を容易に設定でき、実用性を向上させることができる。
【００１６】
なお、第１の発明は、「装置」として表現されているが、これに限らず、「システム」、「方法」、「プログラム」又は「記憶媒体」等として表現してもよいことは言うまでもない。
【００１７】
【発明の実施の形態】
以下、本発明の各実施形態について図面を用いて説明するが、その前に、各実施形態の前提となる関係式について述べる。始めに、周知の中国人剰余定理（Chinese remainder theorem）について説明する。
【００１８】
中国人剰余定理とは、互いに素なｋ個の整数π１、π２、…、πｋが存在する時、以下の各式を満たす整数α（０≦α＜π１π２…πｋ）が一意に定まるというものである。
【００１９】
α  ≡  β１  ｍｏｄ π１
α  ≡  β２  ｍｏｄ π２
…
α  ≡  βｋ  ｍｏｄ πｋ
以上が中国人剰余定理の内容であるが、ここでｎ＝π１π２…πｋとすると、αは次の式で定まることが知られている。
【００２０】
【数１】
0004068352.tif 000002
但し、Ｎｉ＝ｎ／πｉ，Ｍｉ＝Ｎｉ-1ｍｏｄ πｉ
【００２１】
これはガウスのアルゴリズムとも呼ばれている。続いて、各実施形態の概略について述べる。
各実施形態は、概略的には、演算対象Ｘに対する法ｎの剰余演算Ｘ ｍｏｄ ｎの際に、新たな２つの法ｎ＋ａ，ｎ＋ｂを用いた中国人剰余定理により、Ｘ ｍｏｄ （ｎ＋ａ）と、Ｘ ｍｏｄ （ｎ＋ｂ）とを効率的に算出し、この算出結果を用いて本来の剰余演算Ｘ ｍｏｄ ｎを高速に処理するものである。
【００２２】
ここで、演算対象Ｘ＝ｘ２（平方剰余算）又はＸ＝ｘ・ｕ（剰余乗算）であり、各ｘは０≦ｘ＜ｎの範囲にある。
【００２３】
また、法ｎ＋ａ，ｎ＋ｂは、事前に計算されるが、いずれも互いに素な整数の積に分解可能な値であるとする。具体的には次の各式に示すように、法ｎ＋ａはｈ個の整数ｐｉ（ｉ＝１、…、ｈ）に分解可能であり、法ｎ＋ｂはｍ個の整数ｑｊ（ｊ＝１、…、ｍ）に分解可能であるとする。但し、必ずしも素因数分解できなくてもよい。
【００２４】
【数２】
0004068352.tif 000003
【００２５】
なお、法ｎ＋ａ，ｎ＋ｂの因数分解を行う機能は、Ｘ ｍｏｄ ｎ  を計算する装置に必ずしも備わっている必要はない。例えば、法ｎを決定した機関装置が法ｎ＋ａ，ｎ＋ｂを各因数ｐｉ，ｑｊに分解し、得られたｐｉ，ｑｊを法ｎと同様に入手可能な公開パラメータとして設定しておいてもよい。
【００２６】
ここで、各実施形態の前提となる各関係式を［補題］、［補題の証明］、［定理］及び［定理の証明］の形式を用いて説明する。なお、以下の［補題］〜［定理の証明］は、数学上の根拠記載であり、各実施形態の高速演算アルゴリズムの手順とは無関係である。このため、各実施形態を先に読んでもよい。
【００２７】
［補題］
法ｎ＋ａ，ｎ＋ｂに関係するｎ、ａ及びｂは、正の整数であり、互いに、０＜ａ＜ｂ＜ｎ1/2、最大公約数ｇｃｄ（ｎ＋ａ、ｎ＋ｂ）＝１の関係がある。このとき、演算対象ｘ，ｕは次の関係式を満たす。
【００２８】
０≦（ｂ−ａ）ｘ＜（ｎ＋ａ）（ｎ＋ｂ）
０≦（ｂ−ａ）ｕ＜（ｎ＋ａ）（ｎ＋ｂ）
この関係式を満たすｘから２つの整数ｘａ，ｘｂを次のように定める。
【００２９】
ｘａ＝ｘ（ｍｏｄ（ｎ＋ａ））
ｘｂ＝ｘ（ｍｏｄ（ｎ＋ｂ））
また、各整数ｘａ，ｘｂを用いて整数ｘ’を次のようにおく。
【００３０】
ｘ’＝（ｎ＋ｂ）ｘａ−（ｎ＋ａ）ｘｂ
このとき、次の関係式（１）が成り立つ。
【００３１】
（ｂ−ａ）ｘ＝ｘ’＋ｋ（ｎ＋ａ）（ｎ＋ｂ）      …（１）
但し、ｋ＝０、（ｘ’≧０）又は
ｋ＝１、（ｘ’＜０）
［補題の証明］
ｘ’≡（ｎ＋ｂ）ｘａ≡（ｂ−ａ）ｘ（ｍｏｄ（ｎ＋ａ））
同様に、ｘ’≡（ｂ−ａ）ｘ（ｍｏｄ（ｎ＋ｂ））で（ｎ＋１，ｎ＋ｂ）＝１であるから、
ｘ’≡（ｂ−ａ）ｘ（ｍｏｄ（ｎ＋ａ）（ｎ＋ｂ））
である。そこで、ｋを整数として、前述した式（１）を得られる。
【００３２】
ここで、補題の冒頭の関係式より、（ｂ−ａ）ｘが法（ｎ＋ａ）（ｎ＋ｂ）より小さいので、ｘ’が負の時のみｋ＝１になる（ｘ’が非負の時にはｋ＝０）。
【００３３】
［定理］
補題と同じ条件下で、ｘ，ｘａ，ｘｂを関連付ける次の式（２）が成り立つ。
【００３４】
（ｂ−ａ）ｘ≡ｂｘａ−ａｘｂ＋ｋａｂ （ｍｏｄ ｎ）      …（２）
ここで、ｂｘａ−ａｘｂを法ｎで割った商をｑ、余りをｒ（０≦ｒ＜ｎ）とすると（ｂｘａ−ａｘｂ＝ｑｎ＋ｒ）、整数ｋは次の値をとる。
【００３５】
ｋ＝０、（ｘａ−ｘｂ＋ｑ≧０）又は
ｋ＝１、（ｘａ−ｘｂ＋ｑ＜０）
さらに、ａｂ＜０を仮定すると、次の式（３）が成り立つ。
【００３６】
（ｂ−ａ）ｘ （ｍｏｄ ｎ）＝ｒ、ｒ＋ａｂ、又はｒ＋ａｂ−ｎ…（３）
式（３）の演算結果は、次の３通りに場合分けされる。
【００３７】
ｒ、          （ｘａ−ｘｂ＋ｑ≧０）
ｒ＋ａｂ、    （ｘａ−ｘｂ＋ｑ＜０、ｒ＋ａｂ＜ｎ）
ｒ＋ａｂ−ｎ、（ｘａ−ｘｂ＋ｑ＜０、ｒ＋ａｂ＞ｎ）
［定理の証明］
定理の式（２）は、補題の式（１）の右辺をｍｏｄ ｎして得られる。定理の後半に関しては、ｋの値を証明し、次いで、式（３）を証明する。
まず、ｘ’の定義から次の式（４）が得られる。
【００３８】
0004068352.tif 000004
式（４）に、定理で述べた式ｂｘａ−ａｘｂ＝ｑｎ＋ｒを代入すると、次の式（５）が得られる。
【００３９】
ｘ’＝ｎ（ｘａ−ｘｂ＋ｑ）＋ｒ      …（５）
式（５）と、余りｒの値（０≦ｒ＜ｎ）とから、次の関係が分かる。
【００４０】
ｘ’≧０、（ｘａ−ｘｂ＋ｑ≧０）又は
ｘ’＜０、（ｘａ−ｘｂ＋ｑ＜０）
この関係は、補題１のｋの条件からそれぞれがｋ＝０，１に対応することが分かる（ｋの値の証明）。
【００４１】
また、式（５）を式（２）に代入すると次の式（６）が得られる。
【００４２】
（ｂ−ａ）ｘ≡ｑｎ＋ｒ＋ｋａｂ
≡ｒ＋ｋａｂ（ｍｏｄ ｎ）…（６）
式（６）と、ｒの値（０≦ｒ＜ｎ）と、定理での仮定ａｂ＜ｎより、ｒ＋ａｂ＜２ｎである。この式からｒ＋ａｂ−ｎ＜ｎが分かり、ｋの条件を組合せて式（３）が得られる（式（３）の証明）。
【００４３】
以上により、各実施形態の前提となる関係式の説明を終える。続いて、本発明の各実施形態について説明する。
【００４４】
（第１の実施形態）
図１は本発明の第１の実施形態に係る平方剰余演算装置の構成を示す模式図である。この平方剰余演算装置１０は、平方剰余算 ｘ２ ｍｏｄ ｎを高速に算出するものであり、平方入出力管理部１１及び平方演算部１２を備えており、各部１１，１２はそれぞれハードウェア、ソフトウェア又はその組合せにより構成可能となっている。ここで、各部１１，１２がソフトウェアにより構成される場合、後述する各機能を実現させるための剰余演算プログラムが予め平方剰余演算装置１０のコンピュータにインストールされている。なお、ハードウェア及び／又はソフトウェアにより各部１１，１２を個別に構成可能な旨の説明は、以下の各実施形態にも適用される。
【００４５】
ここで、平方入出力管理部１１は、外部から入力された入力データを管理する機能と、図２のフローチャート（高速化演算アルゴリズム）に基づいて、データ及び演算命令を平方演算部１２に送信する機能と、平方演算部１２からの演算結果を受け取り管理する機能と、最終的な  ｘ２ ｍｏｄ ｎ  の演算結果を出力する機能とをもっている。
【００４６】
平方演算部１２は、平方入出力管理部１１より受けたデータと演算命令に従い、演算を行う機能と、演算結果を平方入出力管理部１１へ送信する機能とをもっている。
【００４７】
次に、以上のように構成された平方剰余演算装置における平方剰余算 ｘ２ ｍｏｄ ｎの算出動作を図２のフローチャートを用いて説明する。
【００４８】
始めに、平方剰余演算装置１０においては、外部から演算対象ｘ（０≦ｘ＜ｎ）と、各パラメータｎ、ｎ＋ａ、ｎ＋ｂ、ａ、ｂ、ｂ−ａ、ｐｉ（ｉ＝１、…、ｈ）及びｑｊ（ｊ＝１、…、ｍ）とが入力データとして平方入出力管理部１１に入力される（ＳＴ１）。
【００４９】
ここで、例えばａ及びｂを入力すれば、各パラメータｎ＋ａ、ｎ＋ｂ、ｂ−ａ、ｐｉ（ｉ＝１、…、ｈ）及びｑｊ（ｊ＝１、…、ｍ）が計算可能なので、必ずしも上述した全てを入力データとする必要はない。特に、演算対象ｘ以外の入力データは予め平方剰余演算装置１０が保持していてもよい。これは以下の各実施形態も同様である。また、これら以外のデータを入力してもよい。
【００５０】
平方入出力管理部１１は、これら入力データを受けると、平方演算部１２を制御して次式のように、ｘを（ｂ−ａ）で割った商ｙと剰余εを求める（ＳＴ２）。
【００５１】
ｘ＝（ｂ−ａ）ｙ＋ε
このとき、ｘ２は以下の式で表すことができる。
【００５２】
ｘ２＝（ｂ−ａ）｛（ｂ−ａ）ｙ２＋２εｙ｝＋ε２
ここで、中括弧｛｝の中身をｓとおく。
【００５３】
ｓ＝（ｂ−ａ）ｙ２＋２εｙ
なお、ｘ２＝（ｂ−ａ）ｓ＋ε２となる。
【００５４】
本実施形態では、上の式のｙを剰余系表現ｙｉ，ｙｊ’に変換すると共にｓを剰余系表現ｓｉ，ｓｊ’に変換し、各ｓｉ，ｓｊ’から中国人剰余定理を用いて２進数表現ｘａ，ｘｂを高速に算出し、得られたｘａ，ｘｂから定理の式（２），（３）により（ｂ−ａ）ｓを求め、最終的にε２を考慮して、ｘ２ ｍｏｄ ｎを求めてゆく。
【００５５】
まず、ｓを構成する商ｙを剰余系表現に変換する。
【００５６】
すなわち、平方入出力管理部１１は、平方演算部１２を制御して次式のように、商ｙを剰余系表現ｙｉに変換する（ＳＴ３）。
【００５７】
ｙｉ＝ｙ ｍｏｄ ｐｉ（ｉ＝１、…、ｈ）
次に、平方入出力管理部１１は、得られたｙｉを用い、平方演算部１２の制御により、次式のように、中間値ｓを剰余系表現ｓｉに変換する（ＳＴ４）。
【００５８】
ｓｉ＝（ｂ−ａ）ｙｉ２ ＋２εｙｉ ｍｏｄ ｐｉ（ｉ＝１、…、ｈ）
平方入出力管理部１１は、得られたｓｉを用い、平方演算部１２の制御により、中国人剰余定理を用いて、剰余系表現ｓｉを２進数表現ｘａに戻す（ＳＴ５）。
【００５９】
ｘａ＝ｓｉ  ｍｏｄ  （ｎ＋ａ）
同様の手順で、平方入出力管理部１１は、平方演算部１２を制御し、ｑｊ（ｊ＝１、…、ｍ）を用いて、ｘｂ＝ｓｊ  ｍｏｄ  （ｎ＋ｂ）を求める（ＳＴ６〜ＳＴ８）。
【００６０】
次に、平方入出力管理部１１は、平方演算部１２を制御し、次式のように、ｂｘａ−ａｘｂをｎで割った商ｑ、余りｒを計算する（ＳＴ９）。
【００６１】
ｂｘａ−ａｘｂ＝ｎｑ＋ｒ
ここで、平方入出力管理部１１は、平方演算部１２を制御し、ｘａ−ｘｂ＋ｑを求め、この値ｘａ−ｘｂ＋ｑに基づいて、定理の式（３）の通りに、ｓｎ＝（ｂ−ａ）ｓ  ｍｏｄ ｎを求める（ＳＴ１０）。
【００６２】
すなわち、ｘａ−ｘｂ＋ｑ≧０ならｓｎ＝ｒとし（ＳＴ１０−１）、ｘａ−ｘｂ＋ｑ＜０かつｒ＋ａｂ＜ｎならｓｎ＝ｒ＋ａｂとし（ＳＴ１０−２）、ｘａ−ｘｂ＋ｑ＜０かつｒ＋ａｂ＞ｎならｓｎ＝ｒ＋ａｂ−ｎとして（ＳＴ１０−３）、ｓｎ＝（ｂ−ａ）ｓ  ｍｏｄ ｎを求める。
【００６３】
続いて、平方入出力管理部１１は、平方演算部１２を制御し、ｓｎ’＝ｓｎ＋ε２を求める（ＳＴ１１）。
【００６４】
最後に、平方入出力管理部１１は、得られたｓｎ’を法ｎと比較し、ｓｎ’≧ｎならばｓｎ’−ｎを平方剰余算ｘ２ｍｏｄ ｎ  の演算結果として出力し（ＳＴ１２−１）、ｓｎ’＜ｎならばｓｎ’を同演算結果として出力する（ＳＴ１２−２）。
【００６５】
（計算量の評価）
次に、上述した平方剰余演算装置１０による計算量の評価について述べる。この評価は、林法の文献２に記載の方法を用いた計算量の見積もりにより行なう。なお、具体的には、以下のように、乗算の計算量の見積もりＭ（ｋ，L）及び除算の計算量の見積もりＤ（ｋ，L）を使用し、加算と減算は、計算量見積もりから除外する。
【００６６】
0004068352.tif 000005
林法の文献２では、乗算、除算を並列計算できるものとして計算量を見積もっており、本実施形態でも並列計算するものとして考えてみることにする。さらに法ｎのビット数をｋとし、拡張した数ａ，ｂの最大ビット数をｔとし、法ｎ＋ａ，ｎ＋ｂの因数ｐｉ，ｑｊの最大ビット数をLとする。また、簡単のため、因数ｐｉ，ｑｊの個数ｈ＝ｍ＝ｋ／Lを仮定する。
【００６７】
また、中国人剰余定理の計算は、ガウスのアルゴリズムと、ガーナー（Garner）のアルゴリズムが知られているが、ここでは並列計算可能なガウスのアルゴリズムを用いる。また、事前計算可能なものは、計算量に含めない。
【００６８】
以上の条件下で計算量の見積もりを行なう。
【００６９】
ＳＴ２：ｘ＝（ｂ−ａ）ｙ＋εの計算量
Ｄ（ｋ，ｔ）＝ｔ（ｋ−ｔ）
ＳＴ３：ｙｉ＝ｙ ｍｏｄ ｐｉの計算量
ｙは（ｋ−ｔ）ビットであるため、Ｄ（ｋ−ｔ，L）＝L（ｋ−ｔ−L）
ＳＴ４：ｓｉ＝（ｂ−ａ）ｙｉ２ ＋２εｙｉ ｍｏｄ ｐｉの計算量
Ｍ（L，L）＋Ｍ（２L，ｔ）＋Ｍ（L，ｔ）＋Ｄ（２L＋ｔ，L）＝３L２＋４ｔL＋２ｔ２
ＳＴ５：ｓｉの中国人剰余定理の計算量
Ｍ（ｋ，L）＋Ｄ（ｋ＋L，ｋ）＝L（２ｋ＋L）
ＳＴ６〜ＳＴ８：ｙｊ’，ｓｊ’の計算量
並列計算のため、計算量に含めず。
【００７０】
ＳＴ９：（ｂｘａ−ａｘｂ）ｍｏｄ ｎの計算量
２Ｍ（ｋ，ｔ）＋Ｄ（ｋ＋ｔ，ｋ）＝３ｔｋ＋２ｔ２
ＳＴ１１：ｓｎ’＝ｓｎ＋ε２の計算量
Ｍ（ｔ，ｔ）＝２ｔ２
ＳＴ１２：ｘ２＝ｓｎ’ｍｏｄ ｎの計算量
比較と減算のため、計算量は０とみなす。
【００７１】
以上の各ステップＳＴ２〜ＳＴ１２の計算量の合計Ｔ１は、次のようになる。
Ｔ１＝５ｔ２＋ｔ（４ｋ＋３L）＋３ｋL＋３L２
ここで、L＝ｋ／ｈとして、Lを消去すると、Ｔ１（ｔ，ｈ）は次式のようになる。
【００７２】
【数３】
0004068352.tif 000006
【００７３】
従って、法ｎ＋ａの因数ｐｉの個数ｈが大きいほど、計算量の合計Ｔ１は小さくなる。そこで、例えば、ｔ＝３２、ｈ＝４、即ち、ａ，ｂが３２ビットで、法ｎ＋ａ，ｎ＋ｂがそれぞれ４個の互いに素な整数の積に因数分解できたとすれば、計算量の合計Ｔ１（３２，４）は次のようになる。
【００７４】
【数４】
0004068352.tif 000007
【００７５】
一方、通常の計算法では、林法の文献２にあるように、計算量Ｔ０が次のようになる。
Ｔ０＝Ｍ（ｋ，ｋ）＋Ｄ（２ｋ，ｋ）＝３ｋ２
このため、本実施形態に係る計算量Ｔ１（３２，４）と、通常の計算量Ｔ０とを比較すると、ｋ≧９９なら本実施形態の方法が高速であることが分かる。例えばｋ＝１０２４の場合、両者の計算量の比Ｔ１／Ｔ０は次式の通りとなる。
【００７６】
【数５】
0004068352.tif 000008
【００７７】
すなわち、本実施形態の計算量Ｔ１は、通常の計算量Ｔ０の約３６．３％に低減されていることが分かる。
【００７８】
上述したように本実施形態によれば、本来の法ｎとは別の２つの法ｎ＋ａ，ｎ＋ｂを補助的に用いる剰余演算ｘ２ ｍｏｄ ｎに関し、別の２つの法ｎ＋ａ，ｎ＋ｂの差を１とする制約が無いので、これら別の２つの法ｎ＋ａ，ｎ＋ｂを容易に設定でき、実用性を向上させることができる。
【００７９】
詳しくは、本発明者の研究により、前述した定理の式（２），（３）を新たに得たことにより、補間する２つの法をｎ＋ａ，ｎ＋ｂに拡張できたので、従来とは異なり、パラメータの設定を容易に実行することができる。
【００８０】
なお、本実施形態は、例えばｙｉ＝ｙ ｍｏｄ ｐｉ  の演算（ＳＴ３〜ＳＴ５）より先にｙｉ’＝ｙ ｍｏｄ ｑｊ の演算（ＳＴ６〜ＳＴ８）を行う等、演算過程において支障をきたさない部分は、逐次演算順序を変更してもよい。これは、以下の各実施形態でも同様である。
【００８１】
また、本実施形態は、因数ｐｉ，ｑｊに関して特に述べなかったが、演算の高速化を図る観点から、２ｕ±ε（但し、ε＜＜２ｕ）の形の整数を用いてもよい。この場合、ｐｉ，ｑｊでの除算計算量を低減でき、演算を高速に実行することができる。
【００８２】
（第２の実施形態）
図３は本発明の第２の実施形態に係る剰余乗算演算装置の構成を示す模式図であり、図４はこの剰余演算装置の動作を説明するためのフローチャートであって、図１及び図２と同一部分には同一符号を付し、変形部分には右肩側に記号（’）を付して重複した説明を省略し、ここでは異なる部分について主に述べる。なお、以下の各実施形態も同様にして重複した説明を省略する。
【００８３】
すなわち、本実施形態は、第１の実施形態の変形例であり、平方乗算に代えて、剰余乗算ｘｕ ｍｏｄ ｎを高速に演算処理するものである。
【００８４】
具体的には、この剰余乗算演算装置１０’は、平方入出力管理部１１及び平方演算部１２に代えて、乗算入出力管理部１１’及び剰余乗算演算部１２’を備えている。
【００８５】
ここで、乗算入出力管理部１１’は、平方入出力管理部１１と同様の管理機能を有するものであるが、特に、図２に代えて図４のフローチャートに基づいて、剰余乗算演算部１２’を制御する機能と、最終的なｚｕ ｍｏｄ ｎの演算結果を出力する機能とを有している。
【００８６】
剰余乗算演算部１２’は、平方演算部１２と同様に、剰余入出力管理部１１’に制御されて演算を行う機能と、演算結果を乗算入出力管理部１１’へ送信する機能とをもっている。
【００８７】
次に、以上のように構成された剰余乗算演算装置における剰余乗算 ｘｕ ｍｏｄ ｎの算出動作を図４のフローチャートを用いて説明する。
【００８８】
始めに、剰余乗算演算装置１０’においては、外部から演算対象ｘ（０≦ｘ＜ｎ）及びｕ（０≦ｕ＜ｎ）と、各パラメータｎ、ｎ＋ａ、ｎ＋ｂ、ａ、ｂ、ｂ−ａ、ｐｉ（ｉ＝１、…、ｈ）及びｑｊ（ｊ＝１、…、ｍ）とが入力データとして乗算入出力管理部１１’に入力される（ＳＴ１’）。
【００８９】
ここで、例えばａ及びｂを入力すれば、各パラメータｎ＋ａ、ｎ＋ｂ、ｂ−ａ、ｐｉ（ｉ＝１、…、ｈ）及びｑｊ（ｊ＝１、…、ｍ）が計算可能なので、全てを入力データとする必要はない。また、これら以外のデータを入力してもよい。
【００９０】
乗算入出力管理部１１’は、これら入力データを受けると、剰余乗算演算部１２’を制御して次式のように、ｘを（ｂ−ａ）で割った商ｙと剰余ε、及びｕを（ｂ−ａ）で割った商μと剰余σを求める（ＳＴ２’）。
【００９１】
ｘ＝（ｂ−ａ）ｙ＋ε
ｕ＝（ｂ−ａ）μ＋σ
このとき、ｘｕは以下の式で表すことができる。
【００９２】
ｘｕ＝（ｂ−ａ）｛（ｂ−ａ）ｙμ＋εμ＋σｙ｝＋εσ
ここで、中括弧｛｝の中身をｓとおく。
【００９３】
ｓ＝（ｂ−ａ）ｙμ＋εμ＋σｙ
なお、ｘｕ＝（ｂ−ａ）ｓ＋εσとなる。
【００９４】
本実施形態では、上の式のｙ，μを剰余系表現ｙｉ，ｙｊ’，μｉ，μｊ’に変換すると共にｓを剰余系表現ｓｉ，ｓｊ’に変換し、各ｓｉ，ｓｊ’から中国人剰余定理を用いて２進数表現ｘａ，ｘｂを高速に算出し、得られたｘａ，ｘｂから定理の式（２），（３）により（ｂ−ａ）ｓを求め、最終的にεμを考慮して、ｘｕ ｍｏｄ ｎを求めてゆく。
【００９５】
まず、ｓを構成する商ｙ，μを剰余系表現に変換する。
【００９６】
すなわち、乗算入出力管理部１１’は、剰余乗算演算部１２’を制御して次式のように、商ｙ，μを剰余系表現ｙｉ，μｉに変換する（ＳＴ３’）。
【００９７】
ｙｉ＝ｙ ｍｏｄ ｐｉ（ｉ＝１、…、ｈ）
μｉ＝μ ｍｏｄ ｐｉ（ｉ＝１、…、ｈ）
次に、乗算入出力管理部１１’は、得られたｙｉ，μｉを用い、剰余乗算演算部１２’の制御により、次式のように、中間値ｓを剰余系表現ｓｉに変換する（ＳＴ４’）。
【００９８】
ｓｉ＝（ｂ−ａ）ｙｉμｉ ＋εμｉ ＋σｙｉ ｍｏｄ ｐｉ（ｉ＝１、…、ｈ）
乗算入出力管理部１１’は、得られたｓｉを用い、剰余乗算演算部１２’の制御により、中国人剰余定理を用いて、剰余系表現ｓｉを２進数表現ｘａに戻す（ＳＴ５）。
【００９９】
ｘａ＝ｓｉ  ｍｏｄ  （ｎ＋ａ）
同様の手順で、乗算入出力管理部１１’は、剰余乗算演算部１２’を制御し、ｑｊ（ｊ＝１、…、ｍ）を用いて、ｘｂ＝ｓｊ  ｍｏｄ  （ｎ＋ｂ）を求める（ＳＴ６’〜ＳＴ８）。
【０１００】
以下、乗算入出力管理部１１’は、前述同様に、ステップＳＴ９〜ＳＴ１１を実行し、ｓｎ’＝ｓｎ＋ε２を求める（ＳＴ１１）。
【０１０１】
最後に、乗算入出力管理部１１’は、得られたｓｎ’を法ｎと比較し、ｓｎ’≧ｎならばｓｎ’−ｎを剰余乗算ｘｕ ｍｏｄ ｎ  の演算結果として出力し（ＳＴ１２−１）、ｓｎ’＜ｎならばｓｎ’を同演算結果として出力する（ＳＴ１２−２）。
【０１０２】
上述したように本実施形態によれば、剰余乗算ｘｕ ｍｏｄ ｎ に関しても、第１の実施形態と同様の効果を得ることができる。
【０１０３】
（第３の実施形態）
図５は本発明の第３の実施形態に係る並列演算装置の構成を示す模式図であり、図６はこの並列演算装置の動作を説明するためのフローチャートである。
【０１０４】
すなわち、本実施形態は、第１の実施形態の変形例であり、平方乗算ｘ２ ｍｏｄ ｎの並列演算処理を図るものであって、具体的には、前述同様の入出力管理部１１”と、この入出力管理部１１”に制御されるｗ個の演算部１２１”〜１２ｗ”とを備えている。
【０１０５】
ここで、入出力管理部１１”は、平方入出力管理部１１と同様の管理機能を有するものであるが、特に、図２に代えて図６のフローチャートに基づいて、各演算部１２１”〜１２ｗ”を制御する機能を有している。
【０１０６】
各演算部１２１”〜１２ｗ”は、平方演算部１２と同様に、入出力管理部１１”に制御されて演算を行う機能と、演算結果を入出力管理部１１”へ送信する機能とをもっている。
【０１０７】
従って、以上のような構成により、第１の実施形態の効果に加え、演算部１２１”〜１２ｗ”の個数ｗが因数の合計個数ｈ＋ｍ以上の場合（ｗ≧ｈ＋ｍ）は、図６に示すように、ステップＳＴ３１…ｈ〜ＳＴ５の演算と、ステップＳＴ６１…ｍ〜ＳＴ８の演算とを並列に実行し、演算の高速化を実現することができる。
【０１０８】
また、演算部１２１”〜１２ｗ”の個数ｗが少ない場合（ｗ＜ｈ＋ｍ）でも、並列演算できる部分を各演算部１２１”〜１２ｗ”で並列に実行することにより、やはり高速化を実現することができる。
【０１０９】
また、他の演算でも、並列演算によって演算効率を向上可能な部分は、適宜、各演算部１２１”〜１２ｗ”により演算してもよい。これは、剰余演算においても同様である。
【０１１０】
また、本実施の形態の並列演算装置１０”は、１台の装置である必要はなく、例えばネットワークを介して複数の計算機が利用可能な環境のように、演算を並列に行える環境にも適用することができる。
【０１１１】
（第４の実施形態）
次に、本発明の第４の実施形態に係る並列演算装置について図５を参照しながら図７のフローチャートを用いて説明する。
すなわち、本実施形態は、第２及び第３の実施形態の組合せ例であり、平方乗算に代えて、剰余乗算ｘｕ ｍｏｄ ｎを並列に演算処理するものであって、具体的には図６に代えて図７のフローチャートに基づき、入出力管理部１１”がｗ個の演算部１２１”〜１２ｗ”を制御する構成となっている。
【０１１２】
従って、以上のような構成によれば、第２及び第３の実施形態の効果に加え、演算部１２１”〜１２ｗ”の個数ｗが多い場合（ｗ≧２ｈ＋２ｍ）には、図７に示すように、ステップＳＴ３’１…ｈ〜ＳＴ５の演算と、ステップＳＴ６’１…ｍ〜ＳＴ８の演算とを並列に実行し、演算の高速化を実現することができる。
【０１１３】
また、演算部１２１”〜１２ｗ”の個数ｗが少ない場合（ｗ＜２ｈ＋２ｍ）でも、独立計算できる部分を各演算部１２１”〜１２ｗ”で並列に実行することにより、やはり高速化を実現することができる。
【０１１４】
また、本実施形態では、例えばｘ及びｕを（ｂ−ａ）で割った商と余りを求める部分のように、並列演算によって演算効率を向上可能な部分は、適宜、各演算部１２１”〜１２ｗ”により演算してもよい。
【０１１５】
（第５の実施形態）
次に、本発明の第５の実施形態に係る演算装置について図１、図３又は図５を参照しながら説明する。
【０１１６】
すなわち、本実施形態は、第１〜第４の実施形態の変形例であり、パラメータの設定に関し、より一層の容易化を図るものである。
【０１１７】
具体的には、法ｎを固定する場合、各入出力管理部１１’〜１１”は、前述した機能に加え、法ｎが入力されると、前述した２つの法ｎ＋ａ，ｎ＋ｂを算出する機能をもつものとなっている。
【０１１８】
なお、これに限らず、法ｎ＋ａ，ｎ＋ｂを固定する場合、各入出力管理部１１’〜１１”は、前述した機能に加え、法ｎ＋ａ，ｎ＋ｂが入力されると、これに近い整数としてｎ（従って、ａ，ｂ）を算出する機能をもつものとなっている。
【０１１９】
以上のような構成により、第１〜第４の実施形態の効果に加え、パラメータの設定をより一層容易にすることができる。
【０１２０】
なお、上記第１及び第２実施形態では、平方剰余演算装置１０と、剰余乗算演算装置１０’とを別の装置として説明したが、これに限らず、１台の装置が平方剰余演算機能及び剰余乗算機能の両方を備えてもよい。これは、第３及び第４の実施形態における並列演算装置１０”も同様である。
【０１２１】
また、上記各実施形態では、整数ｘに関する剰余演算の例として、平方剰余算ｘ（superscript:2） ｍｏｄ ｎ又は剰余乗算ｘｕ ｍｏｄ ｎについて説明したが、これに限らず、他の任意の剰余演算（例えば乗法逆元ｘ（superscript:-1）ｍｏｄ ｎの算出）についても、本発明を同様に実施して同様の効果を得ることができる。
また、本手法の応用として、楕円曲線暗号で用いられる楕円曲線上の点のスカラー倍演算への適用も可能である。この場合は更に、点の座標を逆元計算の不要な射影座標に変換することによって平方剰余算と剰余乗算と加減算のみでスカラー倍演算を構成する方法が効果的である。
また、上記各実施形態に記載した手法は、コンピュータに実行させることのできるプログラムとして、磁気ディスク（フロッピー（登録商標）ディスク、ハードディスクなど）、光ディスク（ＣＤ−ＲＯＭ、ＤＶＤなど）、光磁気ディスク（ＭＯ）、半導体メモリなどの記憶媒体に格納して頒布することもできる。
【０１２２】
また、この記憶媒体としては、プログラムを記憶でき、かつコンピュータが読み取り可能な記憶媒体であれば、その記憶形式は何れの形態であっても良い。
【０１２３】
また、記憶媒体からコンピュータにインストールされたプログラムの指示に基づきコンピュータ上で稼働しているＯＳ（オペレーティングシステム）や、データベース管理ソフト、ネットワークソフト等のＭＷ（ミドルウェア）等が本実施形態を実現するための各処理の一部を実行しても良い。
【０１２４】
さらに、本発明における記憶媒体は、コンピュータと独立した媒体に限らず、ＬＡＮやインターネット等により伝送されたプログラムをダウンロードして記憶または一時記憶した記憶媒体も含まれる。
【０１２５】
また、記憶媒体は１つに限らず、複数の媒体から本実施形態における処理が実行される場合も本発明における記憶媒体に含まれ、媒体構成は何れの構成であっても良い。
【０１２６】
尚、本発明におけるコンピュータは、記憶媒体に記憶されたプログラムに基づき、本実施形態における各処理を実行するものであって、パソコン等の１つからなる装置、複数の装置がネットワーク接続されたシステム等の何れの構成であっても良い。
【０１２７】
また、本発明におけるコンピュータとは、パソコンに限らず、情報処理機器に含まれる演算処理装置、マイコン等も含み、プログラムによって本発明の機能を実現することが可能な機器、装置を総称している。
【０１２８】
なお、本願発明は、上記各実施形態に限定されるものでなく、実施段階ではその要旨を逸脱しない範囲で種々に変形することが可能である。また、各実施形態は可能な限り適宜組み合わせて実施してもよく、その場合、組み合わされた効果が得られる。さらに、上記各実施形態には種々の段階の発明が含まれており、開示される複数の構成用件における適宜な組み合わせにより種々の発明が抽出され得る。例えば実施形態に示される全構成要件から幾つかの構成要件が省略されることで発明が抽出された場合には、その抽出された発明を実施する場合には省略部分が周知慣用技術で適宜補われるものである。
【０１２９】
その他、本発明はその要旨を逸脱しない範囲で種々変形して実施できる。
【０１３０】
【発明の効果】
以上説明したように本発明によれば、本来の法とは別の２つの法を補助的に用いる剰余演算に関し、別の２つの法を容易に設定でき、実用性を向上できる。
【図面の簡単な説明】
【図１】本発明の第１の実施形態に係る平方剰余演算装置の構成を示す模式図。
【図２】同実施形態における動作を説明するためのフローチャート。
【図３】本発明の第２の実施形態に係る剰余乗算演算装置の構成を示す模式図。
【図４】同実施形態における動作を説明するためのフローチャート。
【図５】本発明の第３の実施形態に係る並列演算装置の構成を示す模式図。
【図６】同実施形態における動作を説明するためのフローチャート。
【図７】本発明の第４の実施形態における動作を説明するためのフローチャート。
【符号の説明】
１０…平方剰余演算装置
１１…平方入出力管理部
１２…平方演算部
１０’…剰余乗算演算装置
１１’…乗算入出力管理部
１２’…剰余乗算演算部
１０”…並列演算装置
１１”…入出力管理部
１２１”〜１２ｗ”…演算部
【図１】
0004068352.tif 000009
【図２】
0004068352.tif 000010
【図３】
0004068352.tif 000011
【図４】
0004068352.tif 000012
【図５】
0004068352.tif 000013
【図６】
0004068352.tif 000014
【図７】
0004068352.tif 000015