« 2005年6月 | トップページ | 2005年8月 »

2005年7月の5件の記事

アクセスカウンタ設置


もう昨日になりますが、2005年7月26日に、アクセスカウンタを設置しました。

その際には、ブログ「blogの辺境 ~目指せblogの一市民~」のうち「ウェブログ・ココログ関連」の記事である「独自カウンタを設置する」と「今度はサイドバーへアクセスカウンタを設置する」との内容に全面的に依拠しました。

懇切な解説を書いて下さった「辺境」子と「カウンタ CGI」 GifCounter2 を作成して下さった「職人」さんとに感謝します。

| | コメント (0) | トラックバック (0)
|

米国特許5960411(ワンクリック特許)要約・発明の背景・独立クレーム


本件は、ビジネスモデル特許として著名な、Amazon.com, Inc. の所謂「ワンクリック特許」である。

米国特許 No.5,960,411 (Hartman, et al. September 28, 1999) の要約・発明の背景・独立クレームの訳文。

Method and system for placing a purchase order via a communications network

通信ネットワークを介した購入発注方法及びシステム


Abstract
A method and system for placing an order to purchase an item via the Internet. The order is placed by a purchaser at a client system and received by a server system. The server system receives purchaser information including identification of the purchaser, payment information, and shipment information from the client system. The server system then assigns a client identifier to the client system and associates the assigned client identifier with the received purchaser information. The server system sends to the client system the assigned client identifier and an HTML document identifying the item and including an order button. The client system receives and stores the assigned client identifier and receives and displays the HTML document. In response to the selection of the order button, the client system sends to the server system a request to purchase the identified item. The server system receives the request and combines the purchaser information associated with the client identifier of the client system to generate an order to purchase the item in accordance with the billing and shipment information whereby the purchaser effects the ordering of the product by selection of the order button.


要約
インターネットを介して商品品目を購入するための発注方法及びシステム。購入者による発注は、クライアント・システム側で行なわれ、受注はサーバー・システム側で行なわれる。サーバー・システムは、クライアント・システムから、購入者識別情報、支払い情報、発送情報などからなる購入者情報を受信する。次いで、サーバー・システムは、クライアント・システムに対し、クライアント識別子を付与し、付与されたクライアント識別子に、受信された購入者情報を付随させる。サーバー・システムは、付与されたクライアント識別子と、前記商品項目を確認し且つ注文ボタンを有する HTML 文書とを、クライアント・システムに送信する。クライアント・システムは、付与されたクライアント識別子を受信・記憶し、前記 HTML 文書を受信・表示する。前記注文ボタンの選択に応じて、クライアント・システムは、確認済商品項目を購入する旨の要求を、サーバー・システムに送信する。サーバー・システムは、前記要求を受信し、クライアント・システムのクライアント識別子に付随する購入者情報を組み合わせて、代金請求及び商品発送情報に従って前記商品項目を購入すると云う注文を生成することで、購入者が注文ボタンの選択により製品の注文が行なえるようにする。

TECHNICAL FIELD
The present invention relates to a computer method and system for placing an order and, more particularly, to a method and system for ordering items over the Internet.


BACKGROUND OF THE INVENTION
The Internet comprises a vast number of computers and computer networks that are interconnected through communication links. The interconnected computers exchange information using various services, such as electronic mail, Gopher, and the World Wide Web ("WWW"). The WWW service allows a server computer system (i.e., Web server or Web site) to send graphical Web pages of information to a remote client computer system. The remote client computer system can then display the Web pages. Each resource (e.g., computer or Web page) of the WWW is uniquely identifiable by a Uniform Resource Locator ("URL"). To view a specific Web page, a client computer system specifies the URL for that Web page in a request (e.g., a HyperText Transfer Protocol ("HTTP") request). The request is forwarded to the Web server that supports that Web page. When that Web server receives the request, it sends that Web page to the client computer system. When the client computer system receives that Web page, it typically displays the Web page using a browser. A browser is a special-purpose application program that effects the requesting of Web pages and the displaying of Web pages.

Currently, Web pages are typically defined using HyperText Markup Language ("HTML"). HTML provides a standard set of tags that define how a Web page is to be displayed. When a user indicates to the browser to display a Web page, the browser sends a request to the server computer system to transfer to the client computer system an HTML document that defines the Web page. When the requested HTML document is received by the client computer system, the browser displays the Web page as defined by the HTML document. The HTML document contains various tags that control the displaying of text, graphics, controls, and other features. The HTML document may contain URLs of other Web pages available on that server computer system or other server computer systems.

The World Wide Web is especially conducive to conducting electronic commerce. Many Web servers have been developed through which vendors can advertise and sell product. The products can include items (e.g., music) that are delivered electronically to the purchaser over the Internet and items (e.g., books) that are delivered through conventional distribution channels (e.g., a common carrier). A server computer system may provide an electronic version of a catalog that lists the items that are available. A user, who is a potential purchaser, may browse through the catalog using a browser and select various items that are to be purchased. When the user has completed selecting the items to be purchased, the server computer system then prompts the user for information to complete the ordering of the items. This purchaser-specific order information may include the purchaser's name, the purchaser's credit card number, and a shipping address for the order. The server computer system then typically confirms the order by sending a confirming Web page to the client computer system and schedules shipment of the items.

Since the purchaser-specific order information contains sensitive information (e.g., a credit card number), both vendors and purchasers want to ensure the security of such information. Security is a concern because information transmitted over the Internet may pass through various intermediate computer systems on its way to its final destination. The information could be intercepted by an unscrupulous person at an intermediate system. To help ensure the security of the sensitive information, various encryption techniques are used when transmitting such information between a client computer system and a server computer system. Even though such encrypted information can be intercepted, because the information is encrypted, it is generally useless to the interceptor. Nevertheless, there is always a possibility that such sensitive information may be successfully decrypted by the interceptor. Therefore, it would be desirable to minimize the sensitive information transmitted when placing an order.

