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

290 questions
Filter by
Sorted by
Tagged with
3k 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 ...
43 views

### Will a list of all prime numbers upto certain number of bits compromise crytopgraphic algorithms based on prime factorization? [duplicate]

I understand that many cryptographic algorithms depend on the difficulty of large prime factorization. Will a list of all prime numbers upto certain number of bits make it easy for an attacker to ...
91 views

### Source of very large prime numbers

The RSA cryptosystem makes use of $n=pq$ where $p, q$ are large prime numbers. With quantum computing, factorization might become easier, so it will probably be useful to use much much bigger $p$, $q$ ...
25 views

### RSA encryption. Does message have to be coprime to n? [duplicate]

If I understand correctly, for RSA to work we need the message(cleartext) M $\in Z_n$ and gcd(M,n)=1. That is M coprime to n. This is to fulfil the requirement for Eulers theorem. How does RSA make ...
60 views

### Repeated modular square roots to recover original base

I'm given a large prime $p$ and $c \equiv m^e \pmod p$, and $e = 2^{64}$. Typical RSA rules don't apply here, since $\phi(p) = p - 1$ is even, and $e$ is a power of two, so they share a common factor, ...
91 views

### why to use a safe-prime in Diffie-Hellman key exchange?

In order for Diffie-Hellman to be extra secure we must use a safe prime which is (p – 1) / 2 will also be a prime. so my question is what extra benefit of using ...
1k views

44 views

### FLT is partly applying to RSA equation, and also relation between ED mod phi and Phi + 1 mod N

After numerous attempts from myself and all of you guys, I finally came to understand RSA. I can now prove it and understand how I got there. But I still have some very few polishing questions. 1) We ...
97 views

### Relation between $N = P \times Q$, and $\Phi(N)$

When studying RSA, and proving simple concepts to myself, I went and understood groups and rings, but I failed to understand Lagrange's theorem. I did understand how from invertible finite groups I ...
4k views

### RSA with probable primes

I am a bit of a newbie to RSA encryption, so please be patient. I understand that for a 4096 bit RSA, the numbers p and q should be prime. And to have the best security, the p and q should both be ...
1k views

### Security of Pohlig-Hellman exponentation cipher?

I am looking into implementing Pohlig-Hellman exponentiation cipher and I would like to know how secure that algorithm is? I am guessing it's security relates greatly to the prime number used in it. ...
74 views

### Is it hard to find a big random easy to factor number?

Suppose that I give you the challenge of successfully factoring any very big random number. That is, you pick a big random number (say, 65536 bits) and try to factor it. If you manage to, you win. If ...
1k views

### RSA factorization for special primes $p$ and $q$

I want to factorize the modulus $n = pq$ knowing that $p$ and $q$ are not random, but constructed based on integer numbers $a$ and $b$ as following ($a$ and $b$ are not given): p = a^2 + b^2, \...
138 views

### Why is a prime number used in ECDSA?

So I need to write a piece for school about ECDSA and how it is secure. Now I thought I had a simple question, however, I can't seem to find an answer anywhere: Why does the p in the formula need to ...
24 views

### Three Pass Protocol Question!

Alice and Bob have agreed to use the Three Pass Protocol. p=1009 Alice chooses the encryption exponent e_A = 101 Bob chooses the encryption exponent e_B = 209 Now Alice and Bob send three ...
247 views

### Diffie-Hellman in Https: How are prime numbers picked?

I am trying to understand https, as I understand https uses the Diffie–Hellman method for keys exchange and then AES for encryption. But Diffie–Hellman needs two prime numbers, where do these come ...
5k views

### What place do prime numbers have in cryptography?

My understanding of hashing and encryption is rather limited. I certainly do not understand the mathematical formulas at play in these algorithms. With that said, what part do prime numbers play in ...
41 views

88 views

### Is it possible to construct a multiplicative group from $\mathbb{Z}_n$ if $n$ is not a prime number?

With $n$ being a prime number I know we can generate groups over multiplication. Is it possible the other way around ($n$ not being a prime)?
70 views

### If there is an algorithm A can calculate the modular square root of input n, How to use it to get prime factors?

Suppose you are given an algorithm $A$ which takes $y \in \{0, 1, \ldots , N − 1\}$ as input, and outputs $x \in \{0,1,\ldots,N − 1\}$ such that $x^2 \equiv y \pmod{N}$. Design an efficient, ...
70 views

### Why do we use prime numbers apart from hard factorization?

Why are prime numbers important in cryptographic constructs? I am not interested in RSA examples where factorization is the hard problem itself, that makes sense. However wherever I go I encounter ...
388 views

### Efficient function/algorithm/method to do modular exponentiation

I was working on this project where I needed an RSA key, and I wondered if there was and more efficient way of doing $g^a \bmod n$ other than calculating $g^a$ and then finding the remainder when you ...