Language：English   Publishing type：Research paper (scientific journal)  

researchmap

Publishing type：Part of collection (book)   Publisher：Springer Singapore  

DOI： 10.1007/978-981-16-6890-6_72

researchmap

Language：English   Publishing type：Research paper (scientific journal)  

researchmap

Language：English   Publishing type：Research paper (scientific journal)   Publisher：Elsevier  

Let K be a field equipped with a valuation. Tropical varieties over K can be defined with a theory of Gröbner bases taking into account the valuation of K. Because of the use of the valuation, the theory of tropical Gröbner bases has proved to provide settings for computations over polynomial rings over a p-adic field that are more stable than that of classical Gröbner bases.

Beforehand, these strategies were only available for homogeneous polynomials. In this article, we extend the F5 strategy to a new definition of tropical Gröbner bases in an affine setting. We also provide a competitor with an adaptation of the F4 strategy to tropical Gröbner bases computations.

We provide numerical examples to illustrate time-complexity and p-adic stability of this tropical F5 algorithm. We also illustrate its merits as a first step before an FGLM algorithm to compute (classical) lex bases over p-adics.

DOI： 10.1016/j.jsc.2019.10.012

researchmap

Language：English   Publishing type：Research paper (bulletin of university, research institution)  

researchmap

Publishing type：Research paper (scientific journal)   Publisher：Walter de Gruyter GmbH  

Abstract

Recently, supersingular isogeny cryptosystems have received attention as a candidate of post-quantum cryptography (PQC). Their security relies on the hardness of solving isogeny problems over supersingular elliptic curves. The meet-in-the-middle approach seems the most practical to solve isogeny problems with classical computers. In this paper, we propose two algebraic approaches for isogeny problems of prime power degrees. Our strategy is to reduce isogeny problems to a system of algebraic equations, and to solve it by Gröbner basis computation. The first one uses modular polynomials, and the second one uses kernel polynomials of isogenies. We report running times for solving isogeny problems of 3-power degrees on supersingular elliptic curves over 𝔽_p² with 503-bit prime p, extracted from the NIST PQC candidate SIKE. Our experiments show that our first approach is faster than the meet-in-the-middle approach for isogeny degrees up to 3¹⁰.

DOI： 10.1515/jmc-2020-0072

researchmap

Other Link： https://www.degruyter.com/document/doi/10.1515/jmc-2020-0072/xml

Language：English   Publishing type：Research paper (scientific journal)   Publisher：Walter de Gruyter GmbH  

Abstract

Since Semaev introduced summation polynomials in 2004, a number of studies have been devoted to improving the index calculus method for solving the elliptic curve discrete logarithm problem (ECDLP) with better complexity than generic methods such as Pollard’s rho method and the baby-step and giant-step method (BSGS). In this paper, we provide a deep analysis of Gröbner basis computation for solving polynomial systems appearing in the point decomposition problem (PDP) in Semaev’s naive index calculus method. Our analysis relies on linear algebra under simple statistical assumptions on summation polynomials. We show that the ideal derived from PDP has a special structure and Gröbner basis computation for the ideal is regarded as an extension of the extended Euclidean algorithm. This enables us to obtain a lower bound on the cost of Gröbner basis computation. With the lower bound, we prove that the naive index calculus method cannot be more efficient than generic methods.

DOI： 10.1515/jmc-2019-0029

researchmap

Other Link： https://www.degruyter.com/document/doi/10.1515/jmc-2019-0029/pdf

Language：English   Publishing type：Research paper (international conference proceedings)   Publisher：ACM  

DOI： 10.1145/3384940.3388956

researchmap

Other Link： https://dblp.uni-trier.de/db/conf/ccs/asiapkc2020.html#IkematsuFKYTY20

Publishing type：Research paper (international conference proceedings)   Publisher：ACM  

DOI： 10.1145/3373207.3404037

researchmap

Language：English   Publishing type：Research paper (scientific journal)   Publisher：ACM  

Let K be a field equipped with a valuation. Tropical varieties over K can be defined with a theory of Gröbner bases taking into account the valuation of K . Because of the use of the valuation, the theory of tropical Gröbner bases has proved to provide settings for computations over polynomial rings over a p -adic field that are more stable than that of classical Gröbner bases. Beforehand, these strategies were only available for homogeneous polynomials. In this article, we extend the F5 strategy to a new definition of tropical Gröbner bases in an affine setting. We provide numerical examples to illustrate time-complexity and p -adic stability of this tropical F5 algorithm. We also illustrate its merits as a first step before an FGLM algorithm to compute (classical) lex bases over p -adics.

DOI： 10.1145/3208976.3209012

researchmap

Language：English   Publishing type：Research paper (scientific journal)   Publisher：Birkhauser Verlag AG  

Modular techniques are widely applied to various algebraic computations. In this paper, we discuss how modular techniques can be efficiently applied to computation of Gröbner basis of the ideal generated by a given set, and extend the techniques for further ideal operations such as ideal quotient, saturation and radical computation. In order to make modular techniques very efficient, we focus on the most important issue, how to efficiently guarantee the correctness of computed results. Unifying notions of luckiness of primes proposed by several authors, we give precise and comprehensive explanation on the techniques which shall be a certain basis for further development.

