检索结果-内蒙古大学图书馆

ALGORITHMS BASED ON *-ALGEBRAS, AND THEIR APPLICATIONS TO isomorphism OF POLYNOMIALS WITH ONE SECRET, GROUP isomorphism, AND POLYNOMIAL IDENTITY TESTING

引用

SIAM JOURNAL ON COMPUTING 2019年第3期48卷 926-963页

作者： Ivanyos, Gabor Qiao, Youming Hungarian Acad Sci Inst Comp Sci & Control H-1111 Budapest Hungary Univ Technol Sydney Ctr Quantum Software & Informat Parramatta NSW 2150 Australia

We consider two basic algorithmic problems concerning tuples of (skew-)symmetric matrices. The first problem asks us to decide, given two tuples of (skew-)symmetric matrices (B-1, . . . , B-m) and (C-1, . . . , C-m), whether there exists an invertible matrix A such that for every i is an element of{1, . . . , m}, A(t)B(i)A = C-i. We show that this problem can be solved in randomized polynomial time over finite fields of odd size, the reals, and the complex numbers. The second problem asks us to decide, given a tuple of square matrices (B-1, . . . , B-m), whether there exist invertible matrices A and D, such that for every i is an element of{1, . . . , m}, AB(i)D is (skew-)symmetric. We show that this problem can be solved in deterministic polynomial time over fields of characteristic not 2. For both problems we exploit the structure of the underlying *-algebras (algebras with an involutive antiautomorphism) and utilize results and methods from the module isomorphism problem. Applications of our results range from multivariate cryptography to group isomorphism and to polynomial identity testing. Specifically, these results imply efficient algorithms for the following problems. (1) Test isomorphism of quadratic forms with one secret over a finite field of odd size. This problem belongs to a family of problems that serves as the security basis of certain authentication schemes proposed by Patarin [J. Patarin, in Advances in Cryptology, EUROCRYPT '96, Springer, Berlin, 1996, pp. 33-48]. (2) Test isomorphism of p-groups of class 2 and exponent p (p odd) with order p(l) in time polynomial in the group order, when the commutator subgroup is of order pO((root l)). (3) Deterministically reveal two families of singularity witnesses caused by the skew-symmetric structure. This represents a natural next step for the polynomial identity testing problem, in the direction set up by the recent resolution of the noncommutative rank problem [A. Garg et al., in Proceedings of the 57th

关键词： multivariate cryptography group isomorphism problem polynomial identity testing involutive algebra module isomorphism

来源：评论

学校读者我要写书评

暂无评论

Polynomial-time algorithms for quadratic isomorphism of polynomials: The regular case

引用

JOURNAL OF COMPLEXITY 2015年第4期31卷 590-616页

作者： Berthomieu, Jeremy Faugere, Jean-Charles Perret, Ludovic Univ Paris 06 Sorbonne Univ Equipe PoLSvs LIP6 F-75005 Paris France CNRS LIP6 UMR 7606 F-75005 Paris France INRIA Equipe PoLSYs Ctr Paris Rocquencourt F-75005 Paris France

Let f = (f1,...,f(m)) and g = (g(1),...,gm) be two sets of in >= 1 nonlinear polynomials in K[x(1),...,x(n)] (K being a field). We consider the computational problem of finding - if any - an invertible transformation on the variables mapping f to g. The corresponding equivalence problem is known as isomorphism of Polynomials with one Secret (IP1S) and is a fundamental problem in multivariate cryptography. Amongst its applications, we can cite Graph isomorphism (GI) which reduces to equivalence of cubic polynomials with respect to an invertible linear change of variables, according to Agrawal and Saxena. The main result is a randomized polynomialtime algorithm for solving IP1S for quadratic instances a particular case of importance in cryptography. To this end, we show that IP1S for quadratic polynomials can be reduced to a variant of the classical module isomorphism problem in representation theory. We show that we can essentially linearize the problem by reducing quadratic-IP1S to test the orthogonal simultaneous similarity of symmetric matrices;this latter problem was shown by Chistov, Ivanyos and Karpinski (ISSAC 1997) to be equivalent to finding an invertible matrix in the linear space K-nxn of n x n matrices over K and to compute the square root in a certain representation in a matrix algebra. While computing square roots of matrices can be done efficiently using numerical methods, it seems difficult to control the bit complexity of such methods. However, we present exact and polynomial-time algorithms for computing a representation of the square root of a matrix in K-nxn, for various fields (including finite fields), as a product of two matrices. Each coefficient of these matrices lies in an extension field of K of polynomial degree. We then consider #IP1S, the counting version of IP1S for quadratic instances. In particular, we provide a (complete) characterization of the automorphism group of homogeneous quadratic polynomials. Finally, we also consider the mo

关键词： Quadratic forms Computer algebra Polynomial isomorphism Multivariate cryptography module isomorphism

来源：评论

学校读者我要写书评

暂无评论

Single elements and module isomorphisms of some operator algebra modules

引用

PROCEEDINGS OF THE AMERICAN MATHEMATICAL SOCIETY 2007年第1期135卷 191-200页

作者： Zhe, Dong Zhejiang Univ Dept Math Hangzhou 310027 Peoples R China

In this paper, we first introduce the concept of single elements in a module. A systematic study of single elements in the AlgL-module U is initiated, where L is a completely distributive subspace lattice on a Hilbert space H. Furthermore, as an application of single elements, we study module isomorphisms between norm closed AlgN-modules, where N is a nest, and obtain the following result: Suppose that U, V are norm closed AlgN-modules and that Phi : U -> V is a module isomorphism. Then U = V and there exists a non-zero complex number lambda such that Phi(T) = lambda T, for all T is an element of U.

关键词： single element module isomorphism nest algebra module

来源：评论

学校读者我要写书评

暂无评论

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

建议与咨询 留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案： 新增检索档案 确定 取消

请选择收藏分类： 新增自定义分类 确定 取消

通借通还

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

请选择保存的检索档案：

请选择收藏分类：