While it is commonly believed RSA requires two primes p and q, that is incorrect. Infinite examples of RSA encryption moduli n=pq exist with p and/or q composite that generate correct RSA keys. This can be explained in the undergraduate cryptography classroom with support from public domain technologies like the python numbthy library and the Gephi graph processor.

Once you introduce RSA and probabilistic primality testing to your cryptography class, one of your brighter students will ask "What happens if the test is wrong?" It turns out the answer can vary from "You'll find out immediately" to "It makes no difference" to "It depends". We explain the mathematics that determine where the answer lies, and illustrate with examples suitable for use in the undergraduate classroom. We conclude by showing how to construct a key pair that produces correct RSA results from composite numbers p and q, and thus whose composite nature is not detectable through RSA encryption and decryption alone.

IRONSIDES is an open-source Domain Name System (DNS) server designed using formal methods to reduce DNS vulnerabilities to cyber attacks. The use of formal methods gives IRONSIDES provable security properties, including the absence of numerous security flaws that plague BIND and Windows DNS. It also raises an empirical question: Does the use of formal methods to generate provably secure code require sacrificing performance? We present the results of an experimental investigation to answer this question. We compared IRONSIDES to BIND, Windows DNS, and numerous other DNS servers on both Windows and Unix. Our results show IRONSIDES performs quite well compared to other DNS servers, both proprietary and open-source, particularly given the resources expended in its development. This suggests that, at least in the DNS domain, increasing security with formal methods to render them less vulnerable to cyber attacks does not require sacrificing performance.

We describe the development of IRONSIDES, an implementation of DNS that is provably invulnerable to remote code execution exploits and single-packet denial of service attacks. Our experimental results show it to be over three times as fast as BIND, the most common implementation of DNS.

MyTuringTable is a Turing Machine simulator designed to help students read and understand Turing's seminal 1937 paper on computability. We discuss our reasons for developing the tool, and report on its use in a "Great Ideas in Computer Science" course for the Air Force Academy Cadet Scholars program.

ABET-based program outcomes are the skills and knowledge that a student successfully completing the program has obtained at the time of graduation. For a Computer Science program, many of these outcomes require a developmental progression of learning experiences that are best provided incrementally across courses. Achievement of such a progression is predicated on a cooperative effort by faculty to define effective approaches to realizing the outcomes. However, the progression must also minimize demands on individual courses and eliminate unnecessary restrictions on faculty discretion in course design and implementation. In addition, a time-phased assessment plan should be overlaid upon the progression to measure and track the developmental process. This work documents our effort to define a developmental progression in our computer science program to better achieve ABET-based outcomes, integrate the progression into an existing curriculum in a minimally invasive manner, and incrementally assess the effectiveness of the approach.

In this paper, we describe a programmable emulator for the Princeton IAS/Von Neumann machine. The emulator is historically accurate, preserving the quirks and eccentricities of the machine. It is also user-friendly and robust, suitable for undergraduate architecture and programming classes as a teaching tool. Users can write non-trivial programs in IAS assembly code or machine code. We present some examples here, and discuss assignments from its first use in two undergraduate classes. IASSim is a Java application publicly available at no cost.

We present algorithms that permit increased efficiency in the calculation of conservation functions for cellular automata, and report results obtained from implementations of these algorithms to report conservation laws for 1-D cellular automata of higher order than any previously known. We introduce the notion of trivial and core conservation functions to distinguish truly new conservation functions from simple extensions of lower-order ones. We give new theorems related to these concepts, and show our use of them to derive more efficient algorithms for finding conservation functions. We then present the complete list of conservation functions up to order 16 for the 256 elementary 1-D binary cellular automata. These include CAs that were not previously known to have nontrivial conservation functions.

No abstract available.

We report the results of a year-long experiment in the use of robots to teach computer science. Our data set compares results from over 800 students on identical tests from both robotics and non-robotics based laboratory sessions. We also examine the effectiveness of robots in encouraging students to select computer science or computer engineering as a field of study.Our results are negative: test scores were lower in the robotics sections than in the non-robotics ones, nor did the use of robots have any measurable effect on students choice of discipline. We believe the most significant factor that accounts for this is the lack of a simulator for our robotics programming system. Students in robotics sections must run and debug their programs on robots during assigned lab times, and are therefore deprived of both reflective time and the rapid compile-run-debug cycle outside of class that is an important part of the learning process. We discuss this and other issues, and suggest directions for future work.

No abstract available.