DOI： 10.1007/s11786-017-0325-1

Scopus

researchmap

Language：English   Publishing type：Research paper (international conference proceedings)   Publisher：Springer  

In this paper, we propose a new method for localization of polynomial ideal, which we call “Local Primary Algorithm”. For an ideal I and a prime ideal P, our method computes a P-primary component of I after checking if P is associated with I by using double ideal quotient (I : (I : P)) and its variants which give us a lot of information about localization of I.

DOI： 10.1007/978-3-319-99639-4_19

researchmap

Language：English   Publishing type：Research paper (international conference proceedings)   Publisher：Association for Computing Machinery  

Let K be a field equipped with a valuation. Tropical varieties over K can be defined with a theory of Gröbner bases taking into account the valuation of K. While generalizing the classical theory of Gröbner bases, it is not clear how modern algorithms for computing Gröbner bases can be adapted to the tropical case. Among them, one of the most e.cient is the celebrated F5 Algorithm of Faugère. In this article, we prove that, for homogeneous ideals, it can be adapted to the tropical case. We prove termination and correctness. Because of the use of the valuation, the theory of tropical Gröbner bases is promising for stable computations over polynomial rings over a p-adic field. We provide numerical examples to illustrate time-complexity and p-adic stability of this tropical F5 algorithm.

DOI： 10.1145/3087604.3087630

Scopus

researchmap

Language：English   Publishing type：Research paper (scientific journal)   Publisher：De Gruyter  

In 2015, Fukase and Kashiwabara proposed an efficient method to find a very short lattice vector. Their method has been applied to solve Darmstadt shortest vector problems of dimensions 134 to 150. Their method is based on Schnorr’s random sampling, but their preprocessing is different from others. It aims to decrease the sum of the squared lengths of the Gram–Schmidt vectors of a lattice basis, before executing random sampling of short lattice vectors. The effect is substantiated from their statistical analysis, and it implies that the smaller the sum becomes, the shorter sampled vectors can be. However, no guarantee is known to strictly decrease the sum. In this paper, we study Fukase–Kashiwabara’s method in both theory and practice, and give a heuristic but practical condition that the sum is strictly decreased. We believe that our condition would enable one to monotonically decrease the sum and to find a very short lattice vector in fewer steps.

DOI： 10.1515/jmc-2016-0008

researchmap

Language：English   Publishing type：Research paper (international conference proceedings)  

DOI： 10.1007/978-3-319-19962-7_27

researchmap

Publisher：ACM  

DOI： 10.1145/2732516.2732521

researchmap

Language：English   Publishing type：Research paper (scientific journal)   Publisher：John Wiley and Sons  

Somewhat homomorphic encryption is public key encryption supporting a limited number of additions and multiplications on encrypted data. This encryption gives a powerful tool in performing meaningful computations with protecting data confidentiality, whose property is suitable mainly in cloud computing. In this paper, we focus on the scheme proposed by Brakerski and Vaikuntanathan, and present two types of packed ciphertexts in order to improve performance and reduce size of the encrypted data. One type of our packed ciphertexts is based on the message encoding technique proposed by Lauter, Naehrig and Vaikuntanathan. While their technique empowers efficient secure computation of sums and products over the integers, our second type of packed ciphertexts enables efficient secure computation of more complex functionalities such as multiple inner products and multiple Hamming distances. We apply our packing method to construct several protocols for secure biometric authentication and secure pattern matching computations. Our implementation shows that our method gives faster performance than the state‐of‐the‐art work in such applications.

DOI： 10.1002/sec.1164

researchmap

Publisher：Springer  

DOI： 10.1007/978-3-319-08344-5_22

researchmap

DOI： 10.1007/978-3-642-54568-9_3

researchmap

Language：English   Publishing type：Research paper (international conference proceedings)   Publisher：Springer Verlag  

We propose a modular method for verifying the correctness of a Gröbner basis candidate. For an inhomogeneous ideal I, we propose to check that a Gröbner basis candidate G is a subset of I by computing an exact generating relation for each g in G by the given generating set of I via a modular method. The whole procedure is implemented in Risa/Asir, which is an open source general computer algebra system. By applying this method we succeeded in verifying the correctness of a Gröbner basis candidate computed in Romanovski et al (2007). In their paper the candidate was computed by a black-box software system and it has been necessary to verify the candidate for ensuring the mathematical correctness of the paper. © 2014 Springer-Verlag.

DOI： 10.1007/978-3-662-44199-2_64

Scopus

researchmap

Language：English   Publishing type：Research paper (scientific journal)   Publisher：De Gruyter  

