The storage utilizations of existing similar key search files based on B+-tree and extensible hashing were under 70% and should be improved. A similar key search file based on extensible hashing with partial expansion and that on linear hashing with partial expansion are proposed. Computer simulations on about 230 thousand English words show that the storage utilizations of the files with 32 expansive steps are about 97%.
Hidenori KUWAKADO Kenji KOYAMA
Two methods of the second step of the elliptic curve method for factoring are known. One is the standard method that is similar to the second step of the p-1 method, and the other is the Brent method that is based on the "birthday paradox." In this paper, we propose a revised standard method and a revised Brent method. On an average, the revised standard method is the most efficient, the standard method is the second efficient, the revised Brent method is the third and the Brent method is the fourth. If the largest prime factor on the order of an elliptic curve is congruent to 1 modulo 3, then the revised Brent method becomes more efficient than the standard method. By applying these methods to unsolved problems in the Cunningham project, we found 18 new prime factors. The largest prime factor among them was 43-digits.
Hisato UETSUKA Tomoyuki HAKUTA Hiroaki OKANO Noriaki TAKETANI Tatsuo TERAOKA
An insertion loss, branching deviation and polarization dependent loss (PDL) as to a 2 N optical splitter using silica-based planar lightwave circuits has been investigated. New key technologies such as (1) a novel wedge type Y-branch, (2) an offset waveguide at the junction between the curved input waveguide and the Y-branch, and (3) low birefringence waveguides due to the appropriate dopant concentration of a cladding, have been devised and incorporated into the splitter. As a result, 2 N optical splitters with low average insertion loss ( 13.2 dB), low branching deviation ( 0.4 dB) and low PDL ( 0.2 dB) have been successfully developed.
Nobuhiro YANAGIDA Hiroshi TAKAHASHI Yuzo TAKAMATSU
This paper presents a method of multiple fault diagnosis in sequential circuits by input-sequence pairs having sensitizing input pairs. We, first, introduce an input-sequence pair having sensitizing input pairs to diagnose multiple faults in a sequential circuit represented by a combinational array model. We call such input-sequence pair the sensitizing sequence pair in this paper. Next, we describe a diagnostic method for multiple faults in sequential circuits by the sensitizing sequence pair. From a relation between a sensitizing path generated by a sensitizing sequence pair and a subcircuit, the proposed method deduces the suspected faults for the subcircuits, one by one, based on the responses observed at primary outputs without probing any internal line. Experimental results show that our diagnostic method identifies fault locations within small numbers of suspected faults.
In this letter, a theoretical estimation of pick-up characteristics of the fiber probe of Photon Scanning Tunneling Microscopy based on the Wiener-Hopf technique taken account of the weakly guiding approximation are reported. As a result, it is found that diffracted waves by the extremity of the fiber probe mainly act on the mode excitation rather than transmitted waves, then the pick-up characteristics are well accordance with typical experiments quality and quantity.
Kensei OIMATSU Shizuma YAMAGUCHI Kazuoki KURAMOTO Shin'ya KUWAHARA
For designing the underwater transmission system using directly projected audible sound by underwater loudspeaker to prevent a diving accident and/or to give a working instrucion, it is important to estimate the transmission loss for a wall not onl for pure tones but also for wideband signal such as voice and noise. In this paper, two practical methods of evaluating the underwater insulation effect for a single wall are discussed. One is a reconfirmation that the mass law which is frequently used in air still explains the transmission loss in water. Because parameters such as surface density and sound velocity in the mass law are widely changeable depending on the depth in water, much complexity is involved in preparing a theoretical curve for every parameter. So to avoid such complexity, a unified parameter Φ(=ωm cos θ/2ρc) is introduced to describe the mass law. This newly presented curve as a function of Φ is in good agreement with all rearranged experimental data for every kind of plates. The other is a proposition of new evaluating method of insulation effect of a wall for a wideband signal, using an idea of (100-α) percentage point of the noise level probability destribution, Lα. Firstly proposed method is confirmed experimentally and secondly proposed method is confirmed by a simulation experiment.
Yoshitaka FUJIWARA Shin-ichiro OKADA Hiroyuki TAKADOI Toshiharu MATSUNISHI Hiroshi OHKAMA
In a conventional client-server system using the satellite communications, the responsibility of the system to the client user is considerably degraded by the long transmission time between the satellite and the ground terminal as well as the relatively low data transmission rate in comparison with the ground transmission line as the Ethernet. In this paper, a new client-server control, VEEC, is proposed to solve the problem. As a result of the experimental performance studies, it is clarified that the responsibility in the client is remarkably improved when the pre-fetching mechanism of VEEC works efficiently.
Hiroyuki MORIKAWA Yoshiyuki MIZUI Moriyuki MIZUMACHI
Periodic reservation allows periodic and random packets to share the same satellite random access channel efficiently. The periodic reservation protocol is particularly suitable for mobile satellite position reporting services, where some of the information messages, such as dispatch function, are classified as "periodic" and others, such as signaling, are classified as "random." When a new mobile terminal logs on to the system, Network Management Center (NMC) reserves subsequent time slots for transmitting periodic packets without contention. A mobile terminal recognizes each time slot as "reserved" or "unreserved (available)" according to the broadcast message received from NMC. Other random packets use the slotted ALOHA protocol to contend with other mobile terminals for an unreserved time slot. The performance results suggest that the use of the periodic reservation protocol can be regarded as a viable solution for mobile satellite position reporting services such as automatic dependent surveillance (ADS).
Seiichiro MORO Yoshifumi NISHIO Shinsaku MORI
When N oscillators are coupled by one resistor, we can see N-phase oscillation, because the system tends to minimize the current through the coupling resistor. Moreover, when the hard oscillators are coupled, we can see N, N - 1, , 3, 2-phase oscillation and get much more phase states. In this study, the two types of coupled oscillators networks with third and fifth-power nonlinear characteristics are proposed. One network has two-dimensional hexagonal structure and the other has two-dimensional lattice structure. In the hexagonal circuit, adjacent three oscillators are coupled by one coupling resistor. On the other hand, in the lattice circuit, four oscillators are coupled by one coupling resistor. In this paper we confirm the phenomena seen in the proposed networks by circuit experiments and numerical calculations. In the system with third-power nonlinear characteristics, we can see the phase patterns based on 3-phase oscillation in the hexagonal circuit, and based on anti-phase oscillation in lattice circuit. In the system with fifth-power nonlinear characteristics, we can see the phase patterns based on 3-phase and anti-phase oscillation in both hexagonal and lattice circuits. In particular, in these networks, we can see not only the synchronization based on 3-phase and anti-phase oscillation but the synchronization which is not based on 3-phase and anti-phase oscillation.
Howard J. THOMAS Nobuaki IMAI Eiichi OGAWA
This paper proposes a new approach for distributing millimeter wave signals from a central location to micro-base-stations using optical fiber links. The links utilize two Mach-Zehnder external optical modulators (EOMs) to perform all optical down-conversion, eliminating the need for a local oscillator or laser diode in the micro-base-station. A simple model of the EOMs is developed to illustrate the principle of dual-EOM mixing. The characteristics of conversion loss and intermodulation are examined for two cases: where the EOMs are operated in the linear mode and where the local oscillator's EOM is biased as a frequency doubling modulator. Additionally, we examined the use of an optical amplifier to reduce conversion loss for these two cases. The measured conversion loss of the link was 82 dB, and we estimated this could be reduced to about 48 dB by employing an optical amplifier and a more efficient EOM for RF reception.
NPO-PB is the class of NP optimization problems with polynomially bounded values. In this paper we provide a new characterization for the class: That is, NPO-PB = MIN Σ0. This result shows that quantifiers are not relevant in characterizing approximability for minimization problems, unlike maximization problems. In proving the result, we develop a generic reduction, which combines maximization and minimization problems. Based on the new characterization, several problems are shown to be NPO-PB-complete. All of these problems are shown to be hard to approximate and tighter bounds are given.
Mikio HASEGAWA Tohru IKEGUCHI Takeshi MATOZAKI Kazuyuki AIHARA
We analyze additive effects of nonlinear dynamics for conbinatorial optimization. We apply chaotic time series as noise sequence to neural networks for 10-city and 20-city traveling salesman problems and compare the performance with stochastic processes, such as Gaussian random numbers, uniform random numbers, 1/fα noise and surrogate data sets which preserve several statistics of the original chaotic data. In result, it is shown that not only chaotic noise but also surrogates with similar autocorrelation as chaotic noise exhibit high solving abilities. It is also suggested that since temporal structure of chaotic noise characterized by autocorrelation affects abilities for combinatorial optimization problems, effects of chaotic sequence as additive noise for escaping from undesirable local minima in case of solving combinatorial optimization problems can be replaced by stochastic noise with similar autocorrelation.
Nyberg and Knudsen proved that the maximum average of differential probability (ADPmax) and the maximum average of linear probability (ALPmax) of Feistel cipher with over 4 rounds can be evaluated as ADPmax 2DCP2max and ALPmax 2LCP2max using the maximum of defferential characteristic probability (DCPmax) and the maximum of linear characteristic probability (LCPmax) per round. This paper shows ADPmax DCP2max and ALPmax LCP2max if the F function is a bijection and the Feistel cipher has more than 3 rounds. The results prove that Feistel ciphers are stronger against differential and linear cryptanalyses than previously thought. Combining this result with that of Luby and Rackoff, the implication is that the 3-round Feistel cipher could be used as a building block cipher for the construction of provable secure block cipher algorithm.
To speed up discrete-log based cryptographic schemes, we propose new methods of computing exponentiations {gx1, gx2, , gxs} simultaneously in combination with precomputation. Two proposed methods, VAS-B and VSS-B, are based on an extension of vector addition chains and an extension of vector addition-subtraction chains, respectively. Analysis of these methods clarifies upper bounds for the number of multiplications required. The VAS-B requires less multiplications than previously proposed methods with the same amount of storage. The VSS-B requires less multiplications than previously proposed methods with less amount of storage. The VSS-B can suitably be applied to schemes over elliptic curves.
Takakazu SATOH Kiyomichi ARAKI
We review a fundamental weak point of the OSS digital signature scheme against cryptanalysis by Pollard et al., and propose a new scheme of digital signature which overcomes this defect. More specifically, instead of the ring of the rational integer, we use the ring of integral quaternions, which is a non-commutative Euclidean ring. Known attacks to OSS signature do not work our scheme due to the non-commutativity. On the other hand, this scheme causes little increase in the burden of generation and verification of digital signature for the legitimate users, with respect to the original OSS scheme.
In this paper a new type of public-key cryptosystem, proxy cryptosystem, is studied. The proxy cryptosystem allows an original decryptor to transform its ciphertext to a ciphertext for a designated decryptor, proxy decryptor. Once the ciphertext transformation is executed, the proxy decryptor can compute a plaintext in place of the original decryptor. Such a cryptosystem is very useful when an entity has to deal with large amount of decrypting operation. The entity can actually speed-up the decrypting operation by authorizing multiple proxy decyptors. Concrete proxy cryptosystems are constructed for the ElGamal cryptosystem and the RSA cryptosystem. A straightforward construction of the proxy cryptosystem is given as follows. The original decryptor decrypts its ciphertext and re-encrypts an obtained plaintext under a designated proxy decryptor's public key. Then the designated proxy decryptor can read the plaintext. Our constructions are more efficient than such consecutive execution of decryption and re-encryption. Especially, the computational work done by the original decryptor is reduced in the proxy cryptosystems.
Kaoru KUROSAWA Yutaka KATAYAMA Wakaha OGATA
This paper presents a reshufflable and laziness tolerant mental card game protocol. First, our protocol can reshuffle any subset of cards. For example, some opened cards and some face down cards can be shuffled together. Next, we consider two types of honest players, currently active and currently nonactive. A player is currently nonactive if he dropped out the game or he declared "pass" and has not declared "rejoin" yet. In the proposed protocol, if more than half of the players are currently active, they can play the game. In this case, the privacy of the currently nonactive players are kept secret.
Checkers, self-testers, and self-correctors for a function f are powerful tools in designing programs that compute f. However, the relationships among them have not been known well. In this paper, we first show that (1) if oneway permutations exist, then there exists a language L that has a checker but does not have a self-corrector. We then introduce a novel notion of "self-improvers" that trans form a faulty program into a less faulty program, and show that (2) if a function f has a self-tester/corrector pair, then f has a self-improver. As the applications of self-improvers, we finally show that (3) if a function f has a self-tester/corrector pair, then f has a flexible self-tester and (4) if a function f has a self-tester/corrector pair, then f has self-improver that transforms a faulty program into an alomost correct program.
Yong Up LEE Seong Ro LEE Hyung-Myung KIM Iickho SONG
In direction of arrival estimation, the locations of point sources are usually assumed to be fixed during the observation of data, which is reasonable in many cases. If the locations of the point sources are perturbed due to some reasons in a statistical way during the observed period and the signal sources are not far away from receiver array, however, direction of arrival estimation methods based on the fixed point source assumption may provide with incorrect results. In this paper, we propose a perturved-location source model. Under the model, an estimation method based on eigen-decomposition is investigated. In addition, the asymptotic distributions of the estimation errors of the parameters are obtained to show the statistical properties of the parameters are obtained to show the statistical properties of the estimation method.
Norihiro KATAYAMA Mitsuyuki NAKAO Yoshinari MIZUTANI Mitsuaki YAMAMOTO
So far, neuronal dendrites have been characterized as electrically passive cables. However, recent physiological findings have revealed complex dynamics due to active conductances distributed over dendrites. In particular, the voltage-gated calcium and calcium-activated conductances are essential for producing diverse neuronal dynamics and synaptic plasticity. In this paper, we investigate the functional significance of the dendritic calcium-activated dynamics by computer simulations. First, the dendritic calcium-activated responses are modeled in a discrete compartmental form based on the physiological findings. Second, the basic stimulus-response characteristics of the single compartment dendrite model are investigated. The model is shown to reproduce the neuronal responses qualitatively. Third, the spatio-temporal dynamics of the dendrite shafts are modeled by longitudinally connecting 10 single compartments with coupling constants which are responsible for the dendrite thickness. The thick dendrite models, corresponding to proximal dendrites, respond in a spatially cooperative manner to a localized constant or periodic current stimulation. In contrast, the highly activated compartments are forced to be localized in the neighborhood of the stimulation-site in the fine dendrite models corresponding to distal dendrites. These results suggest that dendritic activities are spatially cooperated in a site-dependent manner.