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

291 questions
Filter by
Sorted by
Tagged with
219 views

### Safety of using GPG's libgcrypt prime generation for generating ephemeral Diffie-Hellman primes?

My company wants to generate new primes for every Diffie-Hellman key exchange. We are thinking of using the prime generation scheme in GPG’s libgcrypt library. The code documentation says that the ...
445 views

### Diffie Hellman unsafe prime vulnerability

I have done some research about how the DH key exchange is unsafe if an unsafe prime p is used (that is, $p-1$ has a lot of small factors). Many answers here on StackExchange claim that for any factor ...
456 views

### Is RSA vulnerable to possible PRNG + Miller Rabin test weaknesses?

Factoring a 2048 bit number is a difficult topic with a well known complexity. But it seems that p, q, the prime numbers used in RSA (order of magnitude: 10^308) are generated thanks to the ...
616 views

### See the RSA's $n = p q, e \text{ and } d$ from ssh-keygen

For learning purposes, how to get the RSA's parameters (I use standard notation): $n = p q$, where $p$ and $q$ are prime and $e$, $d$, such that $ed = 1 \ (mod\ \varphi (n))$ when doing ...
86 views

### Probability of a prime factor [closed]

We are given an arbitrary number $n$ and a sequence of primes $p_1=2$, $p_2=3$, ..., $p_k$. I am interested in the following question: Are the events "Prime $p_i$ is a factor of $n$" independent for ...
157 views

### For large prime P, how often is (P-1) evenly divisible by 65537?

When calculating prime numbers $p$ and $q$ for an RSA private key, one of the requirements is that $\gcd(p-1,e)=1$ and $\gcd(q-1,e)=1$, where $e$ is the RSA exponent (typically 65537). I'm curious ...
139 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 ...
1k views

### How to encrypt the number one using RSA?

for example: if we have public key : (5,221) and private key : (77,221) and we want to encrypt 1: c(m) = (m)^p mod n c(m)=(1)^77 mod 21 =1 so how to deal with ...
2k views

### What algorithm does .NET use to generate primes for RSA and how can I verify it?

There is an implementation of RSA in C# .net, but how can people know that this implementation is considering all the secury stuff conserning to RSA? For example I want to know what is the algorithm ...
912 views

### What are some of the best prime factorization algorithms and their effecitvity

I was wondering aren't the most used prime factorization algorithms a symbolic mile behind the security of the RSA cryptosystem? The way it looks to me is that every time an algorithm is able to ...
2k views

### How to Check Strength of RSA Public Private Key

How to measure strength of RSA public private key pair. is it enough to only measure the length of primes used to generate N? how to check that primes p,q used to make N were selected truly randomly ...
191 views

### Is it easy to factorize a number of the form $n = t^{2} \cdotp p$?

Is it easy to factorize a number of the form $n = t^{2} \cdotp p$, where $t$ and $p$ are large primes?
112 views

886 views

### Find inverse in RSA

I've been reading on RSA for a while but there's something I still can't understand. When generating the key: once you find n = pq and φ(n), you choose a number d coprime with φ(n) and then you need ...
1k views

### Mathematics behind end-to-end encryption

I am interested in end to end encryption, recently I read some articles on its principles but I can't find anything on the maths behind the encrypting and decrypting functions that relates private and ...
256 views

### Can someone explain the definition of four square roots as it pertains to groups in Z*p?

So I'm given the following as a problem: When $p$ and $q$ are distinct odd primes and $N = pq$, the points in $Z^∗_N$ have either zero or four square roots. A quarter of the points have four square ...
333 views

### where does the prime number taken in DH algorithm in IPSEC

I am studying & configuring IPSEC ikev1 and in between i am analysing the wireshark captures. I am using the linux kernel for TCP/IP stack and user-space i took ipsec-tools. In the first two ...
542 views

### Is the prime P is fixed for an elliptic curve defined over a particular prime field F_p?

I have seen the NIST, SEC and Brainpool standards. They have used same prime for a particular bit curve (128,192,256,521). Is the prime value fixed for a particular security (field size)?
2k views

### Why are elliptic curves constructed using prime fields and not composite fields?

I come across this: Numbers mod composite number does not form a field rather it forms a ring and every number has a multiplicative inverse under integer mod prime Maybe these are the reasons ...
384 views

### Role of primitive roots in Pollard's P-1 factorization algorithm

I have recently been reading about different factorization algorithms and I came across this paper that discusses the Pollard's P-1 algorithm. In the footnote of the first page, it states... For ...
100 views

### Proving additive inverse as generator of Z*p [closed]

Let there be $p\ ,q$ odd primes, such that $p=2q+1$. Let the be $a \in Z^*_p$ so that $a \not= \pm 1(mod\ p)$. Prove that if $a$ is not a generator of $Z^*_p$ then $-a$ is a generator of $Z^*_p$.