In this paper, we revisit the fully homomorphic encryption (FHE) scheme implemented by Gentry and Halevi, which is just an instantiation of Gentry's original scheme based on ideal lattices. Their FHE scheme starts from a somewhat homomorphic encryption (SHE) scheme, and its decryption range is deeply related with the FHE construction. Gentry and Halevi gave an experimental evaluation of the decryption range, but theoretical evaluations have not been given so far. Moreover, we give a theoretical upper bound, and reconsider suitable parameters for theoretically obtaining an FHE scheme. In particular, while Gentry and Halevi use the Euclidean norm evaluation in the noise management of ciphertexts, our theoretical bound enables us to use the ∞-norm evaluation, and hence it helps to lower the difficulty of controlling the noise density of ciphertexts.

DOI： 10.1515/jmc-2013-0024

researchmap

Language：English   Publishing type：Research paper (scientific journal)   Publisher：ELSEVIER SCIENCE BV  

With many applications in engineering and scientific fields, quantifier elimination (QE) has received increasing attention. Cylindrical algebraic decomposition (CAD) is used as a basis for a general QE algorithm. In this paper we present an effective symbolic-numeric cylindrical algebraic decomposition (SNCAD) algorithm for QE incorporating several new devices, which we call "quick tests". The simple quick tests are run beforehand to detect an unnecessary procedure that might be skipped without violating the correctness of results and they thus considerably reduce the computing time. The effectiveness of the SNCAD algorithm is examined in a number of experiments including practical engineering problems, which also reveal the quality of the implementation. Experimental results show that our implementation has significantly improved efficiency compared with our previous work. (c) 2012 Elsevier B.V. All rights reserved.

DOI： 10.1016/j.tcs.2012.10.020

researchmap

Publishing type：Research paper (international conference proceedings)   Publisher：ACM  

DOI： 10.1145/2517488.2517497

researchmap

Language：English   Publishing type：Research paper (international conference proceedings)   Publisher：Springer  

Among many approaches for privacy-preserving biometric authentication, we focus on the approach with homomorphic encryption, which is public key encryption supporting some operations on encrypted data. In biometric authentication, the Hamming distance is often used as a metric to compare two biometric feature vectors. In this paper, we propose an efficient method to compute the Hamming distance on encrypted data using the homomorphic encryption based on ideal lattices. In our implementation of secure Hamming distance of 2048-bit binary vectors with a lattice of 4096 dimension, encryption of a vector, secure Hamming distance, and decryption respectively take about 19.89, 18.10, and 9.08 milliseconds (ms) on an Intel Xeon X3480 at 3.07 GHz. We also propose a privacy-preserving biometric authentication protocol using our method, and compare it with related protocols. Our protocol has faster performance and shorter ciphertext size than the state-of-the-art prior work using homomorphic encryption.

DOI： 10.1007/978-3-642-40588-4_5

researchmap

Language：English   Publishing type：Research paper (scientific journal)   Publisher：Birkhaeser/Springer  

In this article, we present new results for efficient arithmetic operations in a number field K represented by successive extensions. These results are based on multi-modular and evaluation-interpolation techniques. We show how to use intrinsic symmetries in order to increase the efficiency of these techniques. Applications to splitting fields of univariate polynomials are presented. © 2012 Springer Basel AG.

DOI： 10.1007/s11786-012-0112-y

Scopus

researchmap

Language：English   Publishing type：Research paper (international conference proceedings)   Publisher：SPRINGER-VERLAG BERLIN  

Modular techniques are widely applied to various algebraic computations. (See [5] for basic modular techniques applied to polynomial computations.) In this talk, we discuss how modular techniques are efficiently applied to computation of various ideal operations such as Gröbner base computation and ideal decompositions. Here, by modular techniques we mean techniques using certain projections for improving the efficiency of the total computation, and by modular computations, we mean corresponding computations applied to projected images.

DOI： 10.1007/978-3-642-32973-9\_30

researchmap

Language：English   Publishing type：Research paper (scientific journal)   Publisher：Birkhaeuser/Springer  

We study the problem of optimizing over parameters a particular real root of a polynomial with parametric coefficients. We propose an efficient symbolic method for solving the optimization problem based on a special cylindrical algebraic decomposition algorithm, which asks for a semi-algebraic decomposition into cells in terms of number-of-roots-invariance. © 2011 Springer Basel AG.

DOI： 10.1007/s11786-011-0090-5

Scopus

researchmap

Language：English   Publishing type：Research paper (international conference proceedings)   Publisher：IEEE Computer Society  

This paper introduces QC2AS which is a newly designed and developed computer algebra system for symbolic quantum chemical computations. With the rapid advancement of computer, the concern with high-level model chemistry has been growing. To handle such models, it is necessary to manipulate huge algebraic formulas. QC2AS has been designed to handle algebraic formulas appeared in quantum chemistry and it provides an access to our computer algebraic techniques without knowing the background theories. In this paper, we introduce its features and the architecture with some illustrative examples. This is the first report about the development of QC2AS. © 2011 IEEE.

DOI： 10.1109/ICCSA.2011.39

Scopus

researchmap

Language：English   Publishing type：Research paper (international conference proceedings)   Publisher：IEEE Computer Society  

