Stack Exchange Network

Stack Exchange network consists of 175 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

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.

5
votes
0answers
58 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
216 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
53 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{...
3
votes
0answers
61 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 ...
2
votes
0answers
78 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
130 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
34 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
62 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
69 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
249 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
319 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
64 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
129 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
0answers
20 views

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

In [1], 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 ...
0
votes
0answers
57 views

What is the computational complexity of Coppersmith's bivariate algorithm?

Coppersmith's original paper Finding a Small Root of a Bivariate Integer Equation; Factoring with High Bits Known says the algorithm to find bivariate roots under certain conditions runs in ...
-3
votes
0answers
66 views

finding private key for RSA

for RSA $N=pq$, $c = m^e \bmod N$ if $m^{12345}= 1 \bmod N$ is given, how to find RSA private key $d$ and message $m$. Note: $N,d,\phi$ are unknown. $e$ is publicly available. I think we can take $...