Tag Info

New answers tagged


If $p=2q+1$ is a safe prime (that is, $q$ is a prime as well), then $p-1=2q$ has exactly two prime factors: $2$ and $q=(p-1)/2$.


Even though this is off-topic, I'll mention that depending on which factoring algorithms you want to implement, the ablity to work with integers of arbitrary sizes may not be sufficient. For example, the sieving algorithms require the ability to do some linear algebra over finite fields, and the Quadratic/Number Field sieves require the ability to work in ...


There are many libraries that allow you to do that in almost any language. There is BigInt/BigInteger class for Java/Scala. (The Scala's class is sjust a wrapper around the Java class.) Haskell has type Integer. Do not confuse it with Int, which is for small numbers only.


Yours is a perfectly legitimate question. I know that C#, F#, Java and Scala have an in-built support to handle arbitrarily large numbers, i.e. as large as your computer’s memory.


While the way that Robert showed can work if $e$ is small (and if $e \cdot d \equiv 1 \pmod{\phi(n)}$ (which is not necessarily true), there is a slightly more complicated method which will work in any case. What we do is compute $\lambda = (e \cdot d - 1)/ 2^k$ odd (and $k$ is the integer that makes $\lambda$ odd. The special property that $\lambda$ has ...


Generally the public exponent is small. then if you know the public and private key, then you can compute $e.d=1+k.\phi(n)$. k is smaller than e and $\phi(n)$ is in the range of n. A direct method allow to make an exhaustive search on the small k which divide ed-1 in such a way that $\frac{e.d-1}{k}$ is an integer. Then $\phi(n)= p.q -(p+q)+1$ allow to find ...


Does the factorization of N somehow help me? It sure does. I think I could compute the logarithm modulo each prime and then combine it, but do not know how exactly. Seems similar like problems for Chinese remainder theorem but I cannot find the way how to do it. You're real close; you do recombine them using the Chinese Remainder Theorem; however ...

Top 50 recent answers are included