Question

Finding p and q. We discussed several times that knowing any one of the secret values in RSA would lead to knowing the others. Clearly if one knows p, one can find q and, from those two values, φ(n) and d. Not knowing p but knowing φ(n) can, as we've seen, also work. Here's another approach to that:

• Use φ(n) = (p-1)(q-1) = pq-p-q+1 to determine p+q.
• Use (p-q)² = p²-2pq+q² to find p-q. (Hint: Add 4pq-4pq to the right side).

From those two values, one can easily find p and q.

Now, apply this technique to the values:

• n=898607526590969848863184322603417866026220164569611859928589
• φ(n) = 898607526590969848863184322601520436048324820954773803576156

Your answer will be the values of p and q in a text block with the format:

=PQ=
Lastname, FirstName
p 
q 

In Java

Answer 1

import java.math.BigInteger;

public class RSA{

     public static void main(String []args){
        BigInteger n = new BigInteger("898607526590969848863184322603417866026220164569611859928589");
        BigInteger phi = new BigInteger("898607526590969848863184322601520436048324820954773803576156");
      
        BigInteger one = new BigInteger("1");
        BigInteger two = new BigInteger("2");
        BigInteger four = new BigInteger("4");
      
        BigInteger p_plus_q = n.add(one);
                   p_plus_q = p_plus_q.subtract(phi);
        BigInteger p_plus_q_square = p_plus_q.multiply(p_plus_q);
      
        BigInteger n4 = n.multiply(four);
        BigInteger p_minus_q = p_plus_q_square.subtract(n4);
                   p_minus_q = bigIntSqRootFloor(p_minus_q);
      
      
        BigInteger p = p_plus_q.add(p_minus_q);
                   p = p.divide(two);
      
        BigInteger q = p_plus_q.subtract(p_minus_q);
                   q = q.divide(two);
                 
      
        String firstname = "Nikhil";       //write your firstname here    
        String lastname = "Dhama";      //write your lastname here
      
        String result = String.format("=PQ=\n%s, %s\n%s\n%s",lastname,firstname,p.toString(),q.toString());
      
        System.out.println(result);
   
     }
   
    public static BigInteger bigIntSqRootFloor(BigInteger x)
        throws IllegalArgumentException {
            if (x.compareTo(BigInteger.ZERO) < 0) {
                throw new IllegalArgumentException("Negative argument.");
             }

            if (x .equals(BigInteger.ZERO) || x.equals(BigInteger.ONE)) {
            return x;
            }
         BigInteger two = BigInteger.valueOf(2L);
         BigInteger y;
         
         for (y = x.divide(two);
                    y.compareTo(x.divide(y)) > 0;
                    y = ((x.divide(y)).add(y)).divide(two));
         return y;
        }
}

Here is the screenshot for command line compilation and output

Explanation:

phi = (p-1)(q-1) = pq - (p+q) +1

as known n=pq

phi = n - (p+q) +1

we get (p+q) = (n+1) - phi

now, we know (p-q)^2 = (p+q)^2 -4pq

(p-q)^2 = (p+q)^2 - 4n

which gives , (p-q) = sqrt( (p+q)^2 - 4n )

now let x= (p+q) , y= (p-q)

x+y = p+q + p-q = 2p

p = (x+y)/2

similarly

x - y = (p+q) - (p-q) = 2q

q = (x-y)/2

hope this helps.