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

171 questions
Filter by
Sorted by
Tagged with
59 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 ...
52 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 ...
43 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. ...
151 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 ...
51 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?
90 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 ...
162 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 ...
119 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: <...
125 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 ...
87 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 ...
56 views

156 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 ...
782 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-...
592 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 ...
59 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 ...
83 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 ...
126 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", "...
198 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

63 views

996 views

### PhD in cryptography using elliptic curves [closed]

I am currently a MSc student in number theory and considering switching to a phD in cryptography. I would like to use number theory techniques. (i.e. RSA, elliptic curves, etc). The purpose of all ...
170 views

### Will reading “Elementary Number Theory” by David M. Burton be useful for Cryptography? [closed]

I am a Computer Science student and interested to learn Cryptography to be a researcher in this field. I heard that Number Theory is useful for Cryptography since there are some Crypto systems based ...
199 views

### More general - what is the hard problem of recovering r from r*p mod q?

I would like to know the cryptographic hard problem that is most closely tied to recovering integer $r$ from the modular product $r\times p\mod q$. (This is a simplification of an earlier post that ...
80 views

### What is the hard problem for this algebraic encryption construct?

I would like to know what cryptographic hard problem this reduces to. Select two large prime numbers $p$ and $q$, and let $N=pq$. Select a random positive integer $r$. Compute the encryption of ...
### Difference between $Z^*_n$ and $Z_n$ [closed]
When studying cyclic groups I stumbled upon the following sentence: The ∗ in $Z_n^*$ stresses that we are only considering mulitplication and forgetting about addition on this site of stanford. I ...