The linear hashing is a well-known dynamic hashing algorithm designed for internal main memory as well as external secondary memory. Traditional analysis of this search algorithm has been proposed under the assumption that all keys are uniformly accessed. In this paper, we present a discrete analysis of the average search cost of the linear dynamic hashing algorithm for internal main memory in consideration of the frequency of access on each key. In the proposed discrete analysis, the number of probes itself is regarded as a random variable and its probability distribution is derived concretely. Furthermore, the evaluate formula derived from the proposed analysis can exactly evaluate the average search cost in conformity with any probability distribution of the frequency of access. The proposed analysis is compared to the traditional one provided that the frequency of access on each key is uniform, and the differences are discussed.

A new algorithm for efficient arithmetic in an optimal extension field is proposed. The new algorithm improves the speeds of multiplication, squaring, and inversion by performing two subfield multiplications simultaneously within a single integer multiplication instruction of a CPU. Our algorithm is used to improve throughputs of elliptic curve operations.

The χ2-attack was originally proposed by Knudsen and Meier. This attack is one of the most effective attacks for RC6. The χ2-attack can be used for both distinguishing attacks and for key recovery attacks. Although, up to the present, theoretical analysis of χ2-attacks, especially the relation between a distinguishing attack and a key recovery attack, has not been discussed, the security against key recovery attacks has been often discussed by the results of distinguishing attacks. In this paper, we investigate the theoretical relation between the distinguishing attack and the key recovery attack, and prove one theorem to evaluate the exact security against the key recovery attacks by using the results of the distinguishing attack. Furthermore we propose two key recovery attacks against RC5-64 and implement them. Our best key recovery attack can analyze RC5-64 with 16 rounds by using 2125.23 plaintexts with a success probability of 30%. This result works faster than exhaustive key search. As far as the authors know, this is the best result of known plaintext attacks to RC5-64. We also apply our theory on our key recovery attacks and demonstrate the validity.

The purpose of this paper is to discuss length estimation based on digitized curves. Information on a curve in the Euclidean plane is lost after digitization. Higher resolution supports a convergence of a digital image towards the original curve with respect to Hausdorff metric. No matter how high resolution is assumed, it is impossible to know the length of an original curve exactly. In image analysis we estimate the length of a curve in the Euclidean plane based on an approximation. An approximate polygon converges to the original curve with an increase of resolution. Several approximation methods have been proposed so far. This paper proposes a new approximation method which generates polygonal curves closer (in the sense of Hausdorff metric) in general to its original curves than any of the previously known methods and discusses its relevance for length estimation by proving a Convergence Theorem.

Control scheme for accurately optimizing (and also automatically stabilizing) the interferometer phase bias of Symmetric-Mach-Zehnder (SMZ)-type ultrafast all-optical switches is proposed. In this control scheme, a weak cw light is used as a supervisory input light and its spectral power ratio at the switch output is used as a bipolar error signal. Our experimental result at 168-Gb/s 16:1 demultiplexing with a hybrid-integrated SMZ switch indicates the feasibility and the sensitivity of this control scheme.

We fabricated 1.3µm AlGaInAs inner-stripe laser diodes (LDs), employing a GaInAsP waveguide layer and an n-InP current blocking layer. We compared the effects of the thickness of n-InP current blocking layer. A blocking layer with 500nm thick restricts the leakage current significantly. The inner-stripe LD was compared with the conventional ridge LD. I-L characteristics of both types of LDs were measured. Threshold currents of the inner-stripe LD and the ridge LD were 8.5 and 10.6mA, respectively. A threshold current of the inner-stripe LD is smaller than that of ridge LD. And the resistance of the inner-stripe LD was a few ohms lower than that of the ridge LD. Output power of 88mW was obtained at 200mA with 300µ m-long cavity. This was twice the power of a conventional ridge laser. The characteristic temperature of the inner-stripe LD was obtained 76 K from 20 to 85. We obtained a good linearity up to 100mA at 85. Therefore the inner-stripe LD has an advantage of high power devices.

A dual greedy polyhedron is defined by a system of linear inequalities, where the right-hand sides are given by a submodular function and the coefficients matrix is given by the incidence vectors of antichains of a rooted forest. Faigle and Kern introduced this concept and showed that a dual greedy algorithm works for the linear program over dual greedy polyhedra. In this paper, we show that a dual greedy polyhedron is the isomorphic image of an ordinary submodular polyhedron under the Mobius function of the underlying rooted forest. This observation enables us to reduce linear optimization problems over dual greedy polyhedra to those over ordinary submodular polyhedra. We show a new max-min theorem for intersection of two dual greedy polyhedra as well.

