Let n=pq, with primes $p=x^a +1$ and $q=x^b+1$, for $x$, $a$, $b$ integers with $a$ not equal to $b$. Is $n$ hard to factor? If not what would be an algorithm and its complexity?
Asked
Active
Viewed 71 times
1
-
Should be easing using Pollard's algorithm as p-1 has many small factors. 2^(k) for k a divisor of p-1 can be equal to 1 modulo p, so if you compute large powers of 2 modulo N and subtract 1 this may be zero modulo p, you can find that out by taking the GCD with N. – Count Iblis Mar 14 '16 at 22:34
-
If $x^a+1$ is prime then $x$ is even and $a$ is a power of $2$. That narrows the search considerably. – lulu Mar 14 '16 at 22:35
-
Lulu, is that the only cases for p and q to be prime? If so why is that? Thanks – Crypto-enthusiast Mar 15 '16 at 08:43
-
a, b, and x must be positive integers! I think I forgot to mention that. – Crypto-enthusiast Mar 15 '16 at 10:25