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.
403 questions
6 votes
2 answers
1k views
Are most RSA integers unbalanced?
RSA integers are integers of form $N=pq$ where $p$ and $q$ are primes. It appears some of the RSA challenge numbers have unequal number of bits. Eg: RSA-190 = ...
- 1,191
0 votes
1 answer
130 views
Twin primes and rsa
Is there any shorter-time computational advantage to using twin primes (p, p-2) in cryptography ? Or is just as efficient to use primes that are not twins ?
1 vote
0 answers
101 views
Can products of primes generated by this random walk algorithm be factored efficiently? [closed]
Algorithm Description: A prime-generation algorithm constructs random primes by appending digits such that: Start with a small initial digit (e.g., 1). At each step, append a new digit d to the ...
- 577
2 votes
3 answers
575 views
Balanced Primes for the RSA modulus
I am currently working on a Multipower RSA given by Takagi. I am following the book 'Cryptanalysis of RSA and Its Variants' by Jason Hinek. It gives the definition of balanced primes for standard RSA ...
- 23
3 votes
1 answer
144 views
d and phi encrypted with small e in RSA; how to decrypt d and phi?
I have $n$, $e = 3$, $d^e \bmod n$, $\phi^e \bmod n$. How can I get $\phi$ or $d$? I know that $3d = 1 \bmod \phi$, so $3d = 1 + k\phi$. I reached the point I cubed both sides and applied modulo n $$...
- 63
0 votes
0 answers
42 views
How to factor a semiprime from a rsa key given both exponents? [duplicate]
Simple question. Let’s suppose I’ve the private exponent of a rsa key in addition to the public 1. How can I use it to factor the modulus ?
- 283
2 votes
1 answer
135 views
A cyclic group of prime order
Is a cyclic group of prime order always a multiplicative group? Can you give an example of a cyclic group with prime order?
- 21
3 votes
1 answer
102 views
Generating finite fields that meet the requirements based on primitive roots
How can I construct a finite field that meets certain requirements using a given generator? For example, if the generator is specified as 5, how can I construct a finite field where $p$ is a 1024-bit ...
- 321
0 votes
1 answer
88 views
Does the ability to solve modular square roots without factorization would allow factorizing semiprime in a more efficent way than using the gnfs?
The gnfs is a fast sieving method for factorizing integers, but as soon as the integer to factor is more than 900 bits long factoring tends to become too costly. I just read having a modular square ...
- 283
1 vote
1 answer
138 views
hardness of factorisation, when n is unkonwn but phi(n) is known
I'm exploring a unique scenario within the RSA framework, which does not align with typical schemes and thus, lacks readily available references. Consider a standard RSA setup but with a twist: $$ n = ...
- 121
0 votes
0 answers
110 views
How to build a prime curve having a specific a prime order or an order containing a specific prime divisor?
There’s algorithms for computing curves’s order from prime curves or even algorithms for building binary curves containing a specific order through torsion. But if I want a prime curve having or ...
- 283
1 vote
2 answers
282 views
AKS Primality-Testing Algorithm
The first step of the AKS algorithm tests an odd input value $n$ for exponentiality: if $n = a^b$ for some integers $a$ and $b$ then return "Composite". How can $n$ be tested for ...
- 13
1 vote
1 answer
141 views
Is the given Somewhat Homomorphic Encryption over Integers still viable and fast?
In the paper: https://eprint.iacr.org/2009/616.pdf They talk about a public key SWHE over Integers scheme that is pretty simple (I do not care about the FHE aspect of the paper). I was wondering if ...
- 195
3 votes
2 answers
581 views
Generating Carmichael numbers in polynomial time
I'm generating RSA 2048-bit keys with $p$ and $q$ of 1024-bit primes. For primality, I'm using the Miller-Rabin test. As Carmichael numbers pass the MR test, I tried to compute how many such numbers ...
- 485
0 votes
1 answer
57 views
Probability of encoded message using Weierstrass equation on NIST elliptic curve over prime finite field to return a quadratic residue?
Suppose we talk about NIST P-256 elliptic curve, and since finite field of an elliptic curve is a known prime number $P$, then approximately half of the Weierstrass equation results will be quadratic ...
- 195