Ada/Mindstorms 2.0 is an Ada interface to the Lego RCX "brick," included as part of the Lego Mindstorms™ Robotics Invention System. Programs are written with an Ada compiler, translated into Dave Baum's Not Quite C language (NQC), then recompiled and downloaded through the Mindstorms IR transmitter to the RCX.Ada/Mindstorms 2.0 is distributed with the USAFA AdaGIDE Windows Ada compiler. This document assumes that you have obtained and installed AdaGIDE. If you are using another Ada compiler, see Appendix B. We also assume a working knowledge of Ada. If you haven't used Ada before, we recommend learning the basics first before reading further. http://www.adahome.com/Discover/Introduction.html is a good place to start. We also assume a general familiarity with the Lego Mindstorms Robotics Invention System and the RCX.

We report the results of a year-long experiment in the use of robots to teach computer science. Our data set compares results from over 800 students on identical tests from both robotics and nonrobotics-based laboratory sessions. We also examine the effectiveness of robots in encouraging students to select computer science or computer engineering as a field of study. Our results are negative: test scores were lower in the robotics sections than in the nonrobotics ones, nor did the use of robots have any measurable effect on students' choice of discipline. We believe the most significant factor that accounts for this is the lack of a simulator for our robotics programming system. Students in robotics sections must run and debug their programs on robots during assigned lab times, and are therefore deprived of both reflective time and the rapid compile-run-debug cycle outside of class that is an important part of the learning process. We discuss this and other issues, and suggest directions for future work.

Using the robot as a metaphor for assisting students in understanding problem solving in general, the algorithmic process, and the relationship between algorithms and computing agents is not new. While simulated robot environments have existed for many years (e.g. Karel the Robot[3]) it is only recently that the technology for inexpensively supplying undergraduates with real robots has become available. Lego Mindstorms, MIT Handyboards, the Rug Warrior, and others are examples of such systems. Programmable in familiar languages, including C, Ada, and Java, these systems allow for the creative exploration of important computer science concepts. Representing a variety of institution types the panelists will discuss their experiences in using hands-on robot-based projects for illustrating various important computer science concepts.

Branch target buffers, or BTBs, are small caches for program branching information. Like data caches, addresses are divided into equivalence classes based on their low order bits. Unlike data caches, however, complete resolution of a single address from within an equivalence class is not required for correct execution. Substantial savings are therefore possible by employing partial resolution, using fewer tag bits than necessary to uniquely identify an address. We present the relationship between the number of tag bits in a branch target buffer and prediction accuracy, based on dynamic simulations of the SPECINT92 benchmark suite. For a 512 entry BTB, on average only two tag bits are necessary to obtain 99.9 percent of the accuracy obtainable with a full tag; no more than nine tag bits are required to obtain identical prediction accuracy. This suggests that microprocessors can achieve substantial area savings in their BTB tag stores by employing partial resolution.

Branch target buffers, or BTBs, are small caches for recently accessed program branching information. Like data caches, the set of intercepted addresses is divided into equivalence classes based on the low order bits of an address. Unlike data caches, however, complete resolution of a single address from within an equivalence class is not required for correct program execution. Substantial savings are therefore possible by employing partial resolution, using fewer tag bits than necessary to uniquely identify an address. We present our analysis of the relationship between the number of tag bits in a branch target buffer and prediction accuracy, based on dynamic simulations of the SPECINT92 benchmark suite. For a 512 entry BTB, our results indicate that, on average, only 2 tag bits are necessary to obtain 99.9% of the accuracy obtainable with a full tag. This suggests that existing microprocessors can achieve substantial area savings in BTB tag storage by employing partial resolution.

Branch target buffers, or BTBs, can be used to improve CPU performance by maintaining target and history information of previously executed branches. We present trace-driven simulation results comparing counter based and correlation-based prediction schemes for a variety of branch target buffer sizes. We report relative performance estimates to show both the relative merits of various techniques and their effects on performance for current microprocessors. Our results indicate that counter-based schemes outperform correlation-based schemes for small buffers, but that the opposite becomes true as buffer size increases. This is due to the importance of hit ratio over prediction success in branch target buffer design. The transition point between counter- and correlation-based schemes is dependent on the size of the working set of dynamic branches for a given collection of benchmark programs. Our results also show that for small BTBs, hit ratio and hence performance decrease as the number of correlation bits increase. This is due to non-random distribution of correlation vectors causing increased collisions for BTB locations. Only when a BTB becomes large enough to capture the working set of a program's branch and correlation vector references do the expected benefits of correlation-based schemes manifest themselves.

We report here our cumulative 2-year experience with the “The Digtal World”, a course designed to increase the technological literacy of non-science students. The course relies heavily on computer-aided instruction, including the extensive use of electronic lectures and multimedia. Students were able to acquire a surprising level of sophistication by working with examples of digital technology chosen from their daily lives. Students were also able to identify weaknesses in areas of current technology and public policy similar to those identified by experts.

