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.

25 questions with no upvoted or accepted answers
Filter by
Sorted by
Tagged with
6
votes
0answers
93 views

Parity of the order of a element

Given an element $g$ in a cyclic group $G$ of known order $m$ its easy to test if $m$ has even or odd order. In other words $\textrm{ord}(g) \pmod 2$ can be computed easily. In some cases where the ...
4
votes
0answers
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 ...
4
votes
0answers
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 "...
4
votes
0answers
110 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 ...
4
votes
0answers
229 views

Is the matrix step of GNFS still the hardest part?

When the factorization of RSA-768 was announced in December 2009: the sieving took about 24 months and the matrix step took 119 days (4 months). So sieving took about 6 times as long. This is despite ...
3
votes
0answers
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 ...
3
votes
0answers
66 views

Problem with Chaum`s Untraceable Electronic Cash

For example according to protocol I need calculate this: $b=F^{(1/h)} \bmod pq.$ Where $p$ and $q$ are prime numbers. I have $F$ and $h$. But how can I calculate $b$? I tried to do this: $\text{...
2
votes
0answers
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 ...
2
votes
0answers
94 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, \...
2
votes
0answers
249 views

Can we break ECDLP with this machine?

Let $P$ and $Q$ are two points of NIST elliptic curve $E$ (defined over $F_{2^m}$ with prime $m$) and $k$ is a private key such that $k.P=Q$. Also we have a machine that is able to leak some ...
1
vote
0answers
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π‘›βˆš))...
1
vote
0answers
43 views

Efficient fields over arithmetic circuits

What sort of fields is efficient over an arithmetic circuit? Efficient meaning that given a field $\mathbb{F}_p$, reduction (modulo) does not require many multiplications and preferably inversion was ...
1
vote
0answers
67 views

Is it hard to determine whether a given matrix is the square of another matrix?

Given a matrix $A\in M_d(\mathbb Z_N)$, is it hard to determine whether there exists another matrix $B\in M_d(\mathbb Z_N)$ such that $A=B^2\bmod N$? Suppose the factorization of $N$ is unknown and ...
1
vote
0answers
96 views

Why use Phi(m) divide Order(p, m) to get slot number in HElib?

I am reading HElib source code, and have a confusion about FindM function: ...
1
vote
0answers
283 views

Compute Modulo exponentiation with prime powers

The problem is to find x such that $$x = M^d \mod p^2$$, where M and d are large numbers, and p is a large prime. Ideally we only want to compute $M^d\mod p$ and then use the result to further ...
1
vote
0answers
404 views

Calculating the discrete logarithm

I'm given a prime number $p = 1217$ I'm also given the following equations: $$ 40 \equiv \log2 \pmod{64} \\ 63 \equiv \log3 \pmod{64} \\ 13 \equiv \log5 \pmod{64} \\ 13 \equiv \log2 \pmod{19} \\ 10 \...
1
vote
0answers
76 views

Using quadratic residue to learn the sign of a field element

Given $x' \in \{-x, x\} \bmod q$ (where $q$ could be any prime of my choice), $s$ is a random element in the field, $y = x'\cdot s$ and $y' = \pm\sqrt{(x\cdot s)^2}\bmod q$ (i.e., both solutions to ...
1
vote
0answers
52 views

What constitutes a “description of B” for probabilistic encryption as defined in Cryptology 6.3.4?

On page 21 of the Rivest's Cryptology chapter, he defines a trapdoor predicate as a boolean function for which it is easy to choose an x such that ...
1
vote
0answers
135 views

$\phi$ function in Dual_EC_DRBG

I am trying to understand the operation of the Dual_EC_DRBG. I'm reading the formal specification (SP 800-90) and can't seem to find a definition of the $\phi$ function used throughout the definition ...
0
votes
1answer
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{...
0
votes
0answers
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 ...
0
votes
0answers
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/...
0
votes
0answers
45 views

FLT is partly applying to RSA equation, and also relation between ED mod phi and Phi + 1 mod N

After numerous attempts from myself and all of you guys, I finally came to understand RSA. I can now prove it and understand how I got there. But I still have some very few polishing questions. 1) We ...
0
votes
0answers
34 views

Proof of two pairs with same exponent

Lets assume we have a group $G$ with unknown order. And we have a pair $(A_1,K_1), (A_2,K_2)$ in which all $A_1,K_1,A_2,K_2$ are group elements. The claim is $A_1= K_1 ^ x$ and $A_2 = K_2 ^ x$. or ...
0
votes
1answer
85 views

Retrieve message from rsa ciphertext based on some conditions

Assume: $x = m^{e-1}\bmod n$ $y = m^{d-1}\bmod n$ Here $m$ is a message, $e$ is the public exponent, $d$ is the private key and $n$ is the modulus of an RSA key pair. Now if I know $e=65537$, $x$, $...