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

187 questions
Filter by
Sorted by
Tagged with
23 views

### Point-halving/solving quartic equations over the elliptic curve E(Z_N)/ring Z_N where N = pq

I am wondering whether there are any results/whether there is any knowledge about the following problem: Given a univariate polynomial (say, a quartic) equation defined over $\mathbb{Z}_N$, is it ...
36 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/...
86 views

### Constructing an integer with specific totient without factorization

Given $N(=pq)$, but not its factorization. Somehow you manage to know, that $k$ divides $\phi(N)$. Is it possible to come up with an integer $N^{*}$, for which $\phi(N^{*})=\phi(N)/k$, without ...
66 views

127 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 ...
23 views

### Help with next step in the Quadratic Sieve

So I am at the same step as someone from math.stackexchange but he never recieved an answer so I will copy-paste his question here: Say, for N = 90283, I compute bound 𝐵=𝑒(12+𝑜(1))(ln(𝑛)ln(ln𝑛√))...
201 views

### Sigma protocol when order is unknown

In the following paper (page 5) they have a proof that a triple $\left(g,b_{i-1},b_{i}\right)$ is of the form: $\left(g,g^{x},g^{x^{2}}\right)$ for some x. The relevant text from the paper is as ...
58 views

### Reciprocity Laws in Cryptography

Does anybody know applications of higher reciprocity laws (i.e. the reciprocity laws "higher" than the quadratic one, like the cubic or quartic reciprocity law) in cryptography? So far I have found ...
43 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 "...
80 views

### Size of $E$ over $\mathbb{F}_p$ contains $p+1$ points

I am struggling to prove this claim: I proved that the map $x\mapsto x^3+1$ is a bijection from $\mathbb{F}_p$ to itself if we have that $p\equiv 2\bmod{3}$. We have to use this fact to prove that ...
59 views

### Why does a primitive root mod n gives a uniform distribution over n?

The result from a primitive root mod n seemly has a uniform distribution over n, is it true? For instance, 3 is a primitive root ...
54 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. ...
302 views

### How to prove if a Hash Function is collision resistant

Say we have the following Hash Function, H(x) = 4x mod N where N is a number generated by multiplying two prime numbers and x={0,1,2,3,...,N-1}. So lets assume that ...
75 views

### How to compute ElGamal decryption by hand

Lets say that $u=3, x=5, v=2$, how do we work out $u^{-x}*v$, so $3^{-5} * 2$. I know how to work out the answer if it was $3^5 * 2$ but how do we do it with negative exponents?
126 views

### Why are some group representations much easier to compute discrete logarithm for? [duplicate]

The multiplicative group mod $p$ is isometric to the additive group mod $p-1$, yet computing discrete logarithms in the additive group is easy and completing discrete logarithms in the multiplicative ...
187 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 ...
129 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 ...
39 views

### Explain the meaning of “$E_i = g^{F_i} g^{G_i}$ is uniformly distributed in $G_q$”?

In this paper Qiong et al.’s CRT-based VSS} {Dealer Phase} To share a secret $d \epsilon Z_{m_0}$ among a group of $n$ users with verifiable shares, the dealer does the following: <...
259 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 ...
93 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 ...
22 views

### Is it possibe to extend DGK method of comparion two integers to $d$-ary settings?

In , a method for comparing two integers is described by using polynomial operations related to the binary representations of the given two integers. The method is re-phrased as follows: Given the ...
61 views

163 views

### Upper bounds on difference of RSA primes

I was wondering whether given a concrete $N = p \cdot q$ whether we can find a upper bound on $\Delta = | p - q|$ as function of $N$ e.g, $N^\delta$, and thus test whether a given $N$ is vulnerable ...
1k views

### How we can calculate AES Inverse SBox?

I am trying to find out the inverse of and SBox, but in vain, I have seen multiple questions over StackExchange, But I cant be able to solve my issue. As in this question, How are the AES inverse S-...
777 views

### Why is Approximate GCD a hard problem?

There are many Fully Homomorphic Encryption over the Integers schemes whose security is based on the intractability of the Approximate GCD (AGCD) problem. The paper Algorithms for the Approximate ...
61 views

### How can process algebra help to design security protocols?

Would you please tell me how process algebra could help me to design security protocols? More specifically, can I use it for proving the security of protocols? Is process algebra used for any ...
94 views

### Why do one-way accumulators use rigid integers as the modulus?

In the paper that introduced one-way accumulators, the author's justify their use of rigid integers as the modulus with the following: The advantage of using a rigid integer $n = pq$ is that the ...
137 views

### Sum of two squares problem

I would like to know if there is any existing research on the following problem: $$\text{For }a, b \in \mathbb Z \text{, given }n = a^2 + b^2, \text{output }a, b$$. Searching for "sum of squares", "...
224 views

### Understanding the Pohlig-Hellman algorithm

The paper has the following relation: $$y^{(p-1)/p_i} \equiv \alpha^{x(p-1)/p_i} \equiv \gamma_i^x \equiv \gamma_i^{b_0} \pmod p$$ where $\gamma_i = \alpha^{(p-1)/p_i}$. I understand this relation ...
78 views

Given $g,h\in\mathbb Z_p$ where $g$ generates $\mathbb Z_p^\star$ Discrete logarithm problem is to find $z$ such that $g^z\equiv h\bmod p$ holds. Take the problem given $g,g',h$ where $g^z\equiv h\... 2answers 889 views ### Why do algebraic proofs apply to cryptography? How do we know that the number theoretic and algebraic results used in cryptography provide a perfect model for the behavior of integers as implemented in computers? Does there exist a bijection ... 0answers 88 views ### Explanation of a proof of one of Shoup's lemmas In Lower Bounds for Discrete Logarithms and Related Problems, Victor Shoup states the following lemma: Lemma 1 Let$p$be prime and let$t \ge 1$. Let$F(X_1, \dots, X_k) \in \mathbb{Z} / p^t[X_1, \...
The question is this... $x^{29}\equiv4\pmod{91}$. Note that $91 = 7*13$. Compute an integer $x$. Since 91 is not prime number, I know I need to use Euler's theorem, not Fermat's. So I get \$a^{...