Tag Info

New answers tagged


The (in my opinion) simplest way to proceed about this is: First compute the square root $m:=\sqrt n$ of $n$ in $\mathbb N$; this can, for instance, be done in time $\mathcal O(\log^3n)$ using a binary search. The next step is to compute $\varphi(m)$ from $\varphi(n)$: by the properties of $\varphi$ we have $$\varphi(n) = (p-1)p(q-1)q=\varphi(m)\cdot m ...


The main reason why the prime factors $p$ and $q$ of RSA modulus $N$ must be distinct is stated in the question: if they are equal, given $N$ (which by definition is public in RSA), it is trivial to find $p=q=\sqrt N$. A secondary reason is that with $p=q$, a few messages $x\in\{0\dots N-1\}$ can't be reliably deciphered from $x^e\bmod N$: all those $x$ ...


You can use the next_prime function available in the GMP library, after generating a random large number. Here's the link : https://gmplib.org/manual/Number-Theoretic-Functions.html


For a given prime $p$, there are many choices for the generator $g$, but $g$ cannot be completely arbitrary. As the name hints, $g$ is supposed to be a generator of the multiplicative group $(\mathbb{Z}/p\mathbb{Z})^*$ (or at least a large subgroup, more on this later), that is, it must have the property that the set of its powers modulo $p$ $\{g^1 \bmod p, ...

Top 50 recent answers are included