This paper describes an algorithm to simplify algebraic formulas appear in electron correlation theories using Grobner basis.The algorithm is designed to sum up the equivalent terms under a set of rewriting rules so that we obtain the simplest representation of the formula.This paper also discusses improvements of our algorithm.

DOI： 10.1109/ICCSA.2010.30

CiNii Article

researchmap

Language：English   Publishing type：Research paper (scientific journal)   Publisher：ACADEMIC PRESS LTD- ELSEVIER SCIENCE LTD  

This paper presents an algebraic approach to polynomial spectral factorization, an important mathematical tool in signal processing and control. The approach exploits an intriguing relationship between the theory of Grobner bases and polynomial spectral factorization which can be observed through the sum of roots, and allows us to perform polynomial spectral factorization in the presence of real parameters. It is discussed that parametric polynomial spectral factorization enables us to express quantities Such as the optimal cost in terms of parameters and the sum of roots. Furthermore an optimization method over parameters is suggested that makes use of the results from parametric polynomial spectral factorization and also employs two quantifier elimination techniques. This proposed approach is demonstrated in a numerical example of a particular control problem. (C) 2008 Elsevier Ltd. All rights reserved.

DOI： 10.1016/j.jsc.2008.04.015

researchmap

Language：English   Publishing type：Research paper (international conference proceedings)   Publisher：ASSOC COMPUTING MACHINERY  

In this article, we present new results about the computation of a general shape of a triangular basis generating the splitting ideal of an irreducible polynomial given with the permutation representation of its Galois group G. We provide some theoretical results and a new general algorithm based on the study of the non redundant bases of permutation groups. These new results deeply increase the efficiency of the computation of the splitting field of a polynomial.

DOI： 10.1145/1576702.1576741

researchmap

Language：English   Publishing type：Research paper (international conference proceedings)   Publisher：ASSOC COMPUTING MACHINERY  

This paper constructs an algebraic solution approach to the algebraic Riccati equation, an important equation in signal processing and control system design. Key features of the proposed approach are the exploitation of useful structures inherent in the problem and the avoidance of Grobner basis computation by generic algorithms. The approach extends the algebraic approach to polynomial spectral factorization by means of the Sum of Roots. The approach further finds an effective symbolic expression of the eigenvector of the associated Hamiltonian matrix in a simple way. An example is presented to demonstrate the proposed algorithm.

DOI： 10.1145/1576702.1576733

researchmap

Language：English   Publishing type：Research paper (international conference proceedings)   Publisher：ASSOC COMPUTING MACHINERY  

Recently quantifier elimination (QE) has been of great interest in many fields of science and engineering. In this paper an effective symbolic-numeric cylindrical algebraic decomposition (SNCAD) algorithm and its variant specially designed for QE are proposed based on the authors' previous work and our implementation of those is reported. Based on analysing experimental performances, we are improving our design/synthesis of the SNCAD for its practical realization with existing efficient computational techniques and several newly introduced ones. The practicality of the SNCAD is now examined by a number of experimental results including practical engineering problems, which also reveals the quality of the implementation.

DOI： 10.1145/1577190.1577203

researchmap

Language：English   Publishing type：Research paper (international conference proceedings)  

researchmap

Language：English   Publishing type：Research paper (scientific journal)   Publisher：ACM  

DOI： 10.1145/1504347.1504359

researchmap

Language：English   Publishing type：Research paper (international conference proceedings)   Publisher：ACM  

Let f be a univariate monic integral polynomial of degree n and let (α1...,αn) be an n-tuple of its roots in an algebraic closure ℚ̄ of ℚ. Obtaining an algebraic representation of the splitting field ℚ (α1...,αn) of f is a question of first importance in effective Galois theory. For instance, it allows us to manipulate symbolically the roots of f. In this paper, we propose a new method based on multi-modular strategy. Actually, we provide algorithms for this task which return a triangular set encoding the splitting ideal of f. We examine the ability/practicality of the method by experiments on a real computer and study its complexity.

DOI： 10.1145/1390768.1390803

Scopus

researchmap

Language：English   Publishing type：Research paper (international conference proceedings)  

This paper attempts to establish a new framework of symbolic optimization of algebraic functions that is relevant to possibly a wide variety of practical application areas. The crucial aspects of the framework are (i) the suitable use of algebraic methods coupled with the discovery and exploitation of structural properties of the problem in the conversion process into the framework, and (ii) the feasibility of algebraic methods when performing the optimization. As an example an algebraic approach is developed for the discrete-time polynomial spectral factorization problem that illustrates the significance and relevance of the proposed framework. A numerical example of a particular control problem is also included to demonstrate the development.

DOI： 10.1145/1390768.1390791

Scopus

researchmap

Language：English   Publishing type：Research paper (scientific journal)   Publisher：SPRINGER  

We deal with ideals generated by polynomials with parametric exponents, and discuss certain stability of forms of Grobner bases of those ideals. Based on the author's previous work, we investigate techniques by "slack variables" and succeed in obtaining further useful notions and new techniques using elimination ideals and ring homomorphisms. We also apply those techniques to cases, where a single parameter appears only on a single variable as its exponent, with help of univariate GCD computation of polynomials with parametric exponent. Moreover, as the original method for GCD computation could not handle some subcase and so it was not complete, we complete the method by adding a concrete procedure for handling the subcase.

