# Questions tagged [number-theory]

Number theory is the study of the properties and construction of numbers, particularly integers. Prime numbers are of particular interest to number theorists and consequently cryptographers as they are considered the "building blocks" of numbers and produce many interesting results which are useful in cryptography. Questions covering number theory and primes should use this tag; questions involving finite fields and groups might use this tag if relevant.

263 questions
Filter by
Sorted by
Tagged with
45 views

### Reflecting a point on the Edwards curve

Let's say we have a point $nP = (x,y)$ on a curve $E$ over a prime $p$. The corresponding Edwards curve coordinates are $(u,v)$. I want to construct the point corresponding to $(u,-v)$ on the Edwards ...
1 vote
61 views

### RSA: does it matter that we recover something congruent to x rather than equal to it?

In the proof that RSA successfully decrypts the message $x$, we show that $x^{e^{d}}\equiv x \pmod N$. However, I am wondering whether it is a problem that we don't recover $x$ exactly, but merely a ...
1 vote
101 views

### finding r-th root in $\mathbb{Z}/n\mathbb{Z}$

I was reading the paper One-way Accumulators: A Decentralized Alternative to Digital Signatures by Benaloh and de Mare [link], and in section 4.2, they say that given $z\in (\mathbb{Z}/n\mathbb{Z})^*$ ...
245 views

### Concrete example of Montgomery Multiplication

I have read about Montgomery Multiplication on several sites, but I haven't found any examples on specific numbers that explain the algorithm to someone who doesn't have a PhD in number theory. I know ...
1 vote
93 views

### Special algorithms for edge cases of binary arithmetic?

I have several mathematical operations on binary numbers that are special cases of more general arithmetic operations. I am wondering whether there exist more specialized algorithms purpose-made for ...
179 views

### Purpose of the b1, b2, b3.... terms in Rabin-Miller Primality Test

In Rabin-Miller primality test, let N be the number you're checking for primality. Here N = 78007. Let m be the number you get after dividing (N - 1) by 2 several times until you can no longer do so. ...
1 vote
476 views

### Challenges like RSA factoring challenge

RSA factoring challenge is a famous one and is still not completely solved. Are there similar challenges for Discrete log over $\mathbb Z_p^*$? Discrete log over Elliptic curves? LWE? LPN?
1 vote
176 views

### Rabin-Miller Primality Test - Elaboration needed

In short, my question is: What exactly do people mean when they say that "The more you apply the Rabin-Miller test to a number, the more certain you can be that the number you're testing is prime....
319 views

### Discrete Logarithm Challenges and Records

I am wondering whether there are any current challenge problems for Discrete Logarithms. Specifically in $\mathbb{Z}_p^\ast$ as well as in elliptic curve groups. It turns out CERTICOM still has some ...
83 views

### Why is $d = e^{-1} \mod \phi(N) \equiv e^{\phi(N)-1} \mod \phi(N)$ and not commonly used in RSA key generation?

On some lecture slides regarding to RSA-Encryption, the formula for calculation of the private key is given as $d = e^{-1} \equiv e^{\phi(N)-1} \mod \phi(N)$. The second equation is justified by the ...
1 vote
89 views

### Non probabilistic algorithm : Given secret key $d$ we can factorize $n$ assuming $e$ is small

I read in an introduction to a paper that if $e$ is small enough and we were given secret key $d$ in RSA, then there is an efficient deterministic algorithm to factorize $n$. I've searched about that ...
127 views

### Verification through prime modulus

Asking this question here since it has a flavor similar to some cryptographic protocols. How likely are two integers which are smaller than some threshold, mod by some prime number to have the same ...
1 vote
142 views

### Proving the generator criterion for group $Zp$

I am trying to understand how to find a generator of Zp. How to find generator $g$ in a cyclic group?. I have heard that we can pick random a Zp and for each primitive d| p-1 check wether: a^[(p-1)/...
1 vote
23 views

### Possible plain text needed on a congruence modulo - based encryption

Suppose m is a positive integer converted from the plain text in bytes. And there are two positive integers a, ...
67 views

### Computing the eth root in Z(N)* i.e set of all elements coprime to N

I understand that it is easy to compute eth root in Z(P)* but what about with Z(N)? I know that it requires the factorization of N but what does that actually mean? What is an example of calculating ...
1 vote
155 views

229 views

### RSA with huge ciphertext

I am trying to find the flag from an RSA ciphertext, I am able to get the factors from factordb.com but the given e is not ...
1 vote
72 views

### Does a list of discrete log equations reveal information?

Given public generator $g$ of some cyclic group, a secrets $x\in Z_q$, and public pairs $(a_1,b_1),...,(a_n,b_n)$ (where $a_1,...,a_n$ are selected at random from a big set), and prime p, that ...
100 views

### Can functional encryption encrypt and decrypt negative integers?

I want to use DCR-based functional encryption for encryption and decryption purpose. However, I'm unsure whether DCR-based functional encryption can support negative integers. Is there any ...
1 vote
### If RSA uses $e$ with $\gcd(e,\phi(N))\ne1$ but $e$ is hard to factorize has an adversary still an advantage in finding $d$ for $m^{ed}\equiv m\mod N$?
Usually RSA uses an encryption exponent $e$ with $\gcd(e,\phi(N))=1$. This question shows why that need to be the case: For $\ne1$ there might exist no decryption exponent $d$ because other $m'\ne m$ ...