A message from our CEO about the future of Stack Overflow and Stack Exchange. Read now.

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

264 questions
Filter by
Sorted by
Tagged with
31 views

### How large a product out of 3 close-by factors need to be to avoid factorization?

For encryption a prime $P = 2 \cdot Q \cdot R \cdot S +1$ was used. An adversary want to solve the discrete log problem $m \equiv g^i \bmod P$. For this he want to use the Pholig-Hellmann algorithm. ...
55 views

### Distance between consecutive primes distribution

In several prime generation schemes I saw we pick a random number uniformly at random from a wide range and find the next prime after it. Obviously with such a scheme some primes are more likely than ...
166 views

### RSA: If the least significant bits of the factors are leaked, what advantage is there in factoring N?

For $N=pq$, if the first $x$ least significant bits of both $p$ and $q$ are leaked. what is the advantage in factoring $N$? Does this give an advantage beyond simply lowering the number of bits we ...
39 views

### Generalized Benaloh cryptosystem with $r=2$

Benaloh cryptosystem requires $\gcd(r, (q-1))=1$ which is impossible if $q>2$ (since it needs to be a large prime) and $r=2$. This confuses me, since Benaloh is referred to as an "extension" or "...
53 views

### Modification of RSA using two inverses, one for P mod (Q-1) and one for Q mode (P-1), instead of inverse d mod [(p-1)(q-1)], more or less secure?

Lets say I have the following modified RSA scheme We choose two large primes P, Q, with additional restriction that these are relatively prime to (p-1) and (q-1) We choose N = PQ as public key We ...
46 views

### Trial division + Miller-Rabin complexity

I was reading a paper that shows time complexity of Trial division + Miller-rabin test for creating prime number. T = N(T_rnd + T_td + T_mr) T_rnd denotes time for making rnd number, T_td denotes ...
57 views

### What does it mean for a number to be “in the order of” a prime number?

In some papers I'm looking at there is some language that says things like "Choose a random number in the order of prime q" and I see some syntax that it is referring to that looks s = Zq (where q is ...
87 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)?
58 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 ...
56 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, ...
85 views

### Would calculating the nth prime ruin encryption?

I'm sure there is some proof that the nth prime can be found. But if we knew, would encryption that relies on primes be easy to decrypt?
140 views

### Factoring 2048 bit number is easy?

my PC found a factor for (2^2048)-1 in under a second...so does that make RSA-2048 less secure right? i used prime 95. and actually i am kinda curious how it found a factor so fast? i can even factor ...
137 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 ...
46 views

### Paillier Complex Residuosity problem?

Paillier Cryptosystem depends on both the factorization where $n = p.q$ and the complex residuosity problem which is defined in the original paper as: The problem of deciding n-th residuosity, i.e. ...
45 views

### Question about using residue number system for repeated multiplications

I understand that when you are using RNS you need a co-prime moduli-set e.g. ${\{m_1, m_2, m_3\}}$, and the dynamic range is the product of each modulus in that set $M = m_1.m_2.m_3$. Also it's ...
40 views

### RSA Modulus doesn't match the primes [closed]

I generated a 2048-bit RSA key with ssh-keygen. When running: openssl rsa -in key -noout -text The result is: ...
71 views

### What is a method for hiding RSA prime values from .exe De-Compiling?

I've just been looking into RSA encryption with C++ and am wanting to make a program that can en/decrypt files of my own custom file extension. Obviously I need to choose two primes numbers (for my p ...
45 views

### Deterministic procedure for mapping an arbitrary value into a 𝑝,𝑞 pair for public key cryptography

I want public key cryptosystem to used for re-encryption as describe in Can Paillier ,RSA or any other schemes be used for universal re-encryption like elGamal? Now i have little solution for ...
392 views

### Algorithm to find primes $q$ and $p$ with $q\, |\, p - 1$?

I understand that if $p$ is prime then $p-1$ must be composite (at least divisible by $2$ as it is even). But how does an algorithm find a prime $q$ such that $q \cdot r = p - 1$. I thought prime ...
177 views

### Why does square root $\pmod n$ find $p$ and $q$ (as $n = p \cdot q$)?

Let $n = p*q$, with $p \neq q$ and $x^2=1 \pmod n$, $x+1 \neq 0 \pmod n, x-1 \neq 0 \pmod n$ (So x is a non-trivial square root mod n.) I don't see how $\gcd(x+1,n) \in \{p,q\}$ follows. I ...
124 views

### Why can every prime number be written as 6k±1? [closed]

I want to know how to be sure that each prime number can be written in the form $6k±1$. How I can find the prime number that exists after a composite number with this property of prime or other ...
17 views

### In practice, do large prime generators account for difference in gaps between primes? [duplicate]

It is my understanding that a method for creating large primes is to: pick a random large number, check the number against trial division of a set of smaller prime numbers, check with something like ...
406 views

### Distribution of safe primes generated using different techniques

Is there any difference in the distribution of safe primes generated by creating prime $q$ and testing $2q+1$ for primality, compared to generating a larger prime $p$ and testing $(p-1)/2$ instead? ...
174 views

### How should I address message size limits in RSA encryption?

I am making an end-to-end encryption software program in Java using RSA. I am using BigIntegers and its number theory methods. (I know this is a very slow approach, but I just want to learn to the ...
91 views

### RSA encryption, Number theory [duplicate]

In RSA algorithm we have the value of $e$ & $d$ exponent and also one of the prime numbers. My question is how to produce another prime number that is not equal to the first one and the digit of a ...
55 views

### Finding a prime field with n-th roots of unity

How can I find the smallest prime $p$, such that field $GF(p)$ has $n$-th roots of unity? For example, I know that for $p=2^{256} - 351 \times 2^{32} + 1$ there exit roots of unity for $n=2^{32}$. ...
### Value of $\varphi(n)$ and $\lambda(n)$
Is it true that $\varphi(n)$ is generally larger than $\lambda(n)$ for the same $n$? If so, can anyone give me a proof?