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

243 questions
Filter by
Sorted by
Tagged with
1 vote
47 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 ...
• 21
64 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 ...
• 21
1 vote
94 views

### 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$ ...
• 475
1 vote
46 views

110 views

### zkSnark Intro by Maksym Petkus: Is the polynomial defined over $Z$ or is it defined over $Z_n$?

I am reading this explanation of zkSnark written by Maksym Petkus - http://www.petkus.info/papers/WhyAndHowZkSnarkWorks.pdf Here he has a polynomial $p(x) = x^3 − 3x^2 + 2x$ and the homomorphic ...
• 1,637
165 views

### zkSnark: Restricting a Polynomial

I am reading this explanation of zkSnark written by Maksym Petkus - http://www.petkus.info/papers/WhyAndHowZkSnarkWorks.pdf I have understood everything in the first 15 pages. In 3.4 Restricting a ...
• 1,637
126 views

### Setting up the discrete logarithm framework

The discrete logarithm problem over prime cyclic groups consist of finding $x$ satisfying $g^x\equiv h\bmod p$ where $g$ is generator of multiplicative group $\mathbb Z/p\mathbb Z$ at a large prime $p$...
• 882
1 vote
78 views

### Extracting genome from a Ciphertext [closed]

Is it Probable to extract the ciphertext's genome and Visualizing it ? Converting this: ...
• 1,854
62 views

### Is there some function of $n$ that is a multiple of $\phi(n^2)$?

Not sure which forum to post this question so here is a link to it from MSE. This is to adapt the approach of Fermat's Little Theorem to the Paillier encryption system. I understand that this will ...
1 vote
137 views

### Pollard's p - 1 - how do you set the bound & how do you set the base numbers

In Pollard's p-1 algorithm for factoring N, you try to find a L such that p - 1 divides L. Then you check $gcd(pow(a,L,N)- 1, N)$. If 1 < gcd < N, then you have found one of the factors. I have ...
• 1,637
91 views

### Simple question about BGV scheme

While I'm trying to implement BGV scheme myself, I found that I'm really confusing about the encryption and decryption of the scheme. Here's my understanding: Let $p$ be a plaintext modulus and $q$ be ...
• 143
1 vote
142 views

### Why is factorial used in Pollard's $p - 1$ algorithm?

Why exactly do we use factorial for finding an $L$ which is divisible by $p - 1$? Pollard's algorithm is about B-powersmooth numbers & not B-smooth numbers. So where exactly does the factorial ...
• 1,637
For RLWE (Ring Learning With Errors) scheme, we use $R_{q} = \mathbb{Z}_{q}[x]/(x^{n} +1) = \mathbb{Z}_{q}[x]/(\Phi_{2n}(x))$ where $n = 2^{d}$ for some $d$. Since there exists $2n$-th root of unity ...