Primitive elements play important roles in the Diffie-Hellman protocol for establishment of secret communication keys, in the design of the ElGamal cryptographic system and as generators of pseudo-random numbers. In g...Primitive elements play important roles in the Diffie-Hellman protocol for establishment of secret communication keys, in the design of the ElGamal cryptographic system and as generators of pseudo-random numbers. In general, a deterministic algorithm that searches for primitive elements is currently unknown. In information-hiding schemes, where a primitive element is the key factor, there is the freedom in selection of a modulus. This paper provides a fast deterministic algorithm, which computes every primitive element in modular arithmetic with special moduli. The algorithm requires at most O(log2p) digital operations for computation of a generator. In addition, the accelerated-descend algorithm that computes small generators is described in this paper. Several numeric examples and tables illustrate the algorithms and their properties.展开更多
In this paper, we prove the following result: Let a and bbe large integers, satistying that (a, b)=1. If Diophantine equation ax+by=z has solutions: |x|=O(log2ab) |y|=O(log2ab) |z|=O(log2ab). then there is a polynomia...In this paper, we prove the following result: Let a and bbe large integers, satistying that (a, b)=1. If Diophantine equation ax+by=z has solutions: |x|=O(log2ab) |y|=O(log2ab) |z|=O(log2ab). then there is a polynomial-time algorithm that factors a large integern = ab, which runs in O(log2^6n)time. Based on the proposed algorithm, we can factor easily n=1600000000000000229500000000000003170601. In fact, we have n=20000000000000002559×80000000000000001239, where 0000000000000002559 and 80000000000000001239 are all safe primes. Our result also shows that some sale primes are not safe.展开更多
How to select a generator of Zp^* is an important problem in cryptographic applications, where p is an odd prime. In this paper, we mainly consider the especial case that p is a safe prime, and give an algorithm for s...How to select a generator of Zp^* is an important problem in cryptographic applications, where p is an odd prime. In this paper, we mainly consider the especial case that p is a safe prime, and give an algorithm for selecting a generator of Zp^* , and find all generators of Zp^* , where p is a safe prime. Our algorithm is more faster than the algorithm in [1]. Based on the proposed algorithm, one could find all generators of Zp^* as well, where p is a perfect prime.展开更多
文摘Primitive elements play important roles in the Diffie-Hellman protocol for establishment of secret communication keys, in the design of the ElGamal cryptographic system and as generators of pseudo-random numbers. In general, a deterministic algorithm that searches for primitive elements is currently unknown. In information-hiding schemes, where a primitive element is the key factor, there is the freedom in selection of a modulus. This paper provides a fast deterministic algorithm, which computes every primitive element in modular arithmetic with special moduli. The algorithm requires at most O(log2p) digital operations for computation of a generator. In addition, the accelerated-descend algorithm that computes small generators is described in this paper. Several numeric examples and tables illustrate the algorithms and their properties.
文摘In this paper, we prove the following result: Let a and bbe large integers, satistying that (a, b)=1. If Diophantine equation ax+by=z has solutions: |x|=O(log2ab) |y|=O(log2ab) |z|=O(log2ab). then there is a polynomial-time algorithm that factors a large integern = ab, which runs in O(log2^6n)time. Based on the proposed algorithm, we can factor easily n=1600000000000000229500000000000003170601. In fact, we have n=20000000000000002559×80000000000000001239, where 0000000000000002559 and 80000000000000001239 are all safe primes. Our result also shows that some sale primes are not safe.
文摘How to select a generator of Zp^* is an important problem in cryptographic applications, where p is an odd prime. In this paper, we mainly consider the especial case that p is a safe prime, and give an algorithm for selecting a generator of Zp^* , and find all generators of Zp^* , where p is a safe prime. Our algorithm is more faster than the algorithm in [1]. Based on the proposed algorithm, one could find all generators of Zp^* as well, where p is a perfect prime.
