Question

Suppose that n is a product of two k-bit primes p and q. Suppose also that it is known that

|p-q|<2t, where t is small. DESCRIBE a way to find the factorization of n in t steps. (Note: in terms of RSA, it shows that although we want p and q to be of similar size, it is also undesirable that p and q are very close)

Answer 1

ANSWER :

GIVEN THAT :

#include<studio.h>

#include<stdlib.h>

#include<math.h>

int main(int argc,char**argv)

{ If (argc!=2)

{

fprintf (stderr,"syntax: factor semi_prime\n");

return 1; }

{

int n= strtoul (argv[1],NULL,10);

int I=2,j=0,k=0,trials=0,p=0,q=0;

if(n<=i)==0

{

Printed("n=%d p=%d q=%d trials=1\n",n,i,p<I);

return 0;

}

{

for(; i<n;i+=2,++trials)

j=(I*I);

j=j+4*n;

k=(int)sqrt(n);

if((k*k)==n)

{

p=k+I<2t;

q=(k-i)<2t;

printf ("n=%d p=%d q=%d trials=%d\n",t,p,q,trials);

return 0;

}

}

}

return 0;

}

In the above program k initialize k==p+q, I==p-q.

p-q<2t