We present empirical results describing the implementation of an IEEE Standard 754 compliant floating-point adder/multiplier using field programmable gate arrays. The use of FPGA's permits fast and accurate quantitative evaluation of a variety of circuit design tradeoffs for addition and multiplication. PPGA's also permit accurate assessments of the area and time costs associated with various features of the IEEE floating-point standard, including rounding and gradual underflow. These costs are analyzed, along with the effects of architectural correlation, a phenomenon that occurs when the cost of combining architectural features exceeds the sum of separate implementation. We conclude with an assessment of the strengths and weaknesses of using FPGA's for floating-point arithmetic.>

Advances in computational biology have occurred primarily in the areas of software and algorithm development; new designs of hardware to support biological computing are extremely scarce. This is due, we believe, to the presence of a non-trivial knowledge gap between molecular biologists and computer designers. The existence of this gap is unfortunate, as it has long been known that for certain problems, special-purpose computers can achieve significant cost/performance gains over general-purpose machines. We describe one such computer here: a custom accelerator for gene sequence analysis. The accelerator implements a version of the Needleman-Wunsch algorithm for nucleotide sequence alignment. Sequence lengths are constrained only by available memory; the product of sequence lengths in the current implementation can be up to 2(22). The machine is implemented as two NuBus boards connected to a Mac IIf/x, using a mixture of TTL and FPGA technology clocked at 10 MHz. The boards are completely functional, and yield a 15-fold performance improvement over an unassisted host.

A custom accelerator for gene sequence analysis is described. The use of rapid prototyping technology, the key to producing a working system in a short amount of time, as well as field-programmable gate arrays (FPGAs) and in-house printed circuit board (PCB) prototyping, are discussed. Price-performance comparisons of the processor with other machines are offered. The processor is completely functional and yields a 15* performance improvement over an unassisted host.>

The prototyping of a functioning DLX microprocessor, based on the 32-b instruction set architecture developed by D. Patterson and J. Hennessy (in Computer Architecture: A Quantitative Approach, 1990), is described. This architecture is an emerging academic standard but has yet to be successfully prototyped. An implementation of DLX as a 12-in*15-in two-layer circuit board, containing 59 chips and running on a 2-MHz clock, is described. The execution of DLX programs and the problems encountered are discussed.>

Previous work has reported on the use of polynomial transforms to compute exact convolution and to perform multiplication of large integers on a massively parallel processor. We now present results of an improved technique, using the Fermat Number Transform. When the Fermat Number Transform was first proposed, word-length constraints limited its effectiveness. Despite the development of multidimensional techniques to extend the length of the FNT, the relatively small word length of existing machines made the transform of little more than academic interest. The emergence of new computer architectures, however, has made the Fermat Number Transform more attractive. On machines like the Connection Machine, for example, we may implement the Fermat Number Transform without regard to word-length considerations. We present a convolution algorithm on a massively parallel processor, based on the Fermat Number Transform. We present some examples of the trade-offs between modulus, interprocessor communication steps, and input size. We then discuss the application of this algorithm in the multiplication of large integers and report performance results on a Connection Machine. Our results show multiplication times ranging from about 50 ms for 2-kbit integers to 2 s for 8-Mbit integers, an improvement of about five times over previous work.

The basic computational model of a massively parallel processor is discussed, and three massively parallel algorithms using carry-lookahead techniques for binary addition of large integers are presented. It is shown how performance can be improved by exploiting the average case behavior of large n-bit additions and the asymmetry of the computation time of two particular operations. Even better performance is obtained by grouping multiple bits per processor. Performance measurements of all the algorithms are presented and discussed.>

Performance results are presented for a parallel execution model for Prolog that supports AND-parallelism, OR-parallelism, and intelligent backtracking. The results show that restricted AND-parallelism is of limited benefit for small programs, but produced speedups from 7-10 on two large programs. OR-parallelism was found to be generally not useful for the benchmarks examined if the semantics of Prolog were preserved. Of particular interest is the phenomenon of super-multiplicative behavior, in which the performance improvement obtained when more than one technique is used is greater than the product of the performance improvements due to each technique individually. The implications of the performance results for parallel Prolog systems are discussed, and directions for future work are indicated.>

This paper presents a new multiprocessor architecture for the parallel execution of logic programs, developed as part of the Aquarius Project. This architecture is designed to support AND-parallelism, OR-parallelism, and intelligent backtracking. We present the most comprehensive experimental results available to date on combined AND-parallelism, OR-parallelism, and intelligent backtracking in Prolog programs. Simulation results indicate that most Prolog programs in use today cannot effectively make use of multiprocessing.