# Tag Info

If now the prime value $P$ gets increased for constant $k$ (order of $g$ still $k$) does this decrease the security? No, for random choice of $g$ among $g$ with large constant order $k$. Why this? If $P \rightarrow \infty$ it would be the normal logarithm .. When $P$ grows, $g$ also grows. So we never reach the threshold where $g^a<P$. Thus we can ...
(I observe $S=c\cdot P$ for some integer $c$.) Is that always the case? Yes. Proof follows. If $g=P$ then $S=0$. We'll disregard this special case in the following. The set $M$ has $k$ elements, with $k$ the lowest strictly positive integer with $g^k\equiv1\pmod P$. This $k$ is known as the order of $g$ modulo $P$. This $k$ divides $P-1$. $M$ also is $\{g^... 1 You've done the hard work by finding that you can obtain$m_i=a_i\,n$for various (unknown but essentially random) values of$a_i$. Now define$n_0=m_0$, and compute$n_i=\gcd(n_{i-1},m_i)$for increasing$i>0$. Sooner rather than later, the$n_i$will converge to$n$. This can be proved rigorously (though we often skip rigorous proofs in a crypto ... 1 This smells like a HW question, so the OP should try it with more hints. By querying this function at$x$, it is easy to tell whether$x\geq n$or$x<n$. Let$k$be a natural number such that$2^k<n\leq 2^{k+1}$, how many queries do you need to find this$k$? Knowing this$k$, how can you figure out$n$? If the modulo operation is part of polynomial ... 3 If you find such you can break RSA. Assuming the order of c is maximal(likely if c is random ciphertext). If we have such distinct exponents 𝑎 and 𝑏 they must be equal mod$\lambda(n) = lcm(p-1,q-1)$. Let the difference between the exponents be$f=b-a$,$f=0\space mod \lambda(n)$We pick a value e coprime with e, pick a small prime and verify. We will ... 2 No! RSA is public-key encryption and in public-key encryption, the known plaintexts are free. Given a public key$(n,e)$we can find many$(p_i,c_i)$such that$c_i = p_i^e \bmod n\$. If this is a weakness, on the first day it will be broken.