# Which impact on security (factorization) has a common prime factor among prime factors? $N=P\cdot Q$ with $P=2\cdot F\cdot p+1$, $Q=2\cdot F\cdot q+1$

Which impact on security (factorization) has a common prime factor among the prime factors $$P$$,$$Q$$ of a number $$N$$ $$N=P\cdot Q$$ $$P=2\cdot F\cdot p+1$$ $$Q=2\cdot F\cdot q+1$$ with $$F,q,p$$ different primes and $$F$$ the biggest prime factor of $$P$$ and $$Q$$ with $$F\gg p,q$$

A potential adversary who want to factorize $$N$$ does know about the internal structure but does not know $$F,p,q,P,Q$$

For example $$N$$ is a $$1024$$-bit number with $$P,Q \approx$$ $$512$$-bit each.
$$F \approx 461$$-bit and $$p,q \approx 50$$-bit each.
Would security significantly change for larger $$N,F$$ but constant size $$p,q$$?
Or how would security change for larger/smaller $$p,q$$ but constant size of $$N$$?

--

Edit Update: It turned out a common factor is not necessary. I did some more detailed question.

There is a large weakness in 1024 bit products created according to the method described if you reuse F.

If N1 and N2 are both created with the same F, F can be calculated immediately:

G = gcd(N1-1,N2-1) = 2Fk.


Factor G to get F, which is easy to spot because it is length 461 bits.

Additionally, security can be significantly weakened if the difficulty of factoring N-1 is significantly easier than factoring N.

N-1 is a composite which can be significantly easier to factor than a 1024 bit product of two 512 bit primes.

Based on the definitions and limitations of F, p and q in the question: N = (2Fp+1)(2Fq+1)

Expanding N = 4*F^2pq+2Fp+2Fq+1

Rearranging N = 2F(2Fpq+p+q)+1

N-1 = 2F(2Fpq+p+q)

After factoring N-1 you have F, an approx. 461 bit prime.

Let u be (N-1)/2F = (2Fpq+p+q)

u = (2Fpq+p+q)

Then calculate s = mod(u,2F) = p+q,

q = s-p


Substitute s-p for q and s for p+q

u = (2Fp(s-p)+s)

u = 2Fps-2Fp^2+s


This results in a quadratic in p

-2Fp^2+2Fsp+s-u = 0


p = (Fs - sqrt(F(Fs^2 + 2s - 2u)))/(2F)

q = s-p

The two approx 512 bit primes can now be calculated.

N = (2Fp+1)(2Fq+1)

Note that factoring N-1 may still take a significant amount of time requiring GNFS or CADO-NFS, but still significantly easier to factor than a 1024 bit product of two 512 bit primes.

• is factoring '$N-1 = 2F(2Fpq+p+q)$' that easy? It's still an 922-bit number. How much easier is it compared to a regular used 922-bit number? Current record of a hard number is 829-bit. If it is easy. Does it significantly depend at the size of $F$? We could scale it as big as we want as long $p,q$ have a constant size. Mar 25, 2022 at 14:46
• ah ok, '$(2Fpq+p+q)$' may be factorized easily. How about we take care about this and set it to a small number times a $500$-bit prime? Would it be still easy? Mar 25, 2022 at 14:56