DOI： 10.1007/s00200-007-0055-8

researchmap

Language：English   Publishing type：Research paper (international conference proceedings)  

It has been pointed out that the notion of the sum of roots can be utilized for solving (parametric) polynomial spectral factorization. This paper reveals another aspect of the sum of roots as an indicator of achievable performance limitations. It is shown that performance limitations for some ℋ2 control problems can be expressed as the difference of two sums of roots. An optimization approach combining the two aspects of the sum of roots is also demonstrated that minimizes the achievable performance limitation over plant parameters. © 2007 IEEE.

DOI： 10.1109/CDC.2007.4434562

Scopus

researchmap

Language：English   Publishing type：Research paper (international conference proceedings)   Publisher：SPRINGER-VERLAG BERLIN  

This paper is concerned with the relationship between the sum of roots with positive real parts (SORPRP) of an even polynomial and the polynomial spectral factor of the even polynomial. The SORPRP and its relationship to Grobner bases are firstly reviewed. Then it is shown that the system of equations satisfied by the coefficients of the polynomial spectral factor is directly related to a Grobner basis. It is then demonstrated by means of an H-2 optimal control problem that the above fact can be used to facilitate guaranteed accuracy computation.

researchmap

Language：English   Publishing type：Research paper (international conference proceedings)   Publisher：ASSOC COMPUTING MACHINERY  

This paper proposes an algebraic approach for parametric optimization which can be utilized for various problems in signal processing and control. The approach exploits the relationship between the sum of roots and polynomial spectral factorization and solves parametric polynomial spectral factorization by means of the sum of roots and the theory of Grobner basis. This enables us to express quantities such as the optimal cost in terms of parameters and the sum of roots. Furthermore an optimization method over parameters is suggested that makes use of the results from parametric polynomial spectral factorization and also employs quantifier elimination. The proposed approach is demonstrated on a numerical example of a particular control problem.

researchmap

Language：English   Publishing type：Research paper (scientific journal)   Publisher：OSAKA JOURNAL OF MATHEMATICS  

A curve that can be parametrized by polynomials is called a polynomial curve. It is well-known that a polynomial curve has only one place at infinity. Let C be a curve with one place at infinity. Sathaye presented the following question raised by Abhyankar: Is there a polynomial curve associated with the semigroup generated by pole orders of C at infinity? In this paper, we give a negative answer to this question using Grobner basis computation.

researchmap

Language：English   Publishing type：Research paper (scientific journal)   Publisher：SPRINGER-VERLAG BERLIN  

We provide a modular method for computing the splitting field K-f of an integral polynomial f by suitable use of the byproduct of computation of its Galois group G(f) by p-adic Stauduhar's method. This method uses the knowledge of G(f) with its action on the roots of f over a p-adic number field, and it reduces the computation of K-f to solving systems of linear equations modulo some powers of p and Hensel liftings. We provide a careful treatment on reducing computational difficulty. We examine the ability/practicality of the method by experiments on a real computer and study its complexity.

researchmap

Language：English   Publishing type：Research paper (scientific journal)   Publisher：SPRINGER-VERLAG BERLIN  

We deal with ideals generated by polynomials with parametric coefficients, and introduce "stabilities on ideal structures" based on stability of forms of Grobner bases. Then, we extend those stabilities to radicals and irreducible decompositions and show the computational tractability on those computations by integrating existing techniques.

researchmap

Language：English   Publishing type：Research paper (international conference proceedings)   Publisher：ACM  

CiNii Article

researchmap

Language：English   Publishing type：Research paper (international conference proceedings)  

CiNii Article

researchmap

Language：English   Publishing type：Research paper (scientific journal)   Publisher：ACADEMIC PRESS LTD- ELSEVIER SCIENCE LTD  

An algorithm for the prime decomposition of polynomial ideals over small finite fields is proposed and implemented on the basis of previous work of the second author. To achieve better performance, several improvements are added to the existing algorithm, with strategies for computational flow proposed, based on experimental results. The practicality of the algorithm is examined by testing the implementation experimentally, which also reveals information about the quality of the implementation. (C) 2004 Elsevier Ltd. All rights reserved.

DOI： 10.1016/j.jsc.2003.08.004

researchmap

Language：English   Publishing type：Research paper (international conference proceedings)   Publisher：ACM  

CiNii Article

researchmap

Language：English   Publishing type：Research paper (scientific journal)   Publisher：PACIFIC JOURNAL MATHEMATICS  

The W-3 algebra of central charge 6/5 is realized as a sub-algebra of the vertex operator algebra V (root2A2) associated with a lattice of type root2A(2) by using both coset construction and orbifold theory. It is proved that W-3 is rational. Its irreducible modules are classified and constructed explicitly. The characters of those irreducible modules are also computed.

researchmap

Language：English   Publishing type：Research paper (international conference proceedings)   Publisher：ACM  

researchmap