The selection of the various items from the electronic catalogs is generally based on the "shopping cart" model. When the purchaser selects an item from the electronic catalog, the server computer system metaphorically adds that item to a shopping cart. When the purchaser is done selecting items, then all the items in the shopping cart are "checked out" (i.e., ordered) when the purchaser provides billing and shipment information. In some models, when a purchaser selects any one item, then that item is "checked out" by automatically prompting the user for the billing and shipment information. Although the shopping cart model is very flexible and intuitive, it has a downside in that it requires many interactions by the purchaser. For example, the purchaser selects the various items from the electronic catalog, and then indicates that the selection is complete. The purchaser is then presented with an order Web page that prompts the purchaser for the purchaser-specific order information to complete the order. That Web page may be prefilled with information that was provided by the purchaser when placing another order. The information is then validated by the server computer system, and the order is completed. Such an ordering model can be problematic for a couple of reasons. If a purchaser is ordering only one item, then the overhead of confirming the various steps of the ordering process and waiting for, viewing, and updating the purchaser-specific order information can be much more than the overhead of selecting the item itself. This overhead makes the purchase of a single item cumbersome. Also, with such an ordering model, each time an order is placed sensitive information is transmitted over the Internet. Each time the sensitive information is transmitted over the Internet, it is susceptible to being intercepted and decrypted.


技術分野
本発明は、コンピュータによる発注方法及びシステムに関し、特に、インターネットを介した商品項目の注文方法及びシステムに関する。


発明の背景
インターネットは、通信リンクを通じて相互接続された膨大な数のコンピュータ及びコンピュータ・ネットワークからなる。相互接続されたコンピュータは、電子メール、ゴーファー (Gopher)、ワールド・ワイド・ウェブ (WWW) などからなる様々なサービスに利用して情報を交換する。WWW サービスを用いると、サーバー・コンピュータ・システム(つまり、ウェブ・サーバー又はウェブ・サイト)は、情報を、グラフィカルなウェブ・ページの形で、遠隔クライアント・コンピュータ・システムへ送信できる。そうすることで、遠隔クライアント・コンピュータ・システムは、そうしたウェブ・ページを表示することができる。WWW の各リソース(例: コンピュータ又はウェブ・ページ)は、「統一資源ロケータ (Uniform Resource Locator)」(URL)により一意的に識別可能である。特定の或るウェブ・ページを閲覧する際、クライアント・コンピュータ・システムは、例えば「ハイパーテキスト転送プロトコル (HyperText Transfer Protocol)」(HTTP) 要求などのような要求において、そのウェブ・ページの URL を指定する。その要求は、そのウェブ・ページをサポートするウェブ・サーバーに送られる。前記要求を受信した前記ウェブ・サーバーは、そのウェブ・ページを、前記クライアント・コンピュータ・システムに送信する。前記ウェブ・ページを受信すると、前記クライアント・コンピュータ・システムは、典型的には、ブラウザを使って、そのウェブ・ページを表示する。ブラウザとは、ウェブ・ページを要求したり、ウェブ・ページを表示したりするのに目的を特化したアプリケーション・プログラムである。

現在のところ、ウェブ・ページは、典型的には、「ハイパーテキスト・マークアップ言語 (HyperText Markup Language)」(HTML) を使って定義される。HTML では、如何にしてウェブ・ページが表示されるべきかを定めるタグの標準的セットが提示されている。ユーザーが、ブラウザに、或るウェブ・ページを表示するよう指示すると、ブラウザは、そのウェブ・ページを定義する HTML 文書をクライアント・コンピュータ・システムに転送するようにと云う要求を、サーバー・コンピュータ・システムに送信する。要求された HTML 文書が、クライアント・コンピュータ・システムにより受信されると、ブラウザは、HTML 文書により定められている通りにウェブ・ページを表示する。HTML 文書は、テキスト、グラフィクス、コントロールその他の要素の表示を制御する様々なタグを含んでいる。そうした HTML は、そのサーバー・コンピュータ・システム又は他のサーバー・コンピュータ・システム上で閲覧可能な他のウェブ・ページの URL を含んでいることがある。

ワールド・ワイド・ウェブは、電子商取引を実施するのに特に適する。多くのウェブ・サーバーが、販売業者による製品の広告・販売を可能にする場として開発されている。そうした製品としては、購入者にインターネットを介して電子的に配達される品目(例: 音楽)もあれば、従来の配送経路(例: 運送業者)を通じて配達される品目(例: 書籍)もある。サーバー・コンピュータ・システムは、購入可能な商品項目を列挙した電子版カタログを提供することもある。潜在的には購入者であるユーザーは、そのようなカタログをブラウザで眺めて、購入すべき様々な商品項目を選択することができる。ユーザーが購入予定の品目選択を完了した際には、サーバー・コンピュータ・システムは、品目の注文を完了するための情報をユーザーが提供するよう促す。この購入者固有の注文情報には、購入者の名前、購入者のクレジットカード番号、注文に対する送り先アドレスが含まれうる。その際、サーバー・コンピュータ・システムは、典型的には、確認用ウェブ・ページをクライアント・コンピュータ・システムに送信することで注文の確認を行ない、そして商品項目発送の予定を組む。

