Tag Info

New answers tagged

0

Generalized Mersenne Prime Numbers are used in Elliptical Curve Cryptography and Random Number Generation.


5

I can think of two places where we use a Mersenne Prime within cryptogaphy: As a modulus within a prime elliptic curve. $2^{521}-1$ is a prime, and so we can define an elliptic curve using $GF(2^{521}-1)$, which is in moderately common use. One reason we use such a modulus (rather than another prime of approximately the same size) is that the special ...


2

I don't believe there's any particular use for them, to be honest. RSA uses large pseudoprimes, but the prime factors don't have to be Mersenne primes. In fact, given how few Mersenne primes there are, using them would be extremely detrimental to security as they can be easily enumerated.


0

First, note that if you know $p-q=a$ and $p+q=b$, for some $a,b$, you have two equations with two unknowns and can solve for $p,q$. Now, $$ n=p*q=\left(\frac{p+q}{2}\right)^2 - \left(\frac{p-q}{2}\right)^2$$ Rearrange $$ \left(\frac{p+q}{2}\right)^2 = n + \left(\frac{p-q}{2}\right)^2$$ Then start guessing values for $p-q$. Start with $2$ and substitute ...


3

For part(a.ii), I am presuming that "enumerating candidate prime factors" means that we have a precomputed list of all 1536-bit primes, which we can simply test one at a time. To determine average running time we can use the prime number theorem, which states that the number of primes less that $N$ is approximately given by $\pi(x) \sim \frac{N}{\ln N}$. ...


0

A. J. Menezes et al., Handbook of Applied Cryptography (available online) 4.62 gives Maurer's algorithm for generating provable primes, which is fairly competitive in runtime with probabilistic methods (commonly employing Rabin-Miller test) for sizes of primes of practical interest. I have recently implemented Maurer's algorithm in Python ...


1

Yes, this is doable. Here is a construction, built out of several basic primitives: Let $R$ be a randomized primality generation algorithm; there are many of them. It uses randomness, so let's make the bits of randomness it uses explicit as input: $R(c)$ is the output it produces, when given a random number generator that outputs the random bits $c$. ...


1

When you go from Affine to Jacobian, $X$ and $Y$ stay the same, and $Z$ is equal to $1$ Affine -> Jacobian: $(X',Y',Z') = (X,Y,1)$ Jacobian -> Affine: $(X',Y') = (\frac{X}{Z^2}, \frac{Y}{Z^3} )$



Top 50 recent answers are included