Language：English   Publishing type：Research paper (scientific journal)   Publisher：SCRIPTA TECHNICA-JOHN WILEY & SONS  

Algorithms for counting the order of the rational points group are indispensable for the random selection of secure elliptic curves used in cryptosystems. In the case of curves over fields having large characteristics, it is possible to use the SEA (Schoof-Elkies-Atkin) algorithm [3, 5, 16], but in the case of elliptic curves defined over finite fields of characteristic 2, the SEA algorithm can be applied only in a modified form. In the case of characteristic 2, the authors implemented the Lercier [10] and Couveignes [2] algorithms, and combined them with an improved Intelligent Choice System [7, 8] proposed by the authors earlier. It was confirmed that in the case of characteristic 2 the combination of these methods allows for a fast generation of secure curves. (C) 2001 Scripta. Technica.

researchmap

Language：English   Publishing type：Research paper (scientific journal)   Publisher：SPRINGER-VERLAG BERLIN  

In this paper, we propose a new symmetric key block cipher SC2000 with 128-bit block length and 128-,192-,256-bit key lengths. The block cipher is constructed by piling two layers: one is a Feistel structure layer and the other is an SPN structure layer. Each operation used in two layers is S-box or logical operation, which has been well studied about security. It is a strong feature of the cipher that the fast software implementations are available by using the techniques of putting together S-boxes in various ways and of the Bitslice implementation.

researchmap

Language：English   Publishing type：Research paper (international conference proceedings)   Publisher：WORLD SCIENTIFIC PUBL CO PTE LTD  

In this paper we propose new algorithm for prime decomposition of polynomial ideals over finite fields. Aiming for practical computation, we employ the strategy by Gianni et al., and modify "decomposition using generic position" with special treatment for positive characteristic.

researchmap

Language：English   Publishing type：Research paper (scientific journal)  

researchmap

Publishing type：Research paper (scientific journal)  

This paper describes elliptic curve cryptosystems (ECCs), which are expected to become the next-generation public key cryptosystems, and also describes Fujitsu Laboratories' study of ECCs. ECCs require a shorter key length than RSA cryptosystems, which are the de facto standards of public key cryptosystems, but provide equivalent security levels. Because of the shorter key length, ECCs are fast and can be implemented with less hardware. First, we outline ECC and describe a typical digital signature algorithm. Then, we describe our technology for parameter generation of a secure ECC and the implementation of a fast ECC by software and by a digital signal processor. ECCs are expected to enter widespread use as a base technology of electronic information services.

Scopus

researchmap

Language：English   Publishing type：Research paper (scientific journal)   Publisher：SPRINGER-VERLAG BERLIN  

In order to choose a secure elliptic curve for Elliptic Curve Cryptosystems, it is necessary to count the order of a randomly selected elliptic curve. Schoof's algorithm and its variants by Elkies and Atkin are known as efficient methods to count the orders of elliptic curves. Intelligent Choice System(ICS) was proposed to combine these methods efficiently. In this paper, we propose an improvement on the ICS. Further, we propose several implementation techniques in the characteristic 2 case.

researchmap

Language：Japanese   Publishing type：Research paper (scientific journal)   Publisher：The Institute of Electronics, Information and Communication Engineers  

CiNii Article

researchmap

Language：English   Publishing type：Research paper (scientific journal)   Publisher：ACADEMIC PRESS LTD- ELSEVIER SCIENCE LTD  

To give an efficiently computable representation of the zeros of a zero-dimensional ideal I, Rouillier (1996) introduced the rational univariate representation (RUR) as an extension of the generalized shape lemma (GSL) proposed by Alonso et al. (1996). In this paper, we propose a new method to compute the RUR of the radical of I, and report on its practical implementation. In the new method, the RUR of the radical of I is computed efficiently by applying modular techniques to solving the systems of linear equations. The performance of the method is examined by practical experiments. We also discuss its theoretical efficiency. (C) 1999 Academic Press.

DOI： 10.1006/jsco.1999.0275

researchmap

Language：English   Publishing type：Research paper (international conference proceedings)   Publisher：Springer Verlag  

The security of elliptic curve cryptosystem depends on the choice of an elliptic curve on which cryptographic operations are performed. Schoof's algorithm is used to define a secure elliptic curve, as it can compute the number of rational points on a randomly selected elliptic curve defined over a finite field. By realizing efficient combination of several improvements, such as Atkin-Elkies’s method, isogeny cycles method, and baby-step-giant-step algorithm, we can count the number of rational points on an elliptic curve over GF(p) in a reasonable time, where p is a prime whose size is around 240-bit.

DOI： 10.1007/BFb0054030

Scopus

researchmap

Language：English   Publishing type：Research paper (scientific journal)   Publisher：SPRINGER-VERLAG BERLIN  

Schoof's algorithm is used to find a secure elliptic curve for cryptosystems, as it can compute the number of rational points on a randomly selected elliptic curve defined over a finite field. By realizing efficient combination of several improvements, such as Atkin-Elkies's method, the isogeny cycles method, and trial search by match-and-sort techniques, we can count the number of rational points on an elliptic curve over GF(p) in a reasonable time, where p is a prime whose size is around 240-bits.

