# Tag Info

3

The problems of determining if a group given by reduction of an elliptic curve over a prime $p$ is cyclic, and if so, finding a point $P$ that generates (a "primitive point"), have been extensively investigated. An obvious "brute force" strategy would set a coordinate to successive values $0,1,\ldots,p-1$ and check if the number of points on the reduced ...

2

This method is guaranteed to find the largest factor of $n$ below the square root: Compute $q_0=\lfloor\sqrt n\rfloor$ and try $q_0, q_0-1, q_0-2, \ldots$ for $q$. By the given constraint, you will succeed within a few steps. (Of course you can speed up by trying only odd values for $q$). Actually, we could exploit a bit more: From $pq\equiv 7\pmod{10}$ we ...

1

The general solution is difficult, it would be the solution of the RSA problem. Your specific solution is simple because your $n$ is far to small. Every reasonable factorization program will show within seconds: $$n=pq, p = 12345678901234568003, q = 12345678901234567891$$ Now compute $$\varphi(n)=(p-1)(q-1) = 152415787532388368884621236813290655780$$ and ...

Only top voted, non community-wiki answers of a minimum length are eligible