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

198 questions
Filter by
Sorted by
Tagged with
45 views

### How to caculate the summation of successive modular inverses?

$p$ is a big prime. $p>2^{2048}$. So how to caculate the summation of successive modular inverses over $p$? $$\sum_{i=1}^{\frac{p+1}{2}-1}{i^{-1}}\pmod p$$ As to $p$ is a big prime, it's ...
56 views

### Lifting a congruence $f(X) \equiv gh (\textrm{mod} \ p)$ to a higher power moduli

I have the polynomial ring $R = \mathbb{Z}[X]/(X^N - 1)$ with $N = 11$ and $h \in R$ with \begin{equation*} h = 7 -11X - 7X^2 -12X^3 + 8X^4 - 11X^5 + -8X^6 + 11X^7 - 4X^8 + 2X^9 + 3X^{10} \end{...
310 views

### How is information disclosed by modular multiplication?

Consider the case that $c = a \cdot b \mod p$ where $p$ is a known prime and $0 < a < p$ and $0 < b < p$ are unknown integers numbers. Furthermore, some bits on the value of $c$ are ...
78k views

### Calculating RSA private exponent when given public exponent and the modulus factors using extended euclid

When given $p = 5, q = 11, N = 55$ and $e = 17$, I'm trying to compute the RSA private key $d$. I can calculate $\varphi(N) = 40$, but my lecturer then says to use the extended Euclidean algorithm to ...
85 views

139 views

### Why discrete logarithm modulo composite moduli not popular and not defined in standards?

The classical discrete logarithm problem is to find $x$ such that $g^x\equiv h\bmod p$ where $p$ is a prime and $g$ is generator of multiplicative group modulo $p$. The demerit of this approach seems ...
95 views

### Resources for mathematics of cryptology

I am an undergraduate student looking for resources (books or lectures) explaining mathematics involved in cryptography, such as number theory, elliptic curves etc. I found the book 'A Course in ...
260 views

### Why is a number of shares that is greater than a threshold required to construct secret?

In this][1] paper of AsmuthāBloom threshold SSS, the algorithm is as follows: Shares Distribution To distribute n shares of a secret $K$ among the set of participants $P = \{ p_i : 1 ā¤ i ā¤ n\}$, the ...
411 views

### Non-commutitive and nonassociative algebraic structures in cryptography

Are there any cryptographic algorithms or primitives that have been developed and studied that make use of non-commutative or non-associative algebraic structures such as quaternion integers or ...
80 views

### Why $f(x)=x^e$ is a bijection i.f.f $e\in{\mathbf{Z^*_{\phi(N)}}}$?

I understand that if $e\in{\mathbf{Z^*_{\phi(N)}}}$ then $\gcd(e,\phi(N))=1$ and if $e\not\in{\mathbf{Z^*_{\phi(N)}}}$ than $\gcd(e,\phi(N))\neq{}1$. But I couldn't figure out why this implies ...
102 views

### How are the constants found in the AVX2 implementation of CRYSTALS-KYBER round 2 generated?

The post-quantum lattice-based cryptosystem CRYSTALS-KYBER which has made it to the second round of NIST PQC includes two implementations: 1) a baseline reference implementation in C and 2) an ...
248 views

### Proving the knowlege of e-th root in an non-interactive way

Just like in this question: Protocol for proof of knowledge of $l$-th root I want to prove that for $u^e = w$ I know $u$ without revealing it. Three other requirements are: e is small (65537) The ...
79 views

### Is there any Information on the “Modular Approximate Greatest Divisor” problem?

The Approximate Greatest Common Divisor (AGCD) problem is the difficulty of obtaining the value $\ p\$ when given samples of $\ pq_i + e_i$ for secret values $p, q_i, e_i$. I would like to know how ...
68 views

### The way to break Diffie-Hellman(small nonprime number)

i am wondering how to break DHļ¼small nonprime numberļ¼. Let's say we don't know: $a$: Alice's private key $b$: Bob's private key And we know: $N$: nonprime number $p$,$q$: $N = p * q$ ($p$ and $q$...
1k views

### Is computing roots moduli a composite $N$ a hard problem without knowing the factorization of $N$?

Suppose that we are given $\mathbb{Z}_{N}$ and an element $x^u \in \mathbb{Z}_{N}$ with $u \in (0,l]$ where $l$ is the bit-size of $N$. Is it difficult to recover $x$ by knowing $u$ without knowing ...
105 views

### RSA calculate $d$ using Chinese Remainder Theorem with $d_p$, $d_q$ and $e$

Suppose for a RSA system I have the following variables given: modulus $n$, expononent $e$, $d_p$ and $d_q$Where, $d_p = d\bmod(p-1)$ and $d_q = d\bmod(q-1)$, Is it possible to find the private ...
83 views

### Protocol for proof of knowledge of $l$-th root

Assume we have Group G in which the adaptive root assumption holds. This assumption states that if we choose an element $w$ and after that, if we receive a prime value $l$ it is hard to find the $u$ ...
36 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 ...
53 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/...
92 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 ...
121 views

141 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 ...
24 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šā))...
231 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 ...
69 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 ...
50 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 "...
82 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 ...
71 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 ...
2k views

### Is there an algorithm for factoring N, which is just as simple as this one, but faster?

I found a simple algorithm for factoring semiprime numbers, you can read about it in Factoring Semiprimes and Possible Implications for RSA (paywall-free). It basically works like this: You reverse ...
62 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. ...
18k views

### What is the relation between RSA & Fermat's little theorem?

I came across this while refreshing my cryptography brain cells. From the RSA algorithm I understand that it somehow depends on the fact that, given a large number (A) it is computationally ...
325 views

### What does modular inversion mean?

I'm trying to implement an e-voting algorithm, which is described at the paper "Internet Voting Protocol Based on Improved Implicit Security" by Abhishek Parakh & Subhash Kak. At the Example 1 ...
74 views

### Difference between when select x from $\mathbb{Z}_{p-1}$ and $\mathbb{Z}_p$ in discrete logarithm Problem?

Reading "Security Arguments for Digital Signatures and Blind Signatures" paper, I confused by some questions. Q1. when it refers to "El Gamal signature scheme", The key generation algorithm: it ...
111 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?
601 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 ...
184 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 ...
### 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 ...
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 ...