Updated on 2024/02/15

写真b

 
YOKOYAMA Kazuhiro
 
*Items subject to periodic update by Rikkyo University (The rest are reprinted from information registered on researchmap.)
Affiliation*
Professor Emeritus
Title*
Professor Emeritus
Degree
Doctor(Science) ( Kyushu University )
Contact information
Mail Address
Research Interests
  • 代数的組合せ論

  • 計算環論

  • Algebraic Combinatorics

  • Computer Algebra

  • Campus Career*
    • 4 2023 - Present 
      Professor Emeritus
     

    Research Areas

    • Natural Science / Applied mathematics and statistics

    • Natural Science / Basic mathematics

    • Natural Science / Algebra

    Research History

    • 4 2023 - Present 
      Rikkyo University   College of Science   emeritus professor

      More details

    • 4 2005 - 3 2023 
      RIKKYO UNIVERSITY   Graduate School of Science Field of Study: Mathematics   Professor

      More details

    • 4 2005 - 3 2023 
      RIKKYO UNIVERSITY   College of Science Department of Mathematics   Professor

      More details

    • 12 2000 - 3 2005 
      Kyushu University   Faculty of Mathematics

      More details

    • 4 1999 - 11 2000 
      富士通研究所 セキュアコンピューティング研究部   主任研究員

      More details

    • 11 1996 - 3 1999 
      Fujitsu Laboratories LTD.   Senior Researcher

      More details

    • 4 1995 - 3 1996 
      Fujitsu Laboratories LTD.   Chief Researcher

      More details

    • 12 1990 - 3 1995 
      Fujitsu Laboratories LTD.   Researcher

      More details

    • 4 1985 - 11 1990 
      Fujitsu   Researcher

      More details

    ▼display all

    Education

    • 4 1983 - 3 1983 
      The University of Tokyo   Graduate School, Division of Science

      More details

      Country: Japan

      researchmap

    • - 3 1983 
      The University of Tokyo   Graduate School, Division of Science

      More details

      Country: Japan

      researchmap

    • - 3 1981 
      The University of Tokyo   Faculty of Science

      More details

      Country: Japan

      researchmap

    Committee Memberships

    • 1 1992 
      日本数式処理学会   監事

      More details

      Committee type:Academic society

      researchmap

    Papers

    • On Hilbert-Poincare series of affine semi-regular polynomial sequences and related Groebner bases Invited Peer-reviewed

      Momonari Kudo, Kazuhiro Yokoyama

      Mathematical Foundations for Post-Quantum Cryptography, Mathematics for Industry   3 2024

      More details

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

      researchmap

    • On Factorization of Parametric Polynomials Peer-reviewed

      Kazuhiro Yokoyama

      accepted at Commentarii Mathematici Universitatis Sancti Pauli   2024

      More details

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

      researchmap

    • Computing endomorphism rings of supersingular elliptic curves by finding cycles in concatenated supersingular isogeny graphs Peer-reviewed

      Yuta Kambe, Akira Katayama, Yusuke Aikawa, Yuki Ishihara, Masaya Yasuda, Kazuhiro Yokoyama

      accepted at Commentarii Mathematici Universitatis Sancti Pauli   2024

      More details

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

      researchmap

    • On the feasibility of computing constructive Deuring correspondence Peer-reviewed

      Yuta Kambe, Yasushi Takahashi, Masaya Yasuda, Kazuhiro Yokoyama

      Banach Center Publications: Post-proceedings of Number-Theoretic Methods in Cryptology (NuTMiC 2021)126   105 - 121   12 2023

      More details

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

      DOI: 10.4064/bc126-7

      researchmap

    • Introduction to algebraic approaches for solving isogeny path-finding problems Peer-reviewed

      Ryoya Fukasaku, Yasuhiko Ikematsu, Momonari Kudo, Masaya Yasuda, Kazuhiro Yokoyama

      RIMS Kˆokyˆuroku BessatsuB90   169 - 184   6 2022

      More details

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

      researchmap

    • Implementation Report of the Kohel–Lauter–Petit–Tignol Algorithm for the Constructive Deuring Correspondence Peer-reviewed

      Yuta Kambe, Yusuke Aikawa, Momonari Kudo, Masaya Yasuda, Katsuyuki Takashima, Kazuhiro Yokoyama

      Proceedings of the Seventh International Conference on Mathematics and Computing   953 - 966   2022

      More details

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

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

      researchmap

    • Solving the constructive Deuring correspondence via the Kohel-Lauter-Petit-Tignol algorithm Peer-reviewed

      Yuta Kambe, Masaya Yasuda, Masayuki Noro, Kazuhiro Yokoyama, Yusuke Aikawa, Katsuyuki Takashima, Momonari Kudo

      Mathematical Cryptology (Special Issue of MathCrypt 2021)1 ( 2 ) 10 - 24   8 2021

      More details

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

      researchmap

    • On affine tropical F5 algorithms Peer-reviewed

      Tristan Vaccon, Thibaut Verron, Kazuhiro Yokoyama

      Journal of Symbolic Computation102   132 - 152   2021

      More details

      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

    • Symbolic Computation of Isogenies of Elliptic Curves by Vélu’s Formula Peer-reviewed

      Masayuki NORO, Masaya YASUDA, Kazuhiro YOKOYAMA

      COMMENTARII MATHEMATICI UNIVERSITATIS SANCTI PAULI68   93 - 127   12 2020

      More details

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

      researchmap

    • Algebraic approaches for solving isogeny problems of prime power degrees Peer-reviewed

      Yasushi Takahashi, Momonari Kudo, Ryoya Fukasaku, Yasuhiko Ikematsu, Masaya Yasuda, Kazuhiro Yokoyama

      Journal of Mathematical Cryptology15 ( 1 ) 31 - 44   17 11 2020

      More details

      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 𝔽<sub>p<sup>2</sup></sub> 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<sup>10</sup>.

      DOI: 10.1515/jmc-2020-0072

      researchmap

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

    • Complexity bounds on Semaev’s naive index calculus method for ECDLP Peer-reviewed

      Kazuhiro Yokoyama, Masaya Yasuda, Yasushi Takahashi, Jun Kogure

      Journal of Mathematical Cryptology14 ( 1 ) 460 - 485   30 10 2020

      More details

      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

    • Hybrid Meet-in-the-Middle Attacks for the Isogeny Path-Finding Problem. Peer-reviewed

      Yasuhiko Ikematsu, Ryoya Fukasaku, Momonari Kudo, Masaya Yasuda, Katsuyuki Takashima, Kazuhiro Yokoyama

      Proceedings of the 7th on ASIA Public-Key Cryptography Workshop(APKC@AsiaCCS)   36 - 44   10 2020

      More details

      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

    • On FGLM algorithms with tropical Gröbner bases Peer-reviewed

      Yuki Ishihara, Tristan Vaccon, Kazuhiro Yokoyama

      Proceedings of the 45th International Symposium on Symbolic and Algebraic Computation   20 7 2020

      More details

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

      DOI: 10.1145/3373207.3404037

      researchmap

    • On Affine Tropical F5 Algorithms Peer-reviewed

      Tristan Vaccon, Thibaut Verron, Kazuhiro Yokoyama

      Proceedings of ISSAC 2018   383 - 390   7 2018

      More details

      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

    • Usage of Modular Techniques for Efficient Computation of Ideal Operations Peer-reviewed

      Masayuki Noro, Kazuhiro Yokoyama

      Mathematics in Computer Science12 ( 1 ) 1 - 32   1 3 2018

      More details

      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

    • Effective Localization Using Double Ideal Quotient and Its Implementation. Peer-reviewed

      Yuki Ishihara, Kazuhiro Yokoyama

      Proceedings of CASC 2018, Lecture Notes in Computer Science11077   272 - 287   2018

      More details

      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

    • A Tropical F5 algorithm Peer-reviewed

      Tristan Vaccon, Kazuhiro Yokoyama

      Proceedings of the International Symposium on Symbolic and Algebraic Computation, ISSAC129312   429 - 436   23 7 2017

      More details

      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

    • Analysis of decreasing squared-sum of Gram-Schmidt lengths for short lattice vectors. Peer-reviewed

      Masaya Yasuda, Kazuhiro Yokoyama, Takeshi Shimoyama, Jun Kogure, Takeshi Koshiba

      J. Mathematical Cryptology11 ( 1 ) 1 - 24   2017

      More details

      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

    • Secure statistical analysis using RLWE-based homomorphic encryption Peer-reviewed

      Masaya Yasuda, Takeshi Shimoyama, Jun Kogure, Kazuhiro Yokoyama, Takeshi Koshiba

      Lecture Notes in Computer Science (ACISP 2015)9144   471 - 487   6 2015

      More details

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

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

      researchmap

    • Secure Data Devolution: Practical Re-encryption with Auxiliary Data in LWE-based Somewhat Homomorphic Encryption. Peer-reviewed

      Masaya Yasuda, Array, Takeshi Shimoyama, Jun Kogure, Kazuhiro Yokoyama

      Proceedings of the 3rd International Workshop on Security in Cloud Computing, SCC@ASIACCS '15, Singapore, Republic of Singapore, April 14, 2015   53 - 61   2015

      More details

    • New packing method in somewhat homomorphic encryption and its applications. Peer-reviewed

      Masaya Yasuda, Takeshi Shimoyama, Jun Kogure, Kazuhiro Yokoyama, Takeshi Koshiba

      Security and Communication Networks8 ( 13 ) 2194 - 2213   2015

      More details

      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

    • Privacy-Preserving Wildcards Pattern Matching Using Symmetric Somewhat Homomorphic Encryption Peer-reviewed

      Yasuda Masaya, Shimoyama Takeshi, Kogure Jun, Yokoyama Kazuhiro, Koshiba Takeshi

      INFORMATION SECURITY AND PRIVACY, ACISP 20148544   338 - 353   2014

      More details

      Publisher:Springer  

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

      researchmap

    • Practical Packing Method in Somewhat Homomorphic Encryption Peer-reviewed

      Yasuda Masaya, Shimoyama Takeshi, Kogure Jun, Yokoyama Kazuhiro, Koshiba Takeshi

      DATA PRIVACY MANAGEMENT AND AUTONOMOUS SPONTANEOUS SECURITY, DPM 20138247   34 - 50   2014

    • Verification of Gröbner basis candidates Peer-reviewed

      Masayuki Noro, Kazuhiro Yokoyama

      Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)8592   419 - 424   2014

      More details

      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

    • On the exact decryption range for Gentry-Halevi's implementation of fully homomorphic encryption. Peer-reviewed

      Masaya Yasuda, Kazuhiro Yokoyama, Takeshi Shimoyama, Jun Kogure, Takeshi Koshiba

      J. Mathematical Cryptology8 ( 3 ) 305 - 329   2014

      More details

      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

    • An effective implementation of symbolic-numeric cylindrical algebraic decomposition for quantifier elimination Peer-reviewed

      Hidenao Iwane, Hitoshi Yanami, Hirokazu Anai, Kazuhiro Yokoyama

      THEORETICAL COMPUTER SCIENCE479 ( 1 ) 43 - 69   4 2013

      More details

      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

    • Secure pattern matching using somewhat homomorphic encryption. Peer-reviewed

      Masaya Yasuda, Takeshi Shimoyama, Jun Kogure, Kazuhiro Yokoyama, Takeshi Koshiba

      CCSW'13, Proceedings of the 2013 ACM Cloud Computing Security Workshop, Co-located with CCS 2013, Berlin, Germany, November 4, 2013   65 - 76   2013

      More details

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

      DOI: 10.1145/2517488.2517497

      researchmap

    • Packed Homomorphic Encryption Based on Ideal Lattices and Its Application to Biometrics. Peer-reviewed

      Masaya Yasuda, Takeshi Shimoyama, Jun Kogure, Kazuhiro Yokoyama, Takeshi Koshiba

      Proceedings of CD-ARES 2013, Lecture Notes in Computer Science8128   55 - 74   2013

      More details

      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

    • Efficient Arithmetic in Successive Algebraic Extension Fields Using Symmetries Peer-reviewed

      Sébastien Orange, Guénaël Renault, Kazuhiro Yokoyama

      Mathematics in Computer Science6 ( 3 ) 217 - 233   9 2012

      More details

      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

    • Usage of Modular Techniques for Efficient Computation of Ideal Operations Invited

      Kazuhiro Yokoyama

      COMPUTER ALGEBRA IN SCIENTIFIC COMPUTING, CASC 20127442   361 - 362   2012

      More details

      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

    • Optimizing a Particular Real Root of a Polynomial by a Special Cylindrical Algebraic Decomposition Peer-reviewed

      Silvia Gandy, Masaaki Kanno, Hirokazu Anai, Kazuhiro Yokoyama

      Mathematics in Computer Science5 ( 2 ) 209 - 221   6 2011

      More details

      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

    • Development of QC2AS- A computer algebra system for symbolic quantum chemical computations Peer-reviewed

      Takeshi Osoekawa, Yuji Mochizuki, Kazuhiro Kyokoyama

      Proceedings - 2011 International Conference on Computational Science and Its Applications, ICCSA 2011   102 - 109   2011

      More details

      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

    • Gröbner Basis Technique for Algebraic Formulas in Electron Correlation Theories Peer-reviewed

      Takeshi Osoekawa, Yuji Mochizuki, Kazuhiro Yokoyama

      Proceedings of ICCSA 2010   17 - 23   2010

      More details

      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

    • Parametric polynomial spectral factorization using the sum of roots and its application to a control design problem Peer-reviewed

      Hirokazu Anai, Shinji Hara, Masaaki Kanno, Kazuhiro Yokoyama

      JOURNAL OF SYMBOLIC COMPUTATION44 ( 7 ) 703 - 725   7 2009

      More details

      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

    • Computation Schemes for Splitting Fields of Polynomials Peer-reviewed

      Sebastien Orange, Guenael Renault, Kazuhiro Yokoyama

      ISSAC2009: PROCEEDINGS OF THE 2009 INTERNATIONAL SYMPOSIUM ON SYMBOLIC AND ALGEBRAIC COMPUTATION   279 - 286   2009

      More details

      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

    • Solution of Algebraic Riccati Equations Using the Sum of Roots Peer-reviewed

      Masaaki Kanno, Kazuhiro Yokoyama, Hirokazu Anai, Shinji Hara

      ISSAC2009: PROCEEDINGS OF THE 2009 INTERNATIONAL SYMPOSIUM ON SYMBOLIC AND ALGEBRAIC COMPUTATION   215 - 222   2009

      More details

      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

    • An Effective Implementation of a Symbolic-Numeric Cylindrical Algebraic Decomposition for Quantifier Elimination Peer-reviewed

      Hidenao Iwane, Hitoshi Yanami, Hirokazu Anai, Kazuhiro Yokoyama

      SNC&apos;09: PROCEEDINGS OF THE 2009 INTERNATIONAL WORKSHOP ON SYMBOLIC-NUMERIC COMPUTATION   55 - 64   2009

      More details

      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&apos; 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

    • Symbolic optimization of algebraic function Peer-reviewed

      Masaaki Kanno, Kazuhiro Yokoyama, Hirokazu Anai, Shinji Hara

      Proceedings of the 2008 International Symposium on Symbolic and Algebraic Computation   247 - 254   7 2008

      More details

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

      researchmap

    • Solution of the algebraic riccati equation using the sum of roots Peer-reviewed

      Masaaki Kanno, Kazuhiro Yokoyama, Hirokazu Anai

      ACM Comm. Computer Algebra42 ( 3 ) 144 - 145   2008

      More details

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

      DOI: 10.1145/1504347.1504359

      researchmap

    • Multi-modular algorithm for computing the splitting field of a polynomial Peer-reviewed

      Guénaël Renault, Kazuhiro Yokoyama

      Proceedings of the International Symposium on Symbolic and Algebraic Computation, ISSAC   247 - 254   2008

      More details

      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

    • Symbolic optimization of algebraic functions Peer-reviewed

      Masaaki Kanno, Kazuhiro Yokoyama, Hirokazu Anai, Shinji Hara

      Proceedings of the International Symposium on Symbolic and Algebraic Computation, ISSAC   147 - 154   2008

      More details

      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

    • On systems of algebraic equations with parametric exponents II Peer-reviewed

      Kazuhiro Yokoyama

      APPLICABLE ALGEBRA IN ENGINEERING COMMUNICATION AND COMPUTING18 ( 6 ) 603 - 630   12 2007

      More details

      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

    • Sum of roots, polynomial spectral factorization, and control performance limitations Peer-reviewed

      Masaaki Kanno, Shinji Hara, Hirokazu Anai, Kazuhiro Yokoyama

      Proceedings of the IEEE Conference on Decision and Control   2968 - 2973   2007

      More details

      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

    • On the relationship between the sum of roots with positive real parts and polynomial spectral factorization Peer-reviewed

      Masaaki Kanno, Hirokazu Anai, Kazuhiro Yokoyama

      Numerical Methods and Applications4310   320 - 328   2007

      More details

      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

    • Parametric Optimization in Control Using the Sum of Roots for Parametric Polynomial Spectral Factorization Peer-reviewed

      Masaaki Kanno, Kazuhiro Yokoyama, Hirokazu Anai, Shinji Hara

      ISSAC 2007: PROCEEDINGS OF THE 2007 INTERNATIONAL SYMPOSIUM ON SYMBOLIC AND ALGEBRAIC COMPUTATION   211 - +   2007

      More details

      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

    • On polynomial curves in the affine plane Peer-reviewed

      Mitsushi Fujimoto, Masakazu Suzuki, Kazuhiro Yokoyama

      OSAKA JOURNAL OF MATHEMATICS43 ( 3 ) 597 - 608   9 2006

      More details

      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

    • A modular method for computing the splitting field of a polynomial Peer-reviewed

      Guenael Renault, Kazuhiro Yokoyama

      ALGORITHMIC NUMBER THEORY, PROCEEDINGS4076   124 - 140   2006

      More details

      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

    • Stability of parametric decomposition Peer-reviewed

      Kazuhiro Yokoyama

      MATHEMATICAL SOFTWARE-ICMS 2006, PROCEEDINGS4151   391 - 402   2006

      More details

      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

    • Sum of roots with positive real parts Peer-reviewed

      Hirokazu Anai, Shinji Hara, Kazuhiro Yokoyama

      Proceedings of ISSAC 2005   21 - 28   7 2005

      More details

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

      CiNii Article

      researchmap

    • Cylindrical algebraic decomposition via numerical computation with validated symbolic reconstruction Peer-reviewed

      Hirokazu Anai, Kazuhiro Yokoyama

      Algorithmic Algebra and Logic (A3L2005)   25 - 30   2005

      More details

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

      CiNii Article

      researchmap

    • Implementation of prime decomposition of polynomial ideals over small finite fields Peer-reviewed

      M Noro, K Yokoyama

      JOURNAL OF SYMBOLIC COMPUTATION38 ( 4 ) 1227 - 1246   10 2004

      More details

      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

    • On systems algebraic equations with parametric exponents Peer-reviewed

      Kazuhiro Yokoyama

      Proceedings of ISSAC 2004   312 - 319   7 2004

      More details

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

      CiNii Article

      researchmap

    • Z(3) symmetry and W-3 algebra in lattice vertex operator algebras Peer-reviewed

      CY Dong, CH Lam, K Tanabe, H Yamada, K Yokoyama

      PACIFIC JOURNAL OF MATHEMATICS215 ( 2 ) 245 - 296   6 2004

      More details

      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

    • Yet another practical implementation of polynomial factorization over finite fields Peer-reviewed

      Masayuki Noro, Kazuhiro Yokoyama

      Proceedings of ISSAC 2002   200 - 206   7 2002

      More details

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

      researchmap

    • Order counting of elliptic curves defined over finite fields of characteristic 2 Peer-reviewed

      T Izu, J Kogure, M Noro, K Yokoyama

      ELECTRONICS AND COMMUNICATIONS IN JAPAN PART III-FUNDAMENTAL ELECTRONIC SCIENCE85 ( 1 ) 62 - 70   2002

      More details

      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

    • The block cipher SC2000 Peer-reviewed

      T Shimoyama, H Yanami, K Yokoyama, M Takenaka, K Itoh, J Yajima, N Torii, H Tanaka

      FAST SOFTWARE ENCRYPTION2355   312 - 327   2002

      More details

      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

    • Prime decomposition of polynomial ideals over finite fields Peer-reviewed

      K Yokoyama

      MATHEMATICAL SOFTWARE, PROCEEDINGS   217 - 227   2002

      More details

      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

    • Radical representation of polynomial roots Peer-reviewed

      Hirokazu Anai, Kazuhiro Yokoyama

      JSSAC(日本数式処理学会誌)9 ( 1 ) 53 - 79   2002

      More details

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

      researchmap

    • Elliptic curve cryptosystem

      Naoya Torii, Kazuhiro Yokoyama

      Fujitsu Scientific and Technical Journal36 ( 2 ) 140 - 146   2000

      More details

      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

    • Efficient implementation of Schoof's algorithm in case of characteristic 2 Peer-reviewed

      T Izu, J Kogure, K Yokoyama

      PUBLIC KEY CRYTOGRAPHY1751   210 - 222   2000

      More details

      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

    • Order counting of elliptic curves defined over finite fields of characteristic 2 Peer-reviewed

      Tetsuya Izu, Jun Kogure, Masayuki Noro, Kazuhiro Yokoyama

      The Transactions of the Institute of Electronics,Information and Communication Engineers. A82 ( 8 ) 1253 - 1260   8 1999

      More details

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

      CiNii Article

      researchmap

    • A modular method to compute the rational univariate representation of zero-dimensional ideals Peer-reviewed

      M Noro, K Yokoyama

      JOURNAL OF SYMBOLIC COMPUTATION28 ( 1-2 ) 243 - 263   7 1999

      More details

      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

    • Parameters for secure elliptic curve cryptosystem -improvements on schoof’s algorithm Peer-reviewed

      Tetsuya Izu, Jun Kogure, Masayuki Noro, Kazuhiro Yokoyama

      Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)1431   253 - 257   1998

      More details

      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

    • Efficient implementation of Schoof's algorithm Peer-reviewed

      T Izu, J Kogure, M Noro, K Yokoyama

      ADVANCES IN CRYPTOLOGY - ASIACRYPT'981514   66 - 79   1998

      More details

      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

    • Factoring polynomials over algebraic extension fields Peer-reviewed

      Masayuki Noro, Kazuhiro Yokoyama

      城西大学情報科学研究紀要(Josai Information Science Researches)9 ( 1 ) 11 - 33   1 1998

      More details

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

      CiNii Article

      researchmap

    • A modular method for computing the Galois groups of polynomials Peer-reviewed

      K. Yokoyama

      Journal of Pure and Applied Algebra117-118   617 - 636   1997

      More details

      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

    • Computation of the splitting fields and the Galois groups of polynomials Peer-reviewed

      H Anai, M Noro, K Yokoyama

      ALGORITHMS IN ALGEBRAIC GEOMETRY AND APPLICATIONS143   29 - 50   1996

      More details

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

      researchmap

    • Localization and primary decomposition of polynomial ideals Peer-reviewed

      Takeshi Shimoyama, Kazuhiro Yokoyama

      Journal of Symbolic Computation22 ( 3 ) 247 - 277   1996

      More details

      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

    • Finding roots of unity among quotients of the roots of an integral polynomial Peer-reviewed

      Kazuhiro Yokoyama, Ziming Li, Istvan Nemes

      Proceedings of ISSAC 1995   85 - 89   7 1995

      More details

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

      researchmap

    • MULTI-MODULAR APPROACH TO POLYNOMIAL-TIME FACTORIZATION OF BIVARIATE INTEGRAL POLYNOMIALS Peer-reviewed

      K YOKOYAMA, M NORO, T TAKESHIMA

      JOURNAL OF SYMBOLIC COMPUTATION17 ( 6 ) 545 - 563   6 1994

      More details

      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

    • On Hensel construction of eigenvalues and eigenvectors of matrices with polynomial entries Peer-reviewed

      Kazuhiro Yokoyama, Taku Takeshima

      Proceedings of ISSAC 1993   218 - 224   7 1993

      More details

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

      CiNii Article

      researchmap

    • SOLUTIONS OF SYSTEMS OF ALGEBRAIC EQUATIONS AND LINEAR-MAPS ON RESIDUE CLASS RINGS Peer-reviewed

      K YOKOYAMA, M NORO, T TAKESHIMA

      JOURNAL OF SYMBOLIC COMPUTATION14 ( 4 ) 399 - 417   10 1992

      More details

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

      researchmap

    • ON DISTANCE TRANSITIVE GRAPHS WHOSE AUTOMORPHISM-GROUPS ARE AFFINE Peer-reviewed

      K YOKOYAMA

      JOURNAL OF COMBINATORIAL THEORY SERIES B55 ( 2 ) 190 - 235   7 1992

      More details

      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

    • 代数制約の処理 Peer-reviewed

      竹島 卓, 横山 和弘

      コンピューターソフトウェア9 ( 6 ) 16 - 30   1992

      More details

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

      researchmap

    • ON FACTORING MULTI-VARIATE POLYNOMIALS OVER ALGEBRAICALLY CLOSED FIELDS Peer-reviewed

      K YOKOYAMA, M NORO, T TAKESHIMA

      ISSAC 90 : PROCEEDINGS OF THE INTERNATIONAL SYMPOSIUM ON SYMBOLIC AND ALGEBRAIC COMPUTATION   297 - 297   1990

      More details

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

      researchmap

    • ON DETERMINING THE SOLVABILITY OF POLYNOMIALS Peer-reviewed

      K YOKOYAMA, M NORO, T TAKESHIMA

      ISSAC 90 : PROCEEDINGS OF THE INTERNATIONAL SYMPOSIUM ON SYMBOLIC AND ALGEBRAIC COMPUTATION   127 - 134   1990

      More details

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

      researchmap

    • Computing primitive elements of extension fields Peer-reviewed

      Kazuhiro Yokoyama, Masayuki Noro, Taku Takeshima

      Journal of Symbolic Computation8 ( 6 ) 553 - 580   1989

      More details

      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

    • On Factoring and Computation of GCD over Euclidean Rings : An Application of Lattice Algorithms. Peer-reviewed

      Kazuhiro Yokoyama, Taku Takeshima

        5 ( 5 ) 42 - 61   1 1 1988

      More details

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

      CiNii Article

      researchmap

    • On Distance Transitive Graphs in Which the Stabilizer of a Point Contains an Alternating Group Peer-reviewed

      Kazuhiro Yokoyama

      European Journal of Combinatorics9 ( 4 ) 379 - 390   1988

      More details

      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

    • DISTANCE TRANSITIVE GRAPHS AND FINITE SIMPLE-GROUPS Peer-reviewed

      CE PRAEGER, J SAXL, K YOKOYAMA

      PROCEEDINGS OF THE LONDON MATHEMATICAL SOCIETY55   1 - 21   7 1987

      More details

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

      researchmap

    ▼display all

    Misc.

    ▼display all

    Books and Other Publications

    • 多項式と計算機代数

      横山, 和弘( Role: Sole author)

      朝倉書店  2 2022  ( ISBN:9784254117677

      More details

      Total pages:x, 239p   Language:Japanese

      CiNii Books

      researchmap

    • Algorithms of Quantifier Elimination and their Applications

      Hirokazu Anai, Kazuhiro Yokoyama( Role: Joint author)

      8 2011  ( ISBN:9784130614061

      More details

      Language:Japanese Book type:Scholarly book

      researchmap

    • 岩波数学辞典第4版

      横山 和弘( Role: Other ,  計算機代数)

      岩波書店  3 2007 

      More details

      Language:Japanese Book type:Dictionary, encyclopedia

      researchmap

    • グレブナー基底の計算 基礎篇,計算代数入門

      横山 和弘, 野呂正行( Role: Joint author)

      東京大学出版会  6 2003 

      More details

      Language:Japanese Book type:Other

      researchmap

    Works

    • Application of Computer Algebra to Engineering Other

      4 2000
      -
      Present

      More details

      Work type:Other  

      researchmap

    • 計算機代数の暗号および制御、設計への応用 Other

      4 2000
      -
      Present

      More details

      Work type:Other  

      researchmap

    • オーストリア ヨハネスケプラー大学記号計算研究所(RISC-Linz) 文部科学省在外研究員 Other

      7 2003
      -
      9 2003

      More details

      Work type:Other  

      researchmap

    • フランス パリ第6大学 情報研究所(LIP6) 招聘教育研究者 Other

      5 2000
      -
      7 2000

      More details

      Work type:Other  

      researchmap

    • オーストリア ヨハネスケプラー大学記号計算研究所(RISC-Linz) 客員講師 Other

      11 1994
      -
      11 1995

      More details

      Work type:Other  

      researchmap

    Research Projects

    • グレブナー基底計算の理論計算量解析とその効率的な実装

      日本学術振興会  科学研究費助成事業 

      横山 和弘, 野呂 正行, 篠原 直行

      More details

      4 2021 - 3 2024

      Grant number:21K03377

      Grant amount:\4030000 ( Direct Cost: \3100000 、 Indirect Cost:\930000 )

      令和3年度は第1段階の研究を行った。
      理論解析では、SBAアルゴリズムの計算量やグレブナー基底の計算の高速化に有効とされる多項式環の特定の項順序に関する文献調査を行い、利用できる数学理論の選別を行った。また、グレブナー基底にはならなくても、求めたい形のイデアル生成元を計算する戦略も検討した。これらは令和4年度中に成果をまとめる予定である。
      SBAアルゴリズムの実装とその有効性検証では、多項式環の項順序と整合しない(compatibleでない)加群項順序を用いたSBAアルゴリズムは停止性が保証されないが,
      入力イデアルをある項順序に関するグレブナー基底とすることで, Hilbert-Poincare 級数による停止条件を用いて目的項順序に関するグレブナー基底を有限回の手間で計算する方法を考案した。この方法ではsyzygy criterionにより0簡約が生じないため、モジュラー演算を用いなくても効率よく有理数体上のグレブナー基底が求められる。当初は、非0次元イデアルに対してのみ有効であると予想したが, 実際には 0次元でも有効な場合があることがわかった。
      応用実験では、連立代数方程式に帰着できるいくつかの問題で、SBAアルゴリズムを直接適用する段階ではないが、既存の方法の実験を行った。実験計画法に関するある数え上げ・分類問題では、この方程式は0次元で解が35200個あるが、Risa/Asir の準素分解機能を用いて効率よく求めることができた。暗号応用では、同種写像暗号の基礎となる数学計算にグレブナー基底計算を利用した改良を雑誌で発表した。多変数公開鍵暗号の安全性評価では、連立2次方程式 (MQ問題) を扱い、S多項式及びreductorの選択方法として,多項式の2番目に大きな項に注目した新たな方法を提案し、効率よく計算できることを数値実験的に立証した。

      researchmap

    • Further development of algorithms for Groebner basis computation

      Japan Society for the Promotion of Science  Grants-in-Aid for Scientific Research 

      YOKOYAMA Kazuhiro

      More details

      4 2018 - 3 2021

      Grant number:18K03432

      Grant amount:\4290000 ( Direct Cost: \3300000 、 Indirect Cost:\990000 )

      Groebner bases, bases of polynomial ideals, have useful computational properties and used in a various areas such as mathematics and engineering science. However, there still remains a problem on their computational efficiency. In this project, focusing an efficient technique named SBA, we succeeded in completing its theoretical correctness and termination, and an efficient its implementation on a
      real computer. As a theoretical result, under a reasonable condition "compatibility" on monomial orders, the correctness and termination of our SBA are theoretically guaranteed. By its implementation on a real computer, we devised several algorithms based on SBA, which have certain superiority to existing algorithms. As application study, we applied Groebner basis computation to analyze the security level of public key cryptosystems.

      researchmap

    • Efficient methods for Groebner basis computation, verification and thier applications

      Japan Society for the Promotion of Science  Grants-in-Aid for Scientific Research 

      NORO Masayuki, AOYAMA Toru

      More details

      4 2015 - 3 2018

      Grant number:15K05008

      Grant amount:\4810000 ( Direct Cost: \3700000 、 Indirect Cost:\1110000 )

      We published a paper describing various modular methods for efficient Groebner basis computation. We published two papers concerned with the signature based
      algorithm (SBA). In these papers we proposed several variants of SBA and showed their correctness and termination. F4 and SBA are main methods for attacking elliptic curve cryptography and post-quantum cryptography. We analyzed the complexity when we applied these methods to cryptanalysis. We studied the system of partial differential equations (PDE) satisfied by the cumulative distribution function (CDF) of Wishart matrices and proposed an efficient method for deriving a system of PDE satisfied by the restriction of the CDF on diagonal regions. This is an application of Groebner basis theory to statistics that is a very active research area.

      researchmap

    • Developments ofcomputational theory of real algebraic geometry for optimization problem

      Japan Society for the Promotion of Science  Grants-in-Aid for Scientific Research 

      ANAI Hirokazu, YOKOYAMA Kazuhiro, YANAMI Hitoshi, IWANE Hidenao

      More details

      2009 - 2012

      Grant number:21340025

      Grant amount:\17160000 ( Direct Cost: \13200000 、 Indirect Cost:\3960000 )

      In this project we have developed effective and efficient quantifier elimination algorithms for optimization problems. We had many original results on quantifier elimination algorithms and published them in international academic journals. Moreover, we also published textbooks on quantifier elimination and optimization.

      researchmap

    • 記号代数的近似と数値的近似の組合せによる数値数式融合計算の研究

      日本学術振興会  科学研究費助成事業 

      横山 和弘

      More details

      4 2006 - 3 2009

      Grant number:18654025

      Grant type:Competitive

      数値計算と記号代数計算の双方を組合せる融合計算が「計算の壁を破る」可能性を持つものとして期待されていますが、個々の具体的な問題に対する事例研究の域をでていません。本研究では、有効な数値数式の融合をシステマチックに行える戦略・理論を構築することを最終的な目標とし、そのための第1歩として、『多項式の根、もしくは、連立代数方程式の解の近似を利用した計算の効率化』という枠の下で、2種類の近似値、「数値的な近似値」と「記号代数的な近似値」の組合せの戦略を構築することを試みています。戦略の構築のための具体的な目標とし、以下を設定していました。
      (a)2種類の近似の特性を解析し、その用途、効果を明らかにする。
      (b)計算対象を豊富に用意し、その融合による適用法を個々に構築しその効果を判定する。
      (c)上記結果を総括し、その中から一般的な適応指針、すなわち、戦略法を確立する。
      (a)に関しては、記号代数的な近似の構成法であるHensel構成とその実際の数への引き戻しを重点に九州大学のXavier博士ら若手研究者たちと討論を重ねました。(b)では、多項式のガロア群と分解体計算を継続して取り上げ、パリ第6大学のRenault博士との共同研究を行い、異なる複数の近似を用いることで計算の効率化が実現できることを検証し、成果を国際会議で発表しました。また、さらなる結果をまとめ、平成21年度に開催される国際会議に投稿し受理されました。(c)の総括として複数の異なる近似を利用する方式の開発の有効な切り口が本研究を通して得られ、今後より発展させる道筋ができたものと思います。

      researchmap

    • Research on rationally connected varieties

      Japan Society for the Promotion of Science  Grants-in-Aid for Scientific Research 

      SATO Eiichi, FURUSHIMA Mikio, YOKOYAMA Kazuhiro, TAKAYAMA Shigeharu

      More details

      2007 - 2009

      Grant number:19540037

      Grant amount:\4420000 ( Direct Cost: \3400000 、 Indirect Cost:\1020000 )

      For the study of higher dimensional algebraic varieity X we take a hyperplane section A of X for the use of Lefschetz Theorem and try to find the structure of X by the one of A.This time we studied whether the bundle structure of A is preserved to X and next the structure of blowing-up is also so. Moreover generalizing the method,we investigate the preservation of the extremal ray.As applications we get the following : Theorem. Let us consider a sequence {X_n} of smooth projective varieties so that X_n s an ample divisor in X_{n+1} for each n. Here n runs over each positive integer. Assume X_1 has an elementary contraction f : X_1 -> Y with dim X_1 - dim Y > 1 and dim X_1 > 2.Then for each n there is an inductively extended morphism f_n : X_n -> Y with f_{n-1}=i_{n-1}f_n where i_{n-1} : X_{n-1} -> X_{n} is a natural embedding. For a very general point y of Y a smooth fiber of f_n is a weighted complete intersection for large enough n.The above theorem says that a variety enjoying a sequence {X_n} of smooth projective varieties has the structure of property "symmetry".

      researchmap

    • The Study of theoretical aspects and practical aspect on Grobner Bases

      Japan Society for the Promotion of Science  Grants-in-Aid for Scientific Research 

      HIBI Takayuki, SAITO Mutsumi, TAKEMURA Akimichi, YOKOYAMA Kazuhiro, OHSUGI Hidefumi, OAKU Toshinori, MATSUI Yasuko, SAITO Kyoji, TAKAYAMA Nobuki, AOKI Satoshi

      More details

      2006 - 2009

      Grant number:18340008

      Grant amount:\15850000 ( Direct Cost: \13600000 、 Indirect Cost:\2250000 )

      With taking the persistence and the internationalization into consideration, in collaboration with many researchers in various field including computational commutative algebra, computational algebraic analysis, computational algebraic statistics as well as algebraic algorithm, this research project strongly developed the study on the theoretical effectivity and practical effectivity of Grobner bases and succeeded in establishing the foundations of the modern theory of Grobner bases. At present, in order for our research group to be one of the strongest international footholds on the theoretical and practical research of Grobner bases, the CREST research project "Harmony of Grobner bases and the modern industry society," whose team leader is Takayuki Hibi, which is supported by JST (Japan Science and Technology Agency) follows this research project.

      researchmap

    • 記号・代数計算に基づく計算技法の一般的適用方法論の確立と適用規模の拡大

      (独)科学技術振興機構  受託研究(一般受託研究) 

      More details

      4 2005 - 3 2007

      Grant type:Competitive

      researchmap

    • Development of efficient algorithms and software for solving parametric systems

      Japan Society for the Promotion of Science  Grants-in-Aid for Scientific Research 

      NORO Masayuki, TAKAYAMA Nobuki, SUZUKI Akira, YOKOYAMA Kazuhiro, SATO Yosuke, OHARA Katsuyoshi

      More details

      2005 - 2007

      Grant number:17340028

      Grant amount:\14290000 ( Direct Cost: \13300000 、 Indirect Cost:\990000 )

      The purpose of this research is to develop efficient algorithms and software for solving polynomial systems or system of differential equations containing parameters. The research results are as follows:
      1. Dynamic evaluation allows us to define algebraic numbers by non-irreducible defining polynomial. We reformulated the dynamic evaluation by using the notion of ideal quotient, and we proposed a modular method to improve the computation. We applied the new method for the computation of discrete comprehensive Groebner basis.
      2. We proposed a new method for computing comprehensive Groebner basis (CGB) and comprehensive Groebner system (CGS). This method can be implemented by using Groebner basis computation over usual polynomial ring and it improves the computation of CGB or CGS.
      3. We investigated the structures of polynomial ideals with parameters. In particular, we focused on the stability of parametric polynomial ideals and we found a periodicity and asymptotic behavior of such ideals in simple cases.
      4. We proposed algorithms for doing division with remainder in rings of differential operators over the field of rational functions or the power series rings. We constructed convergent solutions of A-hypergeometric systems. By using the system of difference equations for Gauss hypergeometric functions, we derived their quadratic relations. For computing these objects we developed a software package named ‘yang' for computing in rings of difference-differential operators over the field of rational functions.
      5. All the results above have been implemented in a computer algebra system Risa/Asir, which is available from our web site. In the conferences of Japan Mathematical Society, we held workshops named "Mathematical software and free documents". Furthermore, we constructed a virtual machine on which KNOPPIX/Math runs and we distributed DVDs containing the virtual machine.

      researchmap

    • 数値処理と数式処理の融合による計算機援用解析学の可能性に関する基礎的研究

      日本学術振興会  科学研究費助成事業 

      中尾 充宏, 吉川 敦, 横山 和弘

      More details

      2005 - 2007

      Grant number:17654026

      Grant amount:\3300000 ( Direct Cost: \3300000 )

      研究分担者がそれぞれの分担課題に関して恒常的に検討を続け、以下のような研究実績を得た。
      1.中尾は、前年度に引き続き非線形楕円型境界値問題および定常Navier-Stokes方程式の解に対する数値的検証法の改良・拡張について検討し、特に本年度は、以下の成果を得た。(1)楕円型方程式の検証に関して、double turning pointの検証法を定式化し具体例を与えた。 (2)非凸領域上の定常Navier-Stokes方程式で記述されるStep-flow問題に対してその解の精度保証付きで計算することに成功した。 (3)特異随伴作用素をもつ楕円型問題に対する有限要素解の構成的なL-2誤差評価について、Aubin-Nitscheの技巧を用いない計算機援用的方法により数値的に評価する知見を得た。 (4)空間3次元熱対流問題の精度保証に関して、新たな分岐解の検証定式化とその実例を与えた。
      2.吉川は、ソボレフ空間の計算可能構造について、数値解析における有限要素法との関連を見込むために、ソボレフ関数の近似と近似の評価の管理を帰納的関数により行う手法について知見を得た。
      3.横山は、制御におけるパラメータ値の決定の最適化問題に対して、記号的代数的手法を適用し、大域的最適値を正確に求めることに成功した。数学研究応用では、逆ガロア問題において数値計算による証明を行い、さらに分解体計算では代数的近似を利用した高速化を実現した。

      researchmap

    • Realization of decompositions of algebraic structures on real computer

      Japan Society for the Promotion of Science  Grants-in-Aid for Scientific Research 

      YOKOYAMA Kazuhiro, NORO Masayuki

      More details

      4 2003 - 3 2006

      Grant number:15340011

      Grant type:Competitive

      The goal of the project consists of two aims : The first aim is to examine how high/deep mathematical operations on algebraic structures can be executed on real computer by concentrating on decompositions of algebraic structures. Using symbolic and algebraic computation, we try to realize the mathematical operations related to "decomposition". The second one is to utilize realized operations for studies on mathematics as computational tools. The realized mathematical operations on computer shall support mathematicians to investigate unsolved problems and it can produce certain computer-assisted-proofs. Extending the ability of such computations, we apply those to real engineering problems. For those aims, we selected a number of themes, for which we developed effective/efficient algorithms, implemented those, and examined their ability on computational experiments. We have obtained satisfactory results and found promising approaches for realization of more higher/deeper mathematical operations. We list themes and give details for each :
      (1)Commutative Algebra :
      For prime decomposition of polynomial ideals over finite fields, we obtained an efficient algorithm and its practical implementation. For polynomial ideals with parametric exponents, we defined certain stability of those ideals based on "forms of Groebner bases", and gave a complete algorithm for deciding such stability for simpler cases. We applied "numeric-symbolic computation" to the CAD algorithm for quantifier elimination.
      (2)Commutative Algebra with High Symmetry :
      We obtained a practical method for computing the splitting field of a polynomial with rational coefficients by using p-adic approximations of its roots and information of its Galois group.
      (3)Non-Commutative Algebra :
      We obtained a computer-assisted-proof in classification of irreducible modules of the vertex operator algebra derived from a lattice.
      (4)Supports for Mathematics and Engineering :
      We also obtained a computer-assisted-proof in solving an unsolved conjecture related algebraic curves, and we also applied Groebner bases technique successfully to problems in control theory.

      researchmap

    • 計算可換代数と計算代数幾何についての国際研究集会の企画調査

      日本学術振興会  科学研究費助成事業 

      日比 孝之, 齋藤 睦, 竹村 彰通, 横山 和弘, 大杉 英史, 大阿久 俊則

      More details

      2006 - 2006

      Grant number:18634001

      Grant amount:\3200000 ( Direct Cost: \3200000 )

      研究代表者らは、従来から、組合せ論と計算可換代数に関する国際研究集会を継続的に開催し、当該分野の国際的な研究活動を円滑に推進させる重要な役割を担ってきた。研究代表者らは、類似の趣旨の国際研究集会「計算可換代数と計算代数幾何」を2008年6月、札幌に於いて開催する準備を進めている。目下の所、当該国際研究集会の根幹となる研究領域は、D加群とアルゴリズム、ジェネリックイニシャルイデアルの理論と実践、シテジーとヒルベルト函数、応用数学・情報数学における計算代数幾何的な展開、グレブナー基底の効率的計算、とするのが有力である。当該企画調査では、それらの研究領域の妥当性を慎重に審議した。具体的には、研究代表者と研究分担者が5回の連絡会議を開催し、会議を担当する分担者が研究領域の調査結果を報告し、海外招待講演者の候補者などを議論した。以下、連絡会議の開催時期、開催場所、審議する研究領域、会議を担当した分担者氏名を記載する。
      ●第1回(2006年6月、京都)「D加群とアルゴリズム」
      齋藤睦 大阿久俊則 高山信毅
      ●第2回(2006年7月、東京)「ジェネリックイニシャルイデアル」
      横山和弘 大杉英史 大阿久俊則
      ●第3回(2006年9月、札幌)「シチジーとヒルベルト函数」
      齋藤睦 大杉英史 高山信毅 (Juergen Herzog)
      ●第4回(2006年11月、京都)「情報数学における計算代数的な展開」
      竹村彰通 阪田省二郎 松井泰子 青木敏
      ●第5回(2006年1月、京都)「グレブナー基底の効率的計算」
      横山和弘 松井泰子 高山信毅

      researchmap

    • 数理モデリングの基礎技術

      富士通研究所  受託研究 

      More details

      4 2004 - 3 2005

      Grant type:Competitive

      researchmap

    • グレブナー基底の理論的有効性と実践的有効性に関する共同研究の企画調査

      日本学術振興会  科学研究費助成事業 

      日比 孝之, 齋藤 睦, 竹村 彰通, 大阿久 俊則, 横山 和弘, 大杉 英史

      More details

      2005 - 2005

      Grant number:17634001

      Grant amount:\2900000 ( Direct Cost: \2900000 )

      研究代表者と研究分担者が研究連絡会議を開催し、グレブナー基底の理論的有効性と実践的有効性に関する共同研究の企画調査を実施する旨の研究計画に従い、5月(東京大学)、8月(立教大学)、9月(東京大学)、11月(大阪大学)と研究連絡会議を開催し、それぞれ、竹村彰通が計算代数統計の、大阿久俊則が計算代数解析の、大杉英史が計算可換代数と計算代数幾何の、横山和弘と松井泰子がグレブナー基底の計算の効率化の研究領域に関する調査結果を報告した。なお、8月の研究連絡会議は、日本学術振興会の国際研究集会(立教大学、2005年8月22日〜26日)Theoretical Effectivity and Practical Effectivity of Grobner Basesに付随して開催し、拡大研究連絡会議と称し、Juergen Herzog(ドイツ)、Henry P.Wynn(イギリス)、Uli Walther(米国)を招聘した。海外招聘者は、グレブナー基底の理論的有効性と実践的有効性に関し、それぞれの専門領域における欧米諸国の研究の現状を報告し、組織的な国際共同研究に発展させる際の具体的な指針についての貴重な意見を述べた。
      企画調査の結果、今後、我が国において、少なくとも5年以上の長期に亘って継続されるグレブナー基底の理論と実践に関する共同研究を推進するための総括的な方針を擁立することができ、永続的な国際共同研究に発展することを視野に入れ、実際の研究活動を展開する準備が整った。企画調査の結果を踏まえ、その実際の研究活動とし、京都大学数理解析研究所、平成18年度、プロジェクト研究「グレブナー基底の理論的有効性と実践的有効性」が始まる。

      researchmap

    • 記号・代数計算による最適化問題解法と定理自動証明の研究

      日本学術振興会  科学研究費助成事業 

      横山 和弘, 吉川 敦, 鈴木 昌和, 中尾 充弘, 穴井 宏和

      More details

      4 2002 - 3 2004

      Grant number:14654024

      Grant type:Competitive

      最適化問題に対する新しいアプローチである記号・代数計算を用いたパラメータを含んだまま正確に解く方法の確立を目指し、(1)ベースとなる記号・代数計算理論とその技術の展開と(2)成功事例の発掘とそのためのアルゴルズムの改良と支援ツール構築を行った。
      (1)では、上位レベルである限定子除去法、パラメータ付きの多項式イデアル操作、パラメータ無しの多項式イデアル操作、に分け、最下層のパラメータ無し多項式イデアル操作については、正標数の場合の素イデアル分解アルゴリズムの更なる改良とその計算機上の実装を行い、正標数での問題の克服と計算の効率化に成功した。次のレベルであるパラメータ付きの多項式イデアル操作については、海外共同研究者Weipsfenning教授との研究討論を通じ、指数部分にパラメータを持つ場合を世界に先駆けて取り扱い、0次元の場合において、零点の周期性や有限性を発見し、その計算法を得た。この成果は、preprintとし、国際会議に投稿中である。さらに、係数にパラメータを含む場合についての一般的な解法についてもComprehensive Groebner basis計算法の拡張として考え、研究を進めている。
      (2)では、研究分担者の穴井と定期的にセミナーおよび研究討論を行い、実際の制御計算への限定子除去法の適用を検討してきた。穴井は独自の支援計算ツールSyNRACの構築を開始し、計算機実験を行った。また、記号・代数計算の啓蒙活動として、グレブナー計算に関する書籍を東京大学出版会より出版し、さらに限定子除去法に関する啓蒙書を準備している。また、研究分担者の鈴木は定理自動証明に関して、より一般的な枠組である「数学知識データの数学研究・教育への活用」の中で、計算機上での実現のためのフォーミュレーションを開始した。
      今後、代表者と穴井は、原教授(東京大学)と共同で、萌芽研究での成果を集約し、この経験をベースに、新たなシミュレーション技術の開発と実際のシステムを構築計画を立て、科学技術振興機構・戦略的創造研究推進事業「シミュレーション技術の革新と実用化基盤の構築」の中の「数値/数式ハイブリッド計算に基づくロバスト最適化プラットフォームの構築」として発展させることになった。

      researchmap

    • Development of high performance computer algebra software

      Japan Society for the Promotion of Science  Grants-in-Aid for Scientific Research 

      NORO Masayuki, TAKAYAMA Nobuki, YOKOYAMA Kazuhiro, OHARA Katsuyoshi, SAITO Masahiko

      More details

      2002 - 2004

      Grant number:14340036

      Grant amount:\8700000 ( Direct Cost: \8700000 )

      We developed the following new algorithms and implemented them in Risa/Asir :
      (1)a polynomial-time bivariate polynomial factorization algorithm over small finite fields,
      (2)an algorithm for computing minimal prime divisors of a polynomial ideal over small finite fields,
      (3)an algorithm for computing the global b-function,
      (4)an efficient algorithm for numerical computation of multivariate hypergeometric functions,
      (5)a method for deriving quadratic relations for generalized hypergeometric functions,
      (6)a tangent cone algorithm in the ring of differential operators over power series ring.
      We implemented the following new facilities in Risa/Asir :
      (1)a new package for computing Groebner basis with a new data representation,
      (2)a new package for efficient computation in algebraic number fields.
      We gave the following applications.
      (1)We exactly solved a polynomial system concerned with quantum computing.
      (2)We proved that W_3 algebra of central charge 6/5 is realized as a subalgebra of a lattice vertex operator algebra and classify its irreducible modules.

      researchmap

    • Study on Number Theoretic Algorithms and Developments of Systems for Number Theory

      Japan Society for the Promotion of Science  Grants-in-Aid for Scientific Research 

      NAKAMULA Ken, OKAMOTO Tatsuaki, KURATA Toshihiko, TSUMURA Hirofumi, NAGAO Koh-ichi, KIDA Masanari

      More details

      2001 - 2003

      Grant number:13440013

      Grant amount:\6500000 ( Direct Cost: \6500000 )

      As in the references below, many theoretical results were obtained on number theoretic algorithms and their applications related to Scholz's conjecture on addition chains, Iwasawa invariants, elliptic curves, prime ideal decomposition in polynomial rings, hyperplane arrangement, unramified extensions of quadratic fields, several zeta values, class groups and unit groups of number fields, and cryptology, for example.
      The 4th to 11th meetings were held each with about 50 participants by our main research organization JANT, and, the details are reported in http://ntw.e-one.uec.ac.jp/jant. As a result, we edited two special issues of Transactions of the JSIAM on the topics of the most advanced results and a general survey on number theoretic algorithms, and held an organized session at the yearly meeting of the JSIAM. To exchange with broader areas of algebra, we organized the 4th and 5th meetings of Algebra and Computation' (AC2001 and AC2003) each with almost 150 participants including those from abroad and published the proceedings at ftp://tnt.math.metro-u.ac.jp/pub/ac0[13]/. For wide international exchange of mathematical software research, we help the international Congress of Mathematical Softwares ICMS2002 at Beijin with about 110participants.
      We took over the system for number theory SIMATH, developed in Germany since 1980's with highly efficient functions for elliptic curves, and have been maintaining and supporting via http://simath.info/. We have succeeded in implementing it on 64 bit machines, have released it as Ver.4.6, and packaged and installed the CEM up to cubic fields. After that, restricting ourselves to maintain SIMATH as it is because of the problems of license and development environment, we started to develop a new system NZMATH by the script language Python, released its alpha version at http://tnt.math.metro-u.ac.jp/nzmath/, and we are going to create a system for number theory constructed together by developers and users of the system.

      researchmap

    • Study on Algebraic Algorithms

      More details

      Grant type:Competitive

      researchmap

    • Study on Algebraic Combinatorics

      More details

      Grant type:Competitive

      researchmap

    • Study on Application of Algebraic Algorithm to Engineering

      More details

      Grant type:Competitive

      researchmap

    • 代数的算法に関する研究

      More details

      Grant type:Competitive

      researchmap

    • 代数的算法の工学(暗号等)への応用に関する研究

      More details

      Grant type:Competitive

      researchmap

    • 代数的組合せ論に関する研究

      More details

      Grant type:Competitive

      researchmap

    ▼display all

    Social Contribution

    • 計算機代数国際会議 ISSAC

      1 2005 - 12 2005

      More details

      プログラム委員

      researchmap

    • 計算数学国際会議 ASCM

      1 2003 - 12 2003

      More details

      プログラム委員

      researchmap

    • 計算数学国際会議 ICMS

      1 2002 - 12 2002

      More details

      プログラム委員

      researchmap

    • 計算数学国際会議 ASCM

      1 2001 - 12 2001

      More details

      プログラム委員長

      researchmap

    • 計算数学国際会議 ASCM

      1 2000 - 12 2000

      More details

      プログラム委員

      researchmap

    • Journal of Symbolic Computation 計算ガロア理論特集号

      1 1997 - 12 1997

      More details

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

      researchmap

    • 計算機代数国際会議 ISSAC

      1 1997 - 12 1997

      More details

      プログラム委員

      researchmap

    • 計算機代数国際会議 ISSAC

      1 1995 - 12 1995

      More details

      ポスタープログラム委員

      researchmap

    • ACM ISSAC Steering Committee

      1 1900

      More details

    • 計算機代数国際会議 ICPSS

      1 1900

      More details

      プログラム委員

      researchmap

    ▼display all