Euler's Totient Function and Cryptography Question

Question

I'm working on a problem set for a class on intro computing and cryptography. I'm being asked to find the $n = pq$, where $p,q$ are integers (not necessarily prime), such that $\phi(n)=$

$2961663103295106586664292574860370$ $9646682909251496874286611652662276888867730054361987$ $0132065232070766756540945872699698884632550737457957$ $60212647480948122249224121531406021196015733929413333$ $931614086054218206830599157256559770960$

for an absurdly large $n$ =

$296166310329510658666429257486037096466829092514968$ $74286611652662276888867730054361987013206523207076675654095484773927425$ $6896134970395727031935392790447797391203973441361$ $72609641046823030764012972259401809379112646137930136087303$

The problem asks me to to write a computer program in Sage that will enable one to solve for $p,q$.

My strategy so far is to create a program that first divides both $\phi(n)$ and $n$ by each prime number successively only if the prime evenly divides itself in order to break it down into prime factors. The idea I had here was that it would allow me to get closer to finding $p$ and $q$. I was thinking of then using the multiplicative property of the $\phi(n)$ function to check that $\phi(n) = \phi(p)*\phi(q)$. Besides this, I'm not sure how else to approach this problem. Any advice would be appreciated.

Answer 1

Using an RSA recovery algorithm I get

p= 32998886283809577512914881459957314326750856532546837122557861905096711274255431870995137546575954361422085081
q= 897503957504227472139484199430066010338139343163145419280183314291067450988520718807102741476596034735471026312154231263

with probable primes $p,q$ and indeed $n=pq$ and $\phi(n)=(p-1)(q-1)$. I use Algorithm 18.16 (Special integer factorization) from the solution to exercise 18.12 (ii) of J. v. zur Gathen, J. Gerhard, Modern computer algebra, 2nd ed., 2003, available online as http://www-math.uni-paderborn.de/mca/solutions.ps.gz

Answer 2

Assume:

$$ n = p_1^{a_1} p_2^{a_2} ... p_k^{a_k}$$

for primes $p_1 ... p_k$

Then

$$ \phi(n) = n\left(1 - \frac{1}{p_1} \right)\left(1 - \frac{1}{p_2} \right)...\left(1 - \frac{1}{p_k} \right)$$

Meaning

$$ \phi(n) = p_1^{a_1-1} p_2^{a_2-1} ... p_k^{a_k-1}(p_1-1)(p_2-1)...(p_k-1) $$

So now for each prime P check if

$$p | \phi(n)$$

and

$$p-1 | \phi(n)$$

If either works then you will have found a factor of n.

Since your work now is dividing $\phi(n)$ that should be a tad bit faster than dividing n directly.

Another much faster option is to block the integers (or primes to save even more time) 1... $sqrt{n}$ into chunks of k at a time.

For example

(1 ... k) , (k+1, k+2 ... 2k) , (2k+1 ... 3k)

and then consider their products

(1*2*3...k) etc...

Now the key here is:

$$ a^{\phi(n)} \equiv \ 1 \ mod \ n $$

For coprime a and n. So for each product a you want to compute the above expression. Example:

$$ (1*2*3...k)^{\phi(n)} \ mod \ n$$

The key here is the exponentiation should be implemented by the method of "Squarings" which will make it extremely fast.

If any of those expressions yield you something that isn't 1. Then somewhere in that block exists a number that shares factors with n. Binary search over the blocks of factors can help you find it

Example. Lets say that (1 * 2 ... k) is such that

$$ (1*2...k)^{\phi(n)} \ \ne 1 \ mod \ n $$

Then check (1*2...k/2) , (k/2+1,... k) for which one isn't congruent. Rinse and repeat this method of splitting up the product to hone in on which number shares a common factor with $n$.

Now repeat the procedure for that number and eventually you will find a factor.

---

For the case of semiprime

$$\phi(n) = (p-1)(q-1)$$

$$n = pq$$

$$1 - \phi(n) + n = p + q$$

Thus:

$$ \frac{n}{q} = p $$

$$1 - \phi(n) + n = \frac{n}{q} + q$$

$$q^2 + (1 \phi(n) -n-1)q + n = 0$$

Use quadratic formula to recover Q as @gammatester's algorithm would have done