ANSI-X9.80-2005.pdf
《ANSI-X9.80-2005.pdf》由会员分享,可在线阅读,更多相关《ANSI-X9.80-2005.pdf(45页珍藏版)》请在三一文库上搜索。
1、 American National Standard for Financial Services X9.802005 Prime Number Generation, Primality Testing, and Primality Certificates Accredited Standards Committee X9, Incorporated Financial Industry Standards Date Approved: August 15, 2005 American National Standards Institute American National Stan
2、dards, Technical Reports and Guides developed through the Accredited Standards Committee X9, Inc., are copyrighted. Copying these documents for personal or commercial use outside X9 membership agreements is prohibited without express written permission of the Accredited Standards Committee X9, Inc.
3、For additional information please contact ASC X9, Inc., P.O. Box 4035, Annapolis, Maryland 21403. Copyright American National Standards Institute Provided by IHS under license with ANSI Licensee=USN Ship Repair Facility Yokosuka/9961031100 Not for Resale, 05/08/2007 20:35:28 MDTNo reproduction or ne
4、tworking permitted without license from IHS -,-,- ANS X9.802005 ii ASC X9, Inc. 2005 All rights reserved Foreword Approval of an American National Standard requires verification by ANSI that the requirements for due process, consensus, and other criteria for approval have been met by the standards d
5、eveloper. Consensus is established when, in the judgment of the ANSI Board of Standards Review, substantial agreement has been reached by directly and materially affected interests. Substantial agreement means much more than a simple majority, but not necessarily unanimity. Consensus requires that a
6、ll views and objections be considered, and that a concerted effort be made toward their resolution. The use of American National Standards is completely voluntary; their existence does not in any respect preclude anyone, whether he has approved the standards or not from manufacturing, marketing, pur
7、chasing, or using products, processes, or procedures not conforming to the standards. The American National Standards Institute does not develop standards and will in no circumstances give an interpretation of any American National Standard. Moreover, no person shall have the right or authority to i
8、ssue an interpretation of an American National Standard in the name of the American National Standards Institute. Requests for interpretations should be addressed to the secretariat or sponsor whose name appears on the title page of this standard. CAUTION NOTICE: This American National Standard may
9、be revised or withdrawn at any time. The procedures of the American National Standards Institute require that action be taken to reaffirm, revise, or withdraw this standard no later than five years from the date of approval. Published by Accredited Standards Committee X9, Incorporated Financial Indu
10、stry Standards P.O. Box 4035 Annapolis, MD 21403 USA X9 Online http:/www.x9.org Copyright 2005 ASC X9, Inc. All rights reserved. No part of this publication may be reproduced in any form, in an electronic retrieval system or otherwise, without prior written permission of the publisher. Printed in th
11、e United States of America. Copyright American National Standards Institute Provided by IHS under license with ANSI Licensee=USN Ship Repair Facility Yokosuka/9961031100 Not for Resale, 05/08/2007 20:35:28 MDTNo reproduction or networking permitted without license from IHS -,-,- ANS X9.802005 ASC X9
12、, Inc. 2005 All rights reserved iii Contents Forewordii Tables.v Introductionvi 1 Scope1 2 Normative references2 3 Terms and definitions .2 4 Symbols and abbreviated terms4 5 Prime Generation Methods.5 5.1 General Discussion.5 5.2 Generation of Primes Using Random Integers.7 5.2.1 Generation of Rand
13、om Primes with Sequential Search7 5.2.2 Generation of Random Primes with Uniform Distribution 8 5.2.3 Testing Using Probabilistic Methods 8 5.2.4 Testing Using Deterministic Methods.11 5.3 Constructive Methods.16 5.3.1 Shawe-Taylors Algorithm 16 5.3.2 Maurers Algorithm17 5.4 Side Conditions for Gene
14、rating Primes using Random Integers.19 6 Candidate Prime Testing Methods.20 7 Tables of Parameters 21 7.1 Rounds Required for Miller-Rabin if Followed by Lucas.21 7.2 Rounds Required for Frobenius-Grantham21 Annex A (normative).23 A.1 Modular Exponentiation23 A.2 Jacobi Symbol .23 A.3 Sieve Procedur
15、e.25 A.4 Algorithms for Polynomial Arithmetic.26 A.5 Lucas Sequence 28 Annex B (informative) 30 B.1 Discussion of General Prime Proving Methods .30 B.2 Discussion of the Distribution of Randomly Chosen Primes.30 Annex C Summary of Changes from ANS X9.802001 (informative)31 C.1 Introduction31 C.2 Tec
16、hnical changes.31 C.2.1 Search Range for primes31 C.2.2 Errors in Jacobi symbol algorithm31 C.2.3 Range of bases in Miller-Rabin test.32 C.2.4 Perfect squares in Lucas test.32 C.2.5 Discriminants with Jacobi symbol 0 in Lucas test 32 C.2.6 Boundary conditions in Shawe-Taylors algorithm .32 C.3 Edito
17、rial issues33 C.3.1 Random bit generators .33 Copyright American National Standards Institute Provided by IHS under license with ANSI Licensee=USN Ship Repair Facility Yokosuka/9961031100 Not for Resale, 05/08/2007 20:35:28 MDTNo reproduction or networking permitted without license from IHS -,-,- AN
18、S X9.802005 iv ASC X9, Inc. 2005 All rights reserved C.3.2 Failure probability .33 C.3.3 Lucas-Lehmer vs. Lucas.33 C.3.4 Reference for combining Miller-Rabin and Lucas tests33 C.3.5 Versions of Shawe-Taylor.33 C.3.6 Binary expansions.33 C.3.7 Modulo p division in Lucas sequence algorithm.33 C.3.8 Ne
19、gative numbers in Lucas sequence example 33 C.3.9 Added Interval34 Bibliography35 Copyright American National Standards Institute Provided by IHS under license with ANSI Licensee=USN Ship Repair Facility Yokosuka/9961031100 Not for Resale, 05/08/2007 20:35:28 MDTNo reproduction or networking permitt
20、ed without license from IHS -,-,- ANS X9.802005 ASC X9, Inc. 2005 All rights reserved v Tables Table 1: An ECPP certificate for p = 377681287. 16 Table 2: Rounds Required for Miller-Rabin. 21 Table 3: Rounds Required for Frobenius-Grantham. 21 Copyright American National Standards Institute Provided
21、 by IHS under license with ANSI Licensee=USN Ship Repair Facility Yokosuka/9961031100 Not for Resale, 05/08/2007 20:35:28 MDTNo reproduction or networking permitted without license from IHS -,-,- ANS X9.802005 vi ASC X9, Inc. 2005 All rights reserved Introduction NOTE The users attention is called t
22、o the possibility that compliance with this standard may require use of an invention covered by patent rights. By publication of this standard, no position is taken with respect to the validity of this claim or of any patent rights in connection therewith. The patent holder has, however, filed a sta
23、tement of willingness to grant a license under these rights on reasonable and nondiscriminatory terms and conditions to applicants desiring to obtain such a license. Details may be obtained from the standards developer. Suggestions for the improvement or revision of this Standard are welcome. They s
24、hould be sent to the X9 Committee Secretariat, Accredited Standards Committee X9, Inc., Financial Industry Standards, P.O. Box 4035, Annapolis, MD 21403 USA. This Standard was processed and approved for submittal to ANSI by the Accredited Standards Committee on Financial Services, X9. Committee appr
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- ANSI X9 80 2005
链接地址:https://www.31doc.com/p-3729393.html