We have exploited a high-power-tolerant variable optical attenuator (VOA) based on the fused fiber coupler in the all-fiber structure. A newly designed VOA employs the external modulation by forcing an axial stress in the tapered region of the fused fiber coupler. In the tapered region, the axial stress changes the refractive index of silica glasses resulting in a change in the coupling coefficient of the coupler. In this paper, we explain the principle of the novel device, VOA, and the optimized fabrication of the fused fiber coupler for the attenuation. The changes of the transmission spectrum for the coupler and the optical power spectrum for pump laser diode (LD), whose center wavelength is 1.47µm, versus the axial displacement were verified by experiment. The possibility of the wavelength uniformity less than 1dB over the range of 1460-1500nm was also obtained by another coupler under a different fabrication condition. The polarization-dependent loss (PDL) at 1.47µm wavelength was 0.65dB for a maximum displacement of 150µm. The designed device has an attractive feature of another output port of the coupler available as a monitoring tap. The device showed a high attenuation above 34dB and an insertion loss below 0.15dB. The all-fiber structure can provide less alignment, which in turn provides a high power tolerance. This novel design, moreover, has a simple and cost-effective structure.

We have formed simple polarization-controller arrays by inserting liquid crystal (LC) in trenches cut across planar lightwave circuits (PLCs). We fabricated LC layers for use as polarization controllers on PLCs in two ways; in one, the ultra-thin layer of LC is held in a cell that is inserted into a trench on the PLC while in the other, the trench is directly filled with the LC. The ultra-thin LC cell can change the phase of 1.55-µm light from 0 to 3π while the LC filling can change the phase of light at the same wavelength from 0 to 12π below 5Vrms. Two former parallel-aligned ultra-thin LC cells, where the directions of alignment of the liquid crystals are rotated by 45 relative to each other, are capable of converting light with an arbitrary input polarization to TE or TM polarization. Ultra-thin cells of twisted nematic LC can switch the polarization between TE and TM modes with an extinction ratio of -15dB. The array we fabricated had a pitch of 1 mm and 5 elements, but an array with more than 100 elements and a pitch below 125µm will easily be possible by using finely patterned transparent electrodes. We have also applied our techniques to the fabrication of LC-based variable optical attenuators (VOA) on the PLC.

Karger, Motwani and Sudan presented a graph coloring algorithm based on semidefinite programming, which colors any k-colorable graph with maximum degree Δ using (Δ1-2/k) colors. This algorithm leads to an algorithm for k-colorable graph using (n 1-3/(k+1)) colors. This improved Wigderson's algorithm, which uses O(n1-1/(k-1)) colors, containing as a subroutine an algorithm using (Δ+1) colors for graphs with maximum degree Δ. It is easy to imagine that an algorithm which uses less colors in terms of Δ leads to an algorithm which uses less colors in terms of n. In this paper, we consider this influence assuming that we have an algorithm which uses (Δ 1-x/k) colors for 2

The one dimensional cutting stock problem (1D-CSP) is one of the representative combinatorial optimization problems, which arises in many industries. As the setup costs of cutting patterns become more dominant in recent cutting industry, we consider a variant of 1D-CSP, in which the total number of applications of cutting patterns is minimized under the constraint that the number of different cutting patterns is specified in advance. We propose a local search algorithm that uses the neighborhood obtained by perturbating one cutting pattern in the current set of patterns, where the perturbations are done by utilizing the dual solution of the auxiliary linear programming problem (LP). In this process, in order to solve a large number of LPs, we start the criss-cross variation of the simplex algorithm from the optimal simplex tableau of the previous solution, instead of starting it from scratch. According to our computational experiment, it is observed that the proposed algorithm obtains a wide variety of good solutions which are comparable to the existing heuristic approaches.

Although the subgraph isomorphism problem has various important applications, it is generally NP-complete and difficult to solve. Though a custom computing circuit can reduce the execution time substantially, it requires considerable hardware resources and is inapplicable to large problems. This paper examines the feasibility of data dependent designs, which are particularly suitable to a Field Programmable Gate Array (FPGA). The data dependent approach drastically reduces hardware requirements. For graphs of 32 vertices, the average logic scale of data dependent circuits is only 5% of the corresponding data independent circuit. The data dependent circuit is estimated to be maximally 460 times faster than the software. Even if the circuit generation time is included, a data dependent circuit is estimated to be 2.04 times faster than software for graphs of 32 vertices. The performance gain would increase for larger graphs.

12 on/off power splitters at λ=0.63µm have been produced in LiNbO3 substrates using strain-induced channel waveguides formed by magnetron deposition of surface metal films and lift-off technology. The static strain resulting from thermal expansion mismatch between the substrate and the metal films induces a localized increase in the refractive index via the strain-optic effect. On/off voltage of about 25V has been demonstrated.

