View Single Post
Old 2019-09-29, 15:48   #17
R. Gerbicz
R. Gerbicz's Avatar
"Robert Gerbicz"
Oct 2005

136310 Posts

Originally Posted by baih View Post
my solution are :qp =c

lets n is integer

e= (c+1)/4

s= n^e Mod c

q= gcd(s-n,c)

for your example :
Yes, more detail:
If n=p*q, and (n+1)/4==1 mod (p-1) then
(p-1) | e=(n-3)/4 with Fermat (for every b)
b^e-1 is divisible by p so p|gcd(b^e-1,n) and in general it is in fact p (and not n).

So (partial) factorization is easy when we know p|n and n mod (p-1).
Say we know that n==r/s mod (p-1) for tiny r,s (in solution just try all r,s pair).

Last fiddled with by R. Gerbicz on 2019-09-29 at 15:48
R. Gerbicz is offline   Reply With Quote