# Questions tagged [prime-numbers]

A prime number is an integer greater than 1 with no divisors other than itself and 1. Primes and prime products play an important role in public key cryptography.

282 questions
Filter by
Sorted by
Tagged with
487 views

### Fermat's factorization method on weak RSA modulus

Given a public key for RSA, I have extracted the modulus which looks like this: ...
81 views

166 views

### Distinguishing generators of RSA primes and moduli

We are trying to distinguish two RSA prime generators: Prime generator 1 draw uniformly at random an integer $p$ with $2^{1023.5}<p<2^{1024}$, until it is prime output $p$. Prime generator 2 ...
448 views

### Are relatively prime numbers used in RSA

We know that the Totient function is multiplicative. Which means that when $p$ and $q$ are relatively prime, then $\varphi(p q)$ is equal to $\varphi(p) \varphi(q)$. My question is, are only prime ...
2k views

### How does Python's pycrypto library generate primes?

The pycrypto library in Python can generate random n-bit prime numbers. The syntax I use is as follows: from Crypto.Util import number number.getPrime(2048) The ...
118 views

### Magic Number to calculate number of rounds for M-R in FIPS 186-4

In Fips 186-4, there is an algorithm in Appendix F (at page 117 in my copy of the 2013 version) to calculate the number of rounds of the Miller-Rabin primality test to random bases. Does anybody ...
43 views

### Random Primes Conjecture [closed]

I know it is believed that primes appear to be randomly distributed among the integers. Is there a formal conjecture or theorem that expressly states that the occurrence of the prime numbers is ...
115 views

### How can I generate large primes for Pedersen commitment?

I want to make a commitment on Shamir's Secret Sharing, based on the work of Pedersen, "Non-Interactive and Information-Theoretic Secure Verifiable Secret Sharing". To implement the commitment ...
2k views

### How to efficiently generate a random safe prime of given length?

A prime $p$ is said to be safe prime if $(p-1)/2$ is also a prime. How to efficiently generate a safe prime? I have written the following code in sagemath which generates a random safe prime of 1536 ...
302 views

### DSA: How to calculate 224-bit $q$ for 2048-bit $p$

$p$ is a 2048 bit prime number $q$ is a 224 bit prime number I know that $q$ is a prime divisor of $p-1$, thus $p=1 \bmod q$ but I couldn't write efficient code to calculate this. I can calculate ...
63 views

### How to formally say that the integers modulo $p$ for a prime $p$ gives results that are “more random” than for a composite $n$?

I'm doing a presentation on cryptography for non-experts. My main algorithm of the presentation is the Diffie Hellman key exchange. It uses modulo arithmetic for a prime $p$. During my presentation, I'...
230 views

### Swift and (very) large integers [closed]

I am trying to write a simple Mac program to factor primes. Nothing new, but I have a problem. The largest integer I can use seems to be 2^64, which is not that big. Did you hit any similar problem? ...
694 views

### RSA finding p and q integer with condition

I'm given $N=p\,q$ and told that $44\,p\approx 17\,q$ (with the value given for $N$ some 49-digit integer 8124642558124642555899928124642555899924479992447). In ...
73 views

### What is the difference between these cyclic groups

$\mathbb{Z}^*_p$ vs $\mathbb{Z}^*_{p-1}$ vs $\mathbb{Z}^*_{p^2}$ vs $\mathbb{Z}^+_{p^2}$ I know $p$ is the value. The value create must be coprime to $p$. Does that mean that the value create must be ...
1k views

### How big are the primes used in modern cryptography?

I know that this depends on which techniques you're using, but roughly speaking, when modern cryptography makes use of so-called "large prime numbers", how large (in bits or digits) are these primes ...
583 views

### In RSA, is it possible to compute the private key if one knows one of the primes used to generate n?

Within RSA the private key can be derived if one knows both $p$ and $q$. Is it possible to derive the RSA private key or decrypt / learn something about encrypted messages if you only know one of the ...
2k views

### Can multiplication of two primes be seen as a strong cipher?

If we were define such a cipher: A reversible function that would accept a message $M$ and an initialization vector $\text{IV}_1$ $\operatorname{map}(\text{IV}_1, M)$ which can map an input $M$ to a ...
89 views

### Public-key generation - primes reuse

Given the following Trap-door Commitment scheme Secret key receiver: $x_B \in_u Z_q$ Public key receiver: $y_B = g^{x_B} \mod p$ Here, $p=q*k+1$ for two primes $p,q$ and $k \in Z$. And $g$ is the ...
346 views

### Efficient algorithm for finding Sophie Germain primes

What's the industry standard for an efficient finding large Sophie Germain primes? As a part of request handling in my application, I need to generate Paillier key. My current approach is to ...
1k views

83 views

### Understanding reversible addition in a prime field

I'm trying to understand the security implications of addition in a prime field. Suppose I have X + Y = Z, occurring under prime field P(W) where W is the size of the field. If I know X and Z, I ...
1k views

### primitive root of a very big prime number (Elgamal DS)

For encryption methods there is a need for (very large) prime numbers. So for Elgamal digital signature there is the problem of finding a primitive root of $(p)$ where $p$ must be very large prime ...
157 views

### Biased RSA moduli and ROCA

Say I can generate many 1024-bit RSA public keys $(N,e)$ with fixed public exponent $e = 65537$. They turn out to be heavily biased when computing $N \bmod x$ for small primes $x$. These congruences ...
151 views

### Malicious DH parameters without using composite numbers [duplicate]

I know that it's possible to generate DH parameters that lead to it being easy to attack (e.g. trivial composite numbers), but is it possible to create a malicious parameter that is not a composite ...
93 views

### Checking if discrete logarithm is $\geq\frac{\varphi(p)}2$ in polynomial time?

Given $p$ a prime, $g$ generator of $\Bbb Z_p^*$, and $h\in\Bbb Z_p^*$, that uniquely defines some $z\in[0,\varphi(p)[$ such that $g^z\equiv h\pmod p$. Is it possible to determine in polynomial time ...
148 views

### Integer Factorisation

If I have a set of numbers of the form $\{ {kp+r}:k\geq0\}$ with p a prime or product of primes k large in $\in Z^+$ and r fixed, is it computationally feasible to find a factorisation for any one ...
101 views

### generating prime p and q, with alpha of element of order q

I'm working on VSSS (Feldman) but I cannot understand the statement as follows: I'm not good in reading mathematical statements (but working on it). Can anyone explain this in simple mathematics. ...
184 views

### Linear Feedback shift register over integers

The Solina's paper Generalized Mersenne Numbers contains a Linear Feedback shift register I am not able to understand. Here it is: It is supposed to be a normal Linear Feedback shift register but it ...
78 views

136 views

### are all elements of ZpxZp in ECC definite over Zp

are all elements of ZpxZp in ECC (elliptic curve) definite over Zp ? otherwise: assume G a base point of ECC and n the order of G. why n is equal or nother to p*p ? (p a prime number). (Think to a ...