researchmap

Language：English   Publishing type：Research paper (bulletin of university, research institution)  

CiNii Article

researchmap

Language：English   Publishing type：Research paper (scientific journal)   Publisher：Elsevier  

We propose a new method to compute the Galois group of an integral polynomial based on resolvent computation by modular techniques. We developed an exact method to find integral roots of relative resolvents by direct evaluation of invariants over some p-adic number field or its extension. Experiments on a set of test polynomials suggest that the presented method is quite practical by virtue of efficient evaluation of invariants based on modular techniques introduced here. © 1997 Elsevier Science B.V.

DOI： 10.1016/S0022-4049(97)00030-3

Scopus

researchmap

Language：English   Publishing type：Research paper (international conference proceedings)   Publisher：BIRKHAUSER VERLAG  

researchmap

Language：English   Publishing type：Research paper (scientific journal)   Publisher：Academic Press  

In this paper, we propose a new method for primary decomposition of a polynomial ideal, not necessarily zero-dimensional, and report on a detailed study for its practical implementation. In our method, we introduce two key techniques, effective localization and fast elimination of redundant components, by which we can get a good performance for several examples. The performance of our method is examined by comparison with other existing methods based on practical experiments. © 1996 Academic Press Limited.

DOI： 10.1006/jsco.1996.0052

Scopus

researchmap

Language：English   Publishing type：Research paper (international conference proceedings)   Publisher：ACM  

researchmap

Language：English   Publishing type：Research paper (scientific journal)   Publisher：ACADEMIC PRESS LTD  

Efficient algorithms to factorize bivariate integral polynomials are discussed. As a key technique to provide the most efficient algorithms in theory, an approach, named multi-modular approach, is proposed and its implication is discussed intensively. The approach uses combined information from several modular factorizations of different types. Although essentially the same idea was already proposed by Chistov and Grigoryev in 1982, the concept is presented independently in detail but in a more intelligible form. Effectiveness of the multi-modular approach is proved by affording two new algorithms superior to any other existing algorithms.

researchmap

Language：English   Publishing type：Research paper (international conference proceedings)   Publisher：ACM  

CiNii Article

researchmap

Language：English   Publishing type：Research paper (scientific journal)   Publisher：ACADEMIC PRESS LTD  

researchmap

Language：English   Publishing type：Research paper (scientific journal)   Publisher：ACADEMIC PRESS INC JNL-COMP SUBSCRIPTIONS  

By Praeger, Saxl, and Yokoyama, the classification problem of finite primitive distance transitive graphs is reduced to the case where the automorphism group is either almost simple or affine. Here we study graphs in the affine case, that is, we classify some classes of distance transitive graphs whose automorphism groups are affine.

DOI： 10.1016/0095-8956(92)90041-U

researchmap

Language：Japanese   Publishing type：Research paper (scientific journal)  

researchmap

Language：English   Publishing type：Research paper (scientific journal)  

Computer algebra is a newly developing research area that bridges constructive mathematics and scientific information processing technology. Research in this area includes design, analysis, and prototyping of mathematical algorithms for symbolic and algebraic computation. This paper describes an experimental system for computer algebra, named risa - Research Instrument for Symbolic Algebra. At present, the system forms the basic kernel of a computer algebra system, and is expected to become an essential engine for advanced future systems. As a general-purpose computer algebra system, risa's operating speed is competitive and sometimes outstanding. This paper also briefly describes several mathematical results of some algebraic computations related mainly to polynomials.

Scopus

researchmap

Language：English   Publishing type：Research paper (international conference proceedings)   Publisher：ASSOC COMPUTING MACHINERY  

researchmap

Language：English   Publishing type：Research paper (international conference proceedings)   Publisher：ASSOC COMPUTING MACHINERY  

researchmap

Language：English   Publishing type：Research paper (scientific journal)  

Several mathematical results and new computational methods are presented for primitive elements and their minimal polynomials of algebraic extension fields. For a field Q(α1,…,αt) obtained by adjoining algebraic numbers α1,…αt to the rational number field Q, it is shown that there exists at least one vector =(s1,…,st) of integers in a specially selected set of (−1)N vectors such that s1α1+s2α2+…+stαt is a primitive element, where N is the degree of Q(α1,…,αt) over Q. Furthermore, a method is presented for directly calculating such a vector, that gives a primitive element. Finally, for a given polynomial f over Q, a new method is presented for computing a primitive element of the splitting field of f and its minimal polynomial over Q. © 1989, Academic Press Limited. All rights reserved.

DOI： 10.1016/S0747-7171(89)80061-6

Scopus

researchmap

Language：Japanese   Publishing type：Research paper (scientific journal)  

CiNii Article

researchmap

Language：English   Publishing type：Research paper (scientific journal)   Publisher：Elsevier  

Distance transitive graphs with some local properties are completely classified under the following condition: the diameter d of the graph is at least 2, the valency υ of the graph is at least 7 and the stabilizer of a point acts (υ — 2)-transitively on its neighborhood, i.e. the stabilizer contains an alternating group. © 1988, Academic Press Limited. All rights reserved.

