34980398
Efficient Checkers for Number-Theoretic Computations
Blum has recently proposed a new approach to the problem of program correctness, the program checker. Here, efficient program checkers are presented for two important number theory problems, integer GCD and modular exponentiation. The former result answers an open problem posed by Blum. The latter result paves the way for more robust cryptographic programs, as modular exponentiation is the basis for several cryptosystems. Taken together, these results lay the foundation for more reliable number-theoretic programs.
31352363
Some Computational Problems of Cryptographic Significance Concerning Elliptic Curves over Rings
Elliptic curves over the ring Zn were first employed by Lenstra [Len1, Len2] to present his algorithm on factorization of integers. These curves have also been used to construct new public-key cryptographic schemes [Dem, Koy, KMOV, Men]. Elliptic analogs of the RSA-scheme have been proposed in [Dem, Koy, KMOV], and an elliptic analog of Rabin-type scheme has been proposed in [KMOV]. In this paper we consider the following computational problems of cryptographic significance concerning elliptic curves over the ring Zn with n being square-free: (1) Given an odd positive integer n, and integers a, b such that 4a+27b is prime to n, to compute the number of rational points on the elliptic curve E defined by Y=X +aX+b over Zn . (2) Given an odd positive integer n, integers a, b with 4a+27b prime to n, and a point P=(u, v) on the elliptic curve E defined by Y=X+aX+b over Zn , where u, v # Zn , to find a rational point Q on E such that 2Q=P.
40799553
Function Field Sieve Method for Discrete Logarithms over Finite Fields
We present a function field sieve method for discrete logarithms over finite fields. This method is an analog of the number field sieve method originally developed for factoring integers. It is asymptotically faster than the previously known algorithms when applied to finite fields Fpn, where p6?n.
7442937
SEED: Scalable, efficient enforcement of dependences
Instruction issue logic is a critical component in modern high-performance out-of-order processors. The ever increasing latencies found in modern processors, mostly associated with memory accesses and longer pipelines, can be attenuated using large issue queues. Conventional designs rely on atomic wakeup-select cycles to ensure compact scheduling. These designs must aggressively utilize broadcasting, compaction, and heavily-ported structures that scale poorly in terms of both power consumption and access time. To provide high scheduling flexibility and large instruction capacity without incurring prohibitive latency and energy overhead, we propose a novel scheme that uses an out-of-order, broadcast-free instruction wakeup block feeding an in-order scheduler. Multi-banked, index-based structures are used throughout this scheme to provide a high degree of scalability while achieving efficient dependence tracking, resulting in good overall performance and energy efficiency. We call this design "Scalable, Efficient Enforcement of Dependences (SEED)". We present a detailed design and analysis of SEED through an extensive evaluation. Compared to a conventional issue queue design, which is assumed favorably to scale in size without any impact on cycle time, the performance degradation of our design is 3% for both INT and FP suites of SPEC CPU2000. For such a small performance cost, SEED enjoys a 19% reduction in total chip power consumption for a 32-entry configuration. We also synthesize SEED and a conventional issue logic with 90nm standard cell logic. Synthesis results show that SEED can cycle twice the speed of a conventional issue logic of equivalent size. Cycling at the same frequency, SEED consumes ten times less dynamic power and five times less static power while achieving substantial area savings.
39737048
Creating a Visual Interface for Navigating Large UDDI Business Registries
This paper introduces a framework of a 20 visual interface for interactive navigating of UDDI Business Registries to discover appropriate services for the service requester among the available Web Services. By creating a 20 interactive visual interface, users are able to visually navigate through the large information hierarchies that are usually used to present the UDDI Business Registries, instead of using the traditional keywords or click-through searching methodologies which are often inefficient and less obvious. Several visualization techniques can be employed to achieve this objective, Image-Map used in this case. A simplified web-based UDDI business registry prototype with visual interface has been developed by using some open source technologies, such as, MySQL for backend data source layer, Apache HTTP server with PHP for business logic layer and dynamic ImageMap visualization with XHTML and client side scripting language JavaScript for presentation layer.
6607773
DMDC: Delayed Memory Dependence Checking through Age-Based Filtering
One of the main challenges of modern processor design is the implementation of a scalable and efficient mechanism to detect memory access order violations as a result of out-of-order execution of memory instructions. Traditional CAM-based associative queues can be very slow and energy hungry. In this paper we introduce two new management schemes. The first one is a filtering scheme based on simple age-tracking. This scheme can easily avoid 95-98% of associative load queue (LQ) searches using only a few registers. This translates into significant power savings. More importantly, however, this filtering makes our second scheme, delayed memory dependence checking (DMDC), practical. With a small hash table, DMDC completely avoids the need for an associative LQ and relies on indexing-based checking at the commit phase and hence cuts the energy spent on LQ by an average of 95%. At an average of about 0.3%, the performance impact is negligible. When the energy cost of the increased execution time is factored in, the processor still makes net energy savings of about 3-8%, depending on the configuration and the applications
11321138
Attributed graph visualization of collaborative workspaces
Collaborative workspaces are becoming increasingly commonplace, particularly in large, distributed organizations where virtual teams formed in order to jointly carry out collaborative project work. Typical collaborative workspaces often have a large number of objects and relations as well as their associated domain-specific attributes. The visualization of these domain-specific attributes is the challenge of this research. This paper presents a new approach for visualizing the attributes of objects and relations in collaborative workspaces. This new visualization provides not only a structural view of the collaborative workspaces but also a graphical view of a variety of domain-specific attributes associated with collaborative objects and relations. This paper also describes a framework for the attributed visualization of collaborative workspaces.
34970182
Application-oriented Spatial Graph Grammars
The Reserved Graph Grammar (RGG) is a general graph grammar Jormalism that expresses a wide range oj visual languages, This paper presents an extension to RGG with the capability oj spatial specification, Graph transJormation satisfying the spatial specification can be performed in the process oj parsing. The RGG with spatial specification can be applied to various types oj applications, The paper demonstrates an exampleJor mathematical expression recognition.