Reconfigurable architectures have been focused for its potential on achieving high performance by reconfiguring special purpose circuits for a target application and its flexibility due to its ability of reconfiguring. We have set our sights on use of a reconfigurable architecture as a general-purpose computer by extending the advantageous properties of the architecture. To achieve the goal, a generalized execution model for reconfigurable architecture is required, so we have proposed an Ideal PARallel Structure (I-PARS) execution model. In the I-PARS execution model, any programs based on its model has no restriction depending on hardware structures based on a specific reconfigurable processor, which makes it easier to develop software. Further, we have proposed a PARS architecture which executes programs based on the I-PARS execution model effectively. The PARS architecture has a large reconfigurable part for highly parallel execution, which utilizes parallelism described on the I-PARS execution model. For effective utilization of the reconfigurable part in the PARS architecture, it has an ability to reconfigure and execute operations simultaneously in one cycle. Further, the PARS architecture supports branch operations to introduce control flow in an execution on the architecture, which makes it possible to skip an execution which does not produce a valid result. In this paper, we introduce the detailed structure of an implemented prototype processor based on the PARS architecture. In the implementation, 420,377 CMOS transistors were used, which was only 3.8% of the number of transistors used in the UltraSPARC-III in logic circuits. Additionally, we evaluated the performance of the prototype processor by using some benchmark programs. From the evaluation results, we found that the prototype processor could achieve nearly the same performance and be implemented with extremely the less number of transistors compared with UltraSPARC-III 750MHz.

In this paper, we propose a novel pulse-coupled neural network (PCNN) simulator using a programmable gate array (PGA) technique. The simulator is composed of modified phase-locked loops (PLLs) and a programmable gate array (PGA). The PLL, which is modified by the addition of multiple inputs and multiple feedbacks, works as a neuron. The PGA, which controls the network connection, works as nodes of dendritic trees. This simulator, which has 16 neurons and 32 32 network connections, is designed on a chip (4.73mm 4.73mm), and its basic operations such as synchronization, an oscillatory associative memory, and FM interactions are confirmed using circuit simulator SPICE.

The strong RSA assumption is an assumption that the following problem is hard to solve: Given an RSA modulus and a ciphertext, find a pair of plaintext and exponent corresponding to them. It differs from the standard RSA assumption in a sense that in the strong version, no exponent is given as an input. The strong RSA assumption is considered to be stronger than the RSA assumption, but their exact relationship is not known. We investigate the strength of the strong RSA assumption and show that the strong RSA assumption restricted to low exponents is equivalent to the assumption that RSA problem is intractable for any low exponent. We also show that in terms of algebraic computation, the strong RSA assumption is properly stronger than the RSA assumption if there exists an RSA modulus n such that gcd((n),3)=1 and RSA problem is intractable.

In testing the possible biological effects of electromagnetic exposure from cellular telephones in small animals such as mice, it is essential to realize a highly localized head exposure as close as possible to that due to cellular telephones in humans. In this study, a 1.5GHz exposure setup was developed which has a highly localized specific absorption rate (SAR) of 2W/kg in the mouse brain and a low whole-body averaged SAR of 0.27W/kg. The low whole-body averaged SAR was realized by using a flexible magnetic sheet attachment on the mouse holder. Its validity has been carefully examined by both numerical simulation with an anatomically based mouse model and experimental simulation with a solid mouse phantom. Good agreement was obtained between the numerical and experimental results, which confirmed the effectiveness of the magnetic sheet attachment to the mouse holder.

Lin and Jan recently proposed a new automatic signature scheme using a compiler in distributed systems. The proposed scheme adopts a digital signature scheme to detect the change of computer programs, thus it allows computer programs prevent from the infection of computer viruses. However, this article will present a forgery signature attack on their scheme. Moreover, the author also points out one restriction in their scheme. It is impractical for most application programs.

The generation of high repetition-rate optical pulse train using a passively mode-locked figure-8 fiber ring laser is presented. The laser employs a novel configuration incorporating a superstructure fiber Bragg grating. Pulse train with repetition rates up to 100GHz is possible and transform-limited pulses with pulsewidth below 1ps can be achieved with chirp compensation. The output pulses can further be reduced to 83fs with an external pulse compressor.

It is found that the supercontinuum spectrum is generated from cross-phase modulated soliton pulses which are propagated through a dispersion-flattened/decreasing fiber with low birefringence. The cross-phase modulation is achieved by exciting two orthogonally polarized modes in a birefringent fiber and the effect of input azimuth of linearly polarized pulses is discussed theoretically and numerically.