In certain computational systems the amount of space required to execute an algorithm is even more restrictive than the corresponding time necessary for solution of a problem. In this paper an algorithm for modular mu...In certain computational systems the amount of space required to execute an algorithm is even more restrictive than the corresponding time necessary for solution of a problem. In this paper an algorithm for modular multiplicative inverse is introduced and its computational space complexity is analyzed. A tight upper bound for bit storage required for execution of the algorithm is provided. It is demonstrated that for range of numbers used in public-key encryption systems, the size of bit storage does not exceed a 2K-bit threshold in the worst-case. This feature of the Enhanced-Euclid algorithm allows designing special-purpose hardware for its implementation as a subroutine in communication-secure wireless devices.展开更多
In this paper, the concept of a finite mass-points system ΣN(H(A))(N > n) being in a sphere in an n-dimensional hyperbolic space H n and a finite mass-points system ΣN(S(A))(N > n) being in a hyperplane in an ...In this paper, the concept of a finite mass-points system ΣN(H(A))(N > n) being in a sphere in an n-dimensional hyperbolic space H n and a finite mass-points system ΣN(S(A))(N > n) being in a hyperplane in an n-dimensional spherical space S n is introduced, then, the rank of the Cayley-Menger matrix-ΛN(H) (or a-ΛN(S)) of the finite mass-points system ΣN(S(A)) (or ΣN(S(A))) in an n-dimensional hyperbolic space H n (or spherical space S n) is no more than n + 2 when ΣN(H(A))(N > n) (or ΣN(S(A))(N > n)) are in a sphere (or hyperplane). On the one hand, the Yang-Zhang’s inequalities, the Neuberg-Pedoe’s inequalities and the inequality of the metric addition in an n-dimensional hyperbolic space H n and in an n-dimensional spherical space S n are established by the method of characteristic roots. These are basic inequalities in hyperbolic geometry and spherical geometry. On the other hand, some relative problems and conjectures are brought.展开更多
文摘In certain computational systems the amount of space required to execute an algorithm is even more restrictive than the corresponding time necessary for solution of a problem. In this paper an algorithm for modular multiplicative inverse is introduced and its computational space complexity is analyzed. A tight upper bound for bit storage required for execution of the algorithm is provided. It is demonstrated that for range of numbers used in public-key encryption systems, the size of bit storage does not exceed a 2K-bit threshold in the worst-case. This feature of the Enhanced-Euclid algorithm allows designing special-purpose hardware for its implementation as a subroutine in communication-secure wireless devices.
基金This work was partially supported by the National Key Basic Research Project of China(Grant No.2004CB318003).
文摘In this paper, the concept of a finite mass-points system ΣN(H(A))(N > n) being in a sphere in an n-dimensional hyperbolic space H n and a finite mass-points system ΣN(S(A))(N > n) being in a hyperplane in an n-dimensional spherical space S n is introduced, then, the rank of the Cayley-Menger matrix-ΛN(H) (or a-ΛN(S)) of the finite mass-points system ΣN(S(A)) (or ΣN(S(A))) in an n-dimensional hyperbolic space H n (or spherical space S n) is no more than n + 2 when ΣN(H(A))(N > n) (or ΣN(S(A))(N > n)) are in a sphere (or hyperplane). On the one hand, the Yang-Zhang’s inequalities, the Neuberg-Pedoe’s inequalities and the inequality of the metric addition in an n-dimensional hyperbolic space H n and in an n-dimensional spherical space S n are established by the method of characteristic roots. These are basic inequalities in hyperbolic geometry and spherical geometry. On the other hand, some relative problems and conjectures are brought.
