TAILIEUCHUNG - A Fast Algorithm for Modular Reduction

We also present a variant of the algorithm that performs modular multiplication by interleaving the shift-and-add and the modular reduction steps. The modular multiplication algorithm can be used to obtain efficient VLSI implementations of exponentiation cryptosystems. | A Fast Algorithm for Modular Reduction C. K. Kog t Electrical and Computer Engineering Oregon State University Corvallis Oregon 97331 USA C. Y. Hung DSP R D Center Texas Instruments Inc. Dallas Texas 75265 USA Abstract We present an algorithm for computing the residue R X mod M. The algorithm is based on a sign estimation technique that estimates the sign of a number represented by a carry-sum pair produced by a carry save adder. Given the n k -bit X and the n-bit M the modular reduction algorithm computes the n-bit residue R in O k logn time and is particularly useful when the operand size is large. We also present a variant of the algorithm that performs modular multiplication by interleaving the shift-and-add and the modular reduction steps. The modular multiplication algorithm can be used to obtain efficient VLSI implementations of exponentiation cryptosystems. Key Words Carry save adder sign estimation technique division modular multiplication. 1 Introduction Arithmetic operations with long operands are often carried out using redundant representations in order to avoid a full-length carry propagation delay. In the modular reduction operation X mod M we need to compare X with some integer multiple q of M or equivalently calculate the sign of X qM . However in a redundant representation the sign of a number may not be readily available. In particular when the carry save addition technique is used the precise determination of the sign of an n-bit number represented by a carry-sum pair requires the computation of the total sum which takes O n time with a carry propagate adder. We present an improved version of the sign estimation technique 13 for detecting the sign of a number represented in the form of a carry-sum pair. The sign estimation technique was used to obtain fast algorithms for multi-operand modular addition 13 and modular multiplication 12 14 operations. The improved sign estimation algorithm presented here correctly computes the sign of the number .

• Toán học
• Carry save adder
• Sign estimation technique
• The Modular multiplication
• The Sign Estimation Technique
• The Modular Reduction Algorithm
• Implementation and Application
• Journal of technology and science education
• The design and implementation
• Arabic pronunciation application
• International University of La Rioja
• Attains better academic performance
• Vestyna application at PT XYZ
• COBIT 5 framework
• Process Assessment Model
• Standard Operating Procedure
• Application of the vesty
• Web engineering
• Introduction to web engineering
• Web applications
• Web application development
• Testing web application
• System implementation
• Business system development
• Information systems
• Information systems analysis
• Application software
• Systems development
• Journal of Automation and Control Engineering
• The implementation of controlled humanoid robot with android
• Controlled humanoid robot
• Android control application
• Servo motors control
• Doctoral thesis in Business Administration
• Key factors of the successful implementation
• Statistical Process Control
• Manufacturing enterprises
• Application of PMS
• Application of occupational safety and health
• OSH in vocational schools
• Health and safety
• Aspects of OSH implementation
• Socialization of OSH
• Web technologies
• Web programming
• Computer programming
• Web development technologies
• Modeling web applications
• Exchange Application
• State based Exchange
• assistance and consultation
• operational implementation
• Exchange beginning
• development activities
• báo cáo khoa học
• báo cáo hóa học
• công trình nghiên cứu về hóa học
• tài liệu về hóa học
• cách trình bày báo cáo
• Tangible User Interfaces
• Broader Context
• Application Domains
• Frameworks
• Taxonomies
• Conceptual Foundations
• Implementation Technologies
• Expanding Core Revenue
• Membership and Sponsorship
• Mission Integral
• spread application
• relationship capital
• product innovation
• Systems analysis
• Systems design
• Systems planning
• Systems implementation
• Requirements modeling
• Joint application development
• Database processing
• SQL for database construction
• Application processing
• Database redesign
• Managing multiuser databases
• Managing databases
• Industry Revolution 4 0
• SME business processe
• PT Faco Global Engineering
• Open source ERP application
• Bill of material tab components