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.展开更多
基金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.