论文部分内容阅读
In this paper, we prove the following result: Let a and bbe large integers, satisfying that (a, b)=1. If Diophantine equation ax+by=z has solutions: |X0|=O(log2ab) |y0|=O(log2ab) |Z0|=O(log2ab) then there is a polynomial-time algorithm that factors a large integern = ab , which runs in O(log2 6 n) time. Based on the proposed algorithm, we can factor easily n=1600000000000000229500000000000003170601. In fact, we have n=20000000000000002559 ×80000000000000001239, where 20000000000000002559 and 80000000000000001239 are all safe primes. Our result also shows that some safe primes are not safe.
In this paper, we prove the following result: Let a and bbe large integers, satisfying that (a, b) = 1. If Diophantine equation ax + by = z has solutions: | X0 | = O (log2ab) | y0 | O (log2ab) then Z0 | = O (log2ab) then there is a polynomial-time algorithm that factors a large integern = ab, which runs in O (log2 6 n) time. Based on the proposed algorithm, we can factor easily n = 1600000000000000229500000000000003170601. In fact, we have n = 20000000000000002559 × 80000000000000001239, where 20000000000000002559 and 80000000000000001239 are all safe primes. Our result also shows that some safe primes are not safe.