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.展开更多
文摘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.
