# Tagged Questions

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.

78 views

### Highest prime factor that is Safe for a particular scheme

My question is how many bits of prime number is secure so that it cannot be factored from very large number? Until today how large prime factor is found in large number? Quantum computing find ...
348 views

### RFC 3526 - What does pi mean?

In RFC 3526 there are a series of primes listed as standard parameters used for Diffie-Helman. The primes are list in two formats. One is the long format, where the number is given in hex. For example:...
104 views

421 views

### Sophie Germain primes and safe primes

I am trying to find a list or table of safe prime numbers i.e. the ones that are based on the Sophie Germain primes i.e. $N = 2p + 1$ where $p$ is also prime. All I found till now is this database. ...
460 views

### Random numbers for Rabin-Miller primality tests

I've implemented a Rabin-Miller primality test fuction following Wikipedia and the book Applied Cryptography. Now I'm using it for generating primes with a string seed. The book suggests the following ...
627 views

### Why should the primes used in RSA be distinct?

The two primes $p$ and $q$ part of the public key need to be distinct. What's the reason for them to be distinct? Is it because factorization of $p^2$ where $p$ is a prime is relatively easier, or is ...
2k views

501 views

### Prime number theorem - RSA

I am having trouble understanding the prime number theorem. As part of some revision for an exam, I am trying to answer the following questions (but seeing as I don't understand the concept of the ...
490 views

### Primality testing (deterministic vs. non-deterministic)

I noticed that non-deterministic primality testing algorithms are more commonly used in practice while there is a deterministic algorithm e.g., AKS which runs in polynomial time? I am right? if so, ...
356 views

### Choosing good parameter for Lenstra's elliptic curve factorization

In Wikipedia, there is an article explaining Lenstra's factorization algorithm. As far as I got it, we choose some $e \in \mathbb{N}$ and a point $P$ on the curve and then calculate $eP$. While ...
74 views

### Obtaining Diffie-Hellman generator

In the Wikipedia article on Diffie-Hellman, the algorithm calls for a large prime modulus, $p$, and a generator, $g$, which is a primitive root of $p$. As far as my knowledge of number theory goes, ...
91 views

### Find plaintext of RSA by solving extended euclidean algorith for two encrptions with two different exponents for same plaintext

This is my homework question (but I am not asking the answer to it): Suppose two users Alice and Bob have the same RSA modulus n and suppose that their encryption exponents eA and eB are ...
47 views

### Requirements for the modulus in the Massey-Omura three pass protocol

In the Massey-Omura three pass protocol: How many bits long should the prime modulus $M$ be in order to be secure? Should the $M$ be secret? Should the $M$ be generated every time or it could be ...
520 views

### Generation of N bit prime numbers -> what is the actual range?

Short version: When generating a prime number of N bits, should I draw random numbers from the range $[0 , 2^n]$, or $[2^{(n-1)} , 2^n]$? Context: I'm trying to implement a toy-version of RSA as a ...
352 views

291 views

### Factors of RSA modulus

In the article A Method for Obtaining Digital Signatures and Public-Key Cryptosystems, the original RSA article, it is mentioned that Miller has shown that n (the modulus) can be factored using any ...
440 views

### why AKS is so slow in practice? [closed]

This note (http://maths-people.anu.edu.au/~brent/pd/primality4.pdf) states that AKS is not practical. However, it is known that AKS runs in polynomial-time, and I cannot understand where the slowness ...
130 views

### Three different numbers with x³=x mod p

p is a prime greater than 2 and $a \in \mathbb{Z}_p$. Why are there exactly three solutions for a³ = a mod p? Obviously 0 and 1 are both in $\mathbb{Z}$ and valid solutions, but that still means, ...
151 views

### Of what use is my code for finding prime numbers of a certain size?

I've developed a bit of Mathematica code that can find primes within a range of numbers. For example, if I wanted all the primes between one million and two million, it could do that. Of what use is ...
449 views

### Significance of 3mod4 in squares and square roots mod n?

Why do most literature while discussing squares or square root modulo a prime P, consider P to be congruent to 3 mod 4?
204 views

### Why doesn't this defeat RSA?

Apologies for the obviously ridiculous question but I need to know where I'm going wrong here. For RSA, we compute $n=pq$ for primes $p$ and $q$. We then choose an $e$ such that $gcd(e, \varphi(n))=1$...
904 views

### Quadratic residue problem on composite integers

Its believed that the quadratic residue modulo $n=p·q$ for large primes $p$ and $q$ is intractable, which forms the basis of some cryptosystems. However, it is solvable if the factors of $n$ are know,...
1k views

### What is the correct value for “certainty” in RSA key pair generation?

I'm creating an RSA key pair in Bouncy Castle and need to specify an int value for certainty. This Stack Overflow answer says it is a relative test for how prime the values are. There is another ...