購入者固有の注文情報は、取り扱いに注意を要する情報(例: クレジットカード番号)を含んでいるので、販売業者及び購入者双方とも、そうした情報の安全性を確保することを望む。インターネットを介して転送される情報は、その最終目的地に至る途中で様々な介在コンピュータ・システムを通過するから、安全性問題は重要である。情報は、介在システムにおいて、不道徳な人物が傍受してしまうかもしれないからだ。取り扱いに注意を要する情報の安全性確保の一助として、そうした情報をクライアント・コンピュータ・システムとサーバー・コンピュータ・システムとの間で転送する際には、様々な暗号技術が利用されている。そうした暗号化情報も傍受されうるとは言え、暗号化されているから、おおむね、傍受者の役には立たない。それでも、そうした取り扱いに注意を要する情報の暗号解読に、傍受者が成功する可能性は常にある。従って、発注の際には、取り扱いに注意を要する情報の転送を最小限にすることが望ましいと言える。

電子カタログから様々な商品項目を選択を行うのは、一般的に「ショッピング・カート」型モデルに基づいている。購入者が、電子カタログから或る商品項目を選択すると、サーバー・コンピュータ・システムは、その商品項目を、譬えて言うなら、ショッピング・カートに入れていく。購入者の商品項目選択が完了すると、購入者が、代金請求・発送情報を提供した時点で、ショッピング・カート中の全ての商品項目が「チェックアウト」(つまり、注文)される。購入者が、何か一つの商品項目を選択するたびに、自動的にユーザーに代金請求・発送情報の提供を促して、その商品項目の「チェックアウト」が行なわれるモデルも幾つかある。「ショッピング・カート」型モデルは、非常に柔軟かつ直感的で解かりやすいとはいえ、購入者に多くの情報交換を行うよう求めると云うマイナス面がある。例えば、購入者が電子カタログから様々な商品項目を選択し、次いで、選択が終了した旨を示した際、購入者には、注文完結のために、購入者固有の注文情報を提供するよう促す注文用ウェブ・ページが提示される。そうしたウェブ・ページには、他の発注を以前行った際に購入者が提供していた情報が予め書き込まれているようにできる。そうした情報は、サーバー・コンピュータ・システムにより有効性が確かめられてから、注文が完結する。こうした注文モデルには、二つの点で問題が発生しうる。まず、もし、購入者が注文しようとする品目が一つだけの場合、注文過程の様々なステップを確認し、購入者固有の注文情報の点検・更新を待機するオーバヘッドが、商品項目選択を行うオーバヘッド自体より、遥かに大きくなる可能性がある。このオーバヘッドは、単一の商品項目の購入を煩わしいものにする。また、こうした注文モデルにあっては、発注が行なわれる度に、取り扱いに注意を要する情報がインターネットを介して転送される。取り扱いに注意を要する情報がインターネットを介して転送される度に、傍受され暗号解読される可能性がある。

We claim:
1. A method of placing an order for an item comprising:

under control of a client system,

displaying information identifying the item; and

in response to only a single action being performed, sending a request to order the item along with an identifier of a purchaser of the item to a server system;

under control of a single-action ordering component of the server system,

receiving the request;

retrieving additional information previously stored for the purchaser identified by the identifier in the received request; and

generating an order to purchase the requested item for the purchaser identified by the identifier in the received request using the retrieved additional information; and

fulfilling the generated order to complete purchase of the item

whereby the item is ordered without using a shopping cart ordering model.


6. A client system for ordering an item comprising:

an identifier that identifies a customer;

a display component for displaying information identifying the item;

a single-action ordering component that in response to performance of only a single action, sends a request to a server system to order the identified item, the request including the identifier so that the server system can locate additional information needed to complete the order and so that the server system can fulfill the generated order to complete purchase of the item; and

a shopping cart ordering component that in response to performance of an add-to-shopping-cart action, sends a request to the server system to add the item to a shopping cart.


9. A server system for generating an order comprising:

a shopping cart ordering component; and

a single-action ordering component including:

a data storage medium storing information for a plurality of users;

a receiving component for receiving requests to order an item, a request including an indication of one of the plurality of users, the request being sent in response to only a single action being performed; and

an order placement component that retrieves from the data storage medium information for the indicated user and that uses the retrieved information to place an order for the indicated user for the item; and

an order fulfillment component that completes a purchase of the item in accordance with the order placed by the single-action ordering component.


11. A method for ordering an item using a client system, the method comprising:

displaying information identifying the item and displaying an indication of a single action that is to be performed to order the identified item; and

in response to only the indicated single action being performed, sending to a server system a request to order the identified item

whereby the item is ordered independently of a shopping cart model and the order is fulfilled to complete a purchase of the item.


クレーム
1. 商品項目の発注方法であって、

クライアント・システムの制御下にあって

前記商品項目を確認する情報を表示する段階と、

単一の動作が実行されただけで、前記商品項目を注文する旨の要求を、前記商品項目の購入者の識別子と共に、サーバー・システムに送信する段階と、

前記サーバー・システムの単一動作注文コンポーネントの制御下にあって、

前記要求を受信する段階と、

前記受信された要求中の前記識別子により識別される購入者に関して以前から記憶されていた付加的な情報を検索する段階と、

前記検索された付加的情報を用いて、前記受信された要求中の前記識別子により識別される購入者に関して、前記要求された商品項目を購入するための注文を生成する段階と、

前記生成された注文に応じた納品を行って、前記商品項目の購入を完結する段階からなることで、

ショッピング・カート型注文モデルを用いることなく、前記商品項目が注文されるようにすることを特徴とする商品項目発注方法。


6. 商品項目を注文するクライアント・システムであって、

顧客を識別する識別子と、

前記商品項目を確認する情報を表示する表示コンポーネントと、

単一の動作が実行されただけで、前記確認された商品項目を注文する旨の要求をサーバー・システムに送信し、前記要求には、前記サーバー・システムが、注文完結に必要な付加的情報の所在場所を探し出すことかでき、そして、前記サーバー・システムが、前記生成された注文に応じた納品を行って、前記商品項目の購入を完結するようができるようにするために、前記識別子がふくまれるようにしてなる単一動作注文コンポーネントと、

