Evolutionary computation techniques have mostly been used to solve various optimization problems, and it is well known that graph isomorphism problem （GIP） is a nondeterministic polynomial problem. A simulated annea...Evolutionary computation techniques have mostly been used to solve various optimization problems, and it is well known that graph isomorphism problem （GIP） is a nondeterministic polynomial problem. A simulated annealing （SA） algorithm for detecting graph isomorphism is proposed, and the proposed SA algorithm is well suited to deal with random graphs with large size. To verify the validity of the proposed SA algorithm, simulations are performed on three pairs of small graphs and four pairs of large random graphs with edge densities 0.5, 0.1, and 0.01, respectively. The simulation results show that the proposed SA algorithm can detect graph isomorphism with a high probability.展开更多
The isomorphism of polynomials （IP）, one of the hard problems in multivariate public key cryptography induces an equivalence relation on a set of systems of polynomials. Then the enumeration problem of IP consists o...The isomorphism of polynomials （IP）, one of the hard problems in multivariate public key cryptography induces an equivalence relation on a set of systems of polynomials. Then the enumeration problem of IP consists of counting the numbers of different classes and counting the cardinality of each class that is highly related to the scale of key space for a multivariate publi9 key cryptosystem. In this paper we show the enumeration of the equivalence classes containing ∑n-1 i=0 aiX^2qi when char（Fq） = 2, which implies that these polynomials are all weak IP instances. Moreover, we study the cardinality of an equivalence class containing the binomial aX2qi ＋ bX2qj （i ≠ j） over Fqn without the restriction that char（Fq） = 2, which gives us a deeper understanding of finite geometry as a tool to investigate the enumeration problem of IP.展开更多
基金the National Natural Science Foundation of China (60373089, 60674106, and 60533010)the National High Technology Research and Development "863" Program (2006AA01Z104)
文摘Evolutionary computation techniques have mostly been used to solve various optimization problems, and it is well known that graph isomorphism problem （GIP） is a nondeterministic polynomial problem. A simulated annealing （SA） algorithm for detecting graph isomorphism is proposed, and the proposed SA algorithm is well suited to deal with random graphs with large size. To verify the validity of the proposed SA algorithm, simulations are performed on three pairs of small graphs and four pairs of large random graphs with edge densities 0.5, 0.1, and 0.01, respectively. The simulation results show that the proposed SA algorithm can detect graph isomorphism with a high probability.
基金supported by National Basic Research Program of China (973 Program)(Grant No. 2011CB302400)National Natural Science Foundation of China (Grant No. 60970152)Grand Project of Institute of Software (Grant No. YOCX285056)
文摘The isomorphism of polynomials （IP）, one of the hard problems in multivariate public key cryptography induces an equivalence relation on a set of systems of polynomials. Then the enumeration problem of IP consists of counting the numbers of different classes and counting the cardinality of each class that is highly related to the scale of key space for a multivariate publi9 key cryptosystem. In this paper we show the enumeration of the equivalence classes containing ∑n-1 i=0 aiX^2qi when char（Fq） = 2, which implies that these polynomials are all weak IP instances. Moreover, we study the cardinality of an equivalence class containing the binomial aX2qi ＋ bX2qj （i ≠ j） over Fqn without the restriction that char（Fq） = 2, which gives us a deeper understanding of finite geometry as a tool to investigate the enumeration problem of IP.
