# How can I solve congruence modulo N?

I am trying to solve congruences of the form $$J_A \cdot a^e\equiv 1 \pmod n$$

where $n=pq$ for $p,q$ prime and $\gcd(e,\varphi(n))=\gcd(J_A,n)=1$

Solve for $a\in \mathbb{Z}$, in terms of $n,J_A$ and $e$.

Nota Bene: This is not a homework question. I am looking for a way to implement it.

-
What are $J_A$ and $e$? – orlp Jan 1 '14 at 17:46
Values of $J_A$ and $e$ are known. I am using example from GQ signature scheme from the book Page 451 cacr.uwaterloo.ca/hac/about/chap11.pdf – user5507 Jan 1 '14 at 17:54
So did you mean $J_Aa^e \equiv 1 \mod n$, with $n = pq$, $1 < J_A < n$, $0 < e < n, gcd(e, (p-1)(q-1)) = 1$, $gcd(J_A, n) = 1$ and $a \in \mathbb{Z}$? – orlp Jan 1 '14 at 17:58
Yes. It was my mistake – user5507 Jan 2 '14 at 1:19

$J_A \cdot a^e \: \equiv \: 1 \:\: \pmod{n} \;\;\;\;\; \iff \;\;\;\;\; a^e \: \equiv \;\; $$\operatorname{modinv}$$(J_A,\hspace{-0.02 in}n) \:\: \pmod{n}$

Since that is the RSA problem, the fastest known way to solve it is to factor $n$ which reveals $\lambda$$(n)$,
and then try $\;\;\; a \: = \: \operatorname{mod}\left(\hspace{-0.03 in}(\operatorname{modinv}(J_A,\hspace{-0.02 in}n))^{\operatorname{modinv}(e,\hspace{.02 in}\lambda(n))},n\hspace{-0.03 in}\right) \:\:\:\:$.

-

It seems that you are finding a way to solve the RSA assumption.

The RSA assumption says:

If for any probabilistic polynomial time adversary $\mathcal{A}$, that on input $N,e,R$, where $R\in_R \mathbb{Z}_N^*$, outputs $a$ such that $a^e \equiv R\pmod N$ is negligible in security parameter $n$.

Using your way, $R\equiv J_A^{-1} \pmod N$. To solve $a$ is equivalent to solving $a \equiv R^d \pmod N$. So, if the RSA assumption holds, finding the $a$ is no easier than factoring $N$.

Let $N,e,d$ be RSA parameters and $f$ be an integer relatively prime to $e$. There is an efficient procedure that given $N,e,f$ (but not $d$) and a value $(a^f)^d \pmod N$ computes $a^d \pmod N$
Proof: from $gcd(e,f)=1$ we have $ve+uf=1$. Let $s=(a^f)^d$, then $\bar{s}=a^vs^u$ is the value we want. Because $\bar{s}^e=a^{ve+uf}=a$, hence $a^d \equiv \bar{s} \pmod N$.
So, my answer is: if you don't want to factor $N$, you can find this value $(a^f)^d \pmod N$ such that $gcd(e,f)=1$.
The RSA assumption is just that it's infeasible to find the a, which is logically independent $\hspace{1.15 in}$ of "finding the a is no easier than factoring N". $\;$ – Ricky Demer Jan 2 '14 at 4:09
And in fact the statement should be the other way around, namely "finding $a$ is no harder than factoring $N$". Then as an interesting side note you may say that this is the fastest known method, but it is by no means proven optimal. – orlp Jan 5 '14 at 13:30