How to quickly compute the number of points on an Elliptic Curve （EC） has been a longstanding challenge. The computational complexity of the algorithm usually employed makes it highly inefficient. Unlike the general...How to quickly compute the number of points on an Elliptic Curve （EC） has been a longstanding challenge. The computational complexity of the algorithm usually employed makes it highly inefficient. Unlike the general EC, a simple method called the Weil theorem can be used to compute the order of an EC characterized by a small prime number, such as the Kobltiz EC characterized by two. The fifteen secure ECs recommended by the National Institute of Standards and Technology （NIST） Digital Signature Standard contain five Koblitz ECs whose maximum base domain reaches 571 bits. Experimental results show that the computation speed decreases for base domains exceeding 600 bits. In this paper, we propose a simple method that combines the Weil theorem with Pascals triangle, which greatly reduces the computational complexity. We have validated the performance of this method for base fields ranging from 2l^100 to 2^1000. Furthermore, this new method can be generalized to any ECs characterized by any small prime number.展开更多
Projective invariants are not only important objects in mathematics especially in geometry,but also widely used in many practical applications such as in computer vision and object recognition. In this work,we show a ...Projective invariants are not only important objects in mathematics especially in geometry,but also widely used in many practical applications such as in computer vision and object recognition. In this work,we show a projective invariant named as characteristic number,from which we obtain an intrinsic property of an algebraic hypersurface involving the intersections of the hypersurface and some lines that constitute a closed loop. From this property,two high-dimensional generalizations of Pascal's theorem are given,one establishing the connection of hypersurfaces of distinct degrees,and the other concerned with the intersections of a hypersurface and a simplex.展开更多
基金supported by the National Natura Science Foundation of China (Nos.61332019 61572304, 61272056, and 60970006)the Innovation Grant of Shanghai Municipal Education Commission (No.14ZZ089)Shanghai Key Laboratory of Specialty Fiber Optics and Optical Access Networks (No.SKLSFO2014-06)
文摘How to quickly compute the number of points on an Elliptic Curve （EC） has been a longstanding challenge. The computational complexity of the algorithm usually employed makes it highly inefficient. Unlike the general EC, a simple method called the Weil theorem can be used to compute the order of an EC characterized by a small prime number, such as the Kobltiz EC characterized by two. The fifteen secure ECs recommended by the National Institute of Standards and Technology （NIST） Digital Signature Standard contain five Koblitz ECs whose maximum base domain reaches 571 bits. Experimental results show that the computation speed decreases for base domains exceeding 600 bits. In this paper, we propose a simple method that combines the Weil theorem with Pascals triangle, which greatly reduces the computational complexity. We have validated the performance of this method for base fields ranging from 2l^100 to 2^1000. Furthermore, this new method can be generalized to any ECs characterized by any small prime number.
基金supported by National Natural Science Foundation of China(Grant Nos.61033012,11171052 and 61328206)
文摘Projective invariants are not only important objects in mathematics especially in geometry,but also widely used in many practical applications such as in computer vision and object recognition. In this work,we show a projective invariant named as characteristic number,from which we obtain an intrinsic property of an algebraic hypersurface involving the intersections of the hypersurface and some lines that constitute a closed loop. From this property,two high-dimensional generalizations of Pascal's theorem are given,one establishing the connection of hypersurfaces of distinct degrees,and the other concerned with the intersections of a hypersurface and a simplex.
