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.

Filter by
Sorted by
Tagged with
0
votes
1answer
82 views

If $((p-1)*(q-1) -1)$ divisible by $e$ ($e$ is odd number) , then $\text{gcd}(e,(p-1)*(q-1)) = 1$

If $((p-1)(q-1) -1)$ divisible by $e$ ($e$ is odd number) , then $\text{gcd}(e,(p-1)(q-1)) = 1$. ($p,q$ are prime numbers ) Is this true, if yes why, if not why not ?
0
votes
1answer
42 views

ZKP for product of two primes

I'm struggling to understand the intuition of the zero knowledge-ness of this proof from the following paper. The proof is a 2 round where the verifier asks the prover to extract square roots of ...
3
votes
1answer
54 views

Computational trapdoor where the problem is tractable for both parties but easier for one

Usually the sort of trapdoors which are talked about are designed such as to make the computation intractable for one party and tractable for the other. But what if one party merely has a big ...
1
vote
1answer
60 views

With composite $n_1$ = $p_1q_1$, and a separate $n_2 = p_1q_2$, can the primes be calculated more efficiently than factorization?

Supposing that the (3 total) primes are kept secret? Does the reuse of $p_1$ allow an attacker to compromise $n_1$ and $n_2$ if the attacker guesses that both were generated with a shared prime ...
1
vote
1answer
115 views

How to produce large list of BigInteger prime numbers (RSA) in fast and efficient way

Hello fellow experts here, in order to use RSA to encrypt and decrypt in a controlled environment, we will actually need to have a list of prime numbers to do so instead of using library generated RSA ...
5
votes
2answers
148 views

Prime numbers of the form $(2^k)p+1$, for a given prime $p$

Let $p$ be a prime. (say 256 bit) Does there a exist a prime $q$ such that $q = (2^k)p + 1$, for a large $k$ (something like 256), if it does exist, is there a way to find out for which all $k$ such ...
2
votes
1answer
84 views

Problem with RSA deciphering

I don't quite get the algorithm yet. Sometimes it works and other times it doesn't,so clearly I am overseeing or misunderstanding something. I will just write what I did. My $N=143$ and has factors ...
3
votes
0answers
73 views

RSA calculate $d$ using Chinese Remainder Theorem with $d_p$, $d_q$ and $e$

Suppose for a RSA system I have the following variables given: modulus $n$, expononent $e$, $d_p$ and $d_q$Where, $d_p = d\bmod(p-1)$ and $d_q = d\bmod(q-1)$, Is it possible to find the private ...
0
votes
0answers
43 views

Trivariate Coppersmith Implementation

Bivariate Coppersmith is standard package in math software with number theory support. Bauer and Antoine Joux introduced trivariate Coppersmith in https://www.iacr.org/archive/eurocrypt2007/45150361/...
0
votes
1answer
95 views

Prime Factorization in RSA always leads to the product of two primes?

Lets prime factorize $30$: $$30 = 3 \cdot 10 = 3 \cdot 2 \cdot 5$$ We see that the number $30$ is a product of $3$ primes. But in RSA, when factorizing huge numbers, we always seem to only get two ...
0
votes
2answers
87 views

Why is Multiplicative group used in RSA or Euler's theorem but not additive?

I am on the verge to understanding RSA, but suddenly a question popped into mind. When we are calculating $U(N)$ i.e $U(PQ)$, we are taking invertible elements that are co-prime to $N$. For example, $...
0
votes
0answers
39 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 ...
2
votes
1answer
86 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 ...
0
votes
1answer
73 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 ...
1
vote
1answer
111 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 ...
0
votes
0answers
23 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 ...
3
votes
1answer
199 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 ...
0
votes
0answers
39 views

About the irreducible test for a polynomial over $GF(2^m)$ (its coefficients belong to $GF(2^m)$)

For the Miller-Rabin probabilistic primality test, we can apply it to test a big number whether a probably prime number or not. Does there exist a method to test a higher-degree polynomial over $GF(2^...
1
vote
0answers
36 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. ...
7
votes
1answer
132 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 ...
3
votes
1answer
189 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 ...
4
votes
0answers
48 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 "...
2
votes
1answer
59 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 ...
0
votes
1answer
65 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 ...
0
votes
1answer
62 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 ...
3
votes
1answer
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)?
1
vote
1answer
68 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 ...
0
votes
1answer
64 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, ...
0
votes
2answers
86 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?
-1
votes
1answer
213 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 ...
0
votes
2answers
276 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 ...
1
vote
1answer
59 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. ...
1
vote
0answers
46 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 ...
1
vote
0answers
55 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: ...
0
votes
1answer
74 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 ...
-1
votes
1answer
48 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 ...
7
votes
1answer
410 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 ...
3
votes
2answers
191 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 ...
-2
votes
1answer
140 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 ...
0
votes
0answers
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 ...
2
votes
1answer
417 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? ...
1
vote
1answer
410 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 ...
-1
votes
1answer
94 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 ...
-1
votes
1answer
66 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}$. ...
1
vote
1answer
84 views

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?
3
votes
0answers
64 views

Problem with Chaum`s Untraceable Electronic Cash

For example according to protocol I need calculate this: $b=F^{(1/h)} \bmod pq.$ Where $p$ and $q$ are prime numbers. I have $F$ and $h$. But how can I calculate $b$? I tried to do this: $\text{...
2
votes
1answer
64 views

Lenstra's ECM Algorithm - field requirement

In Lenstra's ECM algorithm, $\#E(\mathbb{F}_{p})$ is required to have small prime factors. Why is this so? I understand that the p-1 method is efficient for factoring N with small factors. The ECM ...
5
votes
3answers
2k views

How to verify if g is a generator for p?

For learning purpose, supposed I have a 16-digit prime which is 2685735182215187, how do I verify if g is a generator? (p is supposedly a special kind of prime)
5
votes
3answers
419 views

Is it possible to check if a number is the product of two primes without factorizing it?

I have a large number which I suspect may be a private RSA key (although its size, at 613 bits, seems a bit unorthodox). I have started to run a factorization algorithm on it, and after a few hours ...
0
votes
1answer
216 views

Does a Finite Field of 36 elements exist? [duplicate]

I'm having a little trouble understanding the finite fields theory, so I'm sorry if my question would seem a little stupid. I wanted to know if a finite field of 36 elements could exist. Basically, I ...

1
2 3 4 5 6