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

389 questions
Filter by
Sorted by
Tagged with
23 views

### Probability of encoded message using Weierstrass equation on NIST elliptic curve over prime finite field to return a quadratic residue?

Suppose we talk about NIST P-256 elliptic curve, and since finite field of an elliptic curve is a known prime number $P$, then approximately half of the Weierstrass equation results will be quadratic ...
• 123
117 views

### Probability of Enhanced MR test outcome for NOT A POWER OF PRIME

I come up with an approach to find the probability of the outcome "PROVABLY COMPOSITE AND NOT A POWER OF A PRIME" of enhanced MR test. In context of this question, the probability/error ...
• 453
1 vote
158 views

### fastest prime number check formulae available

which is the fastest prime number check formulae available and that can be used using a scientific calculator easily. you can also refer to a patent if available. looking to use it in a software.
• 111
286 views

1 vote
83 views

### How zetas are computed in CRYSTALS-Kyber?

As shown below it explains how generate zetas table and use it. But curious thing is that how KYBER_ROOT_OF_UNITY constant is generated ? I've tried multiple ways to generated it and cannot explain ...
51 views

55 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?
• 459
1 vote
73 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
96 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
190 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 ...
192 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. ...
142 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
907 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....
187 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, ...
• 11
590 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 ...
• 23.1k
299 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 ...
313 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 ...
• 359
43 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
164 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 ...
• 139
1 vote
133 views

### RSA - plaintext equal ciphertext

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