As we examine the behaviour of the number field sieve(NFS) in the medium prime case, we notice various patterns that can be exploited to improve the running time of the sieving stage. The contributions of these observ...As we examine the behaviour of the number field sieve(NFS) in the medium prime case, we notice various patterns that can be exploited to improve the running time of the sieving stage. The contributions of these observations to the computational mathematics community are twofold. Firstly, we clarify the understanding of the true practical effectiveness of the algorithm. Secondly, we propose a test for a better choice of the polynomials used in the NFS. These results are of particular interest to cryptographers as the run-time of the NFS directly determines the security level of some discrete logarithm problem based protocols.展开更多
In this paper,the integer N = pkq is called a <k,1>-integer,if p and q are odd primes with almost the same size and k is a positive integer. Such integers were previously proposed for various cryptographic appli...In this paper,the integer N = pkq is called a <k,1>-integer,if p and q are odd primes with almost the same size and k is a positive integer. Such integers were previously proposed for various cryptographic applications. The conditional factorization based on lattice theory for n-bit <k,1>-integersis considered,and there is an algorithm in time polynomial in n to factor these integers if the least significant 「((2k-1)n)/((3k-1)(k+1))」bits of p are given.展开更多
文摘As we examine the behaviour of the number field sieve(NFS) in the medium prime case, we notice various patterns that can be exploited to improve the running time of the sieving stage. The contributions of these observations to the computational mathematics community are twofold. Firstly, we clarify the understanding of the true practical effectiveness of the algorithm. Secondly, we propose a test for a better choice of the polynomials used in the NFS. These results are of particular interest to cryptographers as the run-time of the NFS directly determines the security level of some discrete logarithm problem based protocols.
基金the National Natural Science Foundation of China (No.60473021).
文摘In this paper,the integer N = pkq is called a <k,1>-integer,if p and q are odd primes with almost the same size and k is a positive integer. Such integers were previously proposed for various cryptographic applications. The conditional factorization based on lattice theory for n-bit <k,1>-integersis considered,and there is an algorithm in time polynomial in n to factor these integers if the least significant 「((2k-1)n)/((3k-1)(k+1))」bits of p are given.
