CONDITIONAL FACTORIZATION BASED ON LATTICE THEORY FOR 〈K,1〉-INTEGERS

In this paper, the integer N = p^kq 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〉-integers is 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.