# Modular arithmetic

Given $e,d,N$ such that $e \times d \equiv 1 \pmod{ \varphi(n)}$. Can we efficiently calculate $\varphi(N)$.

$\varphi(N)$ will have multiples values. We need to eliminate those values that are

1. higher than $N$
2. Odd and some other criteria

Is there any efficient algorithm to find $\varphi(N)$.

Bellow algorithm is able to factor $n$ with probability at least $\frac{1}{2}$:

RSA-FACTOR(n, a, b)

comment: we are assuming that $ab=1\pmod {\phi(n)}$

write $ab - 1 = 2^sr$

choose $w$ at random such that $1\leq w \leq n-1$

$x= gcd(w, n)$

if $l<x<n$ then return $(x)$

comment: $x$ is a factor of $n$

$v=w^r \pmod n$

if $v=1 \pmod n$ then

then return ("failure")

while $v \ne 1 \pmod n$ do

$v_0=v$

$v =v^2 \pmod n$

if $v_0=-1 \pmod n$ then return ("failure")

else $x=gcd (v_0+ 1 , n )$

return $(x)$

This is an algorithm 5.10 in the page $204$ of "CRYPTOGRAPHY THEORY AND PRACTICE" by DOUGLAS R. STINSON.

• Does that algorithm also work when $ab\equiv 1 \pmod {\lambda(n)}$, since $ab\equiv 1 \pmod {\varphi(n)}$ is not a necessary condition for RSA to work? – CodesInChaos May 2 '17 at 11:39
• Dear @CodesInChaos, In the proof of algorithm, $w^{2^sr}=1 \pmod n$ is important for us. So algorithm also work when $ab\equiv 1 \pmod {\lambda(n)}$. – Meysam Ghahramani May 2 '17 at 12:05

When you know $e,d,N$, you can calculate $ed-1$, which is a multiple of $\Phi(n)$. I guess that's what you meant by

$\Phi(n)$ will have multiple values.

The sentence itself is wrong, though. As a function it does not have "multiple values" for a fixed $n$. You know a multiple of the value.

There are various algorithms to do this:

This looks like a homework question, so I won't give an explicit algorithm.