Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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$.

I am using example from GQ signature scheme from the book Page 451.

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

share|improve this question
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 – 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) \:\:\:\:$.

share|improve this answer

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$.

But there is a lemma about this:

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$

I'll give a short proof about this lemma:

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$.

share|improve this answer
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

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.