「ショッピング・カートへの投入動作」実行に応じて、ショッピング・カートに、前記商品項目を投入させる旨の要求を前記サーバ・システムに送信するショッピング・カート注文コンポーネントとからなることを特徴とする商品項目注文クライアント・システム。


9. 注文を生成するサーバー・システムであって、

ショッピング・カート注文コンポーネントと、

複数のユーザーに関する情報を記憶するデータ記憶媒体と、各々が前記複数のユーザーのうちの一人を指定する情報を含み、単一動作が実行されただけで送信される商品項目注文要求を受信する受信コンポーネントと、指定されたユーザーに関する情報を前記データ記憶媒体から検索し、前記検索された情報を、前記指定されたユーザーのために前記商品項目の発注を行うのに利用する発注コンポーネントとからなる単一動作注文コンポーネントと、

前記単一動作注文コンポーネントによる発注に従って前記商品項目の購入を完結する納品コンポーネントとからなることを特徴とする注文生成サーバー・システム。


11. クライアント・システムを用いて、商品項目を注文する方法であって、

前記商品項目を確認する情報を表示し、前記確認された商品項目を注文するために実行されるべき単一動作を指定する表示を行う段階と、

前記指定された単一動作が実行されただけで、前記確認された商品項目を注文する旨の要求を、サーバー・システムに送信する段階とからなることで、

前記商品項目が、ショッピング・カート型モデルとは独立して注文され、納品されて、前記商品項目の購入が完結することを特徴とするクライアント・システムを用いた商品項目注文方法。

| | コメント (0) | トラックバック (0)
|

立花 隆「臨死体験」中の誤植

文春文庫版「臨死体験(下)」(文藝春秋 東京 2000年3月10日第1刷 ISBN4-16-733010-5) の第72ページで「六つの炭素分子が輪になったベンゼン環(いわゆる亀の甲)の構造を思いついた」ドイツの化学者「ケフレ」なる人物が言及されているが、これは「ケクレ」に訂正すべきである。

これについては、例えば、ウィキペディアの「フリードリヒ・ケクレ」を参照。そこにも記されているように、ベンゼン分子が6員環構造を有することを着想したのは Friedrich August Kekulé von Stradonitz (1829-1896) である。ドイツ語 "Kekulé" の日本語音化に「ケフレ」は当てづらいだろう。また、一般でも「ケクレ」と云う表記が流通しているのに対し「ケフレ」はそうでないのは、それぞれをキーワードとしてネット検索してみれば判る。


該当するのは、第72ページに4ヶ所、対応する索引に1ヶ所あり、その全てで「ケフレ」となっている。

ここで言い添えておくと「臨死体験」は、好著と言ってよい。この扱いづらい対象を嗤わず嘆かず憎まずに迫って行って、結局は非神秘的解釈では判らないところが残ることを素直に認めている。しかし、こうして自己限定ができると云うことが、まさに立花隆が合理的(つまり、他者による構成的な理解が可能な)発想の持ち主であることを示しているのだ。

| | コメント (0) | トラックバック (0)
|

米国特許6286022(有限体の基底変換)独立クレーム


本件は、楕円曲線暗号等で用いられる有限体の基底変換計算の効率化に関する。

米国特許 No.6,286,022 (Kaliski, Jr. et al. September 4, 2001) の「独立クレーム」の訳。

What is claimed is:

1. An apparatus for determining elements in a dual of a normal basis for a finite field, the apparatus comprising:
an exponentiator which is operative to raise one of an input value and an output of a multiplier to a power; and
the multiplier which is operative to multiply one of the input value and an output of the exponentiator by a function of a generator of the dual basis, wherein the multiplier and exponentiator are configured to operate such that one of the multiplier and exponentiator generates an output value corresponding to a shifted version of the input value in the dual of the normal basis.

16. An apparatus for determining elements of a dual of a normal basis for a finite field, the apparatus comprising:
an exponentiator which raises an input value to a power, wherein the output of the exponentiator is applied to its input such that the exponentiator repeats the raising to a power operation a designated number of times; and
a multiplier which is operative to multiply an output of the exponentiator, generated after the designated number of repetitions, by a scaling factor which is a function of a (q-1).sup.st root of S, where S is a generator of the normal basis and q is a prime or a power of a prime, such that an output of the multiplier corresponds to an element of the dual of the normal basis.

19. An apparatus for determining elements of a dual of a normal basis for a finite field, the apparatus comprising:
an exponentiator which raises an input value to a power, wherein the output of the exponentiator is applied to its input such that the exponentiator repeats the raising to a power operation a designated number of times; and
a multiplier which is operative to multiply an output of the exponentiator, generated after the designated number of repetitions, by one of an initial value and a previously-generated output of the multiplier, such that a current output of the multiplier corresponds to an element of the dual of the normal basis.

25. A method for determining elements in a dual of a normal basis for a finite field, the method comprising:
exponentiating one of a signal corresponding to an input value and a signal corresponding to an output of a multiplier in an exponentiator; and
multiplying one of a signal corresponding to the input value and a signal corresponding to an output of the exponentiator by a function of a generator of the dual basis in the multiplier, wherein the multiplier and exponentiator are configured to operate such that one of the multiplier and exponentiator generates an output value corresponding to a shifted version of the input value in the dual of the normal basis.

26. A method for determining elements of a dual of a normal basis for a finite field, the method comprising:
raising a signal corresponding to an input value to a power in an exponentiator, wherein the output of the exponentiator is applied to its input such that the exponentiator repeats the raising to a power operation a designated number of times; and
multiplying an output of the exponentiator, generated after the designated number of repetitions, in a multiplier by a scaling factor which is a function of a (q-1).sup.st root of S, where S is a generator of the normal basis and q is a prime or a power of a prime, such that an output of the multiplier corresponds to an element of the dual of the normal basis.

