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