(57)【特許請求の範囲】
【請求項１】
第１のデータ信号ｙを第２のデータ信号ｘとともに処理するマルチプレシジョン整数演算用の装置であって、
「ｎ」を複数の大整数ユニット内の大整数ユニットの総数とする複数の大整数ユニット（ＬＩＵ）、ＬＩＵ｛０｝、ＬＩＵ｛１｝、ＬＩＵ｛２｝、．．．、ＬＩＵ｛ｎ−１｝であって、各大整数ユニットが、
第１の乗算器入力、第２の乗算器入力、上位部分積出力、および下位部
分積出力を有する乗算器と、
第１の加算器入力、第２の加算器入力、第３の加算器入力、第４の加算
器入力、および加算器出力を有し、前記第３の加算器入力が下位部分積出
力を受け取るように乗算器に結合された加算器と、
ＬＩＵレジスタ入力およびＬＩＵレジスタ出力を有するＬＩＵレジスタ
であって、前記ＬＩＵレジスタ入力は加算器出力を受け取るように加算器
に結合され、前記ＬＩＵレジスタはクロックパルスの前に加算器出力の値
をラッチしてクロックパルスの後にその値を前記ＬＩＵレジスタ出力に転
送し、前記ＬＩＵレジスタ出力はＬＩＵレジスタ上位出力とＬＩＵレジス
タ下位出力に分割され、前記ＬＩＵレジスタ上位出力は前記ＬＩＵレジス
タ出力の上位２ビットを含み、前記ＬＩＵレジスタ下位出力は前記ＬＩＵ
レジスタ上位出力のビット以外の前記ＬＩＵレジスタ出力の全ビットを含
み、前記ＬＩＵレジスタ上位出力は第４の加算器入力に結合され、前記Ｌ
ＩＵレジスタはさらにＬＩＵレジスタクリア入力がアクティブとされたと
きに前記ＬＩＵレジスタ出力を０にクリアするための前記ＬＩＵレジスタ
クリア入力を有するＬＩＵレジスタと、
ＬＩＵレジスタ出力とキャリーイン信号ｃｉを受け取るためＬＩＵレジ
スタに結合された第１の論理ＯＲゲートであって、前記第１の論理ＯＲゲ
ートはキャリーアウト信号ｃｏを発生し、前記キャリーアウト信号ｃｏは
アクティブとされているＬＩＵレジスタ出力の任意の１ビットに応答して
アクティブとされ、前記キャリーイン信号ｃｉはアクティブとされる第１
の論理ＯＲゲートと、
ＬＩＵレジスタ上位出力を受け取り、補助キャリーアウト信号ｃａを発
生するためＬＩＵレジスタに結合された第２の論理ＯＲゲートであって、
前記補助キャリーアウト信号ｃａはＬＩＵレジスタ上位出力のいずれかの
ビットがアクティブのときにアクティブとされる第２の論理ＯＲゲートとを有する複数の大整数ユニットを備え、
前記複数の大整数ユニットのそれぞれの大整数ユニットの第１の乗算器入力に第１のデータ信号ｙが印加されており、
複数の要素ｘ｛０｝、ｘ｛１｝、ｘ｛２｝、．．．、ｘ｛ｎ−１｝を持つ第２のデータ信号ｘが、各要素を前記複数の大整数ユニットの各大整数ユニットの第２の乗算器入力に結合されており、
０よりも大きいｉに対し、前記複数の大整数ユニットの各ｉ番目の大整数ユニットＬＩＵ｛ｉ｝は、｛ｉ−１｝番目の大整数ユニットＬＩＵ｛ｉ−１｝の上位部分積出力に結合された第１の加算器入力を持ち、
０よりも大きいｉに対し、各ｉ番目の大整数ユニットＬＩＵ｛ｉ｝は、｛ｉ−１｝番目の大整数ユニットＬＩＵ｛ｉ−１｝の第２の加算器入力に結合されたＬＩＵレジスタ下位出力を持ち、
減算信号がアクティブのときに第３のデータ信号ｚの補数をとるための、第１の大整数ユニットＬＩＵ｛０｝の第１の加算器入力に結合された第１の相補ゲートと、
第１の大整数ユニットＬＩＵ｛０｝のＬＩＵレジスタ下位出力に結合され、前記減算信号がアクティブのときに前記ＬＩＵレジスタ下位出力の補数をとるための、第４のデータ信号ａを発生する第２の相補ゲートと、
ラッチレジスタ入力とラッチレジスタ出力を有するラッチレジスタであって、前記ラッチレジスタ入力は前記ｎ番目の大整数ユニットＬＩＵ｛ｎ−１｝の上位部分積出力に結合され、前記ラッチレジスタ出力は、クロックパルスの前にｎ番目の上位部分積の値をラッチし、クロックパルスの後にｎ番目の上位部分積の値を前記ｎ番目の大整数ユニットの第２の加算器入力に供給するための前記ｎ番目の大整数ユニットＬＩＵ｛ｎ−１｝の第２の加算器入力に結合されたラッチレジスタとを備え、
前記第１の大整数ユニットＬＩＵ｛０｝は論理０の値に結合されたｃｉ入力を持ち、
前記第２の大整数ユニットＬＩＵ｛１｝は第１の大整数ユニットＬＩＵ｛０｝のｃａ出力に結合されたｃｉ入力を持ち、
１よりも大きいｉに対し、前記複数の大整数ユニットのそれぞれのｉ番目の大整数ユニットＬＩＵ｛ｉ｝は｛ｉ−１｝番目の大整数ユニットＬＩＵ｛ｉ−１｝のｃｏ出力に結合されたｃｉ入力を持ち、ｎ番目の大整数ユニットＬＩＵ｛ｎ−１｝のｃｏ出力は第５のデータ信号、キャリーフロー信号ｃｙであり、
前記ラッチレジスタはラッチレジスタクリア信号を持ち、また各ＬＩＵはＬＩＵレジスタクリア入力を持ち、複数のＬＩＵレジスタクリア入力と前記ラッチレジスタクリア信号が一緒に結合されてデータ信号ｃｌｒを形成し、
前記ラッチレジスタはクロック入力を持ち、また各ＬＩＵはクロック入力を持ち、複数のクロック入力が一緒に結合されてクロック信号ｃｌｋを形成することを特徴とする装置。
【請求項２】
第１のデータ信号ｙを第２のデータ信号ｘとともに処理するマルチプレシジョン整数演算用の装置であって、
「ｎ」を複数の大整数ユニット内の大整数ユニットの総数とする複数の大整数ユニット（ＬＩＵ）、ＬＩＵ｛０｝、ＬＩＵ｛１｝、ＬＩＵ｛２｝、．．．、ＬＩＵ｛ｎ−１｝であって、各大整数ユニットが、
第１の乗算器入力、第２の乗算器入力、上位部分積出力、および下位部
分積出力を有する乗算器と、
第１の加算器入力および第２の加算器入力を有し、下位部分積出力を受
け取るため乗算器に結合された加算器と、
総和信号出力を持っており、前記加算器と結合された前記ＬＩＵレジス
タと
を有する複数の大整数ユニットを備え、
前記複数の大整数ユニットのそれぞれの大整数ユニットの第１の乗算器入力に第１のデータ信号ｙが印加されており、
複数の要素ｘ｛０｝、ｘ｛１｝、ｘ｛２｝、．．．、ｘ｛ｎ−１｝を持つ第２のデータ信号ｘが、各要素を前記複数の大整数ユニットの各大整数ユニットの第２の乗算器入力に結合されており、
０よりも大きいｉに対し、前記複数の大整数ユニットの各ｉ番目の大整数ユニットＬＩＵ｛ｉ｝は、｛ｉ−１｝番目の大整数ユニットＬＩＵ｛ｉ−１｝の上位部分積出力に結合された第１の加算器入力を持ち、
０よりも大きいｉに対し、各ｉ番目の大整数ユニットＬＩＵ｛ｉ｝は、｛ｉ−１｝番目の大整数ユニットＬＩＵ｛ｉ−１｝の第２の加算器入力に結合された総和信号出力を持ち、
減算信号がアクティブのときに第３のデータ信号ｚの補数をとるための、第１の大整数ユニットＬＩＵ｛０｝の第１の加算器入力に結合された相補ゲートと、
前記ｎ番目の大整数ユニットＬＩＵ｛ｎ−１｝の上位部分積出力と前記ｎ番目の大整数ユニットＬＩＵ｛ｎ−１｝の第２の加算器入力とに結合され、クロックパルスの前にｎ番目の上位部分積の値をラッチし、クロックパルスの後にｎ番目の上位部分積の値を前記ｎ番目の大整数ユニットの第２の加算器入力に供給するためのラッチレジスタと
を備えることを特徴とする装置。
【請求項３】
第１のデータ信号ｙを第２のデータ信号ｘとともに処理するマルチプレシジョン整数演算用の装置であって、
コンローラと、該コンローラに結合されて該コンローラから第１のデータ信号ｙおよび第２のデータ信号ｘを受け取るように構成された大整数ユニット（ＬＩＵ）とを備えており、
該ＬＩＵが、
第１の乗算器入力、第２の乗算器入力、上位部分積出力、および下位部分積出力を有する乗算器と、
第１の加算器入力および第２の加算器入力を有し、前記下位部分積出力を受け取るため前記乗算器に結合され、第１の総和信号を出力する加算器と、
前記加算器に結合され、第１の総和信号を受け取り、第２の総和信号を出力するＬＩＵレジスタと、
第１の乗算器入力に印加される第１のデータ信号ｙと、
第２の乗算器入力に印加される第２のデータ信号ｘの複数の要素と、
第１の加算器入力に結合され、減算信号がアクティブのときに第３のデータ信号ｚの補数をとる相補ゲートと、
前記上位部分積出力と第２の加算器入力とに結合され、クロックパルスの前に上位部分積の値をラッチし、該クロックパルスの後に該上位部分積の値を第２の加算器入力に供給するラッチレジスタと
を備えることを特徴とするマルチプレシジョン整数演算用の装置。
【請求項４】
前記大整数ユニットがさらに、
前記ＬＩＵレジスタの出力に結合されて前記ＬＩＵレジスタからキャリー信号として第２の総和信号の上位ビットを受け取るＯＲゲートであって、キャリー信号の論理ＯＲをキャリーフロー信号として出力する第２のＯＲゲートを備えることを特徴とする請求項３に記載の装置。
【請求項５】
さらに、
「ｎ」を複数の大整数ユニット内の大整数ユニットの総数とする複数の大整数ユニットＬＩＵ｛０｝、ＬＩＵ｛１｝、ＬＩＵ｛２｝、．．．、ＬＩＵ｛ｎ−１｝を備え、
０よりも大きいｉに対し、前記複数の大整数ユニットの各ｉ番目の大整数ユニットＬＩＵ｛ｉ｝は、｛ｉ−１｝番目の大整数ユニットＬＩＵ｛ｉ−１｝の上位部分積出力に結合された第１の加算器入力を持ち、
０よりも大きいｉに対し、各ｉ番目の大整数ユニットＬＩＵ｛ｉ｝は、｛ｉ−１｝番目の大整数ユニットＬＩＵ｛ｉ−１｝の第２の加算器入力に結合された総和信号出力を持っていることを特徴とする請求項３または４に記載の装置。
【請求項６】
第１のデータ信号ｘを第２のデータ信号ｙとともに処理するマルチプレシジョン整数演算用の装置であって、
コンローラと、該コンローラに結合されて該コンローラから第１のデータ信号ｙおよび第２のデータ信号ｘを受け取るように構成された複数の大整数ユニット（ＬＩＵ）とを備えており、
前記複数の大整数ユニットのそれぞれの大整数ユニットが第１の乗算器入力、第２の乗算器入力、上位部分積出力、第１の加算器入力、第２の加算器入力、および総和信号出力を有しており、
前記複数の大整数ユニットのそれぞれの大整数ユニットの第１の乗算器入力に第１のデータ信号ｙが印加され、
複数の要素を持つ第２のデータ信号ｘの各要素が、前記複数の大整数ユニットのそれぞれの大整数ユニットの第２の乗算器入力に結合されており、
初期の大整数ユニット以外のｉに対し、前記複数の大整数ユニットの各ｉ番目の大整数ユニットＬＩＵ｛ｉ｝は、｛ｉ−１｝番目の大整数ユニットＬＩＵ｛ｉ−１｝の前記上位部分積出力に結合された第１の加算器入力を持ち、
前記初期の大整数ユニット以外のｉに対し、前記複数の大整数ユニットの各ｉ番目の大整数ユニットＬＩＵ｛ｉ｝は、｛ｉ−１｝番目の大整数ユニットＬＩＵ｛ｉ−１｝の第２の加算器入力に結合された前記総和信号出力を持つ
ことを特徴とするマルチプレシジョン整数演算用の装置。
【請求項７】
さらに、
減算信号がアクティブのときに第３のデータ信号ｚの補数をとるための、第１の大整数ユニットＬＩＵ｛０｝の第１の加算器入力に結合された相補ゲートと、
「ｎ」を大整数ユニットの総数としたとき、前記ｎ番目の大整数ユニットＬＩＵ｛ｎ−１｝の上位部分積出力と前記ｎ番目の大整数ユニットＬＩＵ｛ｎ−１｝の第２の加算器入力とに結合され、クロックパルスの前にｎ番目の上位部分積出力の値をラッチし、クロックパルスの後にｎ番目の上位部分積出力の値を前記ｎ番目の大整数ユニットの第２の加算器入力に供給するためのラッチレジスタと
を備えることを特徴とする請求項６に記載のマルチプレシジョン整数演算用の装置。
【請求項８】
さらに、減算信号がアクティブのときに第３のデータ信号ｚの補数をとるための、第１の大整数ユニットＬＩＵ｛０｝の第１の加算器入力に結合された相補ゲートを備えることを特徴とする請求項６に記載のマルチプレシジョン整数演算用の装置。
【請求項９】
さらに、「ｎ」を複数の大整数ユニット内の大整数ユニットの総数としたとき、前記ｎ番目の大整数ユニットＬＩＵ｛ｎ−１｝の上位部分積出力と前記ｎ番目の大整数ユニットＬＩＵ｛ｎ−１｝の第２の加算器入力とに結合され、クロックパルスの前にｎ番目の上位部分積出力の値をラッチし、クロックパルスの後にｎ番目の上位部分積出力の値を前記ｎ番目の大整数ユニットの第２の加算器入力に供給するためのラッチレジスタを備えることを特徴とする請求項６または８に記載のマルチプレシジョン整数演算用の装置。
【請求項１０】
さらに、
減算信号がアクティブのときに第３のデータ信号ｚの補数をとるための、第１の大整数ユニットＬＩＵ｛０｝の第１の加算器入力に結合されたゲート手段と、
「ｎ」を複数の大整数ユニット内の大整数ユニットの総数としたとき、ｎ番目の大整数ユニットＬＩＵ｛ｎ−１｝の上位部分積出力と前記ｎ番目の大整数ユニットＬＩＵ｛ｎ−１｝の第２の加算器入力とに結合され、クロックパルスの前にｎ番目の上位部分積の値をラッチし、クロックパルスの後にｎ番目の上位部分積の値を前記ｎ番目の大整数ユニットの第２の加算器入力に供給するためのレジスタ手段と
を備えることを特徴とする請求項６に記載のマルチプレシジョン整数演算用の装置。
【請求項１１】
さらに、減算信号がアクティブのときに第３のデータ信号ｚの補数をとるための、第１の大整数ユニットＬＩＵ｛０｝の第１の加算器入力に結合されたゲート手段を備えることを特徴とする請求項６に記載のマルチプレシジョン整数演算用の装置。
【請求項１２】
さらに、「ｎ」を複数の大整数ユニット内の大整数ユニットの総数としたとき、ｎ番目の大整数ユニットＬＩＵ｛ｎ−１｝の上位部分積出力と前記ｎ番目の大整数ユニットＬＩＵ｛ｎ−１｝の第２の加算器入力とに結合され、クロックパルスの前にｎ番目の上位部分積の値をラッチし、クロックパルスの後にｎ番目の上位部分積の値を前記ｎ番目の大整数ユニットの第２の加算器入力に供給するためのレジスタ手段を備えることを特徴とする請求項６または１１に記載のマルチプレシジョン整数演算用の装置。
【請求項１３】
さらに、
第１の大整数ユニットＬＩＵ｛０｝の総和信号出力に結合されて、出力信号を出力する出力ゲートを備えることを特徴とする請求項２に記載のマルチプレシジョン整数演算用の装置。
【請求項１４】
さらに、
前記大整数ユニットの総和信号出力に結合されて、出力信号を出力する出力ゲートを備えることを特徴とする請求項３に記載のマルチプレシジョン整数演算用の装置。
【請求項１５】
第１のデータ信号ｘを第２のデータ信号ｙとともに処理するマルチプレシジョン整数演算用の装置であって、
コンローラと、ｎ個（ｎ＞１）の大整数ユニット（ＬＩＵ）を持った大整数ユニット（ＬＩＵ）アレイとを備えており、
該ＬＩＵのそれぞれが、該コンローラに結合されて該コンローラから第１のデータ信号ｙおよび第２のデータ信号ｘを受け取るように構成されており、
該ＬＩＵが、
第１の乗算器入力、第２の乗算器入力、上位部分積出力、および下位部分積出力を有する乗算器と、
第１の加算器入力および第２の加算器入力を有し、前記乗算器に結合されて前記下位部分積出力を受け取り、第１の総和信号を出力する加算器と、
前記加算器に結合され、第１の総和信号を受け取り、第２の総和信号を出力するＬＩＵレジスタと、
前記ＬＩＵレジスタの出力に結合されて前記ＬＩＵレジスタからキャリー信号として第２の総和信号の上位ビットを受け取るＯＲゲートであって、前記キャリー信号の論理ＯＲをキャリーフロー信号として出力するＯＲゲートとを備えており、
第１の乗算器入力に第１のデータ信号ｙが印加され、第２の乗算器入力に複数の要素を持った第２のデータ信号ｘが印加される
ことを特徴とするマルチプレシジョン整数演算用の装置。
【請求項１６】
さらに、
前記大整数ユニットの第１の加算器入力に結合され、減算信号がアクティブのときに第３のデータ信号ｚの補数をとる相補ゲートと、
前記大整数ユニットの上位部分積出力と前記大整数ユニットの第２の加算器入力とに結合され、クロックパルスの前に上位部分積出力の値をラッチし、クロックパルスの後に上位部分積出力の値を前記大整数ユニットの第２の加算器入力に供給するラッチレジスタと
を備えることを特徴とする請求項１５に記載のマルチプレシジョン整数演算用の装置。
【請求項１７】
さらに、前記大整数ユニットの第１の加算器入力に結合され、減算信号がアクティブのときに第３のデータ信号ｚの補数をとる相補ゲートを備えることを特徴とする請求項１５に記載のマルチプレシジョン整数演算用の装置。
【請求項１８】
さらに、前記大整数ユニットの上位部分積出力と前記大整数ユニットの第２の加算器入力とに結合され、クロックパルスの前に上位部分積出力の値をラッチし、クロックパルスの後に上位部分積出力の値を前記大整数ユニットの第２の加算器入力に供給するラッチレジスタを備えることを特徴とする請求項１５または１７に記載のマルチプレシジョン整数演算用の装置。
【請求項１９】
第１のデータ信号ｙを第２のデータ信号ｘとともに処理するマルチプレシジョン整数演算用の装置であって、
「ｎ」を複数の大整数ユニット内の大整数ユニットの総数とする複数の大整数ユニット（ＬＩＵ）、ＬＩＵ｛０｝、ＬＩＵ｛１｝、ＬＩＵ｛２｝、．．．、ＬＩＵ｛ｎ−１｝であって、各大整数ユニットが、
第１の乗算器入力、第２の乗算器入力、上位部分積出力、および下位部
分積出力を有する乗算器と、
第１の加算器入力、第２の加算器入力、第３の加算器入力、第４の加算
器入力、および加算器出力を有し、前記第３の加算器入力が下位部分積出
力を受け取るように乗算器に結合された加算器と、
ＬＩＵレジスタ入力およびＬＩＵレジスタ出力を有するＬＩＵレジスタ
であって、前記ＬＩＵレジスタ入力は加算器出力を受け取るように加算器
に結合され、前記第１のＬＩＵレジスタはクロックパルスの前に加算器出
力の値をラッチしてクロックパルスの後にその値を前記ＬＩＵレジスタ出
力に転送し、前記ＬＩＵレジスタ出力はＬＩＵレジスタ上位出力とＬＩＵ
レジスタ下位出力に分割され、前記ＬＩＵレジスタ上位出力は前記ＬＩＵ
レジスタ出力の上位２ビットを含み、前記ＬＩＵレジスタ下位出力は前記
ＬＩＵレジスタ上位出力のビット以外の前記ＬＩＵレジスタ出力の全ビッ
トを含み、前記ＬＩＵレジスタ上位出力は第４の加算器入力に結合され、
前記第１のＬＩＵレジスタはさらにＬＩＵレジスタクリア入力がアクティ
ブとされたときに前記ＬＩＵレジスタ出力を０にクリアするための前記Ｌ
ＩＵレジスタクリア入力を有する第１のＬＩＵレジスタと、
乗算器の上位部分積出力を受け取るための第２のＬＩＵレジスタと、
ＬＩＵレジスタ出力とキャリーイン信号ｃｉを受け取るため第１のＬＩ
Ｕレジスタに結合された第１の論理ＯＲゲートであって、前記第１の論理
ＯＲゲートはキャリーアウト信号ｃｏを発生し、前記キャリーアウト信号
ｃｏはアクティブとされているＬＩＵレジスタ出力の任意の１ビットに応
答してアクティブとされ、前記キャリーイン信号ｃｉはアクティブとされ
る第１の論理ＯＲゲートと、
ＬＩＵレジスタ上位出力を受け取り、補助キャリーアウト信号ｃａを発
生するため第１のＬＩＵレジスタに結合された第２の論理ＯＲゲートであ
って、前記補助キャリーアウト信号ｃａはＬＩＵレジスタ上位出力のいず
れかのビットがアクティブのときにアクティブとされる第２の論理ＯＲゲ
ートと
を有する複数の大整数ユニットを備え、
前記複数の大整数ユニットのそれぞれの大整数ユニットの第１の乗算器入力に第１のデータ信号ｙが印加されており、
複数の要素ｘ｛０｝、ｘ｛１｝、ｘ｛２｝、．．．、ｘ｛ｎ−１｝を持つ第２のデータ信号ｘが、各要素を前記複数の大整数ユニットの各大整数ユニットの第２の乗算器入力に結合されており、
前記複数の大整数ユニットの各ｉ番目の大整数ユニットＬＩＵ｛ｉ｝は、各ｉ番目の大整数ユニットＬＩＵ｛ｉ｝の上位部分積出力に結合された第１の加算器入力を持ち、
０よりも大きいｉに対し、各ｉ番目の大整数ユニットＬＩＵ｛ｉ｝は、｛ｉ−１｝番目の大整数ユニットＬＩＵ｛ｉ−１｝の第２の加算器入力に結合されたＬＩＵレジスタ下位出力を持ち、
第１の大整数ユニットＬＩＵ｛０｝の第１の加算器入力に結合され、減算信号がアクティブのときに第３のデータ信号ｚの補数をとるための第１の相補ゲートと、
第１の大整数ユニットＬＩＵ｛０｝のＬＩＵレジスタ下位出力に結合され、前記減算信号がアクティブのときに前記ＬＩＵレジスタ下位出力の補数をとるための、第４のデータ信号ａを発生する第２の相補ゲートとを備え、
前記第１の大整数ユニットＬＩＵ｛０｝は論理０の値に結合されたｃｉ入力を持ち、
前記第２の大整数ユニットＬＩＵ｛１｝は第１の大整数ユニットＬＩＵ｛０｝のｃａ出力に結合されたｃｉ入力を持ち、
前記ｎ番目の大整数ユニットＬＩＵ｛ｎ−１｝は論理０の値に結合された第２の加算器入力を持ち、
１よりも大きいｉに対し、前記複数の大整数ユニットのそれぞれのｉ番目の大整数ユニットＬＩＵ｛ｉ｝は｛ｉ−１｝番目の大整数ユニットＬＩＵ｛ｉ−１｝のｃｏ出力に結合されたｃｉ入力を持ち、ｎ番目の大整数ユニットＬＩＵ｛ｎ−１｝のｃｏ出力は第５のデータ信号、キャリーフロー信号ｃｙであることを特徴とする装置。
【請求項２０】
第１のデータ信号ｙを第２のデータ信号ｘとともに処理するマルチプレシジョン整数演算用の装置であって、
コンローラと、該コンローラに結合された大整数ユニット（ＬＩＵ）とを備え、該ＬＩＵが、
第１の乗算器入力、第２の乗算器入力、上位部分積出力、および下位部分積出力を有する乗算器と、
第１の加算器入力、第２の加算器入力、第３の加算器入力、第４の加算器入力、および加算器出力を有し、前記第３の加算器入力が下位部分積出力を受け取るように乗算器に結合された加算器と、
ＬＩＵレジスタ入力およびＬＩＵレジスタ出力を有するＬＩＵレジスタであって、前記ＬＩＵレジスタ入力は加算器出力を受け取るように加算器に結合され、前記第１のＬＩＵレジスタはクロックパルスの前に加算器出力の値をラッチしてクロックパルスの後にその値を前記ＬＩＵレジスタ出力に転送し、前記ＬＩＵレジスタ出力はＬＩＵレジスタ上位出力とＬＩＵレジスタ下位出力に分割され、前記ＬＩＵレジスタ上位出力は前記ＬＩＵレジスタ出力の上位２ビットを含み、前記ＬＩＵレジスタ下位出力は前記ＬＩＵレジスタ上位出力のビット以外の前記ＬＩＵレジスタ出力の全ビットを含み、前記ＬＩＵレジスタ上位出力は第４の加算器入力に結合され、前記第１のＬＩＵレジスタはさらにＬＩＵレジスタクリア入力がアクティブとされたときに前記ＬＩＵレジスタ出力を０にクリアするための前記ＬＩＵレジスタクリア入力を有する第１のＬＩＵレジスタと、
乗算器の上位部分積出力を受け取るための第２のＬＩＵレジスタと、
第１のＬＩＵレジスタに結合されて、ＬＩＵレジスタ上位出力を受け取って、ＬＩＵレジスタ上位出力のいずれかのビットがアクティブのときにアクティブとされるキャリーフロー信号ｃｙを発生する論理ＯＲゲートと、
前記大整数ユニットの第１の乗算器入力に第１のデータ信号ｙが印加され、
前記大整数ユニットの第２の乗算器入力に、複数の要素を持つ第２のデータ信号ｘが印加され、
前記大整数ユニットの第１の加算器入力に結合され、減算信号がアクティブのときに第３のデータ信号ｚの補数をとるための第１の相補ゲートと、
前記大整数ユニットのＬＩＵレジスタ下位出力に結合され、前記減算信号がアクティブのときに前記ＬＩＵレジスタ下位出力の補数をとるための、第４のデータ信号ａを発生する第２の相補ゲートとを備える
ことを特徴とするマルチプレシジョン整数演算用の装置。
【請求項２１】
第１のデータ信号ｙを第２のデータ信号ｘとともに処理するマルチプレシジョン整数演算用の装置であって、
大整数ユニット（ＬＩＵ）であって、
第１の乗算器入力、第２の乗算器入力、上位部分積出力、および下位部
分積出力を有する乗算器と、
第１の加算器入力、第２の加算器入力、第３の加算器入力、第４の加算
器入力、および加算器出力を有し、前記第３の加算器入力が下位部分積出
力を受け取るように乗算器に結合された加算器と、
ＬＩＵレジスタ入力およびＬＩＵレジスタ出力を有するＬＩＵレジスタ
であって、前記ＬＩＵレジスタ入力は加算器出力を受け取るように加算器
に結合され、前記ＬＩＵレジスタはクロックパルスの前に加算器出力の値
をラッチしてクロックパルスの後にその値を前記ＬＩＵレジスタ出力に転
送し、前記ＬＩＵレジスタ出力はＬＩＵレジスタ上位出力とＬＩＵレジス
タ下位出力に分割され、前記ＬＩＵレジスタ上位出力は前記ＬＩＵレジス
タ出力の上位２ビットを含み、前記ＬＩＵレジスタ下位出力は前記ＬＩＵ
レジスタ上位出力のビット以外の前記ＬＩＵレジスタ出力の全ビットを含
み、前記ＬＩＵレジスタ上位出力は第４の加算器入力に結合され、前記Ｌ
ＩＵレジスタはさらにＬＩＵレジスタクリア入力がアクティブとされたと
きに前記ＬＩＵレジスタ出力を０にクリアするための前記ＬＩＵレジスタ
クリア入力を有するＬＩＵレジスタと、
ＬＩＵレジスタに結合されて、ＬＩＵレジスタ上位出力を受け取って、
ＬＩＵレジスタ上位出力のいずれかのビットがアクティブのときにアクテ
ィブとされるキャリーフロー信号ｃｙを発生する論理ＯＲゲートと
を有する大整数ユニットを備え、
前記大整数ユニットの第１の乗算器入力に第１のデータ信号ｙが印加され、
前記大整数ユニットの第２の乗算器入力に第２のデータ信号ｘが結合され、
前記大整数ユニットの第１の加算器入力に結合され、減算信号がアクティブのときに第３のデータ信号ｚの補数をとるための第１の相補ゲートと、
前記大整数ユニットＬＩＵ｛０｝のＬＩＵレジスタ下位出力に結合され、前記減算信号がアクティブのときに前記ＬＩＵレジスタ下位出力の補数をとるための、第４のデータ信号ａを発生する第２の相補ゲートと、
ラッチレジスタ入力とラッチレジスタ出力を有するラッチレジスタであって、前記ラッチレジスタ入力は前記大整数ユニットＬＩＵの上位部分積出力に結合され、前記ラッチレジスタ出力は、クロックパルスの前に上位部分積の値をラッチし、クロックパルスの後に上位部分積の値を前記大整数ユニットの第２の加算器入力に供給するための前記大整数ユニットの第２の加算器入力に結合されたラッチレジスタとを備え、
前記ラッチレジスタはラッチレジスタクリア信号を持ち、また前記大整数ユニットはＬＩＵレジスタクリア入力を持ち、前記ＬＩＵレジスタクリア入力と前記ラッチレジスタクリア信号が一緒に結合されてデータ信号ｃｌｒを形成し、
前記ラッチレジスタはクロック入力を持ち、また前記大整数ユニットはクロック入力を持ち、前記クロック入力が一緒に結合されてクロック信号ｃｌｋを形成することを特徴とする装置。
【発明の詳細な説明】
【０００１】
（発明の背景）
本発明は、大きな整数を扱う算術計算に関し、さらに詳細には、大きな整数の乗算およびモジュラ簡約（modular reduction）を実行する手段に関する。
【０００２】
（関連技術の説明）
本発明は、ＲＳＡ  Ｌａｂｏｒａｔｏｒｉｅｓ著「Ｔｈｅ  Ｐｕｂｌｉｃ−Ｋｅｙ  Ｃｒｙｐｔｏｇｒａｐｈｙ  Ｓｔａｎｄａｒｄｓ」（ＲＳＡ  Ｄａｔａ  Ｓｅｃｕｒｉｔｙ，Ｉｎｃ．，Ｒｅｄｗｏｏｄ  Ｃｉｔｙ，ＣＡ，１９９３年１１月）のＲＳＡ方式、Ｗ．ＤｉｆｆｉｅおよびＭ．Ｈｅｌｌｍａｎ著「Ｎｅｗ  Ｄｉｒｅｃｔｉｏｎｓ  ｉｎ  Ｃｒｙｐｔｏｇｒａｐｈｙ」（ＩＥＥＥ  Ｔｒａｎｓａｃｔｉｏｎｓ  ｏｎ  Ｉｎｆｏｒｍａｔｉｏｎ  Ｔｈｅｏｒｙ，Ｖｏｌ．ＩＴ−２２，Ｎｏ．６，１９７７年６月，ｐｐ．７４〜８４）のＤｉｆｆｉｅ−Ｈｅｉｌｍａｎ  方式、および「Ｄｉｇｉｔａｌ  Ｓｉｇｎａｔｕｒｅ  Ｓｔａｎｄａｒｄ」（ＦＩＰＳ  Ｐｕｂｌｉｃａｔｉｏｎ  １８６，Ｎａｔｉｏｎａｌ  Ｉｎｓｔｉｔｕｔｅ  ｏｆ  Ｓｔａｎｄａｒｄｓ  ａｎｄ  Ｔｅｃｈｎｏｌｏｇｙ，Ｕ．Ｓ．Ｄｅｐａｒｔｍｅｎｔ  ｏｆ  Ｃｏｍｍｅｒｃｅ，１９９４年５月１８日）のＤＳＡ方式などの公開鍵暗号法の応用が動機となっている。これらの応用では、モジュラべき乗の計算ステップ、つまり、Ａ、Ｂ、およびＰをマルチプレシジョン整数とした場合に「ＡB  ｍｏｄ  Ｐ」の形の計算を行う必要がある。モジュラべき乗（modular exponentiation）は、計算量の多い処理手順であるため、特に安価な計算装置で実行する場合には時間がかかる。
【０００３】
計算装置は通常、固定サイズの基本単位でデータを処理するように設計されている。この基本データ単位のことを「ワード」と呼び、「ｂ」ビットで構成される。ｂの値は、計算装置の設計時に選択する。ｂの値としては、８、１６、３２、または６４ビットが標準である。ワードは、範囲０≦ｘ≦Ｗ−１（ただしＷ＝２b）の非負整数ｘを表現するために使用される。
【０００４】
Ｗ−１よりも大きな整数Ｘを表現するには、マルチプレシジョン表現を使用する。０≦Ｘ≦Ｗn−１で、ｎをある正整数とした場合、Ｘは次式で表すことができる。
【０００５】
Ｘ＝ｘ｛ｎ−１｝*Ｗn-1＋ｘ｛ｎ−２｝*Ｗn-2．．．＋ｘ｛１｝*Ｗ＋ｘ｛０｝、
ただし、各Ｘ｛ｊ｝は、範囲０≦ｘ｛ｊ｝≦Ｗ−１（ｊ＝０，１，．．．，ｎ−１）内にあるものとする。したがって、整数Ｘはｎ個のワードｘ｛０｝，ｘ｛１｝，．．．，ｘ｛ｎ−１｝で表され、ワードｘ｛ｊ｝はＷjの係数である整数を表す。与えられたワードサイズｂと、与えられたワード数ｎについて、Ｘのマルチプレシジョン表現は一意的である。
【０００６】
モジュラべき乗は、マルチプレシジョン整数に対するいくつかの演算を必要とする。このような演算の１つに乗算がある。それぞれｎワードのマルチプレシジョン表現を持つ２つの整数ＸおよびＹが与えられた場合、積Ｚ＝Ｘ*Ｙの計算を計算装置にプログラムする作業は簡単である。この処理手順は、中学校で教わる多桁数の乗算の「積算および加算」法と大差ない。この処理手順の複雑さは２次であり、つまり、計算しなければならない「内積」の数がｎ2である。積Ｚは、表現するのに２ｎ個のワードを必要とする。
【０００７】
実際の公開鍵アプリケーションでは、１回のモジュラべき乗の計算にこのような乗算を数百回あるいは数千回実行する必要があり、それぞれの乗算では数十あるいは数百ワード長の整数を扱うのである。単純な計算装置だと、１回のモジュラべき乗の計算時間は数分程度である。電子商取引など多くのアプリケーションでは、これは長すぎて使えない。
【０００８】
乗算は、モジュラべき乗に関わる唯一の演算ではない。他に、モジュラ簡約、つまり、「Ｐを法とする（ｍｏｄｕｌｏ  Ｐ）」演算を適用することにより積Ｚを２ｎ個のワードからｎ個のワードに減らす演算がある。モジュラ簡約の複雑度は、乗算のそれとほとんど同じであり、２つともモジュラべき乗の総計算時間に対する寄与はほぼ同じである。
【０００９】
（発明の概要）
本発明では、計算装置に以下の演算を効率よく実行する能力があれば、マルチプレシジョン乗算とモジュラ簡約（modular reduction）を高速に計算できるという観察結果を利用している。
【００１０】
Ｚ←Ｚ±（Ｘ*Ｙ）
この演算で、Ｘはｍワードで表される整数であり、ＹとＺはそれぞれｎワードで表される整数である。つまり、ｎはモジュラべき乗の計算で使用する法におけるワードの個数で、ｍはｎよりも小さな値である。マルチプレシジョン乗算およびモジュラ簡約は、それぞれこの演算を約ｎ／ｍ回行うことにより実行でき、モジュラべき乗の計算に対しては合計２ｎ／ｍ回の演算となる。
【００１１】
本発明は、計算装置に追加することで、計算装置がこの演算を効率よく実行することができるようにするコプロセッサを開示する。計算装置から命令が送られると、コプロセッサは、Ｘ、Ｙ、およびＺのワードをメモリから読取り、Ｚの新しいワードをメモりに書き込むことにより演算Ｚ←Ｚ±（Ｘ*Ｙ）を実行する。計算装置は、これらの演算をマルチプレシジョン乗算、モジュラ簡約、そして最終的に、モジュラべき乗演算にアセンブルする。
【００１２】
このコプロセッサの基本ブロックは大整数ユニット（ＬＩＵ；ｌａｒｇｅｉｎｔｅｇｅｒ  ｕｎｉｔ）である。コプロセッサは、１つまたは複数のＬＩＵを備えており、それぞれ同じものである。各ＬＩＵは、乗算器、加算器、レジスタ、およびＯＲゲートを含む。複数のＬＩＵ同士を接続して、相補ゲート、ラッチレジスタ、および出力ゲートを備える１つのＬＩＵアレイを構成できる。アレイ内に含まれるＬＩＵの個数が多ければ多いほど、べき乗計算は高速化される。
【００１３】
本発明の追加の目的および利点は、一部は以下の説明で示し、一部は説明から明らかであるか、または本発明を実施することで知ることができる。本発明の目的および利点はまた、添付の特許請求の範囲で特に指摘した手段および組合せを用いて実現し達成することができる。
【００１４】
（好ましい実施形態の詳細な説明）
本発明のこの好ましい実施形態をここで詳しく参照するが、その例は添付図面に示されており、複数の図面にわたって類似の参照番号は類似の要素を示すものとする。
【００１５】
この説明全体を通して、「Ｘ〜ｎワード」という表記は、前記の形式によるマルチプレシジョン表現を使って整数Ｘが表現されていることを意味する。
【００１６】
また、いくつかの演算子を導入すると便利である。演算子「／」は、剰余を無視する整数除算を表すのに使用する。演算子「％」は、整数剰余演算、つまり除算の結果求められる剰余を表すのに使用する。この表記を使うと、Ｘ／Ｗ＝ｘ｛ｎ−１｝*Ｗn-2＋ｘ｛ｎ−２｝*Ｗn-3．．．＋ｘ｛２｝*Ｗ＋ｘ｛１｝、またＸ ％ ｗ＝ｘ｛０｝となる。
【００１７】
本発明は、計算装置に追加することで、計算装置がこの演算を効率よく実行することができるようにするコプロセッサを開示する。計算装置１１におけるコプロセッサ１４の配列を図１に示す。コプロセッサ１４は、計算装置がメモリ１２との通信に使用するバスを共有する。バスは、計算装置のワードサイズｂとマッチする。計算装置から命令が送られると、コプロセッサは、Ｘ、Ｙ、およびＺのワードをメモリ１２から読取り、Ｚの新しいワードをメモり１２に書き込むことにより演算Ｚ←Ｚ±（Ｘ*Ｙ）を実行する。計算装置は、これらの演算をマルチプレシジョン乗算、モジュラ簡約（modular reduction）、そして最終的に、モジュラべき乗演算にアセンブルする。
【００１８】
図２は大整数ユニット（ＬＩＵ）２１を示す図である。コプロセッサ１４はｎ個のＬＩＵを含んでおり、それぞれは互いに同一である。ＬＩＵの個数により、演算Ｚ←Ｚ±（Ｘ*Ｙ）のオペランド内のワード数Ｘが決まる。モジュラべき乗の実行時間は、１／ｍにだいたい比例する。システム設計者向けに、ＬＩＵを増やせばべき乗計算が高速化されるという、複雑さと速度とのトレードオフ関係を考慮したスケーラブルなアーキテクチャを提供している。
【００１９】
大整数ユニット（ＬＩＵ）
図２に示されている大整数ユニット（ＬＩＵ）２１では、１ビット幅の信号を破線で、複数ビット幅の信号を実線で示しており、ビット数が明記されている。ビット数は、他の実施形態では異なる場合があり、本発明はそのような別の実施形態をも含めるものとする。
【００２０】
第１の乗算器入力ｍ１と第２の乗算器入力ｍ２は、大整数ユニット２１への被乗数入力である。第１の乗算器入力ｍ１と第２の乗算器入力ｍ２はそれぞれ、ｂビット整数を表すワードである。第１の乗算器入力ｍ１と第２の乗算器入力ｍ２は乗算器２２に送られ、積信号ｐ＝ｍ１*ｍ２が出力されるが、ただし「*」は乗算を表すものとする。
【００２１】
０≦ｍ１≦（Ｗ−１）および０≦ｍ２≦（Ｗ−１）なので、積信号ｐの範囲は０≦ｐ≦（Ｗ−１）2である。つまり、積信号ｐを表現するには２ｂビット必要だということである。積信号ｐは、上位部分積信号（ｈｉｇｈ  ｐｒｏｄｕｃｔ  ｓｉｇｎａｌ）ｐｈと下位部分積信号（ｌｏｗ  ｐｒｏｄｕｃｔ  ｓｉｇｎａｌ）ｐｌに分けられる。上位部分積信号ｐｈは、積信号ｐの上位ｂビットとして、下位部分積信号ｐｌは下位ｂビットとして構成される。したがって、ｐ＝ｐｈ*Ｗ＋ｐｌ（０≦ｐｈ≦（Ｗ−１）かつ０≦ｐｌ≦（Ｗ−１））である。上位部分積信号ｐｈは大整数ユニット２１の出力信号であり、下位部分積信号ｐｌは内部で使用される。
【００２２】
第１の加算器信号ａｌと第２の加算器信号ａ２は、大整数ユニット２１への加算器入力である。それぞれｂビット整数を表すワードである。第１の加算器信号ａ１と第２の加算器信号ａ２は加算器２３に送られる。加算器２３はさらに、下位部分積信号ｐｌと、２ビットの値であるキャリー信号ｃを受け取る。加算器２３は、第１の総和信号ｑｄ（ｑｄ＝ａ１＋ａ２＋ｐｌ＋ｃ）を出力する。第１の加算器信号ａ１、第２の加算器信号ａ２、または下位部分積信号ｐｌの可能な最大値はＷ−１である。キャリー信号ｃに使用可能な最大の値は３である。したがって、第１の総和信号ｑｄの最大可能値は３*（Ｗ−１）＋３＝３Ｗであり、総和信号ｑｄを表現するにはｂ＋２ビットが必要である。
【００２３】
加算器２３の出力の第１の総和信号ｑｄは、レジスタ２４にラッチされる。レジスタ２４はｂ＋２ビット幅である。第１の総和信号ｑｄの値は、大整数ユニット２１へのクロックｃｌｋ入力が脈動されるとレジスタ２４の出力に転送される。
【００２４】
レジスタ２４の出力は第２の総和信号ｑである。第２の総和信号ｑの値は次回クロックｃｌｋ入力が脈動されるまで、または大整数ユニット２１のクリアｃｌｒ入力が脈動されるまで適所にとどまる。
【００２５】
レジスタ２４は、大整数ユニット２１のｃｌｒ入力信号を脈動することでクリアすることができる。ｃｌｒ入力が脈動されると、レジスタ２４の出力ビットは０にクリアされる。出力は、ｃｌｋ入力が次回脈動されるまで０のままであり、このときに、第１の総和信号ｑｄの値が出力へ転送される。
【００２６】
レジスタ２４の出力の第２の総和信号ｑは、キャリー信号ｃと総和信号ｓに分けられる。キャリー信号ｃは、第２の総和信号ｑの上位２ビットとして、総和信号ｓは下位ｂビットとして構成される。したがってｑ＝ｃＷ＋ｓであり、０≦ｓ≦Ｗ−１、０≦ｃ≦３である。総和信号ｓは大整数ユニット２１の出力信号である。
【００２７】
キャリー入力信号ｃｉは大整数ユニット２１へのキャリー入力であり、キャリー出力信号ｃｏはキャリー出力である。それぞれ１ビットの値である。キャリー出力信号ｃｏは、ＯＲゲート２９を使用して、キャリー入力信号ｃｉと第２の総和信号ｑを構成するビットの論理ＯＲとして計算される。つまり、キャリー出力信号ｃｏは、キャリー入力信号ｃｉが０のときと、第２の総和信号ｑの各ビットが０のときに値が０となる。そうでない場合には、キャリー出力信号ｃｏは値１を持つ。
【００２８】
補助キャリー信号ｃａは、ＯＲゲート２５を使用し、キャリー信号ｃを構成する２ビットの論理ＯＲとして計算される。つまり、補助キャリー信号ｃａは、キャリー信号ｃの各ビットが０の場合に値が０であり、そうでない場合には、補助キャリー信号ｃａは値１となる。
【００２９】
ＬＩＵアレイ
説明
図３に示されているように、複数の大整数ユニットを相互接続して１つのＬＩＵアレイを形成することができる。それとは別に、ＬＩＵアレイにはＬＩＵを１つだけ含めることができる。図３では、各信号は１ビット幅またはｂビット幅のいずれかである。１ビット幅の信号は破線で示されており、ｂビット幅の信号は実線で示されている。
【００３０】
図３は、４つの大整数ユニットＬＩＵ｛０｝、ＬＩＵ｛１｝、ＬＩＵ｛２｝、ＬＩＵ｛３｝を相互接続して１つのＬＩＵアレイ３９を形成する場合を示している。一般に、大整数ユニットはいくつでも相互接続できる。簡単のため、ここでの説明ではまず図４に示されているように４つの大整数ユニットの場合について考察し、その後、他の数の大整数ユニットの場合に一般化する。
【００３１】
第１のデータ信号ｙはＬＩＵアレイ３９への入力であり、それぞれの大整数ユニットＬＩＵ｛０｝、ＬＩＵ｛１｝、ＬＩＵ｛２｝、ＬＩＵ｛３｝の第１の乗算器入力ｍ１に印加される。
【００３２】
第２のデータ信号は複数の要素ｘ｛０｝、ｘ｛１｝、ｘ｛２｝、およびｘ｛３｝を持つ。各要素はそれぞれ、ＬＩＵアレイ３９の各大整数ユニットの第２の乗算器入力ｍ２に接続される、つまり各要素は、それぞれＬＩＵ｛０｝、ＬＩＵ｛１｝、ＬＩＵ｛２｝、ＬＩＵ｛３｝の第２の乗算器入力ｍ２に接続される。
【００３３】
第３のデータ信号ｚはＬＩＵアレイ３９への入力であり、相補ゲート３５の入力に接続されている。この相補ゲート３５は排他ＯＲ（ＸＯＲ）ゲートＧＡＴＥ０であり、第３のデータ信号ｚの各ビットを減算信号と組み合わせる。この減算信号自体はＬＩＵアレイ３９への入力信号である。減算信号が非アクティブ状態、つまり論理０であれば、第３のデータ信号ｚのビットは、相補ゲート３５の通過中に影響を受けない。減算信号がアクティブ状態、つまり論理１であれば、第３のデータ信号の各ビットは相補ゲート３５を通るときに論理相補ビットで置き換えられる。つまり、１のビットは０のビットで、０のビットは１のビットで置き換えられるということである。相補ゲート３５の出力は、第１の大整数ユニットＬＩＵ｛０｝の第１の加算器入力ａ１に接続されている。
【００３４】
出力信号ａはＬＩＵアレイ３９の出力であり、出力ゲート３６の出力から取り出される。出力ゲート３６は排他ＯＲ（ＸＯＲ）ゲートＧＡＴＥ１であり、第１の大整数ユニットＬＩＵ｛０｝の出力である総和信号ｓの各ビットを組み合わせる。減算信号が非アクティブ状態であれば、第１大整数ユニットの総和信号ｓのビットは出力ゲート３６を通るときに影響を受けない。減算信号がアクティブ状態であれば、第１大整数ユニットの総和信号ｓのビットは、その論理相補ビットで置き換えられる。
【００３５】
ラッチレジスタ３４はｂビット幅のレジスタＲＥＧ０である。ラッチレジスタ３４の入力は第４の大整数ユニットＬＩＵ｛３｝の上位部分積信号ｐｈに接続され、ラッチレジスタ３４の出力は第４の大整数ユニットＬＩＵ｛３｝の第２の加算器信号ａ２入力に接続されている。そこで、ラッチレジスタ３４は、１クロックパルス前に第４の大整数ユニットから上位部分積信号ｐｈの値をラッチし、その値をそのクロックパルスの後に第４の大整数ユニットの第２の加算器信号ａ２入力に戻す。ラッチレジスタ３４は、図２の大整数ユニット２１のレジスタ２４のｃｌｒ入力とまったく同じ動作をするクリアｃｒｌ入力を持つ。
【００３６】
クロック信号ｃｌｋはＬＩＵアレイ３９への入力であり、それぞれの大整数ユニットＬＩＵ｛０｝、ＬＩＵ｛１｝、ＬＩＵ｛２｝、ＬＩＵ｛３｝のｃｌｋ入力とラッチレジスタ３４のｃｌｋ入力に接続される。クロック入力が脈動されると、それぞれの大整数ユニット内のレジスタの内容とラッチレジスタ３４の内容は同時に更新される。
【００３７】
クリア信号ｃｌｒはＬＩＵアレイ３９への入力であり、それぞれの大整数ユニットＬＩＵ｛０｝、ＬＩＵ｛１｝、ＬＩＵ｛２｝、ＬＩＵ｛３｝のｃｌｒ入力とラッチレジスタ３４のｃｌｒ入力に接続される。クリア入力が脈動されると、それぞれの大整数ユニット内のレジスタの内容とラッチレジスタ３４の内容は同時に０にクリアされる。
【００３８】
キャリーフロー信号ｃｙはＬＩＵアレイ３９の出力であり、第４の大整数ユニットＬＩＵ｛３｝のｃｏ出力に接続される。このキャリーフロー信号は、オーバーフローまたはアンダーフローが発生したかどうかを示す。
【００３９】
４つよりも多い大整数ユニットを１つのＬＩＵアレイに相互接続するには、第３の大整数ユニットの相互接続ロジックを複製する。以下の表１に、ｍ個（ｍ≧４）の大整数ユニットを１つのＬＩＵアレイに相互接続するロジックの詳細をまとめた。
【００４０】
【表１】
0004201980.tif 000002
【００４１】
表１で、「ＬＩＵ｛ｋ｝：ｘ」という表記はＬＩＵ｛ｋ｝の信号ｘ、「ＲＥＧ０：ｘ」はＲＥＧ０の信号ｘなどを意味し、「Ｎ／Ｃ」は信号が未接続であることを意味している。一番左の欄はｋchの大整数ユニットＬＩＵ｛ｋ｝の信号を示し、後の欄はｋ＝０、１、．．．、ｍ−１に対するその信号の相互接続ロジックを示している。図からわかるように、表１の記載事項はｍ＝４のときの図３に示されている相互接続ロジックとマッチしている。
【００４２】
４つよりも少ない大整数ユニットを１つのＬＩＵアレイに相互接続するには、大整数ユニットのいくつかの相互接続ロジックを集約する。表２、３、および４に、それぞれｍ＝３、ｍ＝２、およびｍ＝１とした場合のｍ個の大整数ユニットを１つのＬＩＵアレイに相互接続するロジックの詳細をまとめた。
【００４３】
【表２】
0004201980.tif 000003
【００４４】
【表３】
0004201980.tif 000004
【００４５】
【表４】
0004201980.tif 000005
【００４６】
表２〜４に記載されていないＬＩＵアレイ信号は、ｍの任意の値に対するのと同じ相互接続ロジックを持つ。完全を期すため、表５に信号の詳細を示す。
【００４７】
【表５】
0004201980.tif 000006
【００４８】
演算
ＬＩＵアレイによって実行される一般関数は以下のとおりである。
【００４９】
Ａ←Ｚ±（Ｘ*Ｙ）
ただし、Ｘ〜ｍワード、Ｙ〜ｎワード、Ｚ〜ｎワード、そしてＡ〜ｎワードである。
【００５０】
整数Ｘ、Ｙ、およびＺは、関数に対する入力オペランドであり、整数Ａは出力オペランドである。ＸのワードはＬＩＵアレイに同時に、入力ｘ｛０｝，ｘ｛ｌ｝，．．．，ｘ｛ｍ−１｝において印加される。ＹおよびＺのワードは一度に１ワードがＬＩＵアレイに、それぞれ入力ｙおよびｚにおいて印加される。ＡのワードはＬＩＵアレイから一度に１ワードが、出力ａにおいて読み出される。
【００５１】
ＬＩＵアレイへの減算入力は、「±」演算において減算か加算かを選択する。減算入力をアクティブにする、つまり減算入力を論理１に設定することで減算を選択し、減算入力を非アクティブにする、つまり減算入力を論理０にクリアすることで加算を選択する。
【００５２】
ＬＩＵアレイのキャリーフロー信号ｃｙは、オーバーフローまたはアンダーフローが発生したかどうかを示す。加算中に計算した値が大きすぎてｎワードで表現できないとオーバーフローが発生する。減算中に計算した値が負になるとアンダーフローが発生する。演算終了時にオーバーフローまたはアンダーフローが発生していれば、キャリフロー信号ｃｙ出力はアクティブになる。オーバーフローもアンダーフローも発生していなければ、キャリーフロー信号ｃｙ出力は非アクティブである。
【００５３】
ＬＩＵアレイは、以下の処理手順に従って一般関数を実行する場合に使用できる。
１．ｃｌｒを脈動する。
２．信号ｓｕｂをアクティブまたは非アクティブにする。
３．データ入力ｘ｛０｝，ｘ｛ｌ｝，．．．，ｘ｛ｍ−１｝を印加する。
４．ｊ＝０，１，．．．，ｎ−１について、
ａ．データ入力ｙを印加する。
ｂ．データ入力ｚを印加する。
ｃ．ｃｌｋを脈動する。
ｄ．データ出力ａを読み取る。
を実行する。
【００５４】
ステップ１で、ＬＩＵレジスタとラッチレジスタ３４（ＲＥＧ０）をクリアする。前の演算からの累計がクリアされる。
ステップ２で、「±」演算における加算と減算を選択する。減算入力が非アクティブ値であれば加算が選択され、アクティブ値であれば減算が選択される。
ステップ３で、Ｘオペランドのワードの値が印加される。これらの値は、そのまま全体の処理手順に印加される。
ステップ４で、ｎ回実行するループを制御する。それぞれの反復には、インデックスｊ（ｊ＝０，１．．．、ｎ−１）で番号が振られる。
ステップ４ａで、オペランドＹのワードｊを印加する。
ステップ４ｂで、オペランドＺのワードｊを印加する。
ステップ４ｃで、信号ｃｌｋを脈動する。これによりＬＩＵレジスタとラッチレジスタ３４（ＲＥＧ０）を新しい値で更新し、出力ａにおいて新しいワードを使用できるようにする。
ステップ４ｄで、オペランドＡのワードｊを読み出す。
【００５５】
ＬＩＵアレイのクロッキングの分析
ＬＩＵアレイの動作は、単一のサイクル、つまりクロック入力信号の単一の脈動（pulsing）について分析することができる。例では、４つのＬＩＵからなるアレイのケースを使用する。この分析をどのように一般化して他の多数のＬＩＵに適用できるかは明白であろう。
【００５６】
この説明では、ＬＩＵアレイへの減算入力信号が非アクティブとなっているケースのみを分析する。アクティブな減算信号のケースについては、後ほど分析する。
【００５７】
図３と図２を参照すると、整数Ｑは値Ｑ＝ｑ｛０｝＋ｑ｛１｝Ｗ＋ｑ｛２｝Ｗ2＋ｑ｛３｝Ｗ3＋ｒｗ4を持つと定義され、ここで、ｑ｛ｊ｝はＬＩＵ｛ｊ｝のレジスタに格納されている値、ｒはＬＩＵアレイのレジスタＲＥＧ０に格納されている値である。それぞれのｑ｛ｊ｝はｂ＋２ビットで構成され、Ｗ＝２bである。
【００５８】
クロック信号が脈動する（pulsed）と、Ｑの値が変化する。新しい値をＱ+と呼ぶ。Ｑ+の値は、それぞれのＬＩＵ内の加算器の出力およびＬＩＵ｛３｝内の乗算器の出力から導かれる。重ね合わせを使って、次のようにしてＱ+の値を決定することができる。
【００５９】
まず、Ｑの値は０、入力信号ｙの値も０であると仮定する。この場合、Ｑ+に寄与するのは入力信号ｚだけである。ｚの値は、ＬＩＵ｛０｝内の加算器を伝播して、ＬＩＵ｛０｝のレジスタ出力に現れる。ＬＩＵアレイ内の他のレジスタはそれぞれ出力値が０である。したがって、この場合、次のようになる。
【００６０】
Ｑ+＝ｚ．        （ｉ）
【００６１】
次に、Ｑの値は０、入力信号ｚの値は０であると仮定する。この場合、Ｑ+への寄与は各ＬＩＵ内の乗算器の出力からだけである。乗算器出力の下位部分は同じＬＩＵ内のレジスタに寄与する。乗算器出力の上位部分は次に高いＬＩＵ内のレジスタ、すなわちＬＩＵ｛３｝の場合には、ＲＥＧ０に寄与する。したがって、Ｑ+の値に寄与する場合には、ＬＩＵ｛ｊ｝内の乗算器出力の下位部分はＷjで重み付けされ、上位部分はＷj+1で重み付けされる。これは、Ｑ+に寄与する場合にはＬＩＵ｛ｊ｝内の乗算器の全出力がＷjで重み付けされることを意味している。ＬＩＵ｛ｊ｝内の乗算器への２つの入力はそれぞれ入力信号ｙおよびｘ｛ｊ｝なので、この場合、次のようになる。
【００６２】
Ｑ+＝ｙｘ｛０｝＋ｙｘ｛１｝Ｗ＋ｙｘ｛２｝Ｗ2＋ｙｘ｛３｝Ｗ3．
（ｉｉ）
【００６３】
次に、ｚの値は０、ｙの値は０であると仮定する。この場合、Ｑ+への寄はＱの現在値からだけである。ＬＩＵ｛ｊ｝内では、ｑ｛ｊ｝の値はｃ｛ｊ｝Ｗ＋ｓ｛ｊ｝と記述でき、ここで、ｃ｛ｊ｝はｑ｛ｊ｝の上位２ビットから、ｓ｛ｊ｝は残りのビットからできている。そこで、Ｑの値は次のように書き下せる。
【００６４】
Ｑ＝ｓ｛０｝＋（ｃ｛０｝＋ｓ｛１｝）Ｗ＋（ｃ｛１｝＋ｓ｛２｝）Ｗ2
＋（ｃ｛２｝＋ｓ｛３｝）Ｗ3＋ｒＷ4．
【００６５】
それぞれのｃ｛ｊ｝はＬＩＵ｛ｊ｝内の新しいレジスタ値に寄与し、Ｑ+に寄与するときのＷjの重み付けがされる。ｊ＝１、２、および３について、各ｓ｛ｊ｝はＬＩＵ｛ｊ−１｝内のレジスタに寄与し、Ｗj-1の重みを付ける。ｒの値はＬＩＵ｛３｝内のレジスタに寄与し、Ｗ3の重みを付ける。したがって、この場合、次のようになる。
【００６６】
Ｑ+＝（ｃ｛０｝＋ｓ｛１｝）＋（ｃ｛ｌ｝＋ｓ｛２｝）Ｗ
＋（ｃ｛２｝＋ｓ｛３｝）Ｗ2＋ｒＷ3．
【００６７】
これは次のように書けることに注意されたい。
【００６８】
Ｑ+＝Ｑ／Ｗ，        （ｉｉｉ）
【００６９】
ただし、「／」は、剰余を無視する整数除算を表す。
式（ｉ）、（ｉｉ）、および（ｉｉｉ）は、新しい値Ｑ+へのすべての寄与分を含む。重ね合わせによる寄与分を組み合わせると、次式が得られる。
【００７０】
Ｑ+＝ｚ＋ｙ（ｘ｛０｝＋ｘ｛１｝Ｗ＋ｘ｛２｝Ｗ2＋ｘ｛３｝Ｗ3）＋Ｑ／Ｗ．                        （ｉｖ）
【００７１】
クロック脈動（clock pulse）後、ＬＩＵアレイの出力信号ａの値は次式で与えられる。
【００７２】
ａ+＝Ｑ+ ％ Ｗ．        （ｖ）
【００７３】
ａ+はクロック脈動後のａの値を意味し、「％」は整数モジュロ演算を表す。つまり、ａ+は、Ｑ+をＷで除算したときの剰余である。
【００７４】
式（ｉｖ）と（ｖ）は、クロックが脈動したときのＬＩＵアレイの演算をまとめたものである。
【００７５】
一般関数を計算するための手続の分析
このセクションでは、一般関数の計算を行うために使用される処理手続中のＬＩＵアレイの演算を分析する。この処理手続については前のセクションで説明した。説明からわかるようにＬＩＵアレイは、この手続とともに使用したときに一般関数の計算を正しく行える。
【００７６】
この説明では、ＬＩＵアレイへの減算入力信号が非アクティブとなっているケースのみを分析する。アクティブな減算信号のケースについては、後ほど分析する。
【００７７】
一般関数はＡ←（Ｚ＋Ｘ*Ｙ） ％ Ｗnである。ただし、
Ｚ＝ｚ｛０｝＋ｚ｛１｝Ｗ＋ｚ｛２｝Ｗ2＋．．．＋ｚ｛ｎ−１｝Ｗn-1；
Ｙ＝ｙ｛０｝＋ｙ｛１｝Ｗ＋ｙ｛２｝Ｗ2＋．．．＋ｙ｛ｎ−１｝Ｗn-1；
Ｘ＝ｘ｛０｝＋ｘ｛１｝Ｗ＋ｘ｛２｝Ｗ2＋．．．＋ｘ｛ｍ−１｝Ｗm-1；
Ａ＝ａ｛０｝＋ａ｛１｝Ｗ＋ａ｛２｝Ｗ2＋．．．＋ａ｛ｎ−１｝Ｗn-1；
【００７８】
ただし、ｍは、ＬＩＵアレイ内のＬＩＵの個数およびオペランドＸにおけるワード数であり、ｎは、オペランドＹ、ＺおよびＡにおけるワード数である。モジュロ演算「％ Ｗn」は、Ｚ＋Ｘ*Ｙの結果の値がＡのｎワードに収まるように切り詰められるという事実を反映している。（Ｚ＋Ｘ*Ｙ）＜ＷnであればＡ＝Ｚ＋Ｘ*Ｙであり、これは、一般関数の「オーバーフローなし」のケースである。（Ｚ＋Ｘ*Ｙ）≧Ｗnであれば、ＡはＺ＋Ｘ*Ｙの下位ｎワードからなり、これは、一般関数の「オーバーフロー」のケースである。
【００７９】
一般関数を計算する処理手続については前のセクションで説明した。この処理手続をＬＩＵアレイの前の分析とを組み合わせることにより、一般関数の計算を次の反復（recursion）で記述できる。
【００８０】
For ｋ ＝０，１，．．．，ｎ−１:
Ｑ｛ｋ｝＝ｚ｛ｋ｝＋ｙ｛ｋ｝Ｘ＋Ｓ｛ｋ−１｝；
ａ｛ｋ｝＝Ｑ｛ｋ｝ ％ Ｗ；
Ｓ｛ｋ｝＝Ｑ｛ｋ｝／Ｗ；
【００８１】
ただし、Ｓ｛−１｝＝０である。「％」は、整数モジュロ演算を表し、「／」は剰余を切り捨てる整数除算を表す。
【００８２】
ｎステップ反復が完了したら、以下の式の成り立つことが明らかになる。
【００８３】
ａ｛０｝＋ａ｛１｝Ｗ＋ａ｛２｝Ｗ2．．．＋ａ｛ｎ−１｝Ｗn-1＋Ｓ｛ｎ−１｝Ｗn
＝
ｚ｛０｝＋ｚ｛１｝Ｗ＋ｚ｛２｝Ｗ2．．．＋ｚ｛ｎ−１｝Ｗn-1
＋Ｘ（ｙ｛０｝＋ｙ｛１｝Ｗ＋ｙ｛２｝Ｗ2．．．＋ｙ｛ｎ−１｝Ｗn-1).
（ｖｉ）
【００８４】
この式の右辺はＺ＋Ｘ*Ｙである。式の左辺はＡ＋Ｓ｛ｎ−１｝Ｗnである。「％ Ｗn」演算を式の両辺に適用すると、Ａ＝（Ｚ＋Ｘ*Ｙ） ％ Ｗnが得られる。したがって、式（ｖｉ）が真であることが明らかにされると、処理手続によって実際にＬＩＵアレイに一般関数を計算させていることが明らかになる。
【００８５】
式（ｖｉ）は帰納法によって証明できる。まず、ｎ＝１について式が成り立つことが示される。次に、ｎ＝ｔについて式が成り立てば、ｎ＝ｔ＋１についても成り立つことが示される。これで、ｎ≧１の任意の値について式が成り立つことがいえる。
【００８６】
ｎ＝１のケースについて考察する。Ｓ｛−１｝＝０なので、反復から次式が得られる。
【００８７】
Ｑ｛０｝＝ｚ｛０｝＋ｙ｛０｝Ｘ．
【００８８】
Ｓ｛ｋ｝は商であり、ａ｛ｋ｝はＱ｛ｋ｝をＷで割って得た剰余であるために、任意のｋについて、ＷＳ｛ｋ｝＋ａ｛ｋ｝＝Ｑ｛ｋ｝であることに注意されたい。ｋ＝０においてこれを評価すると、次式が得られる。
【００８９】
ａ｛０｝＋ＷＳ｛０｝＝Ｑ｛０｝＝ｚ｛０｝＋ｙ｛０｝Ｘ，
【００９０】
これは、ｎ＝１のケースについて式（ｖｉ）を定める。
【００９１】
ここで、ｎ＝ｔ＋１のケースについて考察する。ｎ＝ｔについて式（ｖｉ）が成立すると仮定すると、次式が得られる。
【００９２】
ａ｛０｝＋ａ｛１｝Ｗ＋ａ｛２｝Ｗ2．．．＋ａ｛ｔ−１｝Ｗt-1＋Ｓ｛ｔ−１｝Ｗt
＝
ｚ｛０｝＋ｚ｛１｝Ｗ＋ｚ｛２｝Ｗ2．．．＋ｚ｛ｔ−１｝Ｗt-1
＋Ｘ（ｙ｛０｝＋ｙ｛１｝Ｗ＋ｙ｛２｝Ｗ2．．．＋ｙ｛ｔ−１｝Ｗt-1）．
（ｖｉｉ）
【００９３】
ＷＳ｛ｋ｝＋ａ｛ｋ｝＝Ｑ｛ｋ｝なので、次式が得られる。
【００９４】
Ｗt+1Ｓ｛ｔ｝＋Ｗtａ｛ｔ｝＝ＷtＱ｛ｔ｝＝
Ｗt（ｚ｛ｔ｝＋ｙ｛ｔ｝Ｘ＋Ｓ｛ｔ−１｝）．      （ｉｉｉ）
【００９５】
式（ｖｉｉ）と（ｖｉｉｉ）を足し合わせると次式が得られる。
【００９６】
ａ｛０｝＋ａ｛１｝Ｗ＋ａ｛２｝Ｗ2．．．＋ａ｛ｔ｝Ｗt＋Ｓ｛ｔ｝Ｗt+1
＝
ｚ｛０｝＋ｚ｛１｝Ｗ＋ｚ｛２｝Ｗ2．．．＋ｚ｛ｔ｝Ｗt
＋Ｘ（ｙ｛０｝＋ｙ｛１｝Ｗ＋ｙ｛２｝Ｗ2．．．＋ｙ｛ｔ｝Ｗt）．
【００９７】
これにより、ｎ＝ｔ＋１について式（ｖｉ）が成立し、証明が完成する。
【００９８】
アクティブな減算信号の分析
ＬＩＵアレイの減算入力信号がアクティブになっている場合、オペランドＺの各ワードはＬＩＵアレイに印加される前に相補がとられる。数値についてみると、これはＺを（Ｗn−Ｚ−１）で置き換えることと等価である。同様に、オペランドＡの各ワードはＬＩＵアレイから出力される前に相補がとられる。これはＡを（Ｗn−Ａ−１）で置き換えることと等価である。したがって、減算信号がアクティブのときは、一般関数は次のように計算される。
【００９９】
Ｚ’＝Ｗn−Ｚ−１；
Ａ’＝（Ｚ’＋Ｘ*Ｙ） ％ Ｗn；
Ａ＝Ｗn−Ａ’−１．
０≦Ｚ’＜Ｗnおよび０≦Ａ’＜Ｗnなので、「％ Ｗn」演算をＺ’およびＡ’の式に自由に付加することができる。
【０１００】
Ｚ’＝（Ｗn−Ｚ−１） ％ Ｗn；
Ａ’＝（Ｚ’＋Ｘ*Ｙ） ％ Ｗn；
Ａ ＝（Ｗn−Ａ’−１） ％ Ｗn．
この形式では、次のように、「％ Ｗn」演算を無視し、式をマージし、「％ Ｗn」演算を末尾に付加できることが明白である。
【０１０１】
Ａ  ＝（Ｗn−（（Ｗn−Ｚ−１）＋Ｘ*Ｙ）−１）％ Ｗn．
この式を簡単にすると、次式が得られる。
【０１０２】
Ａ  ＝（Ｚ−Ｘ*Ｙ） ％ Ｗn．
これは、望みどおりの一般関数の減算形式である。
【０１０３】
シングルＲＡＭ装置
ＬＩＵアレイをコントローラおよびランダムアクセスメモリ（ＲＡＭ）と組み合わせて、上述の一般関数に基づき計算を実行できる装置を構成することができる。このような装置を図４に示した。
【０１０４】
コントローラ４１とＬＩＵアレイ３９の組み合わせでは、計算装置とともに使用することができるコプロセッサを備える。このような場合、ランダムアクセスメモリ（ＲＡＭ）４２は、図１に示されているように、計算装置１１と共有することができる。
【０１０５】
コントローラ４１は、ＬＩＵアレイ３９の信号を処理し、望む演算をアレイに実行させる。コントローラ４１は、ＲＡＭ４２から入力オペランドを読み出してＬＩＵアレイ３９と計算装置に転送する。コントローラ４１は、ＬＩＵアレイ３９から出力オペランドを読み出してＲＡＭ４２に書き込む。コントローラ４１を実施する方法は多数あるが、その一つに有限状態機械（finite state machine）を使用するものがある。ＲＡＭ４２は従来の装置である。このＲＡＭはｂビット幅のデータバスを持ち、これはＬＩＵアレイ３９のワードサイズと一致している。コントローラ４１は、適切な値をアドレスバスに印加し、読み取り信号をアクティブにし、データバス上でＲＡＭ４２によって供給されたとおりにワードの値を読み取り、それから読み取り信号を非アクティブにすることにより、ＲＡＭ４２からワードを読み取る。コントローラ４１は、適切な値をアドレスバスに印加し、ワードの値をデータバスに印加し、書込み信号を脈動させることによりＲＡＭ４２にワードを書き込む。
【０１０６】
ワードを読み取る、またはワードを書き込むのに要する時間のことをＲＡＭサイクルと呼ぶ。たとえば、コントローラ４１がｎワードからなる整数Ｘを読み取ったり書き込んだりするときにかかる時間はｎ  ＲＡＭサイクルである。
【０１０７】
コントローラ４１は、装置に、次の処理手順を用いて一般関数Ａ←Ｚ±（Ｘ*Ｙ）を実行させるが、ここで、Ｘ〜ｍワード、Ｚ〜ｎワード、およびＡ〜ｎワードである。
【０１０８】
１．コントローラ４１はＬＩＵアレイ３９のｃｌｒ入力を脈動する。
２．コントローラはＬＩＵアレイ減算入力をアクティブまたは非アクティブにする。コントローラは、この処理手順の残りの間、この値を一定に保つ。
３．コントローラはＲＡＭ４３からｍ個の値を読み出して、ＬＩＵアレイのｘ｛０｝，ｘ｛ｌ｝，．．．，ｘ｛ｍ−１｝入力に印加する。コントローラは、この処理手順の残りの間、これらの値を一定に保つ。
４．ｊ＝０，１，．．．，ｎ−１について、
ａ．コントローラは、ＲＡＭから値を読み取ってＬＩＵアレイのｙ入力に印加する。
ｂ．コントローラは、ＲＡＭから値を読み取ってＬＩＵアレイのｚ入力に印加する。
ｃ．コントローラはＬＩＵアレイのｃｌｋ入力を脈動する。
ｄ．コントローラは、ＬＩＵアレイの出力の値を読み取ってＲＡＭに書き込む。
【０１０９】
ステップ３で、コントローラ４１はＲＡＭ４２からＸオペランドのｍワードを読み取る。これに、ｍ  ＲＡＭサイクルを要する。
ステップ４ａで、コントローラ４１はＲＡＭ４２からＹオペランドのｎワードを読み取る。これに、ｎ  ＲＡＭサイクルを要する。
ステップ４ｂで、コントローラ４１はＲＡＭ４２からＺオペランドのｎワードを読み取る。これに、ｎ  ＲＡＭサイクルを要する。
ステップ４ｄで、コントローラ４１はＲＡＭ４２にＡオペランドのｎワードを書き込む。これに、ｎ  ＲＡＭサイクルを要する。
【０１１０】
この処理手順に必要なＲＡＭサイクルの総数はｍ＋３ｎである。これは、ステップ３、４ａ、４ｂ、および４ｄにおけるサイクル数を足し合わせることで求められる。
【０１１１】
読取り−変更−書込みのあるシングルＲＡＭ装置
図５に示されているように、一般関数を実行するのに必要なＲＡＭサイクル数は、読取り−変更−書込み動作を実行できるＲＡＭ４３をを使用して減らすことができる。このような動作により、コントローラ４１はＲＡＭ４３から１ワード読み取って、そのワードの値を変更し、新しい値をＲＡＭ４３に書き戻す作業すべてを１ＲＡＭサイクル内に実行することができる。
【０１１２】
コントローラ４１とＬＩＵアレイ３９の組み合わせでは、計算装置とともに使用することができるコプロセッサを備える。このような場合、ＲＡＭ４３は、図１に示されているように計算装置１１と共有することができる。
【０１１３】
コントローラ４１は次のようにして、ＲＡＭ４３に対し読取り−変更−書込み動作を実行する。まず、コントローラは適切な値をアドレスバスに印加し、読取り−変更−書込み信号ｒｍｗをアクティブにする。次に、コントローラは読取り信号をアクティブにし、データバス上にＲＡＭが出した値を読取り、読取り信号を非アクティブにする。さらに、コントローラは変更された値をデータバスに印加し、書込み信号を脈動する。最後に、コントローラはｒｍｗ信号を非アクティブにする。この動作全体を１ＲＡＭサイクル内に実行する。
【０１１４】
ＲＡＭ４３はさらに、すでに説明したように、通常の読み書き演算も実行することができる。コントローラは、ｒｍｗ信号を非アクティブにすることにより、通常の読み書き演算を選択する。この３つの演算（読取り、書込み、および読取り−変更−書込み）はそれぞれ、１ＲＡＭサイクルを必要とする。
【０１１５】
読取り−変更−書込み機能を利用する場合には、一般関数はＺ←Ｚ±（Ｘ*Ｙ）となり、ここで、Ｘ〜ｍワード、Ｙ〜ｎワード、およびＺ〜ｎワードてある。したがって、オペランドＺを変更するには、量Ｘ*Ｙの加算または減算を行う。コントローラ４１は、以下の処理手順に従って装置にこの関数（functon）を実行させる。
【０１１６】
１．コントローラ４１はＬＩＵアレイ３９のｃｌｒ入力を脈動する。
２．コントローラはＬＩＵアレイ減算入力をアクティブまたは非アクティブにする。コントローラは、この処理手順の残りの間、この値を一定に保つ。
３．コントローラはＲＡＭ４２からｍ個の値を読み出して、ＬＩＵアレイのｘ｛０｝，ｘ｛ｌ｝，．．．，ｘ｛ｍ−１｝入力に印加する。コントローラは、この処理手順の残りの間、これらの値を一定に保つ。
４．ｊ＝０，１，．．．，ｎ−１について、
ａ．コントローラは、ＲＡＭから値を読み取ってＬＩＵアレイのｙ入力に印加する。
ｂ．コントローラは、ＲＡＭから値を読み取って、ＬＩＵアレイのＺ入力に印加し、ＬＩＵアレイのｃｌｋ信号を脈動し、ＬＩＵアレイのａ出力の値を読み取って、ＲＡＭに書き込む。
【０１１７】
ステップ３で、コントローラはＲＡＭからＸオペランドのｍワードを読み取る。これに、ｍ  ＲＡＭサイクルを要する。
ステップ４ａで、コントローラはＲＡＭからＹオペランドのｎワードを読み取る。これに、ｎ  ＲＡＭサイクルを要する。
ステップ４ｂで、コントローラはＲＡＭのＺオペランドのｎワードのそれぞれについて読取り−変更−書込み演算を実行する。これに、ｎ  ＲＡＭサイクルを要する。
【０１１８】
この手処理順に必要なＲＡＭサイクルの総数はｍ＋２ｎである。これは、ステップ３、４ａ、および４ｂにおけるサイクル数を足し合わせることで求められる。
【０１１９】
デュアルＲＡＭ装置
一般関数を実行するのに必要なＲＡＭサイクル数は、第２のＲＡＭを図６に示されているように装置に追加することによりさらに減らすことができる。「Ｚ−ＲＡＭ」と呼ばれる第１のＲＡＭ４４は、Ｚオペランドを格納する。Ｚ−ＲＡＭ４４は読取り−変更−書込み機能を備える。「Ｙ−ＲＡＭ」と呼ばれる第２のＲＡＭ４５は、Ｙオペランドを格納する。Ｙ−ＲＡＭ４５は読取り−変更−書込み機能を備えている必要はない。デュアルＲＡＭを使用すると、コントローラ４１はＹオペランドの１ワードの読取りとＺオペランドの１ワードの読取り−変更−書込みを同時に実行できる。この同時動作は１ＲＡＭサイクルタイムで実行される。
【０１２０】
コントローラ４１、ＬＩＵアレイ３９、およびＺ−ＲＡＭ４４の組み合わせは、図１の計算装置とともに使用することができるコプロセッサを備える。このような場合、Ｙ−ＲＡＭ４５は、図１に示されているように計算装置１１と共有することができる。
【０１２１】
デュアルＲＡＭ装置は、次の処理手順に従って一般関数Ｚ−Ｚ±（Ｘ*Ｙ）を実行し、ここで、Ｘ〜ｍワード、Ｙ〜ｎワード、およびＺ〜ｎワードである。
【０１２２】
１．コントローラ４１はＬＩＵアレイ３９のｃｌｒ入力を脈動する。
２．コントローラはＬＩＵアレイ減算入力をアクティブまたは非アクティブにする。コントローラは、この処理手順の残りの間、この値を一定に保つ。
３．コントローラはＹ−ＲＡＭ４５またはＺ−ＲＡＭ４４からｍ個の値を読み出して、ＬＩＵアレイのｘ｛０｝，ｘ｛１｝，．．．，ｘ｛ｍ−１｝入力に印加する。コントローラは、この処理手順の残りの間、これらの値を一定に保つ。
４．ｊ＝０，１，．．．，ｎ−１について、
ａ．コントローラは、Ｙ−ＲＡＭから値を読み取ってＬＩＵアレイのＹ入力に印加し、Ｚ−ＲＡＭから値を読み取ってＬＩＵアレイのＺ入力に印加し、ＬＩＵアレイのｃｌｋ信号を脈動、ＬＩＵアレイのａ出力の値を読み取ってＺ−ＲＡＭに書き込む。
【０１２３】
ステップ３で、コントローラはＲＡＭからＸオペランドのｍワードを読み取る。これに、ｍ  ＲＡＭサイクルを要する。
ステップ４ａで、コントローラはＲＡＭからＹオペランドのｎワードを読取り、ＲＡＭからＺオペランドのｎワードのそれぞれについて読取り−変更−書込み演算を実行する。これに、ｎ  ＲＡＭサイクルを要する。
【０１２４】
この処理手順に必要なＲＡＭサイクルの総数はｍ＋ｎである。これは、ステップ３および４ａにおけるサイクル数を足し合わせることで求められる。
【０１２５】
パイプライン化大整数ユニット
ＬＩＵ内のクリティカルパスは、乗算−累算演算のときにアレイ内の第１のｎ−１個のＬＩＵにおいて発生する。ここで、乗算器の部分積信号ｐｈはａ１の次の高い順位のＬＩＵの加算器に入る。このパスは加算器を通り、総和信号ｓとしてそのＬＩＵを抜けて、第２の加算器信号ａ２を通って元のＬＩＵに戻る。
【０１２６】
ロジックをパイプライン化すると、ＬＩＵの動作周波数を上げることができる。パイプライン化ＬＩＵを図７に示す。他のレジスタＲＥＧ１を導入することにより、クリティカルパスに沿った遅延が減少する。新しいレジスタは、乗算器の出力の上位部分積信号上に置かれる。これにより、クリティカルパスは、乗算器の遅延と加算の遅延を足したものからちょうど乗算器遅延に減少される。
【０１２７】
このレジスタの結果として、アレイの相互接続が変わる。パイプライン化ＬＩＵを備えたＬＩＵアレイを図８に示す。各ＬＩＵの上位部分積信号ｐｈは、ａ１において自身にフィードバックすることに注意されたい。信号ｐｈは、第１の加算器信号ａ１で１サイクルだけ遅れる。
【０１２８】
当業者であれば、乗算器も同様にパイプライン化できることを理解するであろう。それぞれのパイプライン段により待ち時間のサイクルが加わるが、動作周波数を高めるだけではこれを補正することはできない。実際、これらのレジスタを最適に配置する電子設計自動化ソフトウェアが入手可能である。コントローラを調整してＸ*Ｙの計算を進め、Ａ←Ｚ±（Ｘ*Ｙ）が正しく計算されるようにできる。
【０１２９】
デュアルポートＲＡＭ装置
乗算−累算（multiply-accumulate）演算以外の設計におけるクリティカルパスは、読取り−変更−書込み演算である。このパスは、シングルポートＲＡＭに代えてデュアルポートＲＡＭを使用することで低減できる。これは、完全デュアルポートＲＡＭではなく、むしろ単一書込みポート単一読取りポートＲＡＭであることに注意されたい。このタイプのＲＡＭによって、１つのアドレスから読み取ることができると同時に、一方で異なるアドレスに書き込むことができる。図９は、改良した装置の図である。
【０１３０】
デュアルポートＲＡＭを使用することにより、読取り−変更−書込み演算を３つの部分に分けられる。図１０にこれを示した。第１の部分は、読取り演算（Ｚ｛ｉ｝）、第２の部分は変更演算であり、Ｚ｛ｉ−１｝＝Ｚ｛ｉ−１｝＋／−Ｘ｛ｉ−１｝*Ｙ｛ｉ−１｝が形成される。第３の部分は、Ａ｛ｉ−２｝のＲＡＭへの書き戻しである。読取りアドレスは決して書込みアドレスと等しくならないので、それらの間の差は常にちょうど２である。このため、ａを書き込んでも、ｚで読み取っているデータに影響しない。このようにして、３つの部分はそれぞれ、完了するサイクル全体を持ち、最高動作周波数をかなり改善する。
【０１３１】
実現可能な別の手段として、変更および書込み演算を単一のサイクルにまとめるという方法がある。これにより、待ち時間は１サイクルだけ短縮し、いくつかの種類のＲＡＭについては、ＲＡＭに書き込むデータがそのサイクルの最後の部分についてのみ通常有効でなければならない程度に高速化することができる。ここでもやはり、読取りアドレスと書込みアドレスが異なるという要件が満たされている。
【０１３２】
特定の算術演算
前のセクションでは、ＹとＺをｎワードのオペランド、Ｘをｍワードのオペランド、そしてｍをＬＩＵアレイ内のＬＩＵの個数以下とした場合に、一般関数Ｚ←Ｚ±（Ｘ*Ｙ）を実行するために装置を使用する方法について説明した。この関数は、マルチプレシジョン演算およびモジュラ簡約で使用できる算術演算を実行するように特殊化させることができる。特殊化は、コントローラの、ＬＩＵアレイの制御信号およびデータ信号処理によって行われる。
【０１３３】
以下の説明では、このような算術演算の例をいくつか取りあげる。これらの例は、実行可能な演算のうちのごくわずかに過ぎず、可能なすべての算術演算を代表しているわけではない。
乗算：この装置を使用して、次の計算を実行することができる。
【０１３４】
Ｚ←Ｘ*Ｙ、
【０１３５】
ただし、Ｘ〜ｍワード、Ｙ〜ｋワード、Ｚ〜ｎワード、ｎ≧ｋである。
【０１３６】
Ｘ*Ｙの値が値が大きすぎてｎワード表現に収まらない場合にオーバーフローが発生する。ｎ≧ｋ＋ｍであれば、Ｘ*Ｙは常に収まる。ｎ＜ｋ＋ｍであれば、ＸおよびＹの値に応じてＸ*Ｙの値は収まる場合も収まらない場合もある。計算の終わりにおけるＬＩＵアレイのｃｙ出力の値は、オーバーフローが発生したかどうかを示す。
【０１３７】
シングルＲＡＭ装置を使用する処理手順を以下に示す。
【０１３８】
１．コントローラはＬＩＵアレイのｃｌｒ入力を脈動する。
２．コントローラはＬＩＵアレイの減算入力を非アクティブにし、ＬＩＵアレイのｚ入力に０を印加する。コントローラは、この処理手順の残りの間、これらの値を一定に保つ。
３．コントローラはＲＡＭからｍ個の値を読み出して、ＬＩＵアレイのｘ｛０｝，ｘ｛１｝，．．．，ｘ｛ｍ−１｝入力に印加する。コントローラは、ＬＩＵアレイの他のすべてのｘ｛  ｝入力に０を印加する。コントローラは、この処理手順の残りの間、これらの値を一定に保つ。
４．ｊ＝０，１，．．．，ｋ−１について、
ａ．コントローラは、ＲＡＭから値を読み取って、ＬＩＵアレイのｙ入力にその値を印加する。
ｂ．コントローラはＬＩＵアレイのｃｌｋ入力を脈動する。
ｃ．コントローラは、ＬＩＵアレイの出力の値を読み取って、ＲＡＭに書き込む。
５．コントローラは、ＬＩＵアレイのｙ入力に０を印加する。コントローラは、この処理手順の残りの間、この値を一定に保つ。
６．ｊ＝ｋ，ｋ＋１，．．．，ｎ−１について、
ａ．コントローラはＬＩＵアレイのｃｌｋ入力を脈動する。
ｂ．コントローラは、ＬＩＵアレイの出力の値を読み取って、ＲＡＭに書き込む。
【０１３９】
ステップ４ｃおよび６ｂにおいてＲＡＭに書き込んだ値は、望む結果のｚのワードである。
【０１４０】
この処理手順によって正しい答えが得られることを調べるために、それが一般関数Ｚ←Ｚ±（Ｘ*Ｙ’）を計算することと等価であることを観察する。ここで、Ｚの初期値は０のｎワード表現、Ｙ’はＹのｎワード表現である。
【０１４１】
読取り−変更−書込み装置を持つシングルＲＡＭ装置の処理手順は同一である。読取り−変更−書込み機能は、Ｚオペランドが書込みのみであって読取りを行わないため、利点がない。
【０１４２】
デュアルポートＲＡＭ装置の処理手順は、ステップ４ａがステップ４ｃと同時に実行される点を除いて類似している。
【０１４３】
各装置に必要なＲＡＭサイクルの数を表６にまとめた。
【０１４４】
【表６】
0004201980.tif 000007
【０１４５】
乗算−累算：この装置を使用して、次の計算を実行することができる。
【０１４６】
Ｚ←Ｚ＋（Ｘ*Ｙ）、
ここで、Ｘ〜ｍワード、Ｙ〜ｋワード、Ｚ〜ｎワード、ｎ≧ｋである。
【０１４７】
結果の値が大きすぎてｎワードに収まらない場合にオーバーフローが発生する。オーバーフローは、計算が終了したときのＬＩＵアレイのｃｙ出力上のアクティブな値で示される。
【０１４８】
シングルＲＡＭ装置を使用する処理手順を以下に示す。
【０１４９】
１．コントローラはＬＩＵアレイのｃｌｒ入力を脈動する。
２．コントローラはＬＩＵアレイ減算入力を非アクティブにする。コントローラは、この処理手順の残りの間、この値を一定に保つ。
３．コントローラはＲＡＭからｍ個の値を読み出して、ＬＩＵアレイのｘ｛０｝，ｘ｛１｝，．．．，ｘ｛ｍ−１｝入力に印加する。コントローラは、ＬＩＵアレイの他のすべてのｘ｛  ｝入力に０を印加する。コントローラは、この処理手順の残りの間、これらの値を一定に保つ。
４．ｊ＝０，１，．．．，ｋ−１について、
ａ．コントローラは、ＲＡＭから値を読み取ってＬＩＵアレイのｙ入力に印加する。
ｂ．コントローラは、ＲＡＭから値を読み取ってＬＩＵアレイのｚ入力に印加する。
ｃ．コントローラはＬＩＵアレイのｃｌｋ入力を脈動する。
ｄ．コントローラは、ＬＩＵアレイの出力の値を読み取ってＲＡＭに書き込む。
５．コントローラは、ＬＩＵアレイのｙ入力に０を印加する。コントローラは、この処理手順の残りの間、この値を一定に保つ。
６．ｊ＝ｋ，ｋ＋１，．．．，ｎ−１について、
ａ．コントローラは、ＬＩＵアレイのｃｙ出力の値を読み取る。値が非アクティブであれば、コントローラは処理手順を終了する。
ｂ．コントローラは、ＲＡＭから値を読み取ってＬＩＵアレイのｚ入力に印加する。
ｃ．コントローラはＬＩＵアレイのＣＬＫ入力を脈動する。
ｄ．コントローラは、ＬＩＵアレイの出力の値を読み取ってＲＡＭに書き込む。
【０１５０】
ステップ４ｃおよび６ｄにおいてＲＡＭに書き込んだ値は、望む結果のｚのワードである。
【０１５１】
この処理手順によって正しい答えが得られることを調べるために、一般関数Ｚ←Ｚ＋（Ｘ*Ｙ’）を計算することと同等であることを観察する。ここで、Ｙ’はＹのｎワード表現である。
【０１５２】
Ｚのｎワードすべてが新しい値で置き換えられる前にこの処理手順がステップ６ａで終了する場合がある。これは、置換後の値が置換前の値と同一であると処理手順によって認識された場合に発生する。処理手順を終了すると、効果のないサイクルを排除することによりＲＡＭサイクル総数が低減される。
【０１５３】
読取り−変更−書込み装置を持ったシングルＲＡＭの処理手順は、ステップ４ｂと４ｄが単一の読取り−変更−書込みサイクルで実行され、ステップ６ｂと６ｄが単一の読取り−変更−書込みサイクルで実行されることを除いて類似している。
【０１５４】
デュアルＲＡＭ装置の処理手順は、ステップ４ａがステップ４ｂおよび４ｄの読取り−変更−書込みサイクルと同時に実行されるという点を除いて、読取り−変更−書込み装置を持つシングルＲＡＭと似ている。
【０１５５】
各装置に必要なＲＡＭサイクルの数を表７にまとめた。
【０１５６】
【表７】
0004201980.tif 000008
【０１５７】
「≦」記号は、ステップ６ａで処理手順が早期に終了する可能性を反映している。
【０１５８】
乗算−否定−累算：この装置を使用して、次の計算を実行することができる。
【０１５９】
Ｚ←Ｚ−（Ｘ*Ｙ）、
【０１６０】
ここで、Ｘ〜ｍワード、Ｙ〜ｋワード、Ｚ〜ｎワード、ｎ≧ｋである。
【０１６１】
結果の値が負になるとアンダーフローが発生する。アンダーフローは、計算が終了したときのＬＩＵアレイのｃｙ出力におけるアクティブな値で示される。
【０１６２】
この処理手順は、減算入力がステップ２でアクティブにされ、非アクティブにはされないという点を除き、乗算−累算（multiply-accumlate）演算の処理手順と同一である。この処理手順は、Ｚのワードについての置換後の値が置換前の値と同じであると認識された場合に早期に終了する。ＲＡＭサイクルの数は、乗算−累算演算と同じである。
【０１６３】
モジュラべき乗への応用
Ａ、Ｂ、およびＰをそれぞれｎワードの整数とする。モジュラべき乗は、ＡB ％ Ｐを計算する問題である。モジュラべき乗を実行するよく知られ得ている手法に、モンゴメリの方法がある。Ｐ．Ｍｏｎｔｇｏｍｅｒｙ著「Ｍｏｄｕｌａｒ  Ｍｕｌｔｉｐｌｉｃａｔｉｏｎ  ｗｉｔｈｏｕｔ  Ｔｒｉａｌ  Ｄｉｖｉｓｉｏｎ」Ｍａｔｈｅｍａｔｉｃｓ  ｏｆ  Ｃｏｍｐｕｔａｔｉｏｎ，４４  （１９８５），ｐｐ．５１９〜５２１。この方法は、ＬＩＵアレイに基づく本装置に適している。
【０１６４】
本特許は、モンゴメリの方法のチュートリアルであることを意図していない。本発明を使用してこの方法を実施する方法を示し、ＲＡＭサイクルに関して実施速度を分析することのみを目的としている。
【０１６５】
モンゴメリの方法は、「モンゴメリ積」と呼ばれる関数に基づいている。Ｐを法とする２つの整数ＸとＹのモンゴメリ積は、次式で定義される。
【０１６６】
ｆ（Ｘ，Ｙ、Ｐ）＝（（Ｘ*Ｙ*Ｇ） ％ Ｐ）＋ｋＰ，
ただし、Ｇは（Ｇ*Ｗn） ％ Ｐ＝１を満たす整数で、ｋは小さな整数である。このような整数Ｇは、Ｐが奇数の場合に存在し、Ｐが偶数の場合には存在しない。したがって、モンゴメリの方法はＰが奇数の場合にのみ使用される。
【０１６７】
「ｋＰ」という項は、ｆ（）の値が０からＰ−１の範囲になければならないという要件を反映するために含まれている。これは、後で明確になる理由から望ましいものである。
【０１６８】
モンゴメリの方法を使用してモジュラべき乗を実行する処理手順は以下のとおりである。
【０１６９】
１．Ｔ←Ｗ2n ％ Ｐ
２．Ａ←ｆ（Ｔ，Ａ，Ｐ）
３．Ｔ←ｆ（Ｔ，１，Ｐ）
４．For each bit in Ｂ, most significant first, do:
ａ．Ｔ←ｆ（Ｔ，Ｔ，Ｐ）
ｂ．if the bit in Ｂ is１,Ｔ←ｆ（Ｔ，Ａ，Ｐ）
５．Ｔ←ｆ（Ｔ，１，Ｐ）
６．Ｔ←Ｔ ％ Ｐ
Ｔはｎワードの整数である。この処理手順が終了すると、ＴはＡB ％ Ｐの値を含む。
【０１７０】
ステップ４におけるループは指数Ｂのビット毎に反復する。Ｂがｎワードを持ち、各ワードはｂビットを持つので、ループはｎｂ回反復する。ステップ４ａにおけるモンゴメリ積は、ループの反復毎に計算される。ステップ４ｂにおけるモンゴメリ積は、指数の対応するビットが１ビットの場合にのみ計算される。指数のビットの半分が１ビットであれば、ステップ４ｂにおけるモンゴメリ積はループ反復の半分について計算される。この仮定を置くと、ループ中で実行されるモンゴメリ積の総数は１．５*ｎｂとなる。
【０１７１】
公開鍵暗号法では、指数のビット数が大きく、数百あるいは数千ビットになるのがふつうである。これは、べき乗を計算するにはモンゴメリ積計算を数百あるいは数千回実行する必要があるということを意味する。そのため、べき乗を高速に計算する鍵は、モンゴメリ積を高速で計算することである。
【０１７２】
ＬＩＵアレイに基づく本発明装置は、モンゴメリ積を効率よく計算することができる。次のセクションでは、この実行方法について説明する。
【０１７３】
ステップ１、２、および３は「計算前」ステップであり、ステップ５および６は「計算後」ステップである。これらのステップは、ステップ４に比べて計算量が非常に少なくて済み、無視できるくらいである。
【０１７４】
この処理手順を管理する責任は、コントローラおよび、装置がコプロセッサとして取り付けられている計算装置に分けることができる。システム設計者は、この責任をどのように分けるかということに関して裁量権がある。極端な場合、コントローラを処理手順のすべてのステップを実行できる充分な情報処理機能を受け持つように設計し、計算装置は単に処理手順を開始し、コントローラにオペランドの記憶場所を提供するだけということも考えられる。また、コントローラは一般関数Ｚ←Ｚ＋（Ｘ*Ｙ）のみを取り扱い、計算装置は、モンゴメリ積を構築し、上記の処理手順によりモジュラべき乗に組み立てる責を負うように設計することもできる。
【０１７５】
マルチプレシジョン乗算
モンゴメリ積ｆ（Ｘ，Ｙ，Ｐ）を計算する第１のステップは、ＸとＹの積を計算することである。この手続は、中学校で教わる通常の「乗算および加算」処理手順である。得られる積は表すのに２ｎワードを必要とし、ここで、ｎはＸ、Ｙ、およびＰのそれぞれのワード数である。
【０１７６】
表記は言い回しを簡単にするためだということで同意できるであろう。Ｘをｎワードの整数とする。表記Ｘ＝（ｘ｛ｊ｝，０≦ｊ＜ｎ）は、Ｘの値がｘ｛０｝＋ｘ｛１｝Ｗ＋ｘ｛２｝Ｗ2．．．＋ｘ｛ｎ−１｝Ｗn-1であることを意味する。Ｘの「部分整数（subinteger）」つまり、Ｘの連続するワードのサブセットから成り立つＸの整数部分の演算が行われる。たとえば、整数Ｘ’＝｛ｘ｛ｊ｝，２≦ｊ＜５｝は値ｘ｛２｝＋ｘ｛３｝Ｗ＋ｘ｛４｝Ｗ2を持つＸの３ワードの部分整数である。演算Ｘ’←Ｘ’＋１はｘ｛２｝をｘ｛２｝＋１で置き換える（ｘ｛２｝は小さく、オーバーフローを起こさないと仮定する）。これは、Ｘ｛２｝がＸにおいてＷ2によって重み付されているためＸをＷ2だけ増やす効果を持つ。
【０１７７】
ｍをＬＩＵアレイ内のＬＩＵの個数とする。ｎはｍの倍数であると仮定する。整数の長さは、０ワードを上位側に付加してｍの倍数にすることで常に増やすことができるため、一般性を失うことなくこのように仮定することができる。整数Ｚ、Ｚi、およびＸiは次のように定義できる。
【０１７８】
Ｚ ＝｛ｚ｛ｊ｝，０≦ｊ≦２ｎ｝；
Ｚi＝｛ｚ｛ｊ｝，ｉ≦ｊ＜ｉ＋ｎ＋ｍ｝；
Ｘ1＝｛ｘ｛ｊ｝，ｉ≦ｊ＜ｉ＋ｍ｝．
【０１７９】
Ｚは、計算された積を保持するために使用する２ｎ＋１ワードの整数である。Ｚ整数は、次のセクションで明らかになる理由から、必要な長さよりも１ワードだけ長くなっている。Ｚiは、ｚ｛ｉ｝で始まるｎ＋ｍワードを持つＺの部分整数である。Ｘiは、ｘ｛ｉ｝で始まるｍワードを持つＸの部分整数である。
【０１８０】
ＸとＹの積は、次の処理手順で計算することができる。
【０１８１】
１．Ｚ←０
２．ｉ←０
３．While (ｉ＜ｎ) do:
ａ．Ｚi←Ｚi＋（Ｘi*Ｙ）
ｂ．ｉ＝ｉ＋ｍ
【０１８２】
ステップ１で、Ｚを０にクリアする。次にステップ３におけるループで、「乗算および加算」を実行する。ループの反復毎に、Ｘオペランドのｍワードを処理する。これらのワードはＸiを形成し、これにオペランドＹを掛け、累算してＺiを求める。Ｚiは、ＸiがＸ内でオフセットされているワードの数と同じ数だけＺ内でオフセットされる。最後の反復の後、Ｚは望んでいた積Ｘ*Ｙを含む。
【０１８３】
演算Ｚi←Ｚi＋（Ｘi*Ｙ）の後のＺの値について考察する。Ｓｉ＝｛ｘ｛ｊ｝，０≦ｊ≦ｉ＋ｍ｝とすると、Ｘのｉ＋ｍワードが処理されているため、Ｚの値はＳi*Ｙである。Ｓi*Ｙはｎ＋ｍ＋ｉワードに収まる。ＺiはｉワードだけＺにオフセットされ、長さはｎ＋ｍなので、演算Ｚi←Ｚi＋（Ｘi*Ｙ）はオーバーフローすることがない。
【０１８４】
ループは、全部でｎ／ｍ回反復する。表８は、ループの反復毎にステップ３ａで必要なＲＡＭサイクルの数と、必要なＲＡＭサイクルの総数をまとめたものである。
【０１８５】
【表８】
0004201980.tif 000009
【０１８６】
ステップ３ａは、表に示されているよりも少ないサイクル数で済ますことができる。これは、ＬＩＵアレイのｃｙ出力が早期終了が受け付けられることを示している場合に発生する。実際には、この効果によるサイクル数の減少は、必要なサイクルの総数のごく数分の１に過ぎない。
【０１８７】
モンゴメリ簡約（Montgomery Reduction）
２ｎワードの積がＺに入ると、モンゴメリ積の第２のステップは、Ｐを法としてそれをｎワードの値に減らすことである。モンゴメリ簡約は右から左へ作用し、Ｚの一番右のワード（つまり、最下位ワード）が無効になるようにＰの適切な倍数がＺに加算される。
【０１８８】
この簡約は、次式を満たす整数Ｑを必要とする。
【０１８９】
（Ｑ*Ｐ） ％ Ｗm＝Ｗm−１.
【０１９０】
Ｑはｍワードの整数である。Ｐが奇数であれば、このようなＱは常に存在する。Ｑの計算は実に簡単である。Ｑはべき乗計算の最初に一度計算され、その後、べき乗の簡約ステップ毎に使用される。Ｑは、一度しか計算されないので、計算量はそれほどでもない。
【０１９１】
部分整数Ｚiは、乗算ステップで定義したのと異なる方法で定義することもできる。
【０１９２】
Ｚi＝（ｚ｛ｊ｝，ｉ≦ｊ≦２ｎ），
【０１９３】
つまり、Ｚiはｚ｛ｉ｝で始まるＺの部分整数であり、ｚ｛ｉ｝の左にあるＺのすべてのワードを含む。Ｚiは２ｎ＋１−ｉワードからなる。
【０１９４】
さらに、ｍワードの整数Ｖを定義する必要もある。Ｖはスクラッチ変数である。
【０１９５】
簡約ステップは、次の処理手順を用いて実行することができる。
【０１９６】
１．ｉ←０
２．While (ｉ＜ｎ) do:
ａ．Ｖ←Ｑ*Ｚi
ｂ．Ｚi←Ｚi＋（Ｖ*Ｐ）
ｃ．ｉ＝ｉ＋ｍ
【０１９７】
ステップ２におけるループの反復毎に、ステップ２ｂでＺのｍワードをクリアする。つまり、ワードｚ｛ｉ｝，ｚ｛ｉ＋１｝，．．．，ｚ｛ｉ＋ｍ−ｌ｝は０の値で終わる。このクリア動作は次の通りである。
【０１９８】
ステップ２ａにおいて、ＱにＺiを掛けて、その結果をＶに置く。ＱとＶはそれぞれｍワードの整数であるため、Ｚiの最下位ｍワード（つまり、｛ｚ｛ｊ｝，ｉ≦ｊ＜ｉ＋ｍ｝）だけが問題であり、Ｚiの他のワードは、いったんｍワードに切り詰められてＶに収まるようになると、その結果に影響しない。したがって、ステップ２ａは、「半乗算」として実行され、ｍワードの２つの整数は乗算されるが、積の下位ｍワードのみが計算される。
【０１９９】
ステップ２ｂにおいて、Ｖに法Ｐを掛けて、累算してＺiとする。ステップ２ａにおいて計算されたＶの値では、Ｚiの最下位ｍワードがそれぞれ０の値を持つ結果になる。Ｚiへの累算はオーバーフローしないことが保証されており、高い確率で、ＬＩＵアレイのｃｙ出力が非アクティブになるために累算は早期に終了する。終了する正確な時間はデータによって異なるが、Ｖはｍワードを、Ｐはｎワードを持つので、終了は通常はＺiのｎ＋ｍワードが累算された後になる。
【０２００】
ループは、全部でｎ／ｍ回反復する。表９は、ループの反復毎にステップ２ａと２ｂで必要なＲＡＭサイクルの数と、必要なＲＡＭサイクルの総数をまとめたものである。
【０２０１】
【表９】
0004201980.tif 000010
【０２０２】
ループの終わりにおいてＺ（つまり、｛ｚ｛ｊ｝，０≦ｊ＜ｎ｝）の下位ｎワードは値０をとり、Ｚ（つまり、ｚ｛２ｎ｝）の最上位ワードは０また１の値をとる。最上位ワードが１であれば、Ｚの上位ワードから次のようにＰを引いてクリアしなければならない。
【０２０３】
Ｚn←Ｚn−（１*Ｐ）
【０２０４】
ここで、本発明装置は、オペランドの１つを１に設定して「乗算−不定−累算」を実行するためにも使用される。この演算は、値０を持つＺの最上位ワードを生じることが保証されている。演算が必要かどうか（演算前にＺ｛２ｎ｝＝１かどうか）はデータによる。それとは関係なく、関係するＲＡＭサイクルの数は乗算および簡約のループに必要なサイクル数と比べるて無視できる。
【０２０５】
この時点で、Ｚは２ｎワードの整数であり、最下位ｎワードは値０を持つ。モンゴメリ積を完了するには、以下を実行する。
【０２０６】
Ｚ←Ｚn／Ｗn
【０２０７】
これは、Ｚの上位ｎワードを下位ｎワードに単に右シフトするだけのものである。得られる値はｎワードの整数であり、得られる値は所望されたモンゴメリ積である。
【０２０８】
この簡約処理手順ではＺがｎワード内に収まることを保証しているが、Ｚ＜Ｐであることは保証していない。ステップ４におけるべき乗処理手順のループを目的とするため、Ｚをｎワードに収まるために必要なもの以上にＺを簡約することは必要ではない。べき乗処理手順は計算後のステップ６を含み、最終結果をＰよりも小さい値に簡約する。
【０２０９】
総ＲＡＭサイクル
乗算および簡約ステップに必要なＲＡＭサイクル数に関する前のセクションの結果を表１０と組み合わせると、モンゴメリ積に対する単一の結果が得られる。この値に１．５ｎｂを掛けると、モジュラべき乗を計算するために必要なＲＡＭサイクル総数が求められる。
【０２１０】
【表１０】
0004201980.tif 000011
【０２１１】
べき乗の公式は、計算前および計算後のステップの間に、つまり、べき乗処理手順におけるステップ１、２、３、および５に必要なＲＡＭサイクルを無視している。これらのステップはステップ４に比べてＲＡＭサイクル数が非常に少なくて済み、無視することができる。
【０２１２】
オペランドがＬＩＵの個数に比べて大きい場合、ｎ／ｍは大きい。これは、実用的な公開鍵暗号法の応用のケースである場合が多い。このような場合、ＲＡＭサイクル数は約Ｋｂｎ3／ｍであり、Ｋは３つのタイプの装置についてそれぞれ９、６、または３である。したがって、ＲＡＭサイクルの総数は１／ｍに略比例する。たとえば、ＬＩＵの個数を倍にすることで、ＲＡＭサイクル数は半分程度に減少する。デュアルＲＡＭ装置は、シングルＲＡＭ装置が必要とするサイクル数のおおよそ１／３を必要とし、デュアルＲＡＭ装置は読取り−変更−書込み装置を持つシングルＲＡＭで必要なサイクル数の約半分を必要とする。
【０２１３】
本発明の範囲または精神から逸脱することなく本発明のマルチプレシジョン整数演算用の計算方法と装置にさまざまな変更を印加することができることは当業者であれば明白であり、特許請求の範囲およびその等価物の範囲内にあるとすれば本発明はマルチプレシジョン整数演算用の計算方法と装置の変更および変種をもその対象とすることを意図している。
【図面の簡単な説明】
添付の図面は、本明細書に含まれかつその一部をなしており、本発明の好ましい実施形態を示すものであり、説明とともに本発明の原理を説明するのに役立つ。
【図１】  計算装置を有するコプロセッサの図である。
【図２】  大整数ユニット（ＬＩＵ）を示す図である。
【図３】  相互接続されてＬＩＵアレイを形成する４つのＬＩＵを示すブロック図である。
【図４】  コントローラおよびランダムアクセスメモリ（ＲＡＭ）と組み合わされたＬＩＵアレイを示す図である。
【図５】  コントローラおよび読取り−変更−書込み機能を有するコントローラおよびＲＡＭと組み合わされたＬＩＵアレイを示す図である。
【図６】  コントローラ、第１のＲＡＭ、および第２のＲＡＭと組み合わされたＬＩＵアレイを示す図である。
【図７】  パイプライン化大整数ユニット（ＬＩＵ）を示す図である。
【図８】  相互接続されてＬＩＵアレイを形成する４つのパイプライン化ＬＩＵを示すブロック図である。
【図９】  デュアルポートＲＡＭ装置を示す図である。
【図１０】  デュアルポートＲＡＭとともに使用するための読取り−変更−書込み装置を示すブロック図である。
【図１】
0004201980.tif 000012
【図２】
0004201980.tif 000013
【図３】
0004201980.tif 000014
【図４】
0004201980.tif 000015
【図５】
0004201980.tif 000016
【図６】
0004201980.tif 000017
【図７】
0004201980.tif 000018
【図８】
0004201980.tif 000019
【図９】
0004201980.tif 000020
【図１０】
0004201980.tif 000021