27. A method for determining elements of a dual of a normal basis for a finite field, the method comprising:
raising a signal corresponding to an input value to a power in an exponentiator, wherein the output of the exponentiator is applied to its input such that the exponentiator repeats the raising to a power operation a designated number of times; and
multiplying an output of the exponentiator, generated after the designated number of repetitions, in a multiplier by one of an initial value and a previously-generated output of the multiplier, such that a current output of the multiplier corresponds to an element of the dual of the normal basis.

28. A method for determining elements in a dual of a normal basis for a finite field, the method comprising:
(a) multiplying a signal corresponding to an input value by a first function;
(b) raising a signal corresponding to a value resulting from step (a) to a power; and
(c) multiplying a signal corresponding to a value resulting from step (b) by a second function thereby generating an output value corresponding to a shifted version of the input value in the dual of the normal basis, wherein one of the first function and the second function is a function of a generator of the dual of the normal basis.


クレーム
1. 有限体の正規基底の双対基底により要素を決定する装置であって、
入力値又は乗算器の出力の一方を冪乗するよう動作する指数冪乗器からなり、
前記乗算器は、前記入力値又は前記指数冪乗器出力の一方に、双対基底生成元の関数を乗算し、前記乗算器と前記指数冪乗器とは、前記乗算器又は前記指数冪乗器の一方が、前記正規基底の双対基底に関して入力値をシフトしたものに対応する出力値を生成するよう構成されてなることを特徴とする有限体の正規基底の双対基底による要素決定装置。

16. 有限体の正規基底の双対基底の要素を決定する装置であって、
入力値を冪乗し、冪乗演算が指定回数繰り返されるよう自身の出力が自身の入力に印加される指数冪乗器と、
前記指定回数の繰り返し後に生成された前記指数冪乗器の出力に、q を素数又は素数の冪乗として、前記正規基底の生成元 S の (q-1) 乗根の関数である調整倍率を乗算して、出力が前記正規基底の双対基底の或る要素に対応するようにしてなる乗算器とからなることを特徴とする有限体の正規基底の双対基底の要素決定装置。


19. 有限体の正規基底の双対基底の要素を決定する装置であって、
入力値を冪乗し、冪乗演算が指定回数繰り返されるよう自身の出力が自身の入力に印加される指数冪乗器と、
前記指定回数の繰り返し後に生成された前記指数冪乗器の出力に、初期値又は自身の以前の出力の一方を乗算して、現在の出力が前記正規基底の双対基底の或る要素に対応するようにしてなる乗算器とからなることを特徴とする有限体の正規基底の双対基底の要素決定装置。

25. 有限体の正規基底の双対基底により要素を決定する方法であって、
指数冪乗器内において、入力値に対応する信号又は乗算器の出力に対応する信号の一方を指数冪乗する段階と、
前記乗算器内において、前記入力値に対応する信号又は前記指数冪乗器出力に対応する信号の一方に、双対基底生成元の関数を乗算するが、ここで前記乗算器及び前記指数冪乗器は、前記乗算器又は前記指数冪乗器の一方が、前記正規基底の双対基底に関して入力値をシフトしたものに対応する出力値を生成するよう構成されてなる段階とからなることを特徴とする有限体の正規基底の双対基底による要素決定方法。

26. 有限体の正規基底の双対基底の要素を決定する方法であって、
指数冪乗器内において、入力値に対応する信号を冪乗する際、前記指数冪乗器が冪乗演算を指定回数繰り返すよう、前記指数冪乗器出力を前記指数冪乗器入力に印加する段階と、
乗算器内において、前記指定回数の繰り返し後に生成された前記指数冪乗器の出力に、q を素数又は素数の冪乗として、前記正規基底の生成元 S の (q-1) 乗根の関数である調整倍率を乗算して、前記乗算器出力が前記正規基底の双対基底の或る要素に対応するようにする段階とからなることを特徴とする有限体の正規基底の双対基底の要素決定方法。

27. 有限体の正規基底の双対基底の要素を決定する方法であって、
指数冪乗器内において、入力値に対応する信号を冪乗する際、前記指数冪乗器が冪乗演算を指定回数繰り返すよう、前記指数冪乗器出力を前記指数冪乗器入力に印加する段階と、
乗算器内において、前記指定回数の繰り返し後に生成された前記指数冪乗器の出力に、初期値又は前記乗算器の以前の出力の一方を乗算して、前記乗算器の現在の出力が前記正規基底の双対基底の或る要素に対応するようにする段階とからなることを特徴とする有限体の正規基底の双対基底の要素決定方法。

28. 有限体の正規基底の双対基底により要素を決定する方法であって、
(a) 入力値に対応する信号に、第1の関数を乗算する段階と、
(b) (a) 段階の結果の値に対応する信号を冪乗する段階と、
(c) (b) 段階の結果の値に対応する信号に、第2の関数を乗算して、前記正規基底の双対基底に関して入力値をシフトしたものに対応する出力値を生成するが、ここで前記第1の関数又は前記第2の関数の一方が、前記正規基底の双対基底の生成元の関数であるようにしてなる段階とからなることを特徴とする有限体の正規基底の双対基底による要素の決定方法。

| | コメント (0) | トラックバック (0)
|

米国特許6286022(有限体の基底変換)発明の背景


本件は、楕円曲線暗号等で用いられる有限体の基底変換計算の効率化に関する。

米国特許 No.6,286,022 (Kaliski, Jr. et al. September 4, 2001) の「発明の背景」の訳文。


FIELD OF THE INVENTION

The present invention relates generally to techniques for converting signals of a finite field having one basis to signals of a finite field having another basis, and more particularly to finite field basis conversion techniques which involve a dual basis.

BACKGROUND OF THE INVENTION

