# 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.

366 questions
Filter by
Sorted by
Tagged with
31 views

### RSA random key generation [duplicate]

How RSA keys are tested for primality if they are random generated? I imagine this could be time consuming task.
1k views

### Why do Mersenne Twister use Mersenne prime but not regular prime numbers

I'm trying to figure out why Mersenne Twister use exactly Mersenne prime numbers but not regular primes. What makes Mersenne prime numbers more appropriate for this role than regular primes?
1 vote
45 views

### Why does sum of remainders of numbers divided by known factors, and repeating the process over and over, give factors of the two starting numbers? [closed]

While working with serial division/remainder method of finding factors, I have found that using knowns such as the known factors of a comparative number, or the difference between a number to be ...
1 vote
62 views

### Question about Modified Miller-Rabin Test?

A few months ago I decided to write my own custom prime number generator. One of the tests I use is a modified Miller-Rabin test that tests the number against base 2 and then only tests random odd ...
1 vote
80 views

### learning with errors

If I talk about efficiency of system of learning with error, is it it fine for q to be composite in Z_q, the ring of integers. As when q would not be prime, Z_q will not be field anymore, won't it ...
179 views

### Purpose of the b1, b2, b3.... terms in Rabin-Miller Primality Test

In Rabin-Miller primality test, let N be the number you're checking for primality. Here N = 78007. Let m be the number you get after dividing (N - 1) by 2 several times until you can no longer do so. ...
86 views

### Big prime factor of the prime number you feed to Diffie Hellman

They say the security of Diffie-Hellman depends on the factorization of (N-1), where N is the big prime number you feed it. More specifically, (N-1) itself has to have a big prime factor, such as (N-1)...
1 vote
176 views

### Rabin-Miller Primality Test - Elaboration needed

In short, my question is: What exactly do people mean when they say that "The more you apply the Rabin-Miller test to a number, the more certain you can be that the number you're testing is prime....
69 views

### OpenSSL prime generation

Recently, I have noticed that openssl always gives numbers which have '1' in upper two bits. It always begins with 0xC or higher values (0xD, 0xE, 0xF). It doesn't give primes that starting with 0xB, ...
319 views

### Discrete Logarithm Challenges and Records

I am wondering whether there are any current challenge problems for Discrete Logarithms. Specifically in $\mathbb{Z}_p^\ast$ as well as in elliptic curve groups. It turns out CERTICOM still has some ...
264 views

### Generating suitable prime numbers for Paillier key pair in GG18

I am working on MPCs (multi party computation) in crypto, and now I am developing a implementation of GG 18. In sign phase, algorithm needs MtA (Multiplicative to Additive) and uses a Paillier key ...
295 views

### EC group order primality test

(Sorry for a newbie question) In ECC the intent is to create a group of a prime order (or prime multiplied by a relatively small cofactor). I know there's an algorithm for ECC to count the number of ...
35 views

### How to find linear complexity of non binary prime fields using berlekamp_massey algorithm in Sagemath?

I am having a prime field of large size (assume it of the type GF(2**18)) and I need to find linear complexity of a sequence (of some specified length) defined on ...
1 vote
144 views

### Given the existence of provably-hard-to-solve problems, why do we routinely rely on conjectured-to-be-hard problems for encryption?

Let $(X, Y, Z)$ be a set of binary strings of length $n$. Let random $X$ be the private key for encoding (or decoding) message random $Y$ as $Z$. Let the encryption algorithm $m$ be a matching ...
1 vote
76 views

### RSA - plaintext equal ciphertext

Just started learning about RSA cryptography so forgive me if I made any mistakes or misunderstandings. ...
1 vote
316 views

388 views

### The number of odd integers we have to test until to find one that is a prime for any arbitrary RSA modulus size

Popular RSA modulus sizes are $1024$, $2048$, $3072$ and $4092$ bit. How many random odd integers do we have to test on average until we expect to find one that is a prime? I know roughly every $\ln p$...
237 views

### Finding large devious primes

Call a prime $p$ devious if $(p-1)/2$ is a Carmichael number. They are called devious since they superficially look like safe primes but are not. In particular, Diffie-Hellman using such a prime could ...
1 vote
579 views

### Specific case of RSA where cipher text equals plain text

How did they arrive at the conclusion that there are 4 messages where plain text equals cipher text from "It is easy to show that in RSA, when e = 3 there are 4 messages m for which the ...
1 vote
89 views

### The significance of the field of the factor in Lenstra’s ECM

I am going through Lenstra's Elliptic Curve Factorisation from Silverman's Mathematical Cryptography book. I have understood the algorithm itself, but unable to understand a specific point the book ...
163 views

### Setting up the discrete logarithm framework

The discrete logarithm problem over prime cyclic groups consist of finding $x$ satisfying $g^x\equiv h\bmod p$ where $g$ is generator of multiplicative group $\mathbb Z/p\mathbb Z$ at a large prime $p$...
126 views

### Constraints on q for q-ary lattices?

In lattice cryptography, people often work with q-ary lattices so that we can use the hardness of short integer solution (SIS) and learning with errors (LWE). I saw in some notes that sometimes we ...
### What would be the safety requirements for the primes in $n=p \cdot q$ regarding the factorization?
Let it be $p, q \in \mathbb{P}$ with $p,q \in [2^{b-1}, 2^b]$ for some $b \in \mathbb{N}$ and $p \cdot q = n \in \mathbb{N}$. What would be the distance between $p$ and $q$ (as a function of b) so ...