DOI： 10.1016/S0195-6698(88)80069-6

Scopus

researchmap

Language：English   Publishing type：Research paper (scientific journal)   Publisher：LONDON MATH SOC  

researchmap

Language：Japanese   Publisher：京都大学  

CiNii Article

researchmap

Language：Japanese   Publisher：京都大学  

CiNii Article

researchmap

Other Link： http://hdl.handle.net/2433/194561

Language：Japanese  

CiNii Article

researchmap

Language：Japanese   Publisher：日本数式処理学会  

CiNii Article

researchmap

Publisher：Kyoto University  

CiNii Article

researchmap

Other Link： http://hdl.handle.net/2433/171330

Language：English   Publisher：Faculty of Mathematics, Kyushu University  

CiNii Article

researchmap

Other Link： http://hdl.handle.net/2324/13975

Language：Japanese   Publishing type：Article, review, commentary, editorial, etc. (trade magazine, newspaper, online media)   Publisher：日本評論社  

CiNii Article

researchmap

Language：Japanese   Publishing type：Article, review, commentary, editorial, etc. (trade magazine, newspaper, online media)   Publisher：日本評論社  

CiNii Article

researchmap

Language：Japanese   Publishing type：Article, review, commentary, editorial, etc. (trade magazine, newspaper, online media)   Publisher：日本評論社  

CiNii Article

researchmap

Language：Japanese   Publisher：日本数式処理学会  

CiNii Article

researchmap

Language：Japanese   Publishing type：Article, review, commentary, editorial, etc. (trade magazine, newspaper, online media)   Publisher：日本評論社  

CiNii Article

researchmap

Language：Japanese   Publishing type：Article, review, commentary, editorial, etc. (trade magazine, newspaper, online media)   Publisher：日本評論社  

CiNii Article

researchmap

Language：Japanese   Publisher：京都大学  

CiNii Article

researchmap

Other Link： http://hdl.handle.net/2433/47845

Language：English   Publisher：Kyoto University  

CiNii Article

researchmap

Other Link： http://hdl.handle.net/2433/47857

Language：English   Publisher：Kyoto University  

CiNii Article

researchmap

Other Link： http://hdl.handle.net/2433/47855

Language：Japanese   Publisher：京都大学  

CiNii Article

researchmap

Other Link： http://hdl.handle.net/2433/25920

Language：English   Publisher：Kyoto University  

CiNii Article

researchmap

Other Link： http://hdl.handle.net/2433/25675

Language：Japanese   Publisher：京都大学  

CiNii Article

researchmap

Other Link： http://hdl.handle.net/2433/43346

Language：Japanese   Publisher：京都大学  

CiNii Article

researchmap

Other Link： http://hdl.handle.net/2433/42601

Language：Japanese   Publisher：The Institute of Electronics, Information and Communication Engineers  

In this paper, we propose a new symmetric key block cipher SC2000 with 128 bit block length and 128, 192, 256 bit key lengths. The block cipher is constructed by piling two layers: one is a Feistel structure layer and the other is an SPN structure layer. Each operation used in two layers is S-box or logical operation, which has been well studied about security. It is a strong feature of the cipher that the fast software implementations are available by using the techniques of putting together S-boxes in various ways and of the Bitslice implementation.

CiNii Article

researchmap

Language：English  

CiNii Article

researchmap

Language：Japanese  

CiNii Article

researchmap

Language：Japanese   Publisher：サイエンス社  

CiNii Article

researchmap

Language：Japanese   Publisher：京都大学  

CiNii Article

researchmap

Language：Japanese   Publisher：The Institute of Electronics, Information and Communication Engineers  

In elliptic curve cryptosystem, it is very important to choose an elliptic curve. Schoof's algorithm is efficient in that it can count rational points on any given elliptic curve, but it takes much time. By implementing modification by Atkin-Elkies, we could calculate rational points on an elliptic curve over 160-bit, finite field in reasonable time.

CiNii Article

researchmap

Language：English  

CiNii Article

researchmap

Language：Japanese   Publisher：京都大学数理解析研究所  

CiNii Article

researchmap

Language：Japanese   Publisher：Kyoto University  

CiNii Article

researchmap

Language：Japanese   Publisher：京都大学  

CiNii Article

researchmap

Language：Japanese  

CiNii Article

researchmap

Other Link： https://projects.repo.nii.ac.jp/?action=repository_uri&item_id=287474

Language：Japanese   Publisher：京都大学  

CiNii Article

researchmap

Language：Japanese   Publisher：京都大学  

CiNii Article

researchmap

Language：Japanese   Publisher：京都大学  

CiNii Article

researchmap

Language：Japanese   Publisher：京都大学  

CiNii Article

researchmap

visiting editor(発行 Volume 30 Number 6， December 2000)

researchmap

プログラム委員

researchmap

ポスタープログラム委員

researchmap

委員

researchmap

プログラム委員

researchmap