As described in U.S. application Ser. No. 08/851,045, filed in the name of inventors Burton S. Kaliski Jr. and Yiqun Lisa Yin on May 5, 1997 and entitled "Methods and Apparatus for Efficient Finite Field Basis Conversion," and which is incorporated by reference herein, conversion between different choices of basis for a finite field is an important problem in today's computer systems, particularly for cryptographic operations. While it is possible to convert between two choices of basis by matrix multiplication, the matrix may be too large for some applications, hence the motivation for more storage-efficient techniques.

Elements of a finite field can be represented in a variety of ways, depending on the choice of basis for the representation. Let GF(q.sup.m) be the finite field, and let GF(q) be the ground field over which it is defined, where q is a prime or a prime power. The characteristic of the field is p where q=p.sup.r for some r.gtoreq.1. For even-characteristic fields, p=2. The degree of the field is m; its order is q.sup.m. A basis for the finite field is a set of m elements .omega..sub.0, . . . , .omega..sub.m-1 .epsilon.GF(q.sup.m) such that every element of the finite field can be represented uniquely as a linear combination of basis elements:

##EQU1##

where B[0], . . . , B[m-1] .epsilon. E GF(q) are the coefficients.

::本来の米国特許公報では、上記の ##EQU1## 相当部分に有限体の任意の要素が、基底の線型結合で表わされることを示す式が書かれている。

Two common types of basis are a polynomial basis and a normal basis. In a polynomial basis, the basis elements are successive powers of an element .gamma., called the generator:

.omega..sub.i =.gamma..sup.i.

A polynomial .function. of degree m, called the minimal polynomial of .gamma., relates the successive powers:

.gamma..sup.m +.function..sub.m-1.gamma..sup.m-1 +.function..sub.m-2.gamma..sup.m-2 + . . . +.function..sub.1.gamma.+.function..sub.0 =0.

In a normal basis, the basis elements are successive exponentiations of an element .gamma., again called the generator:

.omega..sub.i =.gamma..sup.q.sup..sup.i .

Another common type of basis is a dual basis. Let .omega..sub.0, . . . , .omega..sub.m-1 be a basis and let h be a nonzero linear function from GF(q.sup.m) to GF(q), i.e., a function such that for all .epsilon., .phi.,

h(.epsilon.+.phi.)=h(.epsilon.)+h(.phi.).

The dual basis of the basis .omega..sub.0, . . . , .omega..sub.m-1 with respect to h is the basis .xi..sub.0, . . . , .xi..sub.m-1 such that for all i,j,

##EQU2##

::本来の米国特許公報では、上記の ##EQU2## 相当部分に ωi と ξi との h に関する双対性を示す式が書かれている。

The dual basis is uniquely defined, and duality is syrnnetric: the dual basis with respect to h of the basis .xi..sub.0, . . . , .xi..sub.-1 is the basis .omega..sub.0, . . . , .omega..sub.m-1. A dual basis can be defined for a polynomial basis, a normal basis, or any other choice of basis, and with respect to a variety of functions (including, as an example, the function that evaluates to a particular coefficient of the representation of the field element in some basis).

::上記 ".xi..sub.-1" は --.xi..sub.m-1-- と読み替える。

The basis conversion or change-of-basis problem is to compute the representation of an element of a finite field in one basis, given its representation in another basis. The problem has two forms, which distinguish between the internal basis in which finite field operations are performed, and the external basis to and from which one is converting:

Import problem. Given an internal basis and an external basis for a finite field GF(q.sup.m) and the representation B of a field element in the external basis (the "external representation"), determine the corresponding representation A of the same field element in the internal basis (the "internal representation").

Export problem. Given an internal basis and an external basis for a finite field GF(q.sup.m) and the internal representation A of a field element, determine the corresponding external representation B of the same field element.

A conventional solution to both problems is to apply a change-of-basis matrix relating the two a bases. However, as the matrix is potentially quite large, and as the operations involved are not necessarily implementable with operations in either basis, the matrix-based conversion process may be inefficient in many important applications.

Another approach to conversion is to compute with a dual basis. Consider the problem of converting to the basis .omega..sub.0, . . . , .omega..sub.m-1, and let .xi..sub.0, . . . , .xi..sub.m-1 be its dual basis with respect to some linear function h. Then by the definition of the dual basis and the linearity of h, it follows that for all i,

B[]=h(.epsilon..xi..sub.i).

::上記の式の左辺で "B[]" を --B[i]-- と読み替える。

One can therefore convert by multiplying by elements of the dual basis and evaluating the function h, another straightforward and effective solution, which is efficient provided that the elements of the dual basis .xi..sub.0, . . . , .xi..sub.m-1 can be generated efficiently and that the function h can be computed efficiently. But this approach is again limited by a number of difficulties. First, the approach requires the elements of the dual basis, which must either be stored in the form of m.sup.2 coefficients, or computed. Second, it requires the computation of the function h, which may or may not be efficient. More practical choices of h have been suggested, such as a particular coefficient of the representation in some basis. See, for example, S. T. J. Fenn, M. Benaissa, and D. Taylor, "Finite Field Inversion Over the Dual Basis," IEEE Transactions on VLSI, 4(1):134-137, March 1996, which is incorporated by reference herein. But even with a more practical h, there still remains the problem of determining the dual basis efficiently. Moreover, the Fenn et al. method is efficient only when m is very small, and no general efficient conversion algorithm is given.

A number of other references describe finite field basis conversion operations involving dual basis. For example, U.S. Pat. No. 4,994,995, issued Feb. 19, 1991 to R. W. Anderson, R. L. Gee, T. L. Nguyen, and M. A. Hassner, entitled "Bit-Serial Division Method and Apparatus," describes hardware for a converter which converts an element in GF(2.sup.m) in a polynomial basis representation to a scalar multiple of its dual basis representation, where the scalar is an element of the field. The scalar is chosen so that the scalar multiple of the dual has many of the same elements as the polynomial basis. The hardware consists of AND gates, XOR gates, and a table for computing the trace function. Again, no general conversion algorithm is suggested. I. S. Hsu, T. K. Truong, L. J. Deutsch, and I. S. Reed, "A Comparison of VLSI Architecture of Finite Field Multipliers using Dual, Normal, or Standard Bases," IEEE Transactions on Computers, 37(6):735-739, June 1988, discloses conventional techniques for converting between polynomial and dual bases. D. R. Stinson, "On Bit-Serial Multiplication and Dual Bases in GF(2.sup.m)," IEEE Transactions on Information Theory, 37(6):1733-1737, November 1991, describes change-of-basis matrices between polynomial and dual bases. Given it polynomial basis such that the change-of-basis matrix M from the dual basis to some scalar (c.epsilon. GF(2.sup.m)) times the polynomial basis has as few "1" entries as possible, efficient bit-serial multiplication is possible. Given the minimal polynomial of .alpha., a generator of the polynomial basis, the Stinson reference gives simple formulae computing a scalar c and the weight of the matrix M. Although the above-cited references disclose numerous conventional techniques for converting between a polynomial basis and its dual basis, these techniques are generally inefficient in terms of memory, and may also be inefficient in terms of computation time.

The above-cited U.S. application Ser. No. 08/851,045 introduced the "shift-extract" technique of basis conversion, and also provided several storage-efficient and computation-efficient algorithms based on that technique for converting to and from a polynomial or normal basis. The conversion algorithms described therein overcome many of the problems associated with the previously-described conventional approaches. However, a need remains for further improvements in finite field basis conversion, particularly with regard to techniques involving dual basis.

It is therefore an object of the present invention to provide efficient finite field basis conversion techniques involving dual basis which do not require an excessively large amount of storage or an excessively large number of operations, and which take advantage of the built-in efficiency of finite field operations in one basis, rather than implementing new operations such as matrix multiplications.


発明の分野
本発明は、概括的には、或る基底を有する有限体の信号を、他の基底を有する有限体の信号に変換する技法に関し、特に、双対基底に関する有限体基底変換技法に関する。


発明の背景
Burton S. Kaliski Jr. 及び Yiqun Lisa Yin によって発明されたとして、1997年5月5日に出願された米国特許出願番号 08/851,045 "Methods and Apparatus for Efficient Finite Field Basis Conversion" (「効率的な有限体基底変換方法及び装置」) -- ここで参照することで、その内容が本明細書に編入されたものとする -- に記載されている如く、別々に選定された有限体基底間の変換は、現代のコンピュータ・システム、特に暗号演算のためのコンピュータ・システムにとり、重要な課題である。行列の乗算によるなら、選定された2つの基底間の変換は可能だとは言え、応用によっては行列は大規模になりすぎることがあるため、記憶効率が優れた技法が望まれていた。

有限体の要素は、選定される基底に応じて、様々に表現される。GF(qm) をそうした有限体、GF(q) をその基礎体とし(ただし、q は、素数又は素数の冪乗である)、体の標数を p とすると、q=pr かつ r≧1 なる r が存在する。標数が偶数の体では、p=2 となる。体の次数は m であり、位数は、qm である。有限体の基底とは、m 個の要素 ω0, . . . , ωm-1 ∈ GF(qm) からなる集合であって、有限体の全ての要素が、B[0], . . . , B[m-1] ∈ GF(q) を係数とする基底要素の線型結合

  ε =∑i=0m-1B[i]ωi

として一意に表わせるようなもののことである。


訳注::現在の cocolog は、数式の表現能力が貧弱で、上記も、総和記号が旨く表わせなかった。その意とするところは、B[i]ωi の i=0 から i=m-1 までの総和である。mimeTeX と云う CGI を使うと、html 文書においても TeX もどきの数式表現ができるらしいが、cocolog ではサポートされていないようだ。ちなみに「はてなダイアリー」では使えるとのこと。また、どのような実装によっているかは不明だが、Wikipedia でも、TeX による数式表示が可能である。

基底として良く知られているのは、多項式基底と正規基底の2種類である。多項式基底では、基底の要素は、生成元と呼ばれる或る要素 γ の逐次冪乗

   ωii

からなる。

前記の一連の冪乗を以下のように関連付ける γ の最小多項式と呼ばれる次数 m の多項式 f がある:

   γm + fm-1γm-1 + fm-2γm-2 + . . . +f1γ1 + f0 = 0

正規基底では、基底の要素は、やはり生成元と呼ばれる要素 γ の逐次指数乗

   ωiqi

からなる。

基底として、これらの他に良く知られているものとしては、双対基底がある。これを説明するために、まず ω0, . . . , ωm-1 を或る基底とし、h を、GF(qm) から GF(q) への零写像でない線型関数であるとする。つまり、すべての ε 及び φ に対して、

   h(ε+φ)=h(ε)+h(φ)

が成り立つものとする。

基底 ω0, . . . , ωm-1 の h に関する双対基底とは、全ての i, j に対して

   h(ωiξj) = 1 (i=j の時); 0 (i=j でない時)

を満たすような ξ0, . . . , ξm-1 のことである。

::本来の米国特許公報では、ωi と ξi との h に関する双対性を示す式は、場合分けを、大きな左ブレースを用いて表わしているが、現在の cocolog では、それが不可能なようなので、上記のように「= 1 (i=j の時); 0 (i=j でない時)」とした。この問題も、cocolog が mimeTeX (又は、TeX そのもの)をサポートすれば、解決されるはず。

双対基底は一意に定まる。また、双対性は対称的である。つまり、h に関する ξ0, . . . , ξm-1 の双対基底は、ω0, . . . , ωm-1 である。双対基底は、多項式基底にも、正規基底にも、その他の如何なる基底に対しても、そして、(例えば、体要素の或る基底における表現の特定の係数を評価する関数と云ったような)様々な関数に関して、定めることができる。

基底変換、つまり基底の変更とは、有限体の或る要素の或る基底に対する表現を、他の基底に対する表現から計算することである。有限体の演算が行なわれる内部基底と、変換先・変換元の外部基底とを区別すると、この課題は、2通りの形式で表わされる:

内部化: 有限体 GF(qm) の内部基底及び外部基底が与えられ、更に或る体要素の外部基底による表現 B (「外部表現」)が与えられた際に、前記要素の内部基底による対応表現 A (「内部表現」)を決定すること。

外部化: 有限体 GF(qm) の内部基底及び外部基底が与えられ、更に或る要素の内部表現 A が与えられた際に、前記体要素の対応外部表現 B を決定すること。

二つの課題に対する従来の解決策は、双方の基底に関する基底変換行列を適用することであった。しかし、この行列は非常に大規模になることがあり、また、必要となる演算が、基底のどちら側でも演算として実行に適するとは限らないため、行列に基づく変換方法は、多くの重要な応用において効率的でないことがあった。

変換を行う他の手法としては、双対基底でもって計算すると云うものがあった。基底 ω0, . . . , ωm-1 への変換を行う場合、或る線型関数 h に関するその双対基底を ξ0, . . . , ξm-1 とするなら、双対基底の定義及び h の線型性により、全ての i に対して、次の式が成り立つ。

   B[i]=h(εξi)

つまり、双対基底の要素を乗算し、関数 h を評価すると変換が行なえる訣だから、直接的で有効な解決策であり、双対基底要素 ξ0, . . . , ξm-1 が効率的に生成され、関数 h が効率的に計算できるなら、効率も良いものとなる。しかし、この手法にも、幾つかの制限がある。第1に、この手法では、双対基底の要素を m2 個の係数の形式で記憶しておくか、計算するかする必要がある。第2に、関数 h の計算が必要だが、これは効率的なことも非効率的なこともありうる。ある基底における表現の特定の係数と云うような、ヨリ実際的な h の選定も提案されている。例えば、S. T. J. Fenn, M. Benaissa 及び D. Taylor による "Finite Field Inversion Over the Dual Basis「双対基底上の有限体逆元決定」" (IEEE Transactions on VLSI, 4(1):134-137, 1996年3月) を見られたい(ここで参照することで、その内容が本明細書に編入されたものとする)。しかし、ヨリ実際的な関数 h によっても、双対基底を効率的に決定すると云う課題が残っている。更に「Fenn 他」の方法は、m が非常に小さい時にのみ効率的に過ぎず、包括的かつ効率的な変換アルゴリズムは知られていなかった。

双対基底を用いる有限体基底変換演算に就いて記載する文献は、ほかにも幾つかある。例えば、R. W. Anderson, R. L. Gee, T. L. Nguyen 及び M. A. Hassner による米国特許 4,994,995 "Bit-Serial Division Method and Apparatus「ビットシリアル除算方法及び装置」"(1991年2月19日)には、GF(2m) の要素の、多項式基底による表現を、その双対基底表現のスカラー倍(ただし、このスカラーは体の要素)に変換する変換器が記載されている。このスカラーは、双対をこのスカラー倍したものが、多項式基底と同一の要素を多く含むよう選定されている。この変換器は、AND ゲート群、XOR ゲート群、及びトレース関数を計算するための表からなる。やはり包括的ではない変換アルゴリズムであるが、I. S. Hsu, T. K. Truong, L. J. Deutsch 及び I. S. Reed による"A Comparison of VLSI Architecture of Finite Field Multipliers using Dual, Normal, or Standard Bases 「双対、正規又は標準基底を用いる有限体乗算器の VLSI アーキテクチャの比較」"(IEEE Transactions on Computers, 37(6):735-739, 1988年6月)では、多項式基底と双対基底との間を変換する従来技術が開示されている。D. R. Stinson による "On Bit-Serial Multiplication and Dual Bases in GF(2m)「GF(2m) におけるビットシリアル乗法と双対基底に就いて」" (IEEE Transactions on Information Theory, 37(6):1733-1737, 1991年11月)には、多項式基底と双対基底との間の基底変換行列に就いて記載されている。双対基底から多項式基底のスカラー(c ∈ GF(2m))倍への基底変換行列 M ができる限り少ない "1" 要素を有するような多項式基底に就いては、効率的なビットシリアル乗算が可能である。Stinson は、多項式基底の生成元 α の最小多項式が分っている場合に、スカラー c 及び行列 M の重みを計算する単純な公式を示している。上記の文献は、多項式基底とその双対基底との間を変換する様々な従来技術を開示しているが、こうした技術は、メモリーの観点からは概して非効率的であり、また計算時間の観点からも非効率的でありうる。

上記の米国特許出願番号 08/851,045 では、基底変換での「シフト・取り出し」技法が導入されて、その技法に基づく多項式基底又は正規基底への、又は多項式基底又は正規基底からの変換を行うことで記憶に就いても計算に就いても効率的なアルゴリズムが幾つか示されている。そこに記載されている変換アルゴリズムは、前記の従来手法に伴う問題点の多くを解消するものである。しかし、特に双対基底を用いる技法に関しては、有限体基底変換に対する一層の改善が必要であった。

従って、本発明の目的は、行列乗算のような演算を別途実装せずに、一つの基底における有限体演算の本来的な効率性を活用するることで、過度に大容量の記憶や過度に多数の演算を必要としない、双対基底を用いる有限体基底変換技術を提供することにある。

| | コメント (0) | トラックバック (0)
|

« 2005年6月 